# Finding if there exists an input for a given automata for which no matter what the starting state is, final state would be same everytime

I am solving a puzzle (Finding if there exists an input for a given automata for which no matter what the starting state is, final state would be same everytime) and have written following Python code. A few testcases are written in check method in the code. For these cases program is running fairly fast. However, for testcases where 50 lists (nodes) are present, the program is taking forever to execute. I am storing intermediate results to use further as well. Can someone please review the code and give suggestions on how to increase the performance of the code?

from itertools import product
from copy import deepcopy

class Node:
def __init__(self,id):
self.id = id
self.dict = {}

def __str__(self):
return str(self.id) + " : " + str(self.dict)

def __repr__(self):
return str(self.id) + " : " + str(self.dict)

def tryDelete(nodes,_len):
for i in range(len(nodes)):
y = nodes[:]
x = y[i]
del y[i]
tNodes = []
for node in y:
for input,result in node.dict.items():
if result == x:
node.tDict = deepcopy(node.dict)
if x.dict[input] == x.id:
node.dict[input] = node
else:
node.dict[input] = x.dict[input]

if pathPossible(y,_len ,False) == -1:
return x.id
for n in tNodes:
n.dict = n.tDict
del n.tDict
return -2

target = {}
def FindTarget(node,p):
if len(p) == 1:
return node.dict[p[0]]
if node not in target or p not in target[node]:
x = Gnodes[FindTarget(node,p[:-1])].dict[p[-1]]
if node not in target:
target[node] = {}
target[node][p] = x
return target[node][p]

def allSatisy(nodes,p):
x = None
for node in nodes:
if x is None:
x = FindTarget(node,p)
elif FindTarget(node,p) != x:
return False
return True

def allPossiblePaths(l,n):
#x = int(((l+1)*(l+2))/2)
for i in range(1, n + 1):
for p in product(range(l),repeat=i):
yield p

def pathPossible(nodes,_len ,isItereate=True):
i = 1
isFound = False
for p in allPossiblePaths(_len,len(nodes)):
if allSatisy(nodes,p):
isFound = True
break

if isFound:
return -1
elif not isItereate:
return -2
else:
return tryDelete(nodes,_len)

Gnodes = []
Gnodes[:] = []
for i in range(len(li)):
Gnodes.append(Node(i))#[i] = Node(i)
for i in range(len(li)):
for j in range(len(li[i])):
Gnodes[i].dict[j] = li[i][j]
return pathPossible(Gnodes,len(Gnodes[0].dict))

def check(li,ans):
print(str(li) + " : " + str(ans) + " : " + str(x))

def main():
check([[2,1],[2,0],[3,1],[1,0]],-1)
check([[1,2],[1,1],[2,2]],1)
check([[1,3,0],[1,0,2],[1,1,2],[3,3,3]],-1)

if __name__ == '__main__':
main()

• Welcome to Code ReviewIt appears that you have accidentally created two accounts. You should request that they be merged. – 200_success Jan 8 '16 at 7:43
• I don't understand the puzzle description. Can you link to the puzzle? Or quote it in full? – Gareth Rees Jan 8 '16 at 21:43
• @GarethRees From what I get: take a sequence of transitions p and apply it to each node. If for every node, p lead to the same ending node, you're good. The puzzle is to find if such p exists. tryDelete suggests that if you don't find any with the whole automata, you can try again by removing any one node. – 301_Moved_Permanently Jan 9 '16 at 10:43
• @GarethRees For instance, p can be (0, 1) for the first automata, and (1, 1, 1) for the third one. – 301_Moved_Permanently Jan 9 '16 at 10:49

There's no need to define both __str__ and __repr__ for Node when they're both the same functionality. If you just define __repr__ it will be called in place of __str__ when necessary. (though the reverse is not true). See:

>>> class A:
def __repr__(self):
return "self"

>>> str(A())
'self'


Instead of assigning a value to x then deleting it with del, use pop.

x = y.pop(i)


This simultaneously passes y[i] to x while removing it from y.

x = y[i]


This is also quite a confusing function, adding a docstring would make it a lot clearer what it actually is/does. As would better names. y could be nodes_copy and x could be... node I guess? I'm not entirely clear on what x is meant to be for, since the name is meaningless. Also what's tNodes? Does the t stand for something? Traversed possibly? Except I don't see you adding anything to the empty list so I don't see what it does at all.

In FindTarget you're calculating node not in target twice. You do need to use this for two separate if statements, but you could just store the boolean to save running the test twice:

def FindTarget(node,p):
if len(p) == 1:
return node.dict[p[0]]

node_in_target = node in target
if not node_in_target or p not in target[node]:
x = Gnodes[FindTarget(node,p[:-1])].dict[p[-1]]
if not node_in_target:
target[node] = {}
target[node][p] = x
return target[node][p]


As @JoeWallis pointed out, a dictionary is fast at testing these look ups, but that doesn't mean this wont still save time.

In allSatisy, isn't x just being set to the result of FindTarget(nodes[0], p)? Because FindTarget never returns None, x will always be set to some result and therefore will only be set on the first iteration. Unless I'm wrong and the node values returned from FindTarget can be None. If that's not the case though, this would make your function clearer:

def allSatisy(nodes,p):
x = FindTarget(nodes[0], p)
for node in nodes[1:]:
if FindTarget(node,p) != x:
return False
return True


And if this is the same as your function, then there's a faster way to do this using Python's all function. It can take a generator expression to evaluate every element in a list for a condition and return the result as a single boolean. In your case, you want to know if all the results of FindTarget(node, p) are equal to x, for each node in nodes (after the first node). Thankfully that's practically the syntax:

def allSatisy(nodes,p):
x = FindTarget(nodes[0], p)
return all(FindTarget(node, p) == x for node in nodes[1:])

• "means you've checked every node in the list", target is not a list, it's a dictionary. So node not in target is $O(1)$ not $O(n)$. – Peilonrayz Jan 8 '16 at 15:59
• @JoeWallis Good catch, I'll update that note. – SuperBiasedMan Jan 8 '16 at 16:09

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 = {}

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):
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 = {}

self.transitions[transition] = target
self.target_cache[(transition,)] = target


Wait… no… this is completely redundant:

class Node:
def __init__(self, id):
self.id = id
self.transitions = {}

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
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))

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 = {}

self.transitions[transition] = target

def get_target_after(self, path, skip):
try:
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]
else:
# No more transitions, we're done


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 = {}

self.transitions[transition] = target

def get_target_after(self, path, skip):
try:
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]
else:
# No more transitions, we're done

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):
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).