Thursday, April 19, 2018

Path Count

I've bumped into this brain teaser recently:

"Given two integer numbers describing an n by m graph, where n represents the height and m represents the width, calculate the number of ways you can get from the top left to the bottom right if you can only go right and down"

That's a fine challenge, and prior to knowing recursive types in Haskell, I don’t know how I would have approached the problem.

Let's draw what the paths would look like first.

Given 1x1, the case is pretty simple:

{-
  The is what the matrix would look like:

  (0,1) - (1,1)
    |       |
  (0,0) - (1,0)
-}

The only way to get from the top left to the bottom right is to "walk" the perimeters:

{-
  (0,1) - (1,1) - (1,0)
  (0,1) - (0,0) - (1,0)
-}

This case is so easy, I don’t even bother with devising a solution. Let's look at a 1 by 2 graph:

{-
  (0-1) - (1,1) - (2,1)
    |       |       |
  (0-0) - (1,0) - (2,0)
-}

Following the rules laid out, there are 3 ways to get from the top left to the bottom right point:

{-
  (0-1) - (1,1) - (2,1) - (2,0)
  (0-1) - (1,1) - (1,0) - (2,0)
  (0-1) - (0,0) - (1,0) - (2,0)
-}

The rule "you can only go right and down" tells us something: it's a binary tree. How could I draw up a recursive tree structure for this?

I'd like to make sure the logic is correct, I put all this logic into an HSpec file. How 'bout this?

-- test/PathCountSpec.hs

import Test.Hspec

main :: IO ()
main = hspec spec

type Point = (Int, Int)
data Tree a = Leaf
            | Node a (Tree a) (Tree a)
            deriving (Show, Eq)

spec :: Spec
spec =
    describe "Path Count" $ do
        it "can calculate tree branches for 1x2 matrix" $ do
            let tree =
                    Node (0,1)
                        (Node (1,1)
                            (Node (2,1) Leaf
                                        (Node (2,0) Leaf Leaf))
                            (Node (1,0) (Node (2,0) Leaf Leaf)
                                        Leaf))
                        (Node (0,0)
                            (Node (1,0)
                                (Node (2,0) Leaf Leaf)
                                Leaf)
                            Leaf)
            {-
               Possible paths:
                (0,1) - (1,1) - (2,1) - (2,0)
                (0,1) - (1,1) - (1,0) - (2,0)
                (0,1) - (0,0) - (1,0) - (2,0)
            -}
            pending

The key here, that the number of times Node (2,0) Leaf Leaf appears is the number of different ways I can get from the top left to the bottom right. All I have to do is counting the number of times this sub-tree appears in the tree itself.

I wrote a function (that I put into the HSpec file itself) to do just that:

leafCount :: Tree Point -> Int
leafCount Leaf = 0
leafCount (Node _ Leaf Leaf) = 1
leafCount (Node _ left right) = leafCount left + leafCount right

When I call this function with the provided tree I have in the spec, I should receive 3. This assertion passes:

leafCount tree `shouldBe` 3

I manually had to build up this tree, next I looked at how I could generate it myself based on the top left and bottom right points. I had to make sure I won’t add branches outside of the matrix, what I accomplished with two guards.

buildTree :: Point -> Point -> Tree Point
buildTree (a,b) end@(c,d)
    | a > c = Leaf
    | b < 0 = Leaf
    | otherwise = Node (a, b) (buildTree (a+1,b) end) (buildTree (a,b-1) end)

This logic will keep "walking" right and down until the guards will stop it.

I added another assertion to make sure this still passes:

buildTree (0,1) (2,0) `shouldBe` tree

I wanted to make sure this logic still holds when I pivot the two numbers. This is the next assertion I added:

buildTree (0,2) (1,0) `shouldBe` tree

Tests are passing. All right, I need to set up an outer function that takes two numbers and returns the number of paths.

Here it is:

pathCount :: Int -> Int -> Int
pathCount m n = leafCount $ fromTree m n
    where fromTree m n = buildTree (0,m) (n,0)

This assertion will exercise this function:

pathCount 1 2 `shouldBe` 3

Everything is green!

I added one more test to make sure the 1x1 graph works:

pathCount 1 1 `shouldBe` 2

And finally I added a 2x2 test as well. This one has 6 different paths to get from the top left to the bottom right:

{-
    Possible paths:
    (0,2) - (1,2) - (2,2) - (2,1) - (2,0)
    (0,2) - (1,2) - (1,1) - (2,1) - (2,0)
    (0,2) - (1,2) - (1,1) - (1,0) - (2,0)
    (0,2) - (0,1) - (1,1) - (2,1) - (2,0)
    (0,2) - (0,1) - (1,1) - (1,0) - (2,0)
    (0,2) - (0,1) - (0,0) - (1,0) - (2,0)
-}
pathCount 2 2 `shouldBe` 6

And when I run the spec again, it all works! You can find the solution in this gist.

3 comments:

Noah said...

You can do better than a tree, actually. The paths follow the grid structure of the graph.

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
either (n-1,m) or (n,m-1).

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).

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).

This is a classic dynamic programming problem, with the recurrence relation:

P(1,m) = 1
P(n,1) = 1
P(n,m) = P(n-1,m) + P(n,m-1) if n > 1 and m > 1

In haskell, we can think of the grid as list of lists

[ [ (n,m), (n, m-1), (n, m-2), …, (n, 1) ]
, [ (n-1, m), (n-1, m-1), (n-1, m-2), …, (n-1, 1) ]

, [ (1,m), (1, m-1), (1, m-2), …, (1, 1) ]
]

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.

countPathsFrom :: (Height,Width) -> Count
countPathsFrom (n,m) = countPathsFromAll (n,m) !! 0 !! 0

countPathsFromAll :: (Height,Width) -> [[Count]]

For any point on the bottom line of the grid, there's only one
path to (1,1); we can't go down any more, so we have to go right.

If we know how many paths there are for each point in one line of the grid, we can calculate how many paths there'll be for each point in the line above.

The right-most point in the line above will only have one path to (1,1); we can't go right any more, so we have to go down.

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.

We can continue left in this fashion to compute the whole line

This nested recursion can be directly expressed in haskell via `scanr`

countPathsFromAll (n,m) = scanr computeLineAbove bottomLine [n,n-1..2] where
bottomLine = replicate m 1
computeLineAbove _ lineBelow = scanr1 (+) lineBelow

For example for n = 10 and m = 7, countPathsFromAll calculates

[ [5005,2002,715,220,55,10,1]
, [3003,1287,495,165,45, 9,1]
, [1716, 792,330,120,36, 8,1]
, [ 924, 462,210, 84,28, 7,1]
, [ 462, 252,126, 56,21, 6,1]
, [ 210, 126, 70, 35,15, 5,1]
, [ 84, 56, 35, 20,10, 4,1]
, [ 28, 21, 15, 10, 6, 3,1]
, [ 7, 6, 5, 4, 3, 2,1]
, [ 1, 1, 1, 1, 1, 1,1]
]

We could save a little more time (a factor of two) by taking advantage of the diagonal symmetry - there'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.

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)

countPathsFrom (n,m) = (n + m - 2) `choose` (m - 1)

Attila Domokos said...

Thanks! 👌

Anton Lorenzen said...

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!)

For example, for a 10x7 matrix you would get 19.448 ways.

Post a Comment