Expert System Lab 5

es5.py

import operator

goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)

directions = (left, right, up, down) = range(4)
directions_str = {left : 'left', right : 'right', up : 'up', down : 'down'}
moves = {right: (-1, lambda pos: pos % 3 != 0),
     left:   (1, lambda pos: pos % 3 != 2),
     down:  (-3, lambda pos: pos > 2),
     up:     (3, lambda pos: pos < 6)}
class Puzzle:
  def __init__(self, puzzle, path):
    self.puzzle = puzzle
    self.path = path
  def __str__(self):
    def row(i):
      return reduce(lambda x, y: str(x) + ' ' + str(y),\
        self.puzzle[i * 3 : i * 3 + 3])
    return reduce(lambda x, y: str(x) + '\n' + str(y),\
      [row(i) for i in range(3)])

  def __eq__(self, other):
      if self.__class__ != other.__class__:
          return False
      else:
          return self.puzzle == other.puzzle
  def cost(self):
    def dist(i):
      dest = ((i - 1) / 3, (i - 1) % 3)
      pos = (self.puzzle.index(i) / 3, self.puzzle.index(i) % 3)
      return abs(dest[0] - pos[0]) + abs(dest[1] - pos[1])
    dists = [dist(i) for i in range(1, 9)]
    return reduce(operator.__add__, dists, 0) + len(self.path)
    # diff = [x == y for x, y in zip(self.puzzle, goal) if x != 0]
    # return len(filter(lambda x: not x, diff)) + len(self.path)
  def move(self, direction):
    empty_pos = self.puzzle.index(0)
    move = moves[direction]
    if not move[1](empty_pos):
      return None

    swap_pos = empty_pos + move[0]
    min_i, max_i = min(empty_pos, swap_pos), max(empty_pos, swap_pos)
    moved_puzzle = self.puzzle[: min_i] + self.puzzle[max_i : max_i + 1] + \
      self.puzzle[min_i + 1 : max_i] + self.puzzle[min_i : min_i + 1] + \
      self.puzzle[max_i + 1 :]
    return Puzzle(moved_puzzle, self.path + (direction,))

  def possible_moves(self):
    moves = filter(lambda p: p is not None, [self.move(d) for d in\
      directions])
    return tuple(sorted(moves, lambda x, y: x.cost() - y.cost()))

  def resolve(self):
    opened = list(self.possible_moves())
    closed = set()
    while len(opened) != 0:
      current = opened[0]
      if current.puzzle == goal:
        return current.path

      children = list(filter(lambda c: c.puzzle not in closed,\
        current.possible_moves()))
      opened = sorted(opened[1:] + children,\
        lambda x, y: x.cost() - y.cost())
      closed.add(current.puzzle)
    return None


puzzle = Puzzle((1, 2, 3,
                 4, 6, 7,
                 5, 0, 8), ())

print puzzle, "\n\nSolution!"
for r in puzzle.resolve():
  print directions_str[r]