PyCon 2013 Twitter #HASHSWAG Challenge

hashswag.py

from heapq import heappush, heappop


############################
# Game rules
############################
def next_positions(board):
    return [(execute_move(board, move), move) for move in possible_moves(board)]

def possible_moves(board):
    blanks = [i for (i, c) in enumerate(board) if c == '*']
    result = []
    for blank in blanks:
        offsets = [-3, 3] # upper and lower fields
        if blank % 3 != 0:
            offsets.append(-1) # left field
        if blank % 3 != 2:
            offsets.append(1) # right field
        result.extend((blank + offset, blank) for offset in offsets
                      if 0 <= blank + offset < 9 and board[blank + offset] != '*')
    return result

def execute_move(board, move):
    fields = list(board)
    fields[move[0]], fields[move[1]] = fields[move[1]], fields[move[0]]
    return ''.join(fields)


############################
# A* algorithm
############################
def hashswag(initial, goal):
    # Basic A* algorithm. We treat the plane of all game states as a
    # graph and try to find the shortest route from initial state to
    # goal state.
    #
    # In priority queue:
    #     (heuristic overall distance through the node,
    #      distance from initial to node,
    #      board state,
    #      move we made to get here from previous state)
    #
    # We also store the best moves, which can be used to get the
    # shortest path later on.
    #
    queue = [(heuristic(initial, goal), 0, initial, None)]
    visited = {}
    moves = {}

    while len(queue) > 0:
        _, d, board, move = heappop(queue)
        if board not in visited or visited[board] > d:
            visited[board] = d
            moves[board] = move
            if board == goal:
                return moves
            for next_board, move in next_positions(board):
                h = heuristic(next_board, goal)
                heappush(queue, (d + h + 1, d + 1, next_board, move))

def heuristic(board1, board2):
    # Our A* heuristic - Levensthein distance
    return sum(int(c1 != c2) for (c1, c2) in zip(board1, board2))

def walk_moves(moves, board):
    # Retrieve the shortest path
    if moves.get(board) is None:
        return []
    result = [moves[board]]
    while True:
        board = execute_move(board, result[-1])
        prev_move = moves.get(board)
        if prev_move is None:
            return reversed(result)
        result.append(prev_move)


############################
# Command line
############################
if __name__ == '__main__':
    import sys
    goal = 'HASHTAG**'
    moves = hashswag(sys.argv[1], goal)
    print '\n'.join('%d %d' % (move[0] + 1, move[1] + 1)
                    for move in walk_moves(moves, goal))

test_hashswag.py

import unittest
from hashswag import hashswag, walk_moves


class HashswagTestCase(unittest.TestCase):
    def test_initial_equals_goal(self):
        self.assertEqual({'HASHTAG**': None}, hashswag('HASHTAG**', 'HASHTAG**'))

    def test_no_possible_move(self):
        self.assertEqual(None, hashswag('HASHTAH**', 'HASHTAG**'))

    def test_example(self):
        moves = hashswag('HAAHS*T*G', 'HASHTAG**')
        self.assertEqual([(6, 7), (4, 5), (1, 4), (2, 1), (5, 2),
                          (4, 5), (7, 4), (8, 7), (7, 6)],
                         list(walk_moves(moves, 'HASHTAG**')))


if __name__ == '__main__':
    unittest.main()