Project Euler/15: Difference between revisions

From charlesreid1

(Created page with "Project Euler problem 15 gives a square lattice, 20 x 20, and shows a shortest path through the lattice - one that follows the edges of the lattice. The question, then, is how...")
 
No edit summary
Line 1: Line 1:
Project Euler problem 15 gives a square lattice, 20 x 20, and shows a shortest path through the lattice - one that follows the edges of the lattice. The question, then, is how many variations on this shortest path are possible?
Problem 15 link: https://projecteuler.net/problem=15


I solved this question using Wolfram Alpha - as with many combinatorics problems, it turns out you don't need to generate all of the variations, you can write a closed-form expression for the number of combinations instead.
Project Euler problem 15 gives a square lattice, 20 x 20, and asks for the number of shortest paths through the lattice. The shortest paths are illustrated for a 4x4 grid.


To derive the expression, we can think about the shortest path in a step-by-step fashion. We know that, ultimately, we are constrained to 20 down steps and 20 right steps.  
I solved this question using Wolfram Alpha - as with many combinatorics problems, it turns out you don't need to generate all of the variations, you can write a closed-form expression for the number of combinations instead. We use the fact that any shortest path must be constrained to taking 20 down steps and 20 right steps.


If we examine the starting position, and how we are going to move, we know we have to take one right step in the first column. Once we do that, we will be on the second line of the lattice, and we will have 19 right-steps left. And so on.
==A Smaller Example==


But we can take as many down steps as we would like at each point - in fact, we could use up all 20 of our down steps before we ever take one step right. Or, we could use them all up right after we take one step right. Or we could use them all up after we take 20 steps to the right.
Let's look at a small example of an 8x8 square grid, giving us a 9x9 lattice of points. Here, we know that the shortest path will take exactly 9 right steps and 9 down steps, the only question is the order in which they happen.
 
We can distribute how and where we take our 20 down steps, with respect to our right steps. For example, we might take all 20 down steps with a single right step, as shown in the three scenarios below:


{|
{|
Line 14: Line 16:
|[[Image:Euler15_Lattice2.png|200px]]
|[[Image:Euler15_Lattice2.png|200px]]
|[[Image:Euler15_Lattice3.png|200px]]
|[[Image:Euler15_Lattice3.png|200px]]
|}
(There are 20 total such diagrams.)
If we take all 20 down steps with a single right step, there are 9 (or W, where W is the width of our lattice) different places where all 20 down steps can be taken.
Now suppose that instead of taking all 20 down steps with a single right step, we only take 19 down steps at once. Now, we can take those 19 down steps anywhere we would like, except that we have to leave ourselves at least one lattice column to take the last step down:
{|
|-
|[[Image:Euler15_Lattice4.png|200px]]
|[[Image:Euler15_Lattice5.png|200px]]
|[[Image:Euler15_Lattice6.png|200px]]
|}
|}

Revision as of 02:46, 18 July 2017

Problem 15 link: https://projecteuler.net/problem=15

Project Euler problem 15 gives a square lattice, 20 x 20, and asks for the number of shortest paths through the lattice. The shortest paths are illustrated for a 4x4 grid.

I solved this question using Wolfram Alpha - as with many combinatorics problems, it turns out you don't need to generate all of the variations, you can write a closed-form expression for the number of combinations instead. We use the fact that any shortest path must be constrained to taking 20 down steps and 20 right steps.

A Smaller Example

Let's look at a small example of an 8x8 square grid, giving us a 9x9 lattice of points. Here, we know that the shortest path will take exactly 9 right steps and 9 down steps, the only question is the order in which they happen.

We can distribute how and where we take our 20 down steps, with respect to our right steps. For example, we might take all 20 down steps with a single right step, as shown in the three scenarios below:

File:Euler15 Lattice1.png File:Euler15 Lattice2.png Euler15 Lattice3.png

(There are 20 total such diagrams.)

If we take all 20 down steps with a single right step, there are 9 (or W, where W is the width of our lattice) different places where all 20 down steps can be taken.

Now suppose that instead of taking all 20 down steps with a single right step, we only take 19 down steps at once. Now, we can take those 19 down steps anywhere we would like, except that we have to leave ourselves at least one lattice column to take the last step down:

File:Euler15 Lattice4.png File:Euler15 Lattice5.png File:Euler15 Lattice6.png
Retrieved from "https://charlesreid1.com/w/index.php?title=Project_Euler/15&oldid=19707"