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

  • VegOwOtenks@lemmy.world
    link
    fedilink
    English
    arrow-up
    2
    ·
    8 hours ago

    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
    
    • lwhjp@lemmy.sdf.org
      link
      fedilink
      arrow-up
      2
      ·
      8 hours ago

      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)

      • VegOwOtenks@lemmy.world
        link
        fedilink
        English
        arrow-up
        2
        ·
        edit-2
        3 hours ago

        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?

        • lwhjp@lemmy.sdf.org
          link
          fedilink
          arrow-up
          2
          ·
          3 hours ago

          Your code as it stands is basically State BlinkCache written out explicitly, which is I think a natural way to structure the solution. That is, the cache is the state, and the stone count is the (monadic) return value. Good luck!