CodeFights: Snake Game Description

Your task is to imitate a turn-based variation of the popular &quot;Snake&quot; 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([['.', '.', '.', '.'],
           ['.', '.', '&lt;', '*'],
           ['.', '.', '.', '*']],
          &quot;FFFFFRFFRRLLF&quot;)

output:
          [['.', '.', '.', '.'],
           ['X', 'X', 'X', '.'],
           ['.', '.', '.', '.']]


input:
snakeGame([['.', '.', '^', '.', '.'],
           ['.', '.', '*', '*', '.'],
           ['.', '.', '.', '*', '*']],
          &quot;RFRF&quot;)

output:
          [['.', '.', 'X', 'X', '.'],
           ['.', '.', 'X', 'X', '.'],
           ['.', '.', '.', 'X', '.']]


input:
snakeGame([['.', '.', '*', '&gt;', '.'],
           ['.', '*', '*', '.', '.'],
           ['.', '.', '.', '.', '.']],
          &quot;FRFFRFFRFLFF&quot;)

output:
          [['.', '.', '.', '.', '.'],
           ['&lt;', '*', '*', '.', '.'],
           ['.', '.', '*', '.', '.']]


Code
def snakeGame(gameBoard, commands):
    heads = {'v': (1, 0), '^': (-1, 0), '&lt;': (0, -1), '&gt;': (0, 1)}
    new_direc = {'v': {'L': '&gt;', 'R': '&lt;'}, 
                 '^': {'L': '&lt;', 'R': '&gt;'},                 
                 '&lt;': {'L': 'v', 'R': '^'}, 
                 '&gt;': {'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 &quot;LR&quot;:
            # 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
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), '&lt;': (0, -1), '&gt;': (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': '&gt;', 'R': '&lt;'}, 
                 '^': {'L': '&lt;', 'R': '&gt;'},                 
                 '&lt;': {'L': 'v', 'R': '^'}, 
                 '&gt;': {'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([['.', '.', '.', '.'],
            ['.', '.', '&lt;', '*'],
            ['.', '.', '.', '*']],
           "FFFFFRFFRRLLF",
           [['.', '.', '.', '.'],
            ['X', 'X', 'X', '.'],
            ['.', '.', '.', '.']])
test_snake([['.', '.', '^', '.', '.'],
            ['.', '.', '*', '*', '.'],
            ['.', '.', '.', '*', '*']],
           "RFRF",
           [['.', '.', 'X', 'X', '.'],
            ['.', '.', 'X', 'X', '.'],
            ['.', '.', '.', 'X', '.']])
test_snake([['.', '.', '*', '&gt;', '.'],
            ['.', '*', '*', '.', '.'],
            ['.', '.', '.', '.', '.']],
           "FRFFRFFRFLFF",
           [['.', '.', '.', '.', '.'],
            ['&lt;', '*', '*', '.', '.'],
            ['.', '.', '*', '.', '.']])


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), '&lt;': (0, -1), '&gt;': (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': '&gt;', 'R': '&lt;'}, 
                 '^': {'L': '&lt;', 'R': '&gt;'},                 
                 '&lt;': {'L': 'v', 'R': '^'}, 
                 '&gt;': {'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), '&lt;': (0, -1), '&gt;': (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': '&gt;', 'R': '&lt;'}, 
                     '^': {'L': '&lt;', 'R': '&gt;'},                 
                     '&lt;': {'L': 'v', 'R': '^'}, 
                     '&gt;': {'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 &lt;= new_x &lt; 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.