Day 11: Plutonian Pebbles
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 2 points
Haskell
Sometimes I want something mutable, this one takes 0.3s, profiling tells me 30% of my time is spent creating new objects. :/
import Control.Arrow
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import qualified Data.Maybe as Maybe
type StoneCache = Map Int Int
type BlinkCache = Map Int StoneCache
parse :: String -> [Int]
parse = lines >>> head >>> words >>> map read
memoizedCountSplitStones :: BlinkCache -> Int -> Int -> (Int, BlinkCache)
memoizedCountSplitStones m 0 _ = (1, m)
memoizedCountSplitStones m i n
| Maybe.isJust maybeMemoized = (Maybe.fromJust maybeMemoized, m)
| n == 0 = do
let (r, rm) = memoizedCountSplitStones m (pred i) (succ n)
let rm' = cacheWrite rm i n r
(r, rm')
| digitCount `mod` 2 == 0 = do
let (r1, m1) = memoizedCountSplitStones m (pred i) firstSplit
let (r2, m2) = memoizedCountSplitStones m1 (pred i) secondSplit
let m' = cacheWrite m2 i n (r1+r2)
(r1 + r2, m')
| otherwise = do
let (r, m') = memoizedCountSplitStones m (pred i) (n * 2024)
let m'' = cacheWrite m' i n r
(r, m'')
where
secondSplit = n `mod` (10 ^ (digitCount `div` 2))
firstSplit = (n - secondSplit) `div` (10 ^ (digitCount `div` 2))
digitCount = succ . floor . logBase 10 . fromIntegral $ n
maybeMemoized = cacheLookup m i n
foldMemoized :: Int -> (Int, BlinkCache) -> Int -> (Int, BlinkCache)
foldMemoized i (r, m) n = (r + r2, m')
where
(r2, m') = memoizedCountSplitStones m i n
cacheWrite :: BlinkCache -> Int -> Int -> Int -> BlinkCache
cacheWrite bc i n r = Map.adjust (Map.insert n r) i bc
cacheLookup :: BlinkCache -> Int -> Int -> Maybe Int
cacheLookup bc i n = do
sc <- bc Map.!? i
sc Map.!? n
emptyCache :: BlinkCache
emptyCache = Map.fromList [ (i, Map.empty) | i <- [1..75]]
part1 = foldl (foldMemoized 25) (0, emptyCache)
>>> fst
part2 = foldl (foldMemoized 75) (0, emptyCache)
>>> fst
main = getContents
>>= print
. (part1 &&& part2)
. parse
2 points
Some nice monadic code patterns going on there, passing the cache around! (You might want to look into the State monad if you haven’t come across it before)
2 points
*
Thank you for the hint, I wouldn’t have recognized it because I haven’t yet looked into it, I might try it this afternoon if I find the time, I could probably put both the Cache and the current stone count into the monad state?
2 points
