tag:blogger.com,1999:blog-5573355675806579511.post3304212846238321025..comments2021-09-16T06:15:27.436-05:00Comments on Climb That Mountain: Path CountAttila Domokoshttp://www.blogger.com/profile/09067995287578229487noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5573355675806579511.post-76975736206820039682018-04-27T12:08:38.170-05:002018-04-27T12:08:38.170-05:00You can also see this as a combinatorics problem. ...You can also see this as a combinatorics problem. You go down exactly n times and right exactly m times, which means you can use the number of permutations, which is (n + m)! / (n! * m!)<br /><br />For example, for a 10x7 matrix you would get 19.448 ways.Anton Lorenzennoreply@blogger.comtag:blogger.com,1999:blog-5573355675806579511.post-79218250552221383702018-04-26T12:15:35.438-05:002018-04-26T12:15:35.438-05:00Thanks! 👌Thanks! 👌Attila Domokoshttps://www.blogger.com/profile/09067995287578229487noreply@blogger.comtag:blogger.com,1999:blog-5573355675806579511.post-7828592269920839392018-04-26T11:41:47.788-05:002018-04-26T11:41:47.788-05:00You can do better than a tree, actually. The paths...You can do better than a tree, actually. The paths follow the grid structure of the graph.<br /><br />Label the upper-left corner as (n,m) and the lower right-corner as (1,1). Then all paths from (n,m) to (1,1) go through<br />either (n-1,m) or (n,m-1).<br /><br />Using the same logic, all the paths from (n-1,m) to (1,1) go through (n-2,m) or (n-1,m-1), and all the paths from (n,m-1) to (1,1) go through (n-1,m-1) or (n,m-2).<br /><br />This means if we set this up correctly we can calculate the number of paths from (n-1,m-1) to (1,1) once, and use it twice in the calculation of both the number of paths from (n-1,m) to (1,1) and the number of paths from (n,m-1) to (1,1).<br /><br />This is a classic dynamic programming problem, with the recurrence relation:<br /><br /> P(1,m) = 1<br /> P(n,1) = 1<br /> P(n,m) = P(n-1,m) + P(n,m-1) if n &gt; 1 and m &gt; 1<br /><br />In haskell, we can think of the grid as list of lists<br /><br /> [ [ (n,m), (n, m-1), (n, m-2), …, (n, 1) ]<br /> , [ (n-1, m), (n-1, m-1), (n-1, m-2), …, (n-1, 1) ]<br /> ⋮<br /> , [ (1,m), (1, m-1), (1, m-2), …, (1, 1) ]<br /> ]<br /><br />To compute the number of paths from (n,m) to (1,1), the dynamic programming approach has us calculate the number of paths from every point in the grid to (1,1). The straight recursive approach calculates all these values anyway, but dynamic programming lets us only calculate them once and then reuse the calculated values, which is *exponentially* faster.<br /><br /> countPathsFrom :: (Height,Width) -&gt; Count<br /> countPathsFrom (n,m) = countPathsFromAll (n,m) !! 0 !! 0<br /><br /> countPathsFromAll :: (Height,Width) -&gt; [[Count]]<br /><br />For any point on the bottom line of the grid, there&#39;s only one<br />path to (1,1); we can&#39;t go down any more, so we have to go right.<br /><br />If we know how many paths there are for each point in one line of the grid, we can calculate how many paths there&#39;ll be for each point in the line above.<br /><br />The right-most point in the line above will only have one path to (1,1); we can&#39;t go right any more, so we have to go down. <br /><br />From the next-right-most point, we can either go right or down, and we know how many paths there are from the point right and down of here, so summing them gives the total number of paths from this point.<br /><br />We can continue left in this fashion to compute the whole line<br /><br />This nested recursion can be directly expressed in haskell via `scanr`<br /><br /> countPathsFromAll (n,m) = scanr computeLineAbove bottomLine [n,n-1..2] where<br /> bottomLine = replicate m 1<br /> computeLineAbove _ lineBelow = scanr1 (+) lineBelow<br /><br />For example for n = 10 and m = 7, countPathsFromAll calculates<br /><br /> [ [5005,2002,715,220,55,10,1]<br /> , [3003,1287,495,165,45, 9,1]<br /> , [1716, 792,330,120,36, 8,1]<br /> , [ 924, 462,210, 84,28, 7,1]<br /> , [ 462, 252,126, 56,21, 6,1]<br /> , [ 210, 126, 70, 35,15, 5,1]<br /> , [ 84, 56, 35, 20,10, 4,1]<br /> , [ 28, 21, 15, 10, 6, 3,1]<br /> , [ 7, 6, 5, 4, 3, 2,1]<br /> , [ 1, 1, 1, 1, 1, 1,1]<br /> ]<br /><br />We could save a little more time (a factor of two) by taking advantage of the diagonal symmetry - there&#39;s the same number of paths from (i,j) to (1,1) as from (j,i) to (1,1), so no need to calculate both.<br /><br />But of course, if we really want to get fast, we can note that this particular recurrence has a closed form (https://math.stackexchange.com/questions/80582/solving-recursion-with-2-parameters) <br /><br /> countPathsFrom (n,m) = (n + m - 2) `choose` (m - 1)<br />Noahhttps://www.blogger.com/profile/12638229035633367208noreply@blogger.com