Advent of Code 2022 day 20

Day 20 should have been easy, but ended up being a large off-by-one error.

The core of this was a circular list library that handled all the list rotations for me. (I could also have used circular pointed lists, which I did in previous years.) That meant I didn't need to faff around with the list rebuilding all the time, and the problem required rotating the list to a given value to generate the result.

The trouble is, the examples given in the problem description didn't cover a couple of cases that threw me off!

First was that the real data had multiple instances of the same value, and these had to be treated as distinct elements. Second was dealing with values that were larger than the length of the list, leading to the off-by-one errors.

I ended up defining a list element as a record of three elements: its index (when it was to be processed), its shift (how far it moved), and its value (what was finally used in the result.

data IndexedElem = IndexedElem { _idx :: Int, _shift :: Int, _value :: Int}
    deriving (Show, Eq, Ord)
makeLenses ''IndexedElem

type MixList = CList IndexedElem

The off-by-one error comes in calculating the shift. If you're only moving a few spaces, you can ignore it. But if you're moving more positions than the length of the list, you don't need to move all of them: with a list of seven items, moving eight positions is the same as moving one.

Or so I thought.

But if you've already removed an item from the list, moving eight positions is the same as moving two positions in the now-six-element list! That took me an embarrassingly long time to work out.

But handling that is done in mkElem.

successfulParse :: String -> [IndexedElem]
successfulParse text = fmap (mkElem l) $ zip [1..] tns
    where tns =  fmap read $ lines text
          mkElem l (i, n) = 
                IndexedElem {_idx = i, _value = n, 
                    _shift = n `mod` (l - 1) }
          l = length tns

Mixing

Mixing one element is finding it (by index), removing it, rotating the list, and inserting it at the new focus. One round of mixing uses foldl to process each index in turn.

part1 :: [IndexedElem] -> Int
part1 mixlist = findGrove $ mixRound $ fromList mixlist

mixRound :: MixList -> MixList
mixRound mixlist = foldl' mixOne mixlist [1..(size mixlist)]

mixOne :: MixList -> Int -> MixList
mixOne mixlist elemIndex = insertL element $ rotN (element ^. shift) $ removeL elementFocused
    where elementFocused = fromJust $ findRotateTo (\e -> e ^. idx == elemIndex) mixlist
          element = fromJust $ focus elementFocused

Part 2

This was the same, except the shift was recalculated for each scaled element.

part2 :: [IndexedElem] -> Int
part2 mixlist = findGrove $ (!!10) $ iterate mixRound cMixlist
    where cMixlist = fromList $ fmap scaleElem mixlist
          scaleElem e = e & value %~ (* key) & shift .~ (((e ^. value) * key) `mod` (scale - 1))
          scale = length mixlist

Code

You can get the code from my locally-hosted Git repo, or from Gitlab.