Skip to content

Instantly share code, notes, and snippets.

@mstepniowski
Created March 16, 2013 20:50
Show Gist options
  • Save mstepniowski/efb4204eda3ec9544bbb to your computer and use it in GitHub Desktop.
Save mstepniowski/efb4204eda3ec9544bbb to your computer and use it in GitHub Desktop.
PyCon 2013 Twitter #HASHSWAG Challenge
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))
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment