#🔒 Terminal Output Stuck after running one statement
loud remnant
!code
tepid tangleBOT
loud remnant
!paste if it's very long
tepid tangleBOT
crystal badger
okay wait let me try
https://paste.pythondiscord.com/IFIQ
This is the code
This is the output and the terminal stucks
its urgent please anyone help
<@&831776746206265384> sorry for unnessary taging but its urgent
is there anyone can help me now?
loud remnant
Please only ping mods for active moderation concerns (I should have clarified that the first time)
loud remnant
I'm having a look rn
crystal badger
please
shell pawn
Also I think rule 8 applies
crystal badger
Also I think rule 8 applies
na it doesnt
i am not asking for code
i am asking what is the error
why the output got stucked
loud remnant
Also I think rule 8 applies
given the ss, I'd probably say homework rather than exam
loud remnant
why the output got stucked
Line 133, self.dfs_with_forward_checking(self.get_next_state(graph, colors), num_colors, graph, colors, domains): is never returning true, no matter how many colours you give it, so it's looping infinitely
crystal badger
so how may i fix this?
loud remnant
Looks like in dfs_with_forward_checking, domains[state] is always empty
loud remnant
ah found it
Under def get_chromatic_number_with_forward_checking(self, graph): (sorry for no line numbers, I edited the file a lot)
crystal badger
fine
loud remnant
def get_chromatic_number_with_forward_checking(self, graph):
num_colors = 1
colors = {}
domains = {state: list(range(num_colors)) for state in graph}
while True:
...
``` You set up the domains once then never again in the loop. Looks like `domains` is being modified inside the loopSo the second iteration is using domains from the end of the first iteration
crystal badger
oh
loud remnant
I moved domains = {state: list(range(num_colors)) for state in graph} into the loop
And that made the step work
crystal badger
let me see
crystal badger
yes i saw that
there is still lot of work
btw thanks for the fix
PS D:\Assignmensts\Python assignment - 5 april> python -u "d:\Assignmensts\Python assignment - 5 april\demo.py"
Experiment without heuristics:
USA Results (DFS): [(3, 0.0010037422180175781), (3, 0.0), (3, 0.0), (3, 0.0), (3, 0.0)]
Australia Results (DFS): [(3, 0.0), (3, 0.0), (3, 0.0), (3, 0.0), (3, 0.0)]
USA Results (DFS with Forward Checking): [(5, 0.0009989738464355469), (5, 0.0), (5, 0.0), (5, 0.0009944438934326172), (5, 0.0)]
Australia Results (DFS with Forward Checking): [(4, 0.0), (4, 0.0), (4, 0.0010018348693847656), (4, 0.0), (4, 0.0)]
Traceback (most recent call last):
File "d:\Assignmensts\Python assignment - 5 april\demo.py", line 246, in <module>
usa_results_forward_checking_propagation = map_coloring.conduct_experiments(usa_map, map_coloring.get_chromatic_number_with_forward_checking_and_propagation)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "d:\Assignmensts\Python assignment - 5 april\demo.py", line 168, in conduct_experiments
chromatic_number, execution_time = self.run_experiment(graph, algorithm, heuristic)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "d:\Assignmensts\Python assignment - 5 april\demo.py", line 160, in run_experiment
chromatic_number = algorithm(graph)
^^^^^^^^^^^^^^^^
File "d:\Assignmensts\Python assignment - 5 april\demo.py", line 142, in get_chromatic_number_with_forward_checking_and_propagation
if self.dfs_with_forward_checking_and_propagation(self.get_next_state(), num_colors, colors, domains):
^^^^^^^^^^^^^^^^^^^^^
TypeError: MapColoring.get_next_state() missing 2 required positional arguments: 'graph' and 'colors'
PS D:\Assignmensts\Python assignment - 5 april>
this is the output
and it seem the line worked
USA Results (DFS with Forward Checking): [(5, 0.0009989738464355469), (5, 0.0), (5, 0.0), (5, 0.0009944438934326172), (5, 0.0)]
Australia Results (DFS with Forward Checking): [(4, 0.0), (4, 0.0), (4, 0.0010018348693847656), (4, 0.0), (4, 0.0)]
now i need to work on the next error
Btw dont close this post, i will notify for closing the post
loud remnant
Sure
Just to help you debug in future, I found the error by chucking print statements between each major step, and in major loops, removing old statements as I narrowed down the failure point. Then I saw the infinite loop in get_chromatic_number_with_forward_checking, so had to check dfs_with_forward_checking. Inside the function, I did print(state, domains[state]). That showed me that the domains[state] was non-empty in the first iteration of the dfs_with_forward_checking loop, but empty in all subsequent iterations, which was suspicious since they should not affect each other. Hence finding the bug.
crystal badger
@loud remnant
https://paste.pythondiscord.com/WOHA This is updated code
Now the output is stucked here
can you help me again?
the last line is
usa_results_dfs_lcv = map_coloring.conduct_experiments(usa_map, map_coloring.get_chromatic_number_with_heuristics, map_coloring.lcv_heuristic)
australia_results_dfs_lcv = map_coloring.conduct_experiments(australia_map, map_coloring.get_chromatic_number_with_heuristics, map_coloring.lcv_heuristic)
print("USA Results (DFS with LCV Heuristic):", usa_results_dfs_lcv)
print("Australia Results (DFS with LCV Heuristic):", australia_results_dfs_lcv)
here the output is stucked
@loud remnantare u there
please this will be las
last
loud remnant
Yeah looking at it
crystal badger
okay please
also, can you review the code? if there can be any changes let me know
crystal badger
what
loud remnant
dfs_with_heuristics is very strange to me
Because you're using it with 2 different kinds of heuristics
One type returns a single state name
The other type returns a list of state names
loud remnant
One type returns a single state name
I think the version that does this is suspicious
crystal badger
so well i can explain
loud remnant
Since you then do for color in heuristic(state, graph, domains, colors)
This implies that heuristic returns several colours
crystal badger
You're correct. dfs_with_heuristics is a generic function designed to work with different kinds of heuristics.
- For heuristics like MRV (Minimum Remaining Values) or degree constraint heuristic, which return a single state name,
dfs_with_heuristicsiterates over each possible color for that state and continues the depth-first search recursively. - For heuristics like LCV (Least Constraining Value), which return a list of state names,
dfs_with_heuristicsiterates over each state in the list and for each state, iterates over each possible color, continuing the depth-first search recursively.
This flexibility allows dfs_with_heuristics to work with various kinds of heuristics, as long as they provide the necessary information for selecting the next state or states to explore.
loud remnant
Then surely the mrv or distance ones should return a list with one element
(also chatgpt, really...)
crystal badger
yes
just for solving error
becasue i am trying it from last few hours
so i assked to solve the errors and chatgpt updated the code
also, let me show you the assignment
see
this is what the assignment is
loud remnant
Btw as a few side-notes
crystal badger
please help me to fix the error
loud remnant
Your use of heapq doesn't do what you think it does, you'd be thinking of bisect
Also in conduct_experiments, states = self.shuffle_states(graph) doesnt do anything, you don't seem to use states after
crystal badger
what next?
@loud remnant
so what should i do now
@loud remnanthttps://paste.pythondiscord.com/6A3Q CHeck this
i implemented bisect
but still it is stucked
u there bro
help me in this
@loud remnant
loud remnant
Like MRV heuristic says you can colour the maps in 1 single colour?
That's BS
Also should all the techniques result in an optimal colouring? probably, so then why is USA doable in 3 colours but other techniques say 4?
Also by the 4-colouring theorem you should never need 5 colours on a physical map, and yet DFS with Forward Checking reports 5 were needed to colour the US
crystal badger
The MRV (Minimum Remaining Values) heuristic does not guarantee that a map can be colored with only one color. Instead, it prioritizes selecting the variable (state) with the fewest legal values (remaining colors) left in its domain, which can be beneficial for reducing the search space and potentially finding a solution more quickly. However, it doesn't ensure optimality in terms of the number of colors needed to color the entire map.
what should i do now
@loud remnant
@loud remnant hey i g i got it
def lcv_heuristic(self, state, graph, domains, colors):
lcv_values = []
for neighbor in graph[state]:
if neighbor not in colors:
count = sum(color in domains[neighbor] for color in domains[state])
bisect.insort_left(lcv_values, (count, neighbor))
print(lcv_values)
return [neighbor for _, neighbor in lcv_values]
when running this
print(lcv_values)
prints []
infinte time
i g it stucks in inifite loop there
loud remnant
That's part of it, but not really where it loops
I'm more worried with fixing your earlier stuff
Your DFS with forward checking says 3 colours, and yet when I add a graph display and verification it fails
crystal badger
lol
crystal badger
where u are running it?
loud remnant
where u are running it?
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib as mpl
def draw_colored_graph(states, colors):
G = nx.Graph(**states)
for state, neighbors in states.items():
for neighbor in neighbors:
if neighbor in states:
G.add_edge(state, neighbor)
node_colors = [colors[state] for state in G.nodes()]
nx.draw_networkx(G, nx.spring_layout(G), with_labels=True, node_color=node_colors, node_size=150, font_size=5, cmap=mpl.colormaps["Set2"])
plt.show()
def verify_coloring(states, colors):
for state, neighbors in states.items():
for neighbor in neighbors:
if colors[state] == colors[neighbor]:
return False
return True
well, this really
def dfs_with_forward_checking_and_propagation(self, state, num_colors, graph, colors, domains):
if state is None:
return True
for color in domains[state]:
if self.is_safe(state, color,graph, colors):
colors[state] = color
updated_domains = domains.copy()
if not self.forward_check(state, color,graph, colors, updated_domains):
continue
updated_domains = self.propagate_singleton_domains(graph,updated_domains)
if self.dfs_with_forward_checking_and_propagation(self.get_next_state(graph, colors), num_colors, graph, colors, updated_domains):
draw_colored_graph(graph, colors)
assert verify_coloring(graph, colors)
return True
colors[state] = None # Backtrack
return False
Seems to me that you have nodes that have their colour as None
Failed on OR and ID, both had colour None
Yeah it's this end of the graph that's uncoloured
loud remnant
I don't do anything via dms.
loud remnant
Which would be against our rules
crystal badger
yes i know
but
i need your help
i am not getting it now
i tried my best to solve that
will you help me
loud remnant
Yeah it's this end of the graph that's uncoloured
Looks like this occurs even on the dfs_without_heuristics
crystal badger
@loud remnanthello
updated code
and this runs successfully
@loud remnantbut the output is incorroect
crystal badger
yes
loud remnant
In your dfs_without_heuristics
crystal badger
@loud remnant
this is what gpt says
In the dfs_without_heuristics method, there seems to be a potential issue where some states end up with no color assigned. This can occur if the method exhausts all color options for a state without finding a safe color.
That's wrong btu anyway
def get_next_state(self, graph: dict[str, list[str]], colors):
for state in graph:
if colors.get(state) is None:
return state
return None
This fixes one of your mistakes
You used to have if state not in colors which isn't necessarily correct, in your dfs you backtrack by setting colors[state] = None
crystal badger
```py
def get_next_state(self, graph: dict[str, list[str]], colors):
...
with this the code again stucka
def dfs_without_heuristics(self, state, num_colors, graph, colors):
if state is None:
return True
for color in range(num_colors):
if self.is_safe(state, color, graph, colors):
colors[state] = color
if self.dfs_without_heuristics(self.get_next_state(graph, colors), num_colors, graph, colors):
return True
del colors[state] # Backtrack by removing color assignment
return False
``` What About thiswhen backtracking occurs, the color assignment for the current state is properly removed, allowing the algorithm to explore alternative colorings for that state.
loud remnant
Yeah, works equivalently
crystal badger
With this modifications now the output is like ths
and the code stucked
means somewhere it is going on loop
loud remnant
4 definitely makes more sense as a number of colours
But it's strange that it doesnt generate an actually correct graph
crystal badger
yes
wat about th e is safe method
def is_safe(self, state, color, graph, colors):
for neighbor in graph[state]:
if neighbor in colors and colors[neighbor] == color:
return False
return True
there might be issues in the implementation of the backtracking algorithm or in the safety checks that ensure adjacent states have different colors
@loud remnant
what u thinl
thnik
loud remnant
My current problem is that it draws a nice graph but florida just doesn't exist
loud remnant
yeah same
crystal badger
crystal badger
It doesn't have it as a key anywhere
lol yeah
it is in value
but not in key
'AL': ['MS', 'TN', 'GA', 'FL'], # 'FL' added as a neighbor
loud remnant
'FL': ['AL', 'GA'],
'DC': ['VA', 'MD']
Added these two lines to complete the actual map
crystal badger
yep it fixes the key error
loud remnant
ok everything before USA Results (DFS with MRV Heuristic): checks out
loud remnant
wtf
crystal badger
but some values are still 0,0,0
loud remnant
I printed out your colour map for that
And the colours of each state are their own names
{'WA': 'TN', 'OR': 'MO', 'CA': 'TN', 'ID': 'KY', 'NV': 'UT', 'AZ': 'MO', 'UT': 'TN', 'MT': 'TN', 'WY': 'MO', 'CO': 'KY', 'NM': 'SD', 'ND': 'MO', 'SD': 'KY', 'NE': 'TN', 'KS': 'MO', 'OK': 'TN', 'TX': 'MO', 'MN': 'TN', 'IA': 'MO', 'MO': 'KY', 'AR': 'AR', 'LA': 'TN', 'WI': 'KY', 'IL': 'TN', 'IN': 'KY', 'MS': 'KY', 'TN': 'TN', 'MI': 'VA', 'OH': 'PA', 'AL': 'VA', 'GA': 'KY', 'KY': 'VA', 'SC': 'VA', 'NC': 'PA', 'WV': 'WV', 'VA': 'MD', 'MD': 'PA', 'DE': 'NY', 'PA': 'MA', 'NJ': 'NJ', 'NY': 'NY', 'CT': 'MA', 'MA': 'VT', 'VT': 'NH', 'NH': 'RI', 'RI': 'RI', 'ME': 'FL', 'FL': 'FL', 'DC': 'DC'}
no lol
loud remnant
```py
{'WA': 'TN', 'OR': 'MO', 'CA': 'TN', 'ID': 'KY', 'NV': 'UT', 'AZ': 'MO', '...
I'm just saying your current code gives a clour map that looks like this
It's not a colour map at all
loud remnant
It's here
for color in heuristic(state, graph, domains, colors):
What's actually meant to happen when the heuristic returns the names of states
crystal badger
asking me?
loud remnant
yes
crystal badger
,mmmmm
crystal badger
What's actually meant to happen when the heuristic returns the names of states
When the heuristic returns the names of states, it means that the heuristic is suggesting a specific order in which the states should be considered during the search.
loud remnant
def dfs_with_heuristics(self, state, num_colors, graph, colors, domains, heuristic):
if state is None:
return True
for color in domains[state]:
if self.is_safe(state, color, graph, colors):
colors[state] = color
updated_domains = domains.copy()
if not self.forward_check(state, color,graph, colors, updated_domains):
continue
updated_domains = self.propagate_singleton_domains(graph,updated_domains)
for next_state in heuristic(state, graph, domains, colors):
if self.dfs_with_heuristics(next_state, num_colors, graph, colors, domains, heuristic):
# draw_colored_graph(graph, colors)
assert verify_coloring(graph, colors)
return True
colors[state] = None # Backtrack
return False
Yes, exactly. Instead of relying on the get_next_state function to determine the next state to explore, the heuristic provides a specific order in which the states should be considered during the search.
For example, if the heuristic returns a list of states [A, B, C, D], it means that during the search, the algorithm should first consider state A, then B, then C, and finally D. This order is determined by the heuristic's logic, such as MRV, Degree Constraint, or LCV, as mentioned earlier.
loud remnant
Leads to making this, on the assumption that all heuristics return a list of states to try
loud remnant
doesn't work
crystal badger
my mind is not working
crystal badger
doesn't work
i want it to work
how it will work
will you drop the updated code when it works?
@loud remnant
@loud remnantHeu
hey
@loud remnant playing game?
I request you to please help me in this please 🥺
I am stuck
And I want to submit it tomorrow, and I don't know what to do now
Please 🙏🏻🥺
steady pond
please dont harass people
crystal badger
please dont harass people
I didn't 🥹🥹🥹🥹
loud remnant
to be honest, no. I was under no obligation to help you in the first place, you keep pinging me, and aren't really working on it yourself. I should only really be guiding you, and yet here I am having spent far too long writing code to straight up fix problems in your 300+ line file with no comments. It's past midnight for me too, and your time management issues are not my problem
(Oh, not to mention your attempts to violate our paid work rules)
crystal badger
@loud remnant @steady pond 🥹🙏🏻 sorry
tepid tangleBOT
Python help channel closed