How many paths the snake in the Snake game can take?

I was given this challenge last week and I thought I would share my way of solving it with you all

Y'all know the famous game "Snake", so no need for an introduction now. The question is easy: given the position of the snake within a map of known size and the number of movements the snake can do, how many distinct paths can the snake follow without intersecting itself and without going out of the map's boundaries?

Maybe once you go over it the question is not as easy as it sounds, so let's illustrate it with an example.

Let's imagine we have a map that contains 4 rows and 3 columns, like the one below. And let's imagine that we have a snake whose body occupies the following cells: [(2,2),(3,2),(3,1),(3,0),(2,0),(1,0),(0,0)]. The figure on the left represents the empty map and the one on the right represents the one with the snake, where the numbers are the positions of each "piece" of the snake within the map.

Now, let's say that the snake can do up to one movement, this is, it could potentially go up, down, left or right. Being given that each of these movements would not make the snake intersect itself or move the snake out of the boundaries. Going over each of them:

Up: it does neither intersect its body nor leaves the map, therefore it's a valid move
Down: it would cause the head to intersect a part of the body, thus it's an invalid move
Left: it's all fine, another valid move
Right: it would cause the head of the snake to leave the map, hence it's an invalid move

This means that with just one move there are only two possible paths that the snake can follow, it can either go up or go left, which would leave the snake in these positions.

OK, for just one move it seems fairly easy to evaluate all possible options, what about two moves? how many possible paths could the snake follow? Now the problem starts to get more complex, as for each valid position in the previous step it is necessary to evaluate all 4 possible moves again. In this case it would go as follows:

Left branch:

Up: valid move
Down: invalid move (it would cause the head to intersect the body)
Left: invalid move
Right: invalid move (the snake would be out of boundaries)

Up branch:

Up: valid
Down: invalid
Left: valid
Right: invalid

So with two moves there would 3 possible paths that the snake could follow and the positions the snake would occupy on the map:

Left, Up
Up, Left
Up, Up

OK now you can see how it goes, what if we consider three moves instead of just 2, the result is that there are 7 possible paths that the snake can follow, these are the final positions it would have.

So, the snake in the initial position, for this map and for 3 movements has 7 possible paths it can follow. Now, let's imagine that we want to check the number of paths for any snake position and size, any map size, and any number of movements. I will show you how I tackled the problem.

Snake movements

The first thing to do is to create four functions, one for each possible movement, these functions must update the position of the snake. How to do this? My approach was to first calculate the new position of the head, so if the head has coordinates (i,j) being "i" the row number and "j" the column number if I went up I would have to subtract 1 to the "i" coordinate, i.e i-1, while the "j" coordinate remains untouched. Once the head of the snake has its own position calculated the position of the rest of the elements of the snake are cells of the previous snake in the prior index. Here my code snippets.

def up(snake):
    new_snake = []
    for i,j in enumerate(snake):
        if(i == 0):
            new_snake.append([j[0]-1,j[1]])
        else:
            new_snake.append(snake[i-1])
    return new_snake

def down(snake):
    new_snake = []
    for i,j in enumerate(snake):
        if(i == 0):
            new_snake.append([j[0]+1,j[1]])
        else:
            new_snake.append(snake[i-1])
    return new_snake

def left(snake):
    new_snake = []
    for i,j in enumerate(snake):
        if(i == 0):
            new_snake.append([j[0],j[1]-1])
        else:
            new_snake.append(snake[i-1])
    return new_snake

def right(snake):
    new_snake = []
    for i,j in enumerate(snake):
        if(i == 0):
            new_snake.append([j[0],j[1]+1])
        else:
            new_snake.append(snake[i-1])
    return new_snake

Check whether the snake is eating itself or it's out of boundaries

The next step is to create a function that has to check whether either the snakehead is going towards a part of its body, or whether it0s moving out of boundaries. This function should avoid the movements that we created before to be considered for the final calculation. The way I tackled this was like follows:

Out of boundaries: check if the coordinates (i,j) are larger than the size(i,j) of the map. If so happens False variables will be returned.

Intersecting its body: this one took me a lot of time to figure out, but what I went for finally was to check if any of the cells of the snake's body appeared twice. If so happened, a False variable will be returned

If None of this happens, a True variable would be returned.

This is how I implemented it

def check(snake_1, snake_2):
    if(snake_2[0][0] > (size[0]-1)):    
        return False
    elif (snake_2[0][1] > (size[1]-1)):     
        return False
    elif (snake_2[0][0] < 0):          
        return False
    elif (snake_2[0][1] < 0):           
        return False
    for i in snake_2:                  
        if (snake_2.count(i) > 1):
            return False
    else:                               
        return True

Compute the number of possible paths

Once all the functions are defined we need to compute the number of possible paths, this is how I went for it. I created a loop that would compute all the movements, but only if these movements comply with the "check" function the new positions would be stored in an array. Then it would evaluate these new positions in the array again, and it would keep doing for as many times as you want because all this snippet is put within a "while" block. At the end of the first loop I would add a counter, and this counter is just printed at the end.

v = [snake]
step = []
n = 0

while (n < depth):
    for i in v:
        for j in [up(i), down(i), left(i), right(i)]:
            if check(i, j):
                step.append(j)
    v = step
    step = []
    n = n + 1

Testing the thing

I was not only given the statement but 3 tests to check if the code was working or not. These are the ones I was given:

Test 1:

Board: [4,3]
Snake: [[2,2],[3,2],[3,1],[3,0],[2,0],[1,0],[0,,]]
Nº of movements: 3
Result: 7

Test 2:

Board: [2,3]
Snake: [[0,2],[0,1],[0,0],[1,0],[1,1],[1,2]]
Nº of movements: 10
Result: 1

Test 3:

Board: [10,10]
Snake: [[5,5],[5,4],[4,4],[4,5]]
Nº of movements: 4
Result: 81

This is it, I hope you liked it and I hope to do something related to Deep Neural Networks soon. A link to my Google Drive where you can find the full script. (https://drive.google.com/drive/folders/1tVbUa41hEDikTDzYK9zyiivZ70IVCD0H?usp=sharing)

Achefe

Search This Blog