Strongly solving a puzzle through breadth-first search

diehard_puzzle_solver.py

"""
Implementation of the example from https://inst.eecs.berkeley.edu/~cs61c/fa14/projs/02/
"""
import operator

class Puzzle(object):
    """General game representation"""
    def solution(self):
        return Position(0)

class Position(object):
    """A position in the game"""
    delta_values = [3, 5]
    delta_ops = [operator.add, operator.sub]

    def __init__(self, value):
        self.value = value

    def children(self):
        for op in self.delta_ops:
            for delta in self.delta_values:
                c = op(self.value, delta)
                if 0 <= c <= 8:
                    yield Position(c)
                    
    def __eq__(x, y):
        return x.value == y.value

    def __hash__(self):
        return self.value

    def __repr__(self):
        return "Pos %s" % self.value
    
    
def solve(puzzle, max_level=-1):
    """BF visit the entire puzzle graph, build level_to_pos, pos_to_level structures."""
    level_to_pos = {}
    pos_to_level = {}

    solution = puzzle.solution()
    level = 0
    level_to_pos[level] = [solution] ### level 0 consists of a single solution 
    pos_to_level[solution] = level

    ### While there are still positions on the frontier
    ### (seen for the first time in the last iteration)
    while level_to_pos[level] and (max_level==-1 or level < max_level):
        level += 1
        level_to_pos[level] = []
        ### For every position on the last level (these farthest-away positions are the "frontier")
        for position in level_to_pos[level-1]:
            ### For every child of those frontier positions
            for child in position.children():
                ### If it's the first time we've seen this child
                if child not in pos_to_level:
                    ### Update the mappings to remember it, and it will be part of the new frontier
                    pos_to_level[child] = level
                    level_to_pos[level].append(child)

    del level_to_pos[level] ### the last level is always empty, so remove it.
    return level_to_pos, pos_to_level