Skip to content

Instantly share code, notes, and snippets.

@adomokos
Created April 17, 2018 01:45
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save adomokos/fd26a07d8c19f96905828a0670029f5b to your computer and use it in GitHub Desktop.
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