Breadth -first search

START = 11 TARGET = 25 def main(): queue = [(START, [str(START)])] while queue: curr, path = queue.pop(0) if curr == TARGET: return path queue.append((curr * 2, path + ['x2 => %s' % (curr * 2)])) queue.append((curr - 3, path + ['-3 => %s' % (curr - 3)])) assert False, 'Expect never to reach here' if __name__ == "__main__": path = main() print '\n'.join(path)

2 Responses

This is going to run into memory problems pretty soon, as it's using the full 2^n for each level of search. Could improve efficiency by pruning branches which visit a value which has already been reached, as that can never result in a shortest path.
Yes, not surprisingly, pruning branches which visit numbers we've already reached gives a big boost. My laptop was bogging down at depth 20 before, now it's up at 27.

Write a comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.