PyCon 2013 チュートリアル 迷路問題その1

maze.py

#! /usr/bin/env python
# coding:utf-8 

class Maze(object):
  def __init__(self):
    self.bitmap = (
      (1,1,1,1,1,1,1,1),
      (1,0,1,0,1,1,0,1),
      (1,0,1,0,1,0,0,1),
      (1,0,0,0,1,1,0,1),
      (1,1,1,0,0,0,0,1),
      (1,0,1,0,1,1,0,1),
      (1,0,0,0,0,1,0,1),
      (1,1,1,1,1,1,1,1))
    self.bitmap = (0xff, 0xad, 0xa9, 0x8d, 0xe1, 0xad, 0x85, 0xff)
    self.x_max = 8
    self.y_max = 8

  def get_value(self, x, y):
    return 1 if (self.bitmap[y] & 2**(7-x))>0 else 0
#    return self.bitmap[y][x]

  def is_floor(self, x, y):
    return self.get_value(x, y) ==0

  def is_wall(self, x, y):
    return not(self.is_floor(x, y))

  def display(self):
    for j in range(0,8):
      for i in range(0,8):
        print(self.get_value(i, j), end="")
      print()

class Walker(object):
  def __init__(self, maze, x, y, goal_x, goal_y):
    self.maze = maze
    self.x = x
    self.y = y
    self.goal_x = goal_x
    self.goal_y = goal_y
    self.passed_positions = set()
    self.trail_log = list()

  def get_to_goal(self):
    return (self.x == self.goal_x) and (self.y == self.goal_y)

  def get_movable_positions(self):
    result = list()
    for (dx, dy) in ((-1, 0), (0, -1), (1, 0), (0, 1)):
      (mx, my) = (self.x + dx, self.y + dy)
      if self.maze.is_floor(mx, my):
        result.append((mx, my))
    return result

  def move_to(self, x, y):
    print("Move from (%d, %d) to (%d, %d)" % (self.x, self.y, x, y))
    self.x = x
    self.y = y

  def solve(self):
    while not self.get_to_goal():
      no_way = True
      for next_pos in self.get_movable_positions():
        if next_pos not in self.passed_positions:
          no_way = False
          self.passed_positions.add((self.x, self.y))
          self.trail_log.append((self.x, self.y))
          self.move_to(*next_pos)
          break

      if no_way:
        self.passed_positions.add((self.x, self.y))
        next_pos = self.trail_log.pop()
        self.move_to(*next_pos)

    print("I got goal!")


class Borad(object):
  def __init__(self):
      width = 0
      height = 0
      unit_xy = 0

  def calculation_unit(self):
    lf = self.lifeboard
    unitx = int(self.width / lf.xmax())
    unity = int(self.height / lf.ymax())
    self.unit_xy = unitx if unitx <= unity else unity


def main():
  maze = Maze()
  maze.display()
  walker = Walker(maze, 1, 1, 6, 6)
  walker.solve()

if __name__ == "__main__":
  main()