Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
A* solution in Clear category for Snake Lite by PositronicLlama
"""
Play a game of 'snake'.
Use A* to find the most efficient path to the goal, while ensuring that the
snake does not become trapped.
"""
import collections
import heapq
Vec2 = collections.namedtuple('Vec2', ['x', 'y'])
ORTHOGONAL = ((0, 1), (1, 0), (0, -1), (-1, 0))
DIRECTIONS = {0: 'F', 1: 'L', -1: 'R'}
class Board:
"""A representation of the current game state."""
def __init__(self, data):
self.height = len(data)
self.width = len(data[0])
self.empty = set()
self.obstacles = set()
self.snake = {}
self.goal = None
for y, row in enumerate(data):
for x, c in enumerate(row):
cell = Vec2(x, y)
if c == '.':
self.empty.add(cell)
elif c == 'T':
self.obstacles.add(cell)
elif c == 'C':
self.goal = cell
elif c != '.':
self.snake[int(c)] = cell
# The current snake length
self.length = len(self.snake)
# The number of cherries remaining.
self.remaining = 10 - self.length
def hunt(self):
"""
Return a sequence of moves to get to the goal.
Return an empty string if no path is possible.
"""
# A linked list of prior snake positions.
history = None
for i in reversed(range(self.length)):
history = (self.snake[i], history)
return self._hunt(self.goal, history, self.length, True)
def _hunt(self, goal, history, length, check):
"""
Return a sequence of moves to get to the goal.
Return an empty string if no path is possible.
Internal version of hunt. Can override goal, history and length.
"""
# Use A* to navigate to the goal. Avoid obstacles and recent history.
# List of tuples of (estimated path distance, cost, sequence number, history)
visited = set()
pending = [(self.heuristic(goal, self.snake[0]), 0, 0, history)]
ix = 1
while pending:
current = heapq.heappop(pending)
_, cost, _, h = current
if h[0] == goal:
# Unless this is the last goal, ensure that we can escape.
if not check or self.remaining == 1 or self.can_escape(h, length + 1):
return self.get_moves(h, length)
continue
# Build a set of segments occupied by the snake in the recent past.
snake = set()
segment = h
# The tail of the snake moves first, so subtract one.
while len(snake) < length - 1:
snake.add(segment[0])
segment = segment[1]
snake = frozenset(snake)
if snake in visited:
continue
visited.add(snake)
# Consider all adjacent cells not blocked by an obstacle or the snake.
for next_pos in self.adjacent(h[0]):
if next_pos not in snake and next_pos not in self.obstacles:
ix += 1
next_h = (next_pos, h)
next_node = (self.heuristic(goal, next_pos) + cost + 1, cost + 1, ix, next_h)
heapq.heappush(pending, next_node)
return ''
@staticmethod
def heuristic(goal, pos):
"""An admissible A* heuristic for pos. Return Manhattan distance to goal."""
return abs(goal.x - pos.x) + abs(goal.y - pos.y)
def get_moves(self, h, length):
"""Return a string of the moves necessary to replicate history."""
moves = []
delta1 = Vec2(h[0].x - h[1][0].x, h[0].y - h[1][0].y)
while h[1][1] is not None:
h = h[1]
delta2 = Vec2(h[0].x - h[1][0].x, h[0].y - h[1][0].y)
cross = delta1.x * delta2.y - delta1.y * delta2.x
moves.append(DIRECTIONS[cross])
delta1 = delta2
# Subtract moves from the past.
return ''.join(reversed(moves[:-length+2]))
def adjacent(self, pos):
"""Yeild all coordinates adjacent to pos that are in bounds."""
for dx, dy in ORTHOGONAL:
p = Vec2(pos.x + dx, pos.y + dy)
if 0 <= p.x < self.width and 0 <= p.y < self.height:
yield p
def can_escape(self, history, length):
"""
Return True if the snake can escape to a distant cell given recent history.
"""
goal = self.distant_cell(history[0])
escape = self._hunt(goal, history, length, False)
return True if escape else False
def distant_cell(self, pos):
"""Return a distant cell that is not blocked by an obstacle."""
return max(self.empty, key=lambda cell: self.heuristic(pos, cell))
def checkio(data):
"""
Given a game board, determine the best move for the snake.
Return: F to move forward, L to turn left, and R to turn right.
Return a sequence of characters to make multiple moves at one time.
Cells can be:
. Empty space
T Tree
C Cherry
0 Snake head
1..9 Remainder of snake
"""
board = Board(data)
return board.hunt()
if __name__ == '__main__':
pass
Aug. 25, 2013
Comments:
