On top of @SuperBiasedMan answer, I'd like to emphasize the fact that your code lacks clarity.
Your naming does not convey meaningful information, thus it is extremely hard to understand what the algorithm is performing based on the code alone. And since there is no comments nor docstrings, well it is still extremely hard.
Moreover, your two globals variables target and Gnodes does not receive the same treatment. target is kept intact between calls and Gnodes is reinitialized at each check. I don't understand why you reinitialize one and not the other.
Speaking of reinitializing Gnodes, let me introduce you to enumerate and list comprehensions:
def answer(li):
Gnodes[:] = [Node(i, dict(enumerate(l))) for i, l in enumerate(li)]
return pathPossible(Gnodes,len(Gnodes[0].dict))
enumerate will yield both the index and the element being iterated over. So enumerate([[0,1], [2,3], [4,5]]) will yield 0, [0,1] then 1, [2,3] and lastly 2, [4,5]. The dict(enumerate(l)) part will convert [1,4,6] to {0:1, 1:4, 2:6}. And the whole list-comprehension will avoid to use append.
This will need you to change your Node class a little bit so you can initialize the dict attribute using a parameter of the constructor:
class Node:
def __init__(self, id, dic=None):
self.id = id
self.dict = {} if dic is None else dic
Oh, and you might have misspelled allSatisfy. The f is missing.
Ok, took some time to better understand the code, so time for a proper review.
Naming
Yes, again, because it really impairs readability. One letter variable names are note meaningful, it's hard to understand what they hold. And you have them all around the place: x, y, l, n, p, i. Even though i (and j) are generally accepted as iterating variabbles in a for loop. self.dict does not convey any information either, same for li which I guess stand for list (but list of what?). You also happen to have various (_)len which might better be named num_of_something.
Also, PEP8, the de-facto coding-style standard in Python, recommends snake_case instead of camelCase or TitleCase for variables and functions names.
Avoid global variables
Except for constants, using global variables is generaly a code smell. You can always (at the very least) pass them as parameters to functions. But if this means passing this parameter to tens of functions before it becomes useful, then, maybe, a global might be a good idea.
Or there is an alternative…
One of them is the Gnodes list which store the nodes ordered by their indices. It is only used in FindTarget to retrieve a node based on its index. Because… you store the indices of target nodes in each Node's self.dict. If instead you had stored the target node directly, you wouldn't even need to have Gnodes as global. Plus other benefits that we'll see later.
class Node:
def __init__(self, id):
self.id = id
self.transitions = {}
def add_transition(self, transition, target):
self.transitions[transition] = target
def build_automata(list_of_state_transitions):
automata = [Node(i) for i in range(len(list_of_state_transitions))]
for node, transitions in zip(automata, list_of_state_transitions):
for transition, next_node_id in enumerate(transitions):
node.add_transition(transition, automata[next_node_id])
return automata
This way, you can retrieve target nodes easily from a single node with target_node = node.transitions[p[0]] for instance; no need for the list to convert from index to node anymore.
The second global variable is target. First off, you do not clear it between to checks. This will lead to memory growing large after some calls. Second, since you’re hashing with Nodes first, it might get in the way of the computation when tryDelete is involved, leading to potentialy bogus results. And third, since it is some kind of cache per node, why not include it in a Node's state directly?
class Node:
def __init__(self, id):
self.id = id
self.transitions = {}
self.target_cache = {}
def add_transition(self, transition, target):
self.transitions[transition] = target
# start filling cache already
self.target_cache[(transition,)] = target
Wait… no… this is completely redundant:
class Node:
def __init__(self, id):
self.id = id
self.transitions = {}
def add_transition(self, transition, target):
self.transitions[(transition,)] = target
def get_target_after(self, path):
try:
return self.transitions[path]
except KeyError:
next_node = self.transitions[(path[0],)]
value = self.transitions[path] = next_node.get_target_after(path[1:])
return value
Here we use EAFP instead of a simple if ... else because we hope to get path in self.transitions more than we get a KeyError.
This method will replace the FindTarget function and is called using node.get_target_after(path) instead of FindTarget(node, p). And we don't need target anymore.
Have functions that organize the control flow and functions that do things; not both.
There is another strong issue with your code that hinder understandability: the weird "recursion" involved in pathPossible. You check if a path is possible with the list of nodes passed as parameter; which is good But then, if you don't find a path, you recurse (indirectly through tryDelete) to check if there is a configuration with one less node where such path exists; which is bad. pathPossible should not have to do this, it should be it's caller responsibility. This will also help avoid the weird isIterate (really, shouldn't it be shouldIterate?) parameter.
Changing that will allow you to simplify the function a bit and to make the intent clearer in the caller:
# common_ending_exists is your pathPossible
# common_ending is your allSatisy
# all_paths is your allPossiiblePaths
def common_ending_exists(automata, try_remove=None):
num_nodes = len(automata)
num_transitions = len(automata[0].transitions)
return any(common_ending(automata, path, try_remove)
for path in all_paths(num_nodes, num_transitions))
def solve(list_of_state_transitions): # instead of answer
automata = build_automata(list_of_state_transitions) # see above
if common_ending_exists(automata):
return True
for node in automata:
if common_ending_exists(automata, try_remove=node):
return node.id
return False
A few things to note here:
- Meaningful return values:
True instead of -1 when a path is found; False instead of -2 when not; and I kept your return value of the node index to remove when removing it would reveal the existence of such path.
any will short circuit and return True when the first path will trigger a truthy response from common_ending.- Better understanding of the control flow: the search of a path when trying to remove nodes is not hidden in the search of a path anymore.
- Better handling of "removed" nodes: no need to make costly deep copies of the list of nodes anymore.
Speaking of that…
Trying to remove nodes
So, after saying that you don't need the deep copy that tryDelete brings in, what are we left with to deal with skipped nodes (I prefer that to removed, especially with the managing done in solve)? Well, we just have to handle them in allSatisy (well common_ending now) and get_target_after:
def common_ending(automata, path, skip):
reference_node = automata[0]
if reference_node is skip:
reference_node = automata[1]
ending = reference_node.get_target_after(path, skip)
return all(ending == node.get_target_after(path, skip)
for node in automata if node is not skip)
class Node:
def __init__(self, id):
self.id = id
self.transitions = {}
# We now need to cache based on which node is skipped
# so back to square one
self.target_cache = {}
def add_transition(self, transition, target):
self.transitions[transition] = target
def get_target_after(self, path, skip):
path_lead_to = self.target_cache.setdefault(skip, {})
try:
return path_lead_to[path]
except KeyError:
if path:
# Get next node and handle "removed" one if any
transition = path[0]
next_node = self.transitions[transition]
if next_node is skip:
if next_node.transitions[transition] is next_node:
next_node = self
else:
next_node = next_node.transitions[transition]
path_lead_to[path] = next_node.get_target_after(path[1:], skip)
else:
# No more transitions, we're done
path_lead_to[path] = self
return path_lead_to[path]
Note that I use reference comparison with is because all I want to know is if it is the same node, not if they look similar.
Bringing it all together and testing it properly
from itertools import product
class Node:
def __init__(self, id):
self.id = id
self.transitions = {}
self.target_cache = {}
def add_transition(self, transition, target):
self.transitions[transition] = target
def get_target_after(self, path, skip):
path_lead_to = self.target_cache.setdefault(skip, {})
try:
return path_lead_to[path]
except KeyError:
if path:
# Get next node and handle "removed" one if any
transition = path[0]
next_node = self.transitions[transition]
if next_node is skip:
if next_node.transitions[transition] is next_node:
next_node = self
else:
next_node = next_node.transitions[transition]
path_lead_to[path] = next_node.get_target_after(path[1:], skip)
else:
# No more transitions, we're done
path_lead_to[path] = self
return path_lead_to[path]
def all_paths(num_nodes, num_transitions):
for i in range(1, num_nodes + 1):
yield from product(range(num_transitions), repeat=i)
def common_ending(automata, path, skip):
reference_node = automata[0]
if reference_node is skip:
reference_node = automata[1]
ending = reference_node.get_target_after(path, skip)
return all(ending == node.get_target_after(path, skip)
for node in automata if node is not skip)
def common_ending_exists(automata, try_remove=None):
num_nodes = len(automata)
num_transitions = len(automata[0].transitions)
return any(common_ending(automata, path, try_remove)
for path in all_paths(num_nodes, num_transitions))
def build_automata(list_of_state_transitions):
automata = [Node(i) for i in range(len(list_of_state_transitions))]
for node, transitions in zip(automata, list_of_state_transitions):
for transition, next_node_id in enumerate(transitions):
node.add_transition(transition, automata[next_node_id])
return automata
def solve(list_of_state_transitions):
"""
>>> solve([[2,1],[2,0],[3,1],[1,0]])
True
>>> solve([[1,2],[1,1],[2,2]])
1
>>> solve([[1,3,0],[1,0,2],[1,1,2],[3,3,3]])
True
"""
automata = build_automata(list_of_state_transitions) # see above
if common_ending_exists(automata):
return True
for node in automata:
if common_ending_exists(automata, try_remove=node):
return node.id
return False
if __name__ == '__main__':
import doctest
doctest.testmod()
Last notes:
- You can
yield from a generator when you'd have iterated over it and yielded elements without modifying them.
- You can clean your test-cases with the
doctest module.
- Don't forget to document your functions with proper docstrings (which I didn't do here).
pand apply it to each node. If for every node,plead to the same ending node, you're good. The puzzle is to find if suchpexists.tryDeletesuggests that if you don't find any with the whole automata, you can try again by removing any one node. \$\endgroup\$pcan be(0, 1)for the first automata, and(1, 1, 1)for the third one. \$\endgroup\$