Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
31 lines (27 sloc) 1.02 KB
{-
- Solution to Project Euler problem 117
- Copyright (c) Project Nayuki. All rights reserved.
-
- https://www.nayuki.io/page/project-euler-solutions
- https://github.com/nayuki/Project-Euler-solutions
-}
{-
- How many ways can a row n units long be filled with:
- * Black squares 1 unit long
- * Red tiles 2 units long
- * Green tiles 3 units long
- * Blue tiles 4 units long
- Denote this quantity as ways[n].
-
- Compute n = 0 manually as a base case.
- Now assume n >= 1. Look at the leftmost item and sum up the possibilities.
- * Black square (n>=1): Rest of the row can be anything of length n-1. Add ways[n-1].
- * Red tile (n>=2): Rest of the row can be anything of length n-2. Add ways[n-2].
- * Green tile (n>=3): Rest of the row can be anything of length n-3. Add ways[n-3].
- * Blue tile (n>=4): Rest of the row can be anything of length n-4. Add ways[n-4].
-}
main = putStrLn (show ans)
ans = ways 50
ways 0 = 1
ways n = sum $ take (min n 4) $ drop (max (n-4) 0) waysMemo
waysMemo = map ways [0..]