<p>Euler Problem 15 analyses <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Taxicab_geometry">taxicab geometry</a>. This system replaces the usual distance function with the sum of the absolute differences of their Cartesian coordinates. In other words, the distance a taxi would travel in a grid plan. The fifteenth Euler problem asks to determine the number of <a target="_blank" rel="nofollow" href="http://www.intmath.com/blog/mathematics/taxicab-geometry-4941">possible routes a taxi can take</a> in a city of a certain size.</p>
<h2>Euler Problem 15 Definition</h2>
<p>Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. <a target="_blank" rel="nofollow" href="https://projecteuler.net/problem=15">How many possible routes are there through a 20×20 grid</a>?</p>
<p><img alt="Euler Problem 15: Lattice Paths" src="https://i0.wp.com/projecteuler.net/project/images/p015.gif?resize=208%2C151&ssl=1" data-recalc-dims="1"></p>
<h2>Solution</h2>
<p>The defined lattice is one larger than the number of squares. Along the edges of the matrix, only one pathway is possible: straight to the right or down. We can calculate the number of possible pathways for the remaining number by adding the number to the right and below the point.</p>
<p><img title="p_{i,j}=p_{i,j-1}+p_{{i+1},j} " alt="p_{i,j}=p_{i,j-1}+p_{{i+1},j} " class="latex" src="http://s0.wp.com/latex.php?latex=p_%7Bi%2Cj%7D%3Dp_%7Bi%2Cj-1%7D%2Bp_%7B%7Bi%2B1%7D%2Cj%7D+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p>For the two by two lattice the solution space is:</p>
<p>6  3  1<br>
3  2  1<br>
1  1  0</p>
<p>The total number of pathways from the upper left corner to the lower right corner is thus 6. This logic can now be applied to a grid of any arbitrary size using the following code.</p>
<p>The code defines the lattice and initiates the boundary conditions. The bottom row and the right column are filled with 1 as there is only one solution from these points. The code then calculates the pathways by working backwards through the matrix. The final solution is the number is the first cell.</p>
<pre>
# Define lattice
nLattice &lt;- 20
lattice = matrix(ncol=nLattice + 1, nrow=nLattice + 1)

# Boundary conditions
lattice[nLattice + 1,-(nLattice + 1)] &lt;- 1
lattice[-(nLattice + 1), nLattice + 1] &lt;- 1

# Calculate Pathways
for (i in nLattice:1) {
    for (j in nLattice:1) {
        lattice[i,j] &lt;- lattice[i+1, j] + lattice[i, j+1]
    }
}

answer &lt;- lattice[1,1]
</pre>
<h2>Taxicab Geometry</h2>
<p><iframe width="450" allowfullscreen="true" src="https://www.youtube.com/embed/Pll5MXk5AMA?version=3&rel=1&%23038;fs=1&%23038;autohide=2&%23038;showsearch=0&%23038;showinfo=1&%23038;iv_load_policy=1&%23038;wmode=transparent" type="text/html"></iframe></p>
<p>The post <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-15-lattice-paths/">Euler Problem 15: Pathways Through a Lattice</a> appeared first on <a target="_blank" rel="nofollow" href="http://r.prevos.net/">The Devil is in the Data</a>.</p>
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/Hk53rVh8kPk">