Problem 5: Honeycomb Walk

https://open.kattis.com/problems/honey

Given a number$n$between 1 and 14, find the number of paths of length$n$on a hexagonal grid from the origin to itself.

Use a hexagonal coordinate system to keep track of the number of paths from each point to the origin:

example hexagonal coordinate system

Let's denote C[x][y][n] as the number of paths of length n from point $(x, y)$ to the origin.

Base cases:

• C[0][0][0] = 1

• C[x][y][0] = 0 for all $(x, y)$ not equal to $(0, 0)$

  • this means that from all other coordinates on the graph, there are 0 paths of length 0 to the origin

Now consider $n = 1$:

(each grid shows the number of paths of length 1 to the origin)

For $n = 2$ :

(each grid shows the number of paths of length 2 to the origin)

Notice the pattern: from any point $(x, y)$, the number of paths to the origin of length $n$ is the sum of number of paths of length $n - 1$ from its six neighboring points to the origin.

Recurrence relation:

C[x][y][n] = C[x-1][y-1][n-1] + C[x-1][y][n-1] + C[x][y-1][n-1] + C[x+1][y+1][n-1] + C[x+1][y][n-1] + C[x][y+1][n-1]

The solution we want is C[0][0][n]: the number of paths of length $n$ from the origin to itself.

Note that our largest given $n$ is 14, so the farthest points from the origin are $(±7, 0), (0, ±7), (±7, ±7)$. To account for array indexing, we use a matrix of size, say, 17 x 17 x 17. Put the origin at C[8][8].