Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# adomokos/PathCountSpec.hs Secret

Created Apr 17, 2018
Path Count
 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
to join this conversation on GitHub. Already have an account? Sign in to comment