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.