Ståle’s weblog

Euler problem 15 is a bit more complex than the earlier problems I have tackled. The problem is as follows:

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

So, here we are dealing with finding routes through a simple maze. We could brute force this by just exhausting all options in a recursive program, however, this would quickly evolve to take a lot of time. Instead we need to look at how we reach the final number of options, which for 2×2 is 6. The easiest way is to see if we can figure out how to solve it for the next size maze, 3×3, easily. As this would also be possible to verify manually.

We can also solve for a 1×1 maze quickly, which we arrive at 2 possible solutions. Starting from 1×1 we can learn a bit about how 6 for 2×2 is found. If we look at the maze, we know that there is 6 routes ending at the last point. If we look at the previous intersections, one above and one to the left, we see that there are 3 paths to each off those points, going to the final point. So, there are 2 intersections before the end, each with 3 paths, so the final point then of course has 6 entry points.

Now, how can we calculate that there are 3 points to the penultimate intersections. Well, we know from the 1×1 solutions that there is only 2 possible paths to the center. Also, since we can’t backtrack, there is only 1 possible path to each corner. So the 2 entries to each penultimate intersection have 1 and 2 paths, total of 3.

So, we can define the function f(x,y), which is the number of paths to point x,y as f(x-1,y)+f(x,y-1). If x or y is 0, then the result is always 1, as all edge points only have 1 possible path leading to them. The scala code for this function is as follows:

1

def f(x:Int, y:Int):BigInt = if (x==0 || y==0) 1 else f(x-1,y)+f(x,y-1)

However, when x and y gets bigger, the number of recursions skyrocket, and the program is all too slow. Also, it calculates a lot of numbers we don’t need. We can solve this by creating a 20×20 lookup cache. But, if we look at the numbers along the edges, we can see a pattern emerging:

1
2
3
4
5

0 to 1 map {f(1,_)} // RangeM(1, 2)
0 to 2 map {f(2,_)} // RangeM(1, 3, 6)
0 to 3 map {f(3,_)} // RangeM(1, 4, 10, 20)
0 to 4 map {f(4,_)} // RangeM(1, 5, 15, 35, 70)
0 to 5 map {f(5,_)} // RangeM(1, 6, 21, 56, 126, 252)

For each off these lists, the last number is equal to the penultimate number * 2, as we have seen earlier. We can see here a function f2(x) = 0 to x map {f(x,_)}. We can optimize this function by working with f2(x-1). So f2(x)[n] is the same as f2(x)[n-1] + f2(x-1)[n]. Since we need to calculate each number in the array based on earlier values, the best solution here is to use an array to store values as we calculate them. Index 0 will always be 1, and the last index will always be the double of the second to last index:

1
2
3
4
5
6
7
8
9
10
11
12

def f2(n:Int):List[BigInt] = {
    if (n<2) {
        return 0 to n map {f(n,_)} toList
    } else {
        val prev = f2(n-1)
        val res = new Array[BigInt](n+1)        
        res(0) = 1
        for (i <- 1 until prev.size) res(i) = prev(i)+res(i-1)
        res(n) = res(n-1)*2
        return res toList
    }
}

This method is very fast for the values we are using here. We can also define a simple replacement now to calculate the number of paths in an arbitrarily shaped grid:

1

def euler15(x:Int,y:Int) = f2(x max y)(x min y)

We need the first value to be the max off the 2 to avoid list out of bound exceptions.

Thats it for this time. No complete program as I did all off this through the scala console. This solution is using my limited math knowledge and programming skills though. There are mathematics that will allow you to solve this pretty easily, which I found after preparing this post.

Staale Uncategorized