General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 15 – Lattice Paths
My workflow:
Answer: 137846528820
Last Week's Favourite Solution:
There are join winners for last weeks favourite solution. Both @gawa and @PangHC identified different methods to reduce the number of records to compute the sequence for. This in turn reduced the required computation and therefore run time. Please find their solutions on page one of last week's post or click here.
Definitions:
- Lattice: The mathematical definition of a lattice can be confusing – “a partially ordered set in which every subset, consisting of two elements has a smallest upper bound and a greatest lower bound.”
But what this effectively means is a set of points in a regular / repetitive pattern. - Factorial: The product of all numbers less than and equal to the chosen number. I.e The factorial of 5 would be
5 x 4 x 3 x 2 x 1 = 120
This can also be written as 5! = 120
Mathematical Theory:
This week the focus is going to be on something called the Binomial (Choose) function. We will work together to create this formula, whilst examining each element in the context of this weeks problem.
First of all, why is the relevant? Well let’s consider a 2 by 2 grid. In order to get from the top of the grid to the bottom of the grid, I will need to make a total of 4 moves (two moves right, and two moves down). But importantly, the order of these moves does not matter. Lets consider the 4 potential moves (D = down, R = right, _ = currently unassigned):
_ _ _ _
Now lets decided upon the moves to the right. For one of the “R”s it could go in 4 potential positions.
1) R _ _ _ 2) _ R _ _ 3) _ _ R _ 4) _ _ _ R
But we still have another right hand move to make. For each of the examples above, there are 3 remaining spaces therefore 3 potential spots the final R could go in.
- R R _ _ R _ R _ R _ _ R
- R R _ _ _ R R _ _ R _ R
- R _ R _ _ R R _ _ _ R R
- R _ _ R _ R _ R _ _ R R
As we know there are 3 options, for each of the 4 initial moves, we can calculate the total options and equalling .
3 x 4 = 12
Now all the right hand moves have been placed, all the gaps can simply be filled with the down moves.
- R R D D R D R D R D D R
- R R D D D R R D D R D R
- R D R D D R R D D D R R
- R D D R D R D R D D R R
What about a 3 by 3 grid? In this case we would have to make a total of 6 moves, 3 down and 3 to the right. If we follow the same logical thinking as before, we can conclude that:
- Firstly, we have 6 spaces that the first “R” could go it
- For each of those 6 options, there a 5 potential spaces for the second “R”
- For the 3rd and final “R” there are 4 potential spaces per combination above.
That makes a total of:
6 x 5 x 4 = 120 possible options/ routes through the grid
This formula can actually be generalised. If the grid is k x k, we know we need to make 2k ( which we will call n) moves to get through the grid. Combining this with the above logic, we know that the number of paths through the grid is equal to:
n x (n – 1) x (n – 2) x …… x (k +1)
But this isn’t very nice to write out each time. To make things simpler lets multiply the above equation by 1. Remember, anything divided by itself = 1.
Lets take
If we multiply the original equaiton by this we get:
Interestingly, this can then be written as:
You may have spotted that the numerator of that fraction is now simply the product of every single number less than or equal to n. By definition, this is the factorial of n, so the equation can be written as:
We are nearly there. This formula will yield the values we looked at earlier (12 options for the 2x2 grid and 120 options for the 3x3 grid) but there is something we missed. If we look back at the 2 x 2 example, you will notice that there are quite a few sequences that appear more than once:
- R R D D R D R D R D D R
- R R D D D R R D D R D R
- R D R D D R R D D D R R
- R D D R D R D R D D R R
That is because we have assumed that the order of the rights matters. In reality, all the right hand moves (and downs) are equal, to mitigate this we need to adjust out equation.
For the 2 x 2 case there are 2 right hand moves, if we did care about the order, and tried to arrange 2 values, the number of possible options would be 2 x 1 = 2! = 2. As we do not care about the order when considering the path through the grid, we need to divide our previous answer, by this value to get 12/2 = 6 .
As for the 3 x 3 grid. If we did care about the order of 3 values, there would be 3 x 2 x 1 = 3! = 6 Possible ways to rearrange them. But as we do not care about the order in our problem, the answer is 120/6 = 20
The final step is to generalise this. You will notice that we have simply divided our answer by the factorial value of our dimension. k. This can be expressed as k! or as (n-k)! (as n = 2k). Adding this into our formula from before we get the following:
And that’s it. We now have a formula to calculate the number of paths through our grids! If you want to find out more, I would encourage you to look into this formula. Its actually a very well know formula often referred to as the binomial function or choose function.
Method:
1) Create an input in which the grid length is defined.
2) Implement the formula from earlier. As the grid is a 20 x 20, we need to move a total of 40 spaces to get out. Therefore n = 40 (which is 2 times the dimension)
If we choose the order of all 20 horizontal moves (k = 20) the 20 vertical moves will have to take the remaining spaces.
Hence the formula reads:
3) Submit your answer to the Project Euler Website!
Summary:
The formula itself is not immediately obvious however once you are aware of it, this problem becomes a simple substitution exercise, solvable in just one tool!
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
