Machinarium Minigame solver

machinarium-minigame.py

#!/usr/bin/env python
# coding=utf

#       0 1 2
#    9         3
#   10         4
#   11         5
#       6 7 8 
#
#    |-----------|
#    | 0 | 1 | 2 |
#    |-----------|
#    | 3 | 4 | 5 |
#    |-----------|
#    | 6 | 7 | 8 |
#    |-----------|
#

#    Рисование
#     . . . . .
#     ....\....
#     .   \   .
#     .    \...
#     . . . . .
#   
#     . . . . .
#     .   |   .
#     .   |   .
#     .   \....
#     . . . . .
#
#

class Piece:
  UP = 0
  RIGTH = 1
  DOWN = 2
  LEFT = 3

  def __init__(self, joints={}):
    self.image = self.create_image(joints)  
    self.joints = joints
    for k,v in joints.items():
      self.joints[v] = k

  def walk(self, start):
    if start in self.joints:
      return self.joints[start]
    else:
      return None

  def __str__(self):
    return self.image

  def create_image(self, joints):
    s = []
    for k,v in joints.items():
      s.append('{}-{}'.format(k, v))
    return '[' + (' '.join(s)) + ']' 

    s = map(lambda row: [row]*9, [' '] * 5)
    self.draw_border(s)
    for a,b in joints.items():
      self.draw_join(a, b, s)

    return '\n'.join(map(lambda row: ''.join(row), s))

  def draw_join(self, a, b, buf):
    print 'draw_join(a={}, b={})'.format(a,b)
    a_side = a / 3
    b_side = b / 3
    if abs(a_side - b_side) == 2:
      # на противоположных сторонах
      pass
    elif a_side != b_side:
      # на смежных сторонах
      # x1,y1 - на боковой стороне, x2,y2 - снизу или сверху
      if a_side == self.LEFT or a_side == self.RIGTH:
        x1 = a % 3
        y1 = 0 if a_side == self.LEFT else 2
        y2 = b % 3
        x2 = 0 if b_side == self.UP else 2
      else:
        x1 = b % 3
        y1 = 0 if b_side == self.LEFT else 2
        y2 = a % 3
        x2 = 0 if a_side == self.UP else 2

      print 'x1={} y1={}; x2={} y2={}'.format(x1,y1,x2,y2)
      # чертим вертикальную линию
      for row in range(min(x1,x2), max(x1,x2)+1):
        buf[row+1][y2*2+2] = '|'

      for column in range((min(y1,y2)+1)*2, (max(y1,y2)+1)*2):
        buf[x1+1][column] = '.'

      corner = '\\' if (a_side + b_side - 1) % 4 == 0 else '/'
      buf[x1+1][(y2+1)*2] = corner

    else:
      pass
      # на одной стороне

  def draw_border(self, buf):
    for row in range(len(buf)):
      buf[row][0] = '.'
      buf[row][-1] = '.'

    for column in range(0, len(buf[0]), 2):
      buf[0][column] = '.'
      buf[-1][column] = '.'

  def is_empty(self):
    return len(self.joints) == 0

class Board:
  start_piece = 7
  start_door = 7
  end_piece = 1
  end_door = 1
  UP = 0
  RIGTH = 1
  DOWN = 2
  LEFT = 3

  def __init__(self, pieces):
    assert len(pieces) == 9
    self.pieces = pieces
    self.__steps = None

  def test(self, by_step=False):
    door = self.start_door
    piece_num = self.start_piece
    piece = self.pieces[piece_num]
    self.__steps = 0
    while True:
      if by_step:
        print '-'*20
        print self.__str__(piece)
        print 'door =', door
        raw_input()
      if piece.is_empty():
        break
      self.__steps+=1
      door = piece.walk(door)
      if door is None:
        break
      direction = door / 3
      if direction == self.UP:
        piece_num -= 3
        if piece_num < 0:
          break
      elif direction == self.DOWN:
        piece_num += 3
        if piece_num > 8:
          break
      elif direction == self.RIGTH:
        piece_num += 1
        if piece_num % 3 == 0:
          break
      else:
        if piece_num % 3 == 0:
          break
        piece_num -= 1
      piece = self.pieces[piece_num]
      door = (door + 6) % 12
    return piece == self.pieces[self.end_piece] and door == self.end_door

  def steps(self):
    if self.__steps is None:
      self.test()
    return self.__steps

  def __str__(self, current=None):
    s = ''
    for i, piece in enumerate(self.pieces):
      if i%3==0 and i > 0:
        s += '\n'
      if piece == current:
        s += '{{{:^9}}}'.format(piece)
      else:
        s += ' {:^9} '.format(piece)
    return s

if __name__ == '__main__':
  P = Piece
  # board = Board([ P(),      P({3:1}),   P({7:9}),
  #                 P({6:4}), P({10:4}),  P({10:1}), 
  #                 P({0:5}), P({11:7}),  P() ])

  available = [
    P({1:7,3:5}), P({6:8}), P(),
    P({1:4}),     P({1:3,10:5}), P({9:8, 11:6}),
    P({10:7}),    P({9:0,11:2}), P({0:7, 2:4})
  ]

  from itertools import permutations
  boards = [Board(v) for v in permutations(available)]
  results = map(lambda b:b.test(), boards)
  steps = map(lambda b: (b.steps(), b), boards)
  print "OK" if any(results) else "NO"
  n = results.index(True)
  print "found at", n
  boards[n].test(True)

  # top = sorted(steps, reverse=True)[:1]
  # for steps, board in top:
  #   print steps,'steps:'
  #   board.test(True)