title: Shortest Route Optimization Not Working
body: <p>I was trying to solve the Ruby Quiz problem 60 in Python, given here:
  <a href="http://rubyquiz.com/quiz60.html" rel="nofollow">http://rubyquiz.com/quiz60.html</a></p>
  
  <p>One basically has to find the shortest path from one number to another by only doubling, halving, or adding 2 to a number. </p>
  
  <p>Writing a program to actually solve the question wasn't too difficult:</p>
  
  <pre><code>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)
  
  
  &gt;&gt;&gt; maze_solver(9, 2)
  [9, 18, 20, 10, 12, 6, 8, 4, 2]
  &gt;&gt;&gt; maze_solver(2, 9)
  [2, 4, 8, 16, 18, 9]
  </code></pre>
  
  <p>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. </p>
  
  <p>I tried this optimization:</p>
  
  <pre><code>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) &gt;= 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])
  </code></pre>
  
  <p>But this doesn't even yield the right answer:</p>
  
  <pre><code>&gt;&gt;&gt; maze_solver(9, 2)
  [9, 11, 22, 24, 48, 24, 12, 6, 8, 4, 2]
  </code></pre>
  
  <p>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!</p>