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

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

StackExchange Code Review Q#116200, answer score: 4