tag:blogger.com,1999:blog-7577421612120825312.post7980005285052102442..comments2022-11-17T09:39:52.001+00:00Comments on Functional Fun: Project Euler Problem 15: City Grids and Pascal's TriangleAnonymoushttp://www.blogger.com/profile/01345100698738870730noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-7577421612120825312.post-9963118194713266472012-02-09T01:38:12.512+00:002012-02-09T01:38:12.512+00:00ok,i have this question my science teacher asked u...ok,i have this question my science teacher asked us today about a 6x6 grid and how many pathes from top left to bottom right,i didn't understand a thing you guys were talking about,but I also guess im failing this question,any help,my answer is due tomorrow,I hope one of you can help me!Michell-1999noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-85894258717062273562012-01-28T06:55:56.690+00:002012-01-28T06:55:56.690+00:00Great maths solution, but your implementation is v...Great maths solution, but your implementation is very long. Simply iteratively generates each new base, while rotating around two arrays. (one as new base, one as old base)<br /><br />Freebasic code. 22 lines. Can be squished together to 15 or less.<br /><br />dim as integer levels = 20<br />dim as integer curSize = 1<br />dim as ulongint c1, c2<br />dim as integer j<br />dim as ulongint ptr arrayA = callocate (1, sizeof(ulongint))<br />dim as ulongint ptr arrayB = 0<br />arrayA[0] = 1<br /><br />for i as integer = 0 to levels * 2 - 1<br /> curSize += 1<br /> arrayB = reallocate (arrayB, curSize * sizeof(ulongint))<br /> for j = 0 to curSize - 1<br /> if j = 0 then c1 = 0 else c1 = arrayA[j-1]<br /> if j = curSize - 1 then c2 = 0 else c2 = arrayA[j]<br /> arrayB[j] = c1 + c2<br /> next j<br /> swap arrayA, arrayB<br />next i<br /><br />print arrayA[(curSize+1)/2-1]<br />sleep<br />systemagamemnusnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-43675403798514652342011-09-28T03:29:05.495+01:002011-09-28T03:29:05.495+01:00An overnight express company must include ten citi...An overnight express company must include ten cities on its route. How many different routes are possible, assuming that it matters in which order the cities are included in the routing?Traviskendall7noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-52829940760035304992011-06-12T20:08:05.146+01:002011-06-12T20:08:05.146+01:00(m+n)!/m!n! is the actual formula. 2n!/n!n! is mer...(m+n)!/m!n! is the actual formula. 2n!/n!n! is merely a special case where m=n.Khaldacnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-84921973078916210042011-05-16T15:48:54.371+01:002011-05-16T15:48:54.371+01:00for n x m grid the solution is direct extension of...for n x m grid the solution is direct extension of your method: <br>paths(m,n) = binomial(n+m, m), which becomes the same as the solution above when m = n. Neat huh?<br><br>Btw, I didn't know the solution till I saw your grid labeling illustration. That made me say "ahah!" So thank you for that,<br>maxmaxsuhttp://www.blogger.com/profile/01347005588795148983noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-79096791342836894742011-05-16T15:48:53.426+01:002011-05-16T15:48:53.426+01:00For some reason this was straightforward.I only lo...For some reason this was straightforward.<br>I only looked at 2x2 grid with 6 routes and I was like "Wait, the combination formula might work, since 4 nCr 2 is 6." (4 is twice a two, the dimension of a grid)<br>Then I tried 6 nCr 3 and got 20. After that my only problem was the overflow.<br>But yeah, math helps :)Otherworldhttp://www.blogger.com/profile/13449591808096561798noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-28286379876587335802011-04-24T10:34:05.046+01:002011-04-24T10:34:05.046+01:00For some reason this was straightforward.
I only l...For some reason this was straightforward.<br />I only looked at 2x2 grid with 6 routes and I was like "Wait, the combination formula might work, since 4 nCr 2 is 6." (4 is twice a two, the dimension of a grid)<br />Then I tried 6 nCr 3 and got 20. After that my only problem was the overflow.<br />But yeah, math helps :)Otherworldhttps://www.blogger.com/profile/13449591808096561798noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-40300123191596537582011-04-24T10:27:43.220+01:002011-04-24T10:27:43.220+01:00This comment has been removed by the author.Otherworldhttps://www.blogger.com/profile/13449591808096561798noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-41692774798144572992011-03-20T17:02:20.987+00:002011-03-20T17:02:20.987+00:00I found it easy to just create pascals triangle an...I found it easy to just create pascals triangle and then count every line with odd amount of entries and take the middle entry at line number 20. You have to create the triangle with an integer array on each line because with a string, it can be confusing with whitespace, and numbers larger than 10 are more than one char long.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-75755832338057066262010-07-09T13:39:31.288+01:002010-07-09T13:39:31.288+01:00Like Tristan I also wanted to use my new-found ham...Like Tristan I also wanted to use my new-found hammer.. but used it to tackle the problem as written:<br /><br />Func findRouteCount = null;<br />findRouteCount =<br />(x, y) =><br /> {<br /> if (x == 0 && y == 0) return 1;<br /> long routes = 0;<br /> if (x != 0) routes = checked(routes + findRouteCount(x - 1, y));<br /> if (y != 0) routes = checked(routes + findRouteCount(x, y - 1));<br /> return routes;<br /> };<br /><br />findRouteCount = findRouteCount.Memoize();<br />return findRouteCount(20, 20);Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-73969392164731873532010-03-16T02:12:47.673+00:002010-03-16T02:12:47.673+00:00for n x m grid the solution is direct extension of...for n x m grid the solution is direct extension of your method: <br />paths(m,n) = binomial(n+m, m), which becomes the same as the solution above when m = n. Neat huh?<br /><br />Btw, I didn't know the solution till I saw your grid labeling illustration. That made me say "ahah!" So thank you for that,<br />maxmaxsuhttps://www.blogger.com/profile/01347005588795148983noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-80344799559910651442010-02-27T07:02:56.064+00:002010-02-27T07:02:56.064+00:00There are 40 steps to any given path (we have to g...There are 40 steps to any given path (we have to go 20 steps down and 20 steps right). Since the definition of backtracking makes any given move down indistinguishable from any other move down, and any given move right indistinguishable from any other move right, the answer is 40!/(20!20!)..<br /><br />Art of Designing algm lies in looking at the less obvious facts..my soln is way faster than yours mateAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-68262240475772279532010-02-23T17:13:48.170+00:002010-02-23T17:13:48.170+00:00Anonymous,
That's left as an excercise to the...Anonymous,<br /> That's left as an excercise to the reader :-). Seriously though, I have no idea - never thought about it. What are your thoughts?Anonymoushttps://www.blogger.com/profile/01345100698738870730noreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-1182648521994436212010-02-23T01:53:22.438+00:002010-02-23T01:53:22.438+00:00what if it is a 3x4? so its not n x n its m x n?what if it is a 3x4? so its not n x n its m x n?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577421612120825312.post-11592143229763304302009-01-02T19:21:00.000+00:002009-01-02T19:21:00.000+00:00Still loving your blog.I did this one slightly dif...Still loving your blog.<BR/>I did this one slightly differently: in the post preceding this one you introduced memoization. Holding this new hammer, it was hard for me to not see a nail, so I created a Tuple class so that I could make multi-parameter memoize methods. Then the solution becomes:<BR/> Func < int, int, long > getPascalTriangleEntry = null;<BR/> getPascalTriangleEntry = (int row, int col) = ><BR/> {<BR/> if (row < = 1 || col == 0 || col == row)<BR/> {<BR/> return 1;<BR/> }<BR/> return getPascalTriangleEntry(row - 1, col) + getPascalTriangleEntry(row - 1, col - 1);<BR/> };<BR/> getPascalTriangleEntry = getPascalTriangleEntry.Memoize();<BR/><BR/>Cheers,<BR/><BR/>-t.Tristan Reidhttps://www.blogger.com/profile/11770063054853613781noreply@blogger.com