Lattice Paths
I’m continuing to work through Euler project problems, and here is my most recent project:
The two by two square is easy to replicate, but a 20x20 square introduces a new set of challenges. In a previous problem, I worked to solve a problem like this, but the complexity level was much higher. I got stumped and decided to tone it down a notch to see if I could understand the basics more completely before moving on.
I took a few steps to reach my answer, here’s my path:
- I created a system for recording position. In the past I used numbers like 00 represented the top left and 22 represented the finish line. This time I used a list. [0, 0] represents the start and [2, 2] the finish. I randomly add a digit to each value (unless it is a 2). By recording each value along the way, I generated a list of lists that represent one possible path. I stored this in a function and I could generate a random path at will.
- From here I created an array of possible routes making sure not to add any duplicates by calling my generate_path() function inside of a while loop that checks for a high number of rejected routes. By scaling the rejection criteria, I was able to pinpoint the total number of paths.
This solution does not scale well, and I am still working on a solution where the total pathways do not depend on a random pathway generator. Creating a generator that does not produce duplicates in the first place is the root of this optimization problem. Perhaps each digit of a 40-digit number could store a choice as either right or down; 1 being right and 0 being down. How many different combinations of 1s and zeroes can you create in 40 digits (40 digits for 40 decisions along the lattice)?
The answer is 1,099,511,627,776 (2⁴⁰) which is not the solution to this problem. The catch is that once a decision reaches the edge of the lattice, decisions to go down are invalid. The same is true for decisions that move to the right too far. So the real question is, how many 40-digit binary numbers exist where the number of 0s and 1s are equal? Now the problem is simple. By incrementing from 0 to 1111111111111111111111111111111111111111 (that’s 2⁴⁰ in binary) I can evaluate if each number contains an equal number of 0s and 1s. If the answer is yes, then increase the count, otherwise continue.
This is the solution I landed on and it is very scalable. To generate the total number of paths in any size square grid, all that needs to be adjusted is the grid_width as an argument and the binary digits on line 18. That is always twice the grid width and with some interpolation work I could build that into this algorithm. So there you have it, a reason for binary! It is the simplest way to store a decision and it requires a lot less code than my previous answer.
Or so I thought. I did some digging and found that this problem is even simpler than that. I was thinking backwards the whole time. The question boils down to how many options does one have at each step away from the end-point. Consider a two-by-two square. From the position one square up and one square left of that end, there are exactly two routes to the end-point. Stepping up one size to a 3x3, the options increase to 6 routes. This sure sounds familiar…wait:
The top of the pyramid is the bottom-right corner of our problem. In a 2x2 square example, your starting point is 4 rows away from the top, because each potential path requires four decisions. Move either up or left from the end-point and there remains only one possible route back to the end. Make two moves away from the end and in two cases there is only one route back to the end-point. In one case, there are two routes back to the end. Below, I have illustrated what it looks like to move two spaces up and two spaces left away from the end-point. At each decision, the number of possible routes back to the bottom-left corner are shown on pascal’s triangle.
So to solve my problem, writing complex code was not the answer. Examining pascals triangle at the 41st layer was much more effective. Sometimes writing code simplifies a problem, but in this case I fell victim to the ‘if all you have is a hammer, then all of your problems begin to look like nails’ fallacy. Lesson learned, but I still had fun getting my head around binary numbers and how I could store decisions using ones and zeroes.
