Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Snake Lite by Kurush
# migrated from python 2.7
from collections import deque
ACTION = ("L", "R", "F")
CHERRY = 'C'
TREE = 'T'
SNAKE_HEAD = '0'
SNAKE = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}
EMPTY = "."
OBSTACLES = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'T'}
def checkio(field_map):
search_queue = deque()
visited = [[False for j in range(10)] for i in range(10)]
path = ""
cherry = find_cherry(field_map)
search_queue.append([path, field_map]);
while True:
if not search_queue: break
path, field_map = search_queue.popleft()
snake = find_snake(field_map)
head = list(snake['0'])
second = list(snake['1'])
visited[head[0]][head[1]] = True
if head[0] == cherry[0] and head[1] == cherry[1]:
return path
snake_dir = (head[0] - second[0], head[1] - second[1])
possible_moves = [
[head[0] + snake_dir[0], head[1] + snake_dir[1], "F"],
[head[0] - snake_dir[1], head[1] + snake_dir[0], "L"],
[head[0] + snake_dir[1], head[1] - snake_dir[0], "R"]]
for new_head_h, new_head_w, direction in possible_moves:
if is_correct_cell(new_head_h, new_head_w) and visited[new_head_h][new_head_w] == False and field_map[new_head_h][new_head_w] not in OBSTACLES - {max(snake.keys())}:
new_field_map = [list(row) for row in field_map]
tail = snake[max(snake.keys())]
new_field_map[tail[0]][tail[1]] = EMPTY
for s_key in sorted(snake.keys())[:-1]:
s = snake[s_key]
new_field_map[s[0]][s[1]] = str(int(new_field_map[s[0]][s[1]]) + 1)
new_field_map[new_head_h][new_head_w] = '0'
search_queue.append([path + direction, new_field_map])
print("Path not found", field_map)
return 'F'
def is_correct_cell(i, j):
if i < 0 or i > 9: return False
if j < 0 or j > 9: return False
return True
def find_snake(field_map):
snake = {}
for i, row in enumerate(field_map):
for j, ch in enumerate(row):
if ch in SNAKE:
snake[ch] = (i, j)
return snake
def find_cherry(field_map):
for i, row in enumerate(field_map):
for j, ch in enumerate(row):
if ch == 'C':
return (i, j)
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
from random import randint
def find_new_head(snake, action):
head = snake[SNAKE_HEAD]
snake_dir = (head[0] - snake["1"][0], head[1] - snake["1"][1])
if action == 'F':
return head[0] + snake_dir[0], head[1] + snake_dir[1]
elif action == 'L':
return head[0] - snake_dir[1], head[1] + snake_dir[0]
elif action == 'R':
return head[0] + snake_dir[1], head[1] - snake_dir[0]
else:
raise ValueError("The action must be only L,R or F")
def pack_map(list_map):
return [''.join(row) for row in list_map]
def check_solution(func, field_map):
temp_map = [list(row) for row in field_map]
step_count = 250
while True:
route = func(field_map[:])
res_route = ""
for ch in route:
if step_count < 0:
print(("Too many steps (no more than 250)."), end=' ')
return False
if ch not in ACTION:
print("The route must contain only F,L,R symbols")
return False
res_route += ch
snake = find_snake(temp_map)
tail = snake[max(snake.keys())]
temp_map[tail[0]][tail[1]] = EMPTY
new_head = find_new_head(snake, ch)
for s_key in sorted(snake.keys())[:-1]:
s = snake[s_key]
temp_map[s[0]][s[1]] = str(int(temp_map[s[0]][s[1]]) + 1)
if (new_head[0] < 0 or new_head[0] >= len(temp_map) or
new_head[1] < 0 or new_head[1] >= len(temp_map[0])):
print("The snake crawl outside")
return False
elif temp_map[new_head[0]][new_head[1]] == 'T':
print("The snake struck at the tree")
return False
elif temp_map[new_head[0]][new_head[1]] in SNAKE:
print("The snake bit itself")
return False
if temp_map[new_head[0]][new_head[1]] == 'C':
temp_map[new_head[0]][new_head[1]] = SNAKE_HEAD
if max(snake.keys()) == '9':
return True
else:
temp_map[tail[0]][tail[1]] = str(int(max(snake.keys())) + 1)
cherry = (randint(1, len(temp_map) - 2),
randint(1, len(temp_map[0]) - 2))
while temp_map[cherry[0]][cherry[1]] != EMPTY:
cherry = (randint(1, len(temp_map) - 2),
randint(1, len(temp_map[0]) - 2))
temp_map[cherry[0]][cherry[1]] = CHERRY
step_count -= 1
else:
temp_map[new_head[0]][new_head[1]] = SNAKE_HEAD
step_count -= 1
field_map = pack_map(temp_map)
assert check_solution(checkio, [
".T.....T..",
".C........",
".....T....",
"..T....T..",
"..........",
".0...T....",
".1........",
".2.T...T..",
".3...T....",
".4........"]), "Basic map"
assert check_solution(checkio, [
"..T....T.C",
".......T..",
"...TTT....",
"..T....T..",
"..T...T...",
".0T..T....",
".1........",
".2.T..TT..",
".3..TT....",
".4........"]), "Extra map"
June 14, 2014