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 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


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

    Neil Smith

    Read more posts by this author.