CodeFights: Snake Game

Question

Description

Your task is to imitate a turn-based variation of the popular "Snake" game.

You are given the initial configuration of the board and a list of commands which the snake follows one-by-one. The game ends if one of the following happens:

• the snake tries to eat its tail
• the snake tries to move out of the board
• it executes all the given commands.

Output the board configuration after the game ends. With the snake replaced by 'X' if the game ends abnormally.

Examples

input:
snakeGame([['.', '.', '.', '.'],
 ['.', '.', '<', '*'],
 ['.', '.', '.', '*']],
 "FFFFFRFFRRLLF")
output:
 [['.', '.', '.', '.'],
 ['X', 'X', 'X', '.'],
 ['.', '.', '.', '.']]

---

input:
snakeGame([['.', '.', '^', '.', '.'],
 ['.', '.', '*', '*', '.'],
 ['.', '.', '.', '*', '*']],
 "RFRF")
output:
 [['.', '.', 'X', 'X', '.'],
 ['.', '.', 'X', 'X', '.'],
 ['.', '.', '.', 'X', '.']]

---

input:
snakeGame([['.', '.', '*', '>', '.'],
 ['.', '*', '*', '.', '.'],
 ['.', '.', '.', '.', '.']],
 "FRFFRFFRFLFF")
output:
 [['.', '.', '.', '.', '.'],
 ['<', '*', '*', '.', '.'],
 ['.', '.', '*', '.', '.']]

---

Code

def snakeGame(gameBoard, commands):
 heads = {'v': (1, 0), '^': (-1, 0), '<': (0, -1), '>': (0, 1)}
 new_direc = {'v': {'L': '>', 'R': '<'}, 
 '^': {'L': '<', 'R': '>'}, 
 '<': {'L': 'v', 'R': '^'}, 
 '>': {'L': '^', 'R': 'v'}}
 
 def find_snake():
 def get_next(x, y):
 for key, direc in heads.items():
 new_x, new_y = x + direc[0], y + direc[1]
 if new_x in range(len(gameBoard)) and new_y in range(len(gameBoard[0])):
 if (new_x, new_y) not in snake:
 if gameBoard[new_x][new_y] == '*':
 return (new_x, new_y)
 # Get the head and the next body opposite of snake's direction
 snake = []
 for i, row in enumerate(gameBoard):
 for head in heads:
 if head in row:
 snake.append((i, row.index(head)))
 snake.append((snake[0][0] + heads[head][0] * -1, snake[0][1] + heads[head][1] * -1))
 
 # Append the rest of the body
 while True:
 n = get_next(snake[-1][0], snake[-1][1]) 
 if n is None:
 break
 snake.append(n)
 
 return snake
 
 def move_snake(snake):
 head = gameBoard[snake[0][0]][snake[0][1]]
 new_x, new_y = snake[0][0] + heads[head][0], snake[0][1] + heads[head][1]
 new_snake = []
 if new_x in range(len(gameBoard)) and new_y in range(len(gameBoard[0])) and (new_x, new_y) not in snake:
 new_snake.append((new_x, new_y))
 
 for pos in snake[:-1]:
 new_snake.append(pos)
 
 return new_snake
 
 # Find starting snake
 snake = find_snake()
 
 for command in commands: 
 if command in "LR":
 # Change the head
 gameBoard[snake[0][0]][snake[0][1]] = new_direc[gameBoard[snake[0][0]][snake[0][1]]][command]
 else:
 temp = move_snake(snake)
 
 # if not valid move return dead snake
 if temp is None:
 for pos in snake:
 x, y = pos
 gameBoard[x][y] = 'X'
 return gameBoard
 
 # else move snake
 for a, b in zip(snake, temp):
 gameBoard[b[0]][b[1]] = gameBoard[a[0]][a[1]]
 
 gameBoard[snake[-1][0]][snake[-1][1]] = '.'
 snake = temp
 
 return gameBoard

Answer 1

Your code seems to work and is split into small functions. Here are a few things to make it easier to understand.

Try to avoid nested functions

Nested functions can be really useful but in your case, it makes the code hard to understand because it is nested on many levels.

Also, because some parameters are not explicitly provided but somehow used as part of the functions context, it is hard to tell what is used/not used, input/output, updated/unchanged.

This is fairly easy to change to make the code more linear with the different functions defined one after the other (in order to do so, you need to add parameters in the function signatures and in the function calls). Also, you could take this chance to extract a few constant (and name them in UPPERCASE):

EMPTY = '.'
BODY = '*'
DEAD = 'X'
HEADS = {'v': (1, 0), '^': (-1, 0), '<': (0, -1), '>': (0, 1)}
def get_next(x, y, snake, gameBoard):
 for key, direc in HEADS.items():
 new_x, new_y = x + direc[0], y + direc[1]
 if new_x in range(len(gameBoard)) and new_y in range(len(gameBoard[0])):
 if (new_x, new_y) not in snake:
 if gameBoard[new_x][new_y] == BODY:
 return (new_x, new_y)
def find_snake(gameBoard):
 # Get the head and the next body opposite of snake's direction
 snake = []
 for i, row in enumerate(gameBoard):
 for head in HEADS:
 if head in row:
 snake.append((i, row.index(head)))
 snake.append((snake[0][0] + HEADS[head][0] * -1, snake[0][1] + HEADS[head][1] * -1))
 # Append the rest of the body
 while True:
 n = get_next(snake[-1][0], snake[-1][1], snake, gameBoard)
 if n is None:
 break
 snake.append(n)
 return snake
def move_snake(snake, gameBoard):
 head = gameBoard[snake[0][0]][snake[0][1]]
 new_x, new_y = snake[0][0] + HEADS[head][0], snake[0][1] + HEADS[head][1]
 new_snake = []
 if new_x in range(len(gameBoard)) and new_y in range(len(gameBoard[0])) and (new_x, new_y) not in snake:
 new_snake.append((new_x, new_y))
 for pos in snake[:-1]:
 new_snake.append(pos)
 return new_snake
def snakeGame(gameBoard, commands):
 new_direc = {'v': {'L': '>', 'R': '<'}, 
 '^': {'L': '<', 'R': '>'}, 
 '<': {'L': 'v', 'R': '^'}, 
 '>': {'L': '^', 'R': 'v'}}
 # Find starting snake
 snake = find_snake(gameBoard)
 for command in commands: 
 if command in "LR":
 # Change the head
 gameBoard[snake[0][0]][snake[0][1]] = new_direc[gameBoard[snake[0][0]][snake[0][1]]][command]
 else:
 temp = move_snake(snake, gameBoard)
 # if not valid move return dead snake
 if temp is None:
 for pos in snake:
 x, y = pos
 gameBoard[x][y] = DEAD 
 return gameBoard
 # else move snake
 for a, b in zip(snake, temp):
 gameBoard[b[0]][b[1]] = gameBoard[a[0]][a[1]]
 gameBoard[snake[-1][0]][snake[-1][1]] = EMPTY 
 snake = temp
 return gameBoard
def test_snake(gameBoard, commands, expected):
 out = snakeGame(gameBoard, commands)
 if out != expected:
 print(out, commands, expected)
test_snake([['.', '.', '.', '.'],
 ['.', '.', '<', '*'],
 ['.', '.', '.', '*']],
 "FFFFFRFFRRLLF",
 [['.', '.', '.', '.'],
 ['X', 'X', 'X', '.'],
 ['.', '.', '.', '.']])
test_snake([['.', '.', '^', '.', '.'],
 ['.', '.', '*', '*', '.'],
 ['.', '.', '.', '*', '*']],
 "RFRF",
 [['.', '.', 'X', 'X', '.'],
 ['.', '.', 'X', 'X', '.'],
 ['.', '.', '.', 'X', '.']])
test_snake([['.', '.', '*', '>', '.'],
 ['.', '*', '*', '.', '.'],
 ['.', '.', '.', '.', '.']],
 "FRFFRFFRFLFF",
 [['.', '.', '.', '.', '.'],
 ['<', '*', '*', '.', '.'],
 ['.', '.', '*', '.', '.']])

Getting rid of indices (almost) everywhere

In your code, element access (foo[i]) is used everywhere:

• to get/set a particular cell of the grid
• to get the x (or y) part of coordinates
• the get the direction from a particular "head" characters

It may make things confusing but you can use a few techniques to get rid of it:

• When you iterate over a dictionnary, you can choose if you are interested in keys, values or both. Then you don't need to get my_dict[my_key].
• You can use iterator unpacking when you know the number of elements in it. This is very convenient when you handle coordinates: x, y = my_coor. Also, this can be used in the for syntax: for head, (dx, dy) in HEADS.items().

• Instead of using list access to get the element you've just added to the (empty) list, you can use temporary variables:

   snake.append((i, row.index(head)))
   snake.append((snake[0][0] + heads[head][0] * -1, snake[0][1]
  

becomes

 beginx, beginy = i, row.index(head)
 snake.append((beginx, beginy))
 snake.append((beginx - dx, beginy - dy))

It "costs" an additional line but it makes things clearer to me. (Also I took this chance to replace a + b * -1 by a - b).

Combining all these techniques, you'd get something like:

EMPTY = '.'
BODY = '*'
DEAD = 'X'
HEADS = {'v': (1, 0), '^': (-1, 0), '<': (0, -1), '>': (0, 1)}
def get_next(x, y, snake, gameBoard):
 for (dx, dy) in HEADS.values():
 new_x, new_y = x + dx, y + dy
 if new_x in range(len(gameBoard)) and \
 new_y in range(len(gameBoard[0])) and \
 (new_x, new_y) not in snake and \
 gameBoard[new_x][new_y] == BODY:
 return (new_x, new_y)
def find_snake(gameBoard):
 # Get the head and the next body opposite of snake's direction
 snake = []
 for i, row in enumerate(gameBoard):
 for head, (dx, dy) in HEADS.items():
 if head in row:
 beginx, beginy = i, row.index(head)
 snake.append((beginx, beginy))
 snake.append((beginx - dx, beginy - dy))
 # Append the rest of the body
 while True:
 n = get_next(snake[-1][0], snake[-1][1], snake, gameBoard)
 if n is None:
 break
 snake.append(n)
 return snake
def move_snake(snake, gameBoard):
 headx, heady = snake[0]
 head = gameBoard[headx][heady]
 dx, dy = HEADS[head]
 new_x, new_y = headx + dx, heady + dy
 new_coord = new_x, new_y
 new_snake = []
 if new_x in range(len(gameBoard)) and \
 new_y in range(len(gameBoard[0])) and \
 new_coord not in snake:
 new_snake.append(new_coord)
 for pos in snake[:-1]:
 new_snake.append(pos)
 return new_snake
def snakeGame(gameBoard, commands):
 new_direc = {'v': {'L': '>', 'R': '<'}, 
 '^': {'L': '<', 'R': '>'}, 
 '<': {'L': 'v', 'R': '^'}, 
 '>': {'L': '^', 'R': 'v'}}
 # Find starting snake
 snake = find_snake(gameBoard)
 for command in commands: 
 if command in "LR":
 # Change the head
 headx, heady = snake[0]
 gameBoard[headx][heady] = new_direc[gameBoard[headx][heady]][command]
 else:
 temp = move_snake(snake, gameBoard)
 # if not valid move return dead snake
 if temp is None:
 for (x, y) in snake:
 gameBoard[x][y] = DEAD 
 return gameBoard
 # else move snake
 for a, b in zip(snake, temp):
 gameBoard[b[0]][b[1]] = gameBoard[a[0]][a[1]]
 tailx, taily = snake[-1]
 gameBoard[tailx][taily] = EMPTY 
 snake = temp
 return gameBoard

Other code simplifications

Now that we provide the full snake to the get_next function, it doesn't really need to x and y values.

def get_next(snake, gameBoard):
 x, y = snake[-1]
 ....

In the move_snake function, you write a loop to add elements from snake[:-1]. You could use a simple + operation on lists.

Also, it is clearer to add return None at the end of a function whose return value is used. This is one of the latest addition to PEP 8:

Be consistent in return statements. Either all return statements in a function should return an expression, or none of them should. If any return statement returns an expression, any return statements where no value is returned should explicitly state this as return None, and an explicit return statement should be present at the end of the function (if reachable).

Then, the whole function becomes:

def move_snake(snake, gameBoard):
 headx, heady = snake[0]
 head = gameBoard[headx][heady]
 dx, dy = HEADS[head]
 new_x, new_y = headx + dx, heady + dy
 new_coord = new_x, new_y
 if new_x in range(len(gameBoard)) and \
 new_y in range(len(gameBoard[0])) and \
 new_coord not in snake:
 return [new_coord] + snake[:-1]
 return None

Other ideas

At the moment, we have the snakes represented in 2 ways : as a list of body parts (which makes sense given how convenient it is to make the snake go forward) and as a drawing on a grid (which makes sense because it is our input and our output).

Also, for every step forward, we need to update both representations. Maybe, it would make sense to keep the listy-snake (and other data you might need) during the computations of the different steps and only generate the output grid at the very end.

As an exercice, I've tried to do this. I went for an object approach to store the different data needed and interact easily with them. I've tried to keep as much as possible from your code:

EMPTY = '.'
BODY = '*'
DEAD = 'X'
HEADS = {'v': (1, 0), '^': (-1, 0), '<': (0, -1), '>': (0, 1)}
class Snake(object):
 # Heads and body parts are (x, y, char)
 def __init__(self, head, dimx, dimy):
 self.dimx = dimx
 self.dimy = dimy
 self.body = [head]
 self.alive = True
 def add_queue(self, body_part):
 self.body.append(body_part)
 def turn(self, direc):
 new_direc = {'v': {'L': '>', 'R': '<'}, 
 '^': {'L': '<', 'R': '>'}, 
 '<': {'L': 'v', 'R': '^'}, 
 '>': {'L': '^', 'R': 'v'}}
 x, y, head = self.body[0]
 new_head = new_direc[head][direc]
 self.body[0] = (x, y, new_head)
 def move_forward(self):
 x, y, char = self.body[0]
 dx, dy = HEADS[char]
 new_x, new_y = x + dx, y + dy
 if self.position_is_free(new_x, new_y): 
 self.body = [(new_x, new_y, char)] + [(x, y, BODY)] + self.body[1:-1]
 else:
 self.die()
 def position_is_free(self, x, y):
 return x in range(self.dimx) and \
 y in range(self.dimy) and \
 not any(x == x2 and y == y2 for (x2, y2, _) in self.body)
 def die(self):
 self.alive = False
 self.body = [(x, y, DEAD) for (x, y, _) in self.body] 
 def get_as_grid(self):
 g = [[EMPTY for i in range(self.dimy)] for j in range(self.dimx)]
 for x, y, c in self.body:
 g[x][y] = c
 return g
def find_head(gameBoard):
 for i, row in enumerate(gameBoard):
 for head, (dx, dy) in HEADS.items():
 if head in row:
 return Snake((i, row.index(head), head), len(gameBoard), len(gameBoard[0]))
def get_next(snake, gameBoard):
 x, y, _ = snake.body[-1]
 for (dx, dy) in HEADS.values():
 new_x, new_y = x + dx, y + dy
 if snake.position_is_free(new_x, new_y) and \
 gameBoard[new_x][new_y] == BODY:
 return (new_x, new_y, BODY)
def find_snake(gameBoard):
 # Get the head
 s = find_head(gameBoard)
 # Append the rest of the body
 while True:
 n = get_next(s, gameBoard)
 if n is None:
 break
 s.add_queue(n)
 return s
def snakeGame(gameBoard, commands):
 # Find snake
 s = find_snake(gameBoard)
 for command in commands:
 if command in "LR":
 # Change the head
 s.turn(command)
 else:
 s.move_forward()
 if not s.alive:
 break 
 return s.get_as_grid()

Something I had forgotten

if new_x in range(len(gameBoard)) can be rewritten if 0 <= new_x < len(gameBoard).

On Python2, this is much faster (because a list is generated and then we perform a linear search on it). On Python3, the performance impact may not be so big.

• Ludisposed: I think your last point is off. Since Python 3.x, range is a special object that is lazily evaluated, that makes x in range(y) faster