Path Count

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)

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

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

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)

spec :: Spec
spec =
    describe "Path Count" $ do
        it "can calculate paths 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)
            -}
            buildTree (0,1) (2,0) `shouldBe` tree
            leafCount(buildTree (0,1) (2,0)) `shouldBe` 3
            leafCount(buildTree (0,2) (1,0)) `shouldBe` 3
            pathCount 1 2 `shouldBe` 3
            pathCount 2 1 `shouldBe` 3
            pathCount 1 1 `shouldBe` 2
        it "can calculate paths for 2x2 matrix" $ do
            let tree =
                    Node (0,2)
                         (Node (1,2)
                               (Node (2,2)
                                     Leaf
                                     (Node (2,1)
                                           Leaf
                                           (Node (2,0) Leaf Leaf)))
                               (Node (1,1)
                                     (Node (2,1)
                                           Leaf
                                           (Node (2,0) Leaf Leaf))
                                     (Node (1,0)
                                           (Node (2,0) Leaf Leaf)
                                            Leaf)))
                         (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))
            leafCount tree `shouldBe` 6
            buildTree (0,2) (2,0) `shouldBe` tree
            pathCount 2 2 `shouldBe` 6