tag:blogger.com,1999:blog-7577421612120825312.post8724792605994506792..comments2015-07-20T12:08:19.498+01:00Comments on Functional Fun: Project Euler Problems 18 and 67: Finding the Maximal Route through a TriangleUnknownnoreply@blogger.comBlogger24125tag:blogger.com,1999:blog-7577421612120825312.post-22909822818680155772014-06-12T09:53:48.351+01:002014-06-12T09:53:48.351+01:00This solution is a brute-force, but it would take ...This solution is a brute-force, but it would take a long time or a massive processing power .. since the problem size is 2^99khaled khunaifernoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-71183917826713620622012-06-26T22:05:39.739+01:002012-06-26T22:05:39.739+01:00I knew this problem could be solved from the top d...I knew this problem could be solved from the top down but could not come up with solution. Very good explanation.paulius_lhttps://profiles.google.com/112515241373609584746noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-40749790109947144082012-01-18T03:18:03.253+00:002012-01-18T03:18:03.253+00:00I know you've had this already but thanks agai...I know you've had this already but thanks again for this help. I just couldn't get the right start to this problem (I'm only doing 18) and this was great.<br />I'll write my own code rather than use yours as I only have a basic knowledge but this method will help a lotMatthew Welsonnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-75520252701140888572011-06-27T21:14:37.848+01:002011-06-27T21:14:37.848+01:00This has a nice short and clear formulation in Has...This has a nice short and clear formulation in Haskell - the bottom up solution:<br /><br />eu_18_67 tri = head $ foldr1 (\xs ys-> zipWith (+) xs (zipWith max ys (tail ys))) tri<br /><br />Cheers,WillNessnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-72840505980744479782011-06-26T11:05:20.937+01:002011-06-26T11:05:20.937+01:00Excellent algorithm, which is easy to implement in...Excellent algorithm, which is easy to implement in other languages.Máté Kovács-Deáknoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-45904262778475367292011-01-26T15:52:33.279+00:002011-01-26T15:52:33.279+00:00Hi there,
Thank you for your excellent linq tutor...Hi there,<br /><br />Thank you for your excellent linq tutorials!<br /><br />I noticed that the output of your code is the same when removing line 46. Is that line there for a specific reason?kneethttps://www.blogger.com/profile/06339956650067846186noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-11454010413949113712010-08-26T02:13:16.283+01:002010-08-26T02:13:16.283+01:00Just for yucks, here is an F# equivalent.
let an...Just for yucks, here is an F# equivalent.<br /><br /><br />let answer = <br /> System.IO.File.ReadLines(".\\triangle.txt")<br /> |> Seq.map(fun x -> x.Split(' ') |> Seq.map(fun y -> System.Int32.Parse(y)))<br /> |> Seq.fold(fun acc x -> <br /> let rowLen = Seq.length x<br /> x |> Seq.mapi(fun i y -> <br /> let current = fun () -> y+(Seq.nth i acc)<br /> let previous = fun () -> y+(Seq.nth (i-1) acc)<br /> if i=0 then current()<br /> elif i=rowLen-1 then previous()<br /> else System.Math.Max(current() , previous())<br /> )<br /> |> Seq.toList<br /> ) [0;]<br /> |> List.maxAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-84031373222248616392010-02-26T15:14:19.998+00:002010-02-26T15:14:19.998+00:00wouldn't it be simpler to do essentially the s...wouldn't it be simpler to do essentially the same as you did, but to start at the bottom and work ones way up the pyramid.<br /><br />E.g. represent the data as<br /><br />List numbers = new List>()<br />{<br />{15},<br />{23,1},<br />{56,33,5},<br />{5,11,9,33}<br />};<br /><br />and then just do:<br /><br />for (int i = numbers.Count-2; i >= 0; i--)<br /> {<br /> for (int j = 0; j < numbers[i].Count; j++)<br /> {<br /> numbers[i][j] += Math.Max(numbers[i + 1][j], numbers[i + 1][j + 1]);<br /> }<br /> }<br /><br />once your done, numbers[0][0] holds the result.<br /><br />works quite fast for me.<br /><br />cheersMagicdeadhttps://www.blogger.com/profile/12497743683159239659noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-91754614692626735532009-11-07T06:37:31.194+00:002009-11-07T06:37:31.194+00:005stars5starsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-47684824275689946652009-10-04T14:45:37.583+01:002009-10-04T14:45:37.583+01:00I'm trying to solve this problem using an easy...I'm trying to solve this problem using an easy Dijktra's algorithm. Am I wrong or should it be easier this way?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-76703268834922072702009-05-13T17:12:00.000+01:002009-05-13T17:12:00.000+01:00Peter,
Glad you liked it. Thanks for reading!
S...Peter,<br /> Glad you liked it. Thanks for reading!<br /><br />SamSamhttps://www.blogger.com/profile/01345100698738870730noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-33985112145155820322009-05-13T14:40:00.000+01:002009-05-13T14:40:00.000+01:00But yes, the other comments are right about the pr...But yes, the other comments are right about the problem with the graphics. Each row should increase by only a single item. A small flaw in an otherwise outstanding post.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-85699878655051705122009-05-13T14:34:00.000+01:002009-05-13T14:34:00.000+01:00You're an exceptionally talented problem solver, S...You're an exceptionally talented problem solver, Sameul. Thanks for sharing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-57718744418577176462009-03-12T13:02:00.000+00:002009-03-12T13:02:00.000+00:00@Anonymous, I'm afraid I've never used Mathematic...@Anonymous,<BR/> I'm afraid I've never used MathematicaSamhttps://www.blogger.com/profile/01345100698738870730noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-76764724658718570332009-03-11T23:18:00.000+00:002009-03-11T23:18:00.000+00:00I am trying to solve this problem using Mathematic...I am trying to solve this problem using Mathematica any adviceAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-36173536886257060852009-02-12T13:59:00.000+00:002009-02-12T13:59:00.000+00:00You're right that the route you've shown would giv...You're right that the route you've shown would give a greater sum. However in that picture, I was just trying to illustrate one possible route through the triangle, not necessarily the maximal one.Samhttps://www.blogger.com/profile/01345100698738870730noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-48019531820564823862009-02-11T23:43:00.000+00:002009-02-11T23:43:00.000+00:00The first illustration is very wrong. Picking 5-15...The first illustration is very wrong. Picking 5-15-27-58 would yield 105 instead of 95, and that's clearly a greater sum.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-51027298101080555982009-02-11T21:28:00.000+00:002009-02-11T21:28:00.000+00:00Thanks. it would have take me month to think of an...Thanks. it would have take me month to think of an useful idea. Your concept help me do my code in a jiffyEinacionoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-30824042858336324292008-12-13T12:32:00.000+00:002008-12-13T12:32:00.000+00:00Kylar, Glad I could help. It's interesting how my...Kylar,<BR/> Glad I could help. It's interesting how my explanations suit some, but not others.<BR/><BR/>I think you might right about 81: I hadn't looked at it before.<BR/><BR/>SamSamhttps://www.blogger.com/profile/01345100698738870730noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-69663745246365411282008-12-13T04:22:00.000+00:002008-12-13T04:22:00.000+00:00Your explanation was exactly what I needed to get ...Your explanation was exactly what I needed to get past #67. #81 is similar, I think. a matrix for right and down. Rotate, deal with the edge cases and it's the same problem.Kylarhttp://www.jojodyne.com/blognoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-67930786163137536952008-11-29T10:20:00.000+00:002008-11-29T10:20:00.000+00:00You're right about that. I made the same mistake i...You're right about that. I made the same mistake in the second illustration too!<BR/><BR/>I wonder how many other people spotted that but couldn't be bothered to tell me.<BR/><BR/>Thanks.Samhttps://www.blogger.com/profile/01345100698738870730noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-78950916363372509472008-11-29T03:33:00.000+00:002008-11-29T03:33:00.000+00:00in your first illustration, the last row in the tr...in your first illustration, the last row in the triangle has 5 elements....i think it should have 4.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-54147924809423944442008-11-16T17:12:00.000+00:002008-11-16T17:12:00.000+00:00Hey! I believe you explained this as best you coul...Hey! I believe you explained this as best you could but I still am not getting how to resolve this using your algorithm (maybe it's because I am not a c# guy or I am not that great with math)<BR/><BR/>Could you give more examples or something?AntonioCShttp://antoniocs.orgnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-29543216868255368682008-10-24T11:46:00.000+01:002008-10-24T11:46:00.000+01:00Your article has been included in the 42nd Carniva...Your article has been included in the <A HREF="http://www.johndcook.com/blog/2008/10/24/42nd-carnival-of-mathematics/" REL="nofollow">42nd Carnival of Mathematics</A>, just posted a few minutes ago.Johnhttps://www.blogger.com/profile/07480208135315956118noreply@blogger.com