# Project Euler #15 in haskell

I've solved Project Euler #15 in Haskell, but I feel like there might be a better way to express my solution that I'm not seeing. I start out defining my types:

import qualified Data.Map.Strict as Map
import Data.List

data Position = Position Int Int
deriving (Show, Eq, Ord)

start :: Position
start = Position 20 20


I probably should have used newtype on a tuple of Ints, but I think this is ok. I can then generate the list of moves available from a given position via:

moves :: Position -> [Position]
moves (Position x y) | x == 0 && y == 0 = []
| x == 0 = [Position x (y - 1)]
| y == 0 = [Position (x - 1) y]
| otherwise = Position (x - 1) y : Position x (y - 1) : []


From there a naive implementation to solve for the number of paths would simply look like:

naiveWays :: Position -> Int
naiveWays (Position 0 0) = 1
naiveWays pos = sum $map naiveWays$ moves pos


Of course this is highly inefficient, and takes much to long to complete, so I tried to improve it using memoization. This is where I feel like I could probably use the most improvement:

ways :: Position -> Int
ways = snd . memWays Map.empty

memWays :: Map.Map Position Int -> Position -> (Map.Map Position Int, Int)
memWays mem (Position 0 0) = (mem, 1)
memWays mem pos = loop lookupWays
where
lookupWays = Map.lookup pos mem
computeWays = mapAccumR memWays mem (moves pos)
mapWays = fst computeWays
sumWays = sum $snd computeWays loop (Just w) = (mem, w) loop (Nothing) = (Map.insert pos sumWays mapWays, sumWays)  Basically memWays takes a Map of known solutions for the subproblems (number of paths from 2,2, etc), and a position and attempts to use it to find the shortest path. If the position is already in the map, it can simply look it up. Otherwise, it maps over the available moves, using the returned Map as an accumulator. There actually is an even more efficient way to solve it, but I won't spoil that, and since I'm looking for Haskell practice, not math, I'm more interested in figuring out how I can make this approach cleaner. Edit: Thanks to 200_success for pointing out that I don't need to enumerate moves. memWays now looks like: memWays :: Map.Map Position Int -> Position -> (Map.Map Position Int, Int) memWays mem (Position 0 _) = (mem, 1) memWays mem (Position _ 0) = (mem, 1) memWays mem pos@(Position x y) = loop$ Map.lookup pos mem
where right = memWays mem $Position (x - 1) y down = memWays (fst right)$ Position x (y - 1)
both = snd right + snd down
loop (Just paths) = (mem, paths)
loop Nothing = (Map.insert pos both \$ fst down, both)


I feel like this looks a lot cleaner, though if anyone has suggestions for further improvement, I'd love to hear it.

-
Efficiency Review: Optimize the code using mathematical concepts. I suggest you study some combinitorics. –  recursion.ninja Feb 18 '14 at 14:13
If you are registered at project euler and have submitted a valid solution for this problem you have access to the thread for this problem in the project euler forum. Ther you can find a lot and maybe faster solutions of this problem. –  miracle173 Oct 11 '14 at 9:34

There's no need to list all the moves. Here is an unmemoized solution:

naiveWays :: Position -> Int
naiveWays (Position 0 _) = 1
naiveWays (Position _ 0) = 1
naiveWays (Position x y) = (naiveWays (Position (x - 1) y)) +
(naiveWays (Position x (y - 1)))


Note that it also takes better advantage of pattern matching.

-