<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/euler-problem-18-67-maximum-path-sums/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/euler-problem-18-67-maximum-path-sum/"> The Devil is in the Data</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div class="wp-caption"><a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Pedigree_chart"><img alt="A pedigree is an example of a binary tree: Euler Problem 18" src="https://i2.wp.com/upload.wikimedia.org/wikipedia/commons/2/26/Waldburg_Ahnentafel.jpg?resize=303%2C233&ssl=1" data-recalc-dims="1"></a>
<p class="wp-caption-text">An example of a pedigree. Source: Wikimedia.</p>
</div>
<p>Euler Problem 18 and 67 are exactly the same besides that the data set in the second version is larger than in the first one. In this post, I kill two Eulers with one code.</p>
<p>These problems deal with <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Binary_tree">binary trees</a>, which is a data structure where each node has two children. A practical example of a binary tree is a <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Pedigree_chart">pedigree chart</a>, where each person or animal has two parents, four grandparents and so on.</p>
<h2>Euler Problem 18 Definition</h2>
<p>By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.</p>
<p><span>3</span><br>
<span>7</span> 4<br>
2 <span>4</span> 6<br>
8 5 <span>9</span> 3</p>
<p>That is, 3 + 7 + 4 + 9 = 23. <a target="_blank" rel="nofollow" href="https://projecteuler.net/problem=18">Find the maximum total from top to bottom of the triangle below</a>:</p>
<p>75<br>
95 64<br>
17 47 82<br>
18 35 87 10<br>
20 04 82 47 65<br>
19 01 23 75 03 34<br>
88 02 77 73 07 63 67<br>
99 65 04 28 06 16 70 92<br>
41 41 26 56 83 40 80 70 33<br>
41 48 72 33 47 32 37 16 94 29<br>
53 71 44 65 25 43 91 52 97 51 14<br>
70 11 33 28 77 73 17 78 39 68 17 57<br>
91 71 52 38 17 14 91 43 58 50 27 29 48<br>
63 66 04 68 89 53 67 30 73 16 69 87 40 31<br>
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23</p>
<p>As there are only 16,384 routes, it is possible to solve this problem by trying every route. However, <a target="_blank" rel="nofollow" href="https://projecteuler.net/problem=67">Problem 67</a>, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)</p>
<h2>Solution</h2>
<p>This problem seeks a <a target="_blank" rel="nofollow" href="http://www.geeksforgeeks.org/find-maximum-path-sum-in-a-binary-tree/">maximum path sum in a binary tree.</a> The brute force method, as indicated in the problem definition, is a very inefficient way to solve this problem. The video visualises the quest for the maximum path, which takes eleven minutes of hypnotic animation.</p>
<p><iframe width="450" allowfullscreen="true" src="https://www.youtube.com/embed/z-AOWBztnpI?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>A more efficient method is to define the maximum path layer by layer, starting at the bottom. The maximum sum of 2+8 or 2+5 is 10, the maximum sum of 4+5 or 4+9 is 13 and the last maximum sum is 15. These numbers are now placed in the next row. This process cycles until only one number is left. This algorithm solves the sample triangle in four steps:</p>
<p>Step 1:</p>
<p>3<br>
7 4<br>
2 4 6<br>
8 5 9 3</p>
<p>Step 2:</p>
<p>3<br>
7 4<br>
10 13 15</p>
<p>Step 3:</p>
<p>3<br>
20 19</p>
<p>Step 4:</p>
<p>23</p>
<p>In the code below, the data is triangle matrix. The variables <em>rij</em> (row) and <em>kol</em> (column) drive the search for the maximum path. The triangle for Euler Problem 18 is manually created and the triangle for Euler Problem 67 is read from the website.</p>
<pre>
path.sum &lt;- function(triangle) {
    for (rij in nrow(triangle):2) {
        for (kol in 1:(ncol(triangle)-1)) {
            triangle[rij - 1,kol] &lt;- max(triangle[rij,kol:(kol + 1)]) + triangle[rij - 1, kol]
        }
        triangle[rij,] &lt;- NA
    }
    return(max(triangle, na.rm = TRUE))
}

# Euler Problem 18
triangle &lt;- matrix(ncol = 15, nrow = 15)
triangle[1,1] &lt;- 75
triangle[2,1:2] &lt;- c(95, 64)
triangle[3,1:3] &lt;- c(17, 47, 82)
triangle[4,1:4] &lt;- c(18, 35, 87, 10)
triangle[5,1:5] &lt;- c(20, 04, 82, 47, 65)
triangle[6,1:6] &lt;- c(19, 01, 23, 75, 03, 34)
triangle[7,1:7] &lt;- c(88, 02, 77, 73, 07, 63, 67)
triangle[8,1:8] &lt;- c(99, 65, 04, 28, 06, 16, 70, 92)
triangle[9,1:9] &lt;- c(41, 41, 26, 56, 83, 40, 80, 70, 33)
triangle[10,1:10] &lt;- c(41, 48, 72, 33, 47, 32, 37, 16, 94, 29)
triangle[11,1:11] &lt;- c(53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14)
triangle[12,1:12] &lt;- c(70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57)
triangle[13,1:13] &lt;- c(91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48)
triangle[14,1:14] &lt;- c(63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31)
triangle[15,1:15] &lt;- c(04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23)

answer &lt;- path.sum(triangle)
print(answer)
</pre>
<h2>Euler Problem 67</h2>
<p>The solution for problem number 67 is exactly the same. The data is read directly from the Project Euler website.</p>
<pre>
# Euler Problem 67
triangle.file &lt;- read.delim(&quot;https://projecteuler.net/project/resources/p067_triangle.txt&quot;, stringsAsFactors = F, header = F)
triangle.67 &lt;- matrix(nrow = 100, ncol = 100)
for (i in 1:100) {
    triangle.67[i,1:i] &lt;- as.numeric(unlist(strsplit(triangle.file[i,], &quot; &quot;)))
}
answer &lt;- path.sum(triangle.67)
print(answer)
</pre>
<p>The post <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-18-67-maximum-path-sum/">Euler Problem 18 &amp; 67: Maximum Path Sums</a> appeared first on <a target="_blank" rel="nofollow" href="http://r.prevos.net/">The Devil is in the Data</a>.</p>
<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://r.prevos.net/euler-problem-18-67-maximum-path-sum/"> The Devil is in the Data</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/VE3jFgDrQNY"></a></div>