glow puzzle

glow_puzzle.py

#!/usr/bin/python2
# -*- coding: utf-8 -*-
#
# Author: Ray Chen <oldsharp@gmail.com>
#
# This program has been placed in the public domain.


"""A puzzle game with moving tiles."""


from collections import deque


W = 4
H = 4
target_pos_x = 0
target_pos_y = 0
DIRECTION = ['L', 'R', 'U', 'D']
MOVE = [(0, -1), (0, 1), (-1, 0), (1, 0)]

START = (
    ('W', 'R', 'B', 'B'),
    ('R', 'R', 'B', 'B'),
    ('R', 'R', 'B', 'B'),
    ('R', 'R', 'B', 'B'),
)

TARGET = (
    ('W', 'B', 'R', 'B'),
    ('B', 'R', 'B', 'R'),
    ('R', 'B', 'R', 'B'),
    ('B', 'R', 'B', 'R'),
)

# may use collections.deque for better performance
queue = deque()

# set for state hash
visited = set()


class Node(object):
    """Structure for node in state queue."""
    def __init__(self, x=0, y=0, path=list(), board=START):
        """Default to init state."""
        self.x = x
        self.y = y
        self.path = path
        self.board = board


def refresh(curr_board, curr_x, curr_y, next_x, next_y):
    """Refresh state of board."""
    buff_board = list()
    for line in curr_board:
        buff_board.append(list(line))

    buff_tile = buff_board[curr_x][curr_y]
    buff_board[curr_x][curr_y] = buff_board[next_x][next_y]
    buff_board[next_x][next_y] = buff_tile

    res_board = list()
    for line in buff_board:
        res_board.append(tuple(line))
    return tuple(res_board)


def verify(board_to_comp):
    """Verify that if we have reached our goal."""
    for i in range(H):
        for j in range(W):
            if board_to_comp[i][j] != TARGET[i][j]:
                return False
    return True


def bfs():
    """Main routine that implementing bfs algorithm."""
    # push start node in queue
    queue.append(Node())

    # add init state to set
    visited.add(START)

    while queue:
        curr_pos = queue.popleft()

        for i in range(4):
            next_path = list(curr_pos.path)
            next_path.append(DIRECTION[i])
            next_pos = Node(x=curr_pos.x+MOVE[i][0],
                            y=curr_pos.y+MOVE[i][1],
                            path=next_path)
            if (next_pos.x < 0 or next_pos.x >= H or
                    next_pos.y < 0 or next_pos.y >= W):
                continue
            else:
                # re-fresh board
                next_pos.board = refresh(curr_pos.board,
                                         curr_pos.x, curr_pos.y,
                                         next_pos.x, next_pos.y)
                if next_pos.board in visited:
                    continue
                else:
                    # verify
                    if (next_pos.x == target_pos_x and
                            next_pos.y == target_pos_y):
                        if verify(next_pos.board):
                            return next_pos.path
                    # append queue
                    queue.append(next_pos)
                    # add next state into set
                    visited.add(next_pos.board)

    return None


if __name__ == '__main__':
    """Entrance."""
    res = bfs()
    if res:
        print ''.join(res)