Last active
August 3, 2023 08:48
-
-
Save jvlmdr/b964e4eb9ef324a42c91952aa556fb75 to your computer and use it in GitHub Desktop.
Change in Haskell using explicit memoization instead of State monad
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module Change (findFewestCoins) where | |
import Data.Function (on) | |
import Data.Map (Map, (!?)) | |
import qualified Data.Map as Map | |
import Safe.Foldable (minimumByMay) | |
type Change = Maybe [Integer] | |
type Cache = Map Integer Change | |
findFewestCoins :: Integer -> [Integer] -> Change | |
findFewestCoins target coins = snd $ findAndUpdateCache Map.empty target where | |
findAndUpdateCache :: Cache -> Integer -> (Cache, Change) | |
findAndUpdateCache cache target' = | |
case compare target' 0 of | |
LT -> (cache, Nothing) | |
EQ -> (cache, Just []) | |
GT -> case cache !? target' of | |
Just solution -> (cache, solution) | |
Nothing -> (Map.insert target' solution cache', solution) where | |
(cache', solutions') = foldl (solveAndUpdate target') (cache, []) coins | |
candidates = [coin : solution' | (coin, Just solution') <- solutions'] | |
solution = minimumByMay (compare `on` length) candidates | |
solveAndUpdate :: Integer -> (Cache, [(Integer, Change)]) -> Integer -> (Cache, [(Integer, Change)]) | |
solveAndUpdate target (cache, ys) coin = (cache', (coin, solution) : ys) | |
where (cache', solution) = findAndUpdateCache cache $ target - coin |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment