Shifting Paths problem (Code Jam)

Question

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]
        states.add(hash((move,tuple(memory))))
        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:
    inp = f.read()[:-1].split("\n")
    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)

Answer 1

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]
        states.add(hash((move,tuple(memory))))

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:
    inp = f.read()[:-1].split("\n")

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.