Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment