Shortest Route Optimization Not Working

Question

I was trying to solve the Ruby Quiz problem 60 in Python, given here: http://rubyquiz.com/quiz60.html

One basically has to find the shortest path from one number to another by only doubling, halving, or adding 2 to a number.

Writing a program to actually solve the question wasn't too difficult:

def maze_solver(a, b):
    paths = [[a]]
    final = []

    for ind, path in enumerate(paths):

        if path[-1] == b:
            return path

        last = path[-1]

        paths.append(path + [last * 2])
        paths.append(path + [last + 2])
        if last % 2 == 0:
            paths.append(path + [last / 2])


print maze_solver(979, 2)


>>> maze_solver(9, 2)
[9, 18, 20, 10, 12, 6, 8, 4, 2]
>>> maze_solver(2, 9)
[2, 4, 8, 16, 18, 9]

But when I tried to optimize it, which failed. I figured that if two paths ever have the same ending point and one path is shorter than the other, then the longer path could be eliminated.

I tried this optimization:

def maze_solver(a, b):
    paths = [[a]]
    final = []

    for ind, path in enumerate(paths):

        if path[-1] == b:
            return path

        for other in paths:
            if ind != paths.index(other):
                if path[-1] == other[-1] and len(other) >= len(path):
                    paths.remove(other)

        last = path[-1]

        paths.append(path + [last * 2])
        paths.append(path + [last + 2])
        if last % 2 == 0:
            paths.append(path + [last / 2])

But this doesn't even yield the right answer:

>>> maze_solver(9, 2)
[9, 11, 22, 24, 48, 24, 12, 6, 8, 4, 2]

I have no idea why this piece of code isn't working, so if anyone could explain to me what I'm doing wrong, that would be very helpful, thank you!

Answer 1

It can be dangerous to modify a list while iterating through it.

See this answer