Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Smart Snake solution in Uncategorized 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'])
Node = collections.namedtuple('Node', ['estimate', 'dist', 'ix', 'h'])
Link = collections.namedtuple('Link', ['pos', 'link'])
ORTHOGONAL = ((0, 1), (1, 0), (0, -1), (-1, 0))
DIRECTIONS = {0: 'F', 1: 'L', -1: 'R'}
MAX_LEN = 10
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 = MAX_LEN - 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 = Link(self.snake[i], history)
goal = self.goal
def heuristic(pos):
"""
Return the scaled Manhattan distance from pos to goal.
An admissible heuristic for pos.
"""
# Scaling encourages searching closer to the goal.
return (abs(goal.x - pos.x) + abs(goal.y - pos.y)) * 1.5
def at_goal(current):
"""Return True if the snake is at the goal."""
return goal == current.h.pos
return self._hunt(heuristic, at_goal, history, False)
def _hunt(self, heuristic, predicate, history, fleeing):
"""
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 heuristic, history and length.
"""
# Use A* to navigate to the goal. Avoid obstacles and recent history.
# List of tuples of (estimated path distance, dist, sequence number, history)
visited = set()
pending = [Node(heuristic(self.snake[0]), 0, 0, history)]
ix = 1
while pending:
current = heapq.heappop(pending)
_, dist, _, h = current
if predicate(current):
# Unless this is the last goal, ensure that we can escape.
if fleeing or self.remaining == 1 \
or self.can_escape(h):
# Return the reconstructed path.
return self.get_moves(h, self.length)
continue
# Build a list of cells occupied by the snake in the recent past.
length = self.length
if fleeing:
# If we are fleeing, assume the worst case - that
# we are forced to eat a cherry with each step.
#
# We win after all cherries are eaten, so subtract one from
# MAX_LEN.
length = min(length + 1 + dist, MAX_LEN - 1)
trail = []
segment = h
while len(trail) < length:
trail.append(segment.pos)
segment = segment.link
# Record these in visited to prevent infinite searches.
visited.add(tuple(trail))
# The tail of the snake moves first, so remove the last element.
del trail[-1]
trail, snake = tuple(trail), set(trail)
# Consider all adjacent cells not blocked by an obstacle or the
# snake.
dist += 1
for next_pos in self.adjacent(h.pos):
if next_pos not in snake and next_pos not in self.obstacles:
# Prevent infinite searches.
if (next_pos,) + trail in visited:
continue
# Push the next node.
ix += 1
next_h = Link(next_pos, h)
next_node = Node(heuristic(next_pos) + dist, dist, ix, next_h)
heapq.heappush(pending, next_node)
return ''
def get_moves(self, h, length):
"""Return the moves necessary to replicate history, as a string."""
moves = []
delta1 = Vec2(h.pos.x - h.link.pos.x, h.pos.y - h.link.pos.y)
while h.link.link is not None:
h = h.link
delta2 = Vec2(h.pos.x - h.link.pos.x, h.pos.y - h.link.pos.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):
"""
Return True if the snake can escape to a distant cell given recent history.
"""
length, head = self.length + 1, history.pos
def heuristic(pos):
"""A heuristic for fleeing from a location (the initial head)."""
return max(0, length - (abs(head.x - pos.x) + abs(head.y - pos.y)))
def moved_length(current):
"""A completion predicate for moving length cells."""
return current.dist >= length
escape = self._hunt(heuristic, moved_length, history, True)
return True if escape else False
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()
Aug. 26, 2013
Comments:
