# Shifting Paths problem (Code Jam)

I was trying, just for fun, to solve http://code.google.com/codejam/contest/dashboard?c=2075486#s=p4

I can easily solve the small set, but I struggle to solve the big one (my implementation would use approx. 30GB or RAM, which is a bit too much. Any hint or direction is appreciated!

def solve_maze(case_no):
case = cases[case_no]
case_no += 1
edges = case['edges']
#quick and dirty check. Can we reach the goal?
if case['goal'] not in sum([i.values() for i in edges.values()],[]):
return "Case #%s: Infinity" % case_no
last_position = 1
l = 0
states = set()
memory = [1 for i in range(1,1+case['goal'])]
while not last_position==case['goal']:
direction = memory[last_position]
memory[last_position] *= -1
move = edges[last_position][direction]
l+=1
if len(states) != l:
return "Case #%s: Infinity" % case_no
last_position = move
else:
return "Case #%s: %d" % (case_no,len(states))

with open("/xxx/test-small.in","rb") as f:
N = int(inp[0])
cases = []
it = 0
for line in inp[1:]:
if line.find(" ") == -1:
#print int(line)
cases.append({"goal":int(line),"edges":{}})
it = 0
else:
it+=1
cases[-1]['edges'][it] = dict(zip([1,-1],map(int,line.split())))
for i in range(len(cases)):
print solve_maze(i)

-

def solve_maze(case_no):
case = cases[case_no]


It'd make more sense to pass the case here, and operate on that rather then passing in the case number

    case_no += 1
edges = case['edges']
#quick and dirty check. Can we reach the goal?
if case['goal'] not in sum([i.values() for i in edges.values()],[]):
return "Case #%s: Infinity" % case_no


I avoid such quick and dirty checks. The problem is that they are easily defeated by a crafted problem. Not enough cases are really eliminated here to make it work.

    last_position = 1
l = 0
states = set()
memory = [1 for i in range(1,1+case['goal'])]


It's a little odd to add one to both parameters to range and then ignore the count

    while not last_position==case['goal']:


Use !=

        direction = memory[last_position]
memory[last_position] *= -1
move = edges[last_position][direction]


You aren't guaranteed to have distinct hashes for unequal objects so this must fail. You should really add the whole tuple to the state. Actually, you don't even need to track the states. There are are only so many possible states, and you can simply count the number of transitions, if this gets above the number of possible states, you're in an infinite loop.

        l+=1
if len(states) != l:
return "Case #%s: Infinity" % case_no
last_position = move
else:
return "Case #%s: %d" % (case_no,len(states))

with open("/xxx/test-small.in","rb") as f:


This really isn't a good way to read your input. Use f.readline() to fetch a line at a time. It'll be much easier to parse the input that way.

    N = int(inp[0])
cases = []
it = 0
for line in inp[1:]:


Wrong choice of loop. You really want to repeat the process of reading a single case N times, not do something on each line of the file.

        if line.find(" ") == -1:
#print int(line)
cases.append({"goal":int(line),"edges":{}})


Don't treat dictionaries like objects. It'd make more sense to pass goal and edges as parameters rather them stick in a dictionary. At least, you should prefer an object.

            it = 0
else:
it+=1
cases[-1]['edges'][it] = dict(zip([1,-1],map(int,line.split())))
for i in range(len(cases)):
print solve_maze(i)


As for your algorithm. You can't get away with simulating all of the clearings. One can design a test case that takes over 2**39 steps to complete. So you can't simulate the straightforward process of moving one clearing at a time. But any given forest will have patterns in how the states change. You need to find a way to characterize the patterns so that you can simulate the process more quickly.

-
Thanks for the coding review. I was particularly interested in a comment on the algo but I was happy to see how I could have written a cleaner code. As for the infinite loop, now I am doing it by checking if the node I go to is somehow, optimally connected to the goal. If it's not, then I have an infinite loop. The hash was used in a test version to reduce the amount of memory used by the list, but I was aware of the high chance of collisions. I am now following the suggestion of a friend, i.e. trying to implement some DP on half of the set. –  luke14free Nov 4 '12 at 11:52
@luke14free, I believe that checking for connection to the goal won't be sufficient for infinite loops. I'm pretty sure I found cases where I was connected, but still in an infinite loop. The half-set DP solution should work, although its not the same solution I implemented. –  Winston Ewert Nov 4 '12 at 12:44
Now I am tempted about asking for your idea.. :) But I won't! I'll delve a bit deeper and try to figure out other solution schemas –  luke14free Nov 4 '12 at 13:08