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.
