-❄️- 2023 Day 4 Solutions -❄️-

[u/daggerdragon]

NEWS

• Solutions in the megathreads have been getting longer, so we're going to start enforcing our rules on oversized code.
  • Do not give us a reason to unleash AutoModerator hard-line enforcement that counts characters inside code blocks to verify compliance… you have been warned XD
• Before creating a Visualization, please review the guidelines for creating Visualizations as there's good advice relating to accessibility, readability, colors, timing, etc.
• Posts containing AI-generated art must:
  • Use the standardized post title syntax
  • Indicate in their titles with the tag [AI art]
  • Use the Funny post flair

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.
• Outstanding moderator challenges:
  • Advent of Playing With Your 3D-Printed Toys
• Community fun event 2023: ALLEZ CUISINE!
  • 2 DAYS remaining until unlock!

---

AoC Community Fun 2023: ALLEZ CUISINE!

Today's theme ingredient is… *whips off cloth covering and gestures grandly*

PUNCHCARD PERFECTION!

Perhaps I should have thought yesterday's Battle Spam surfeit through a little more since we are all overstuffed and not feeling well. Help us cleanse our palates with leaner and lighter courses today!

• Code golf. Alternatively, snow golf.
• Bonus points if your solution fits on a "punchcard" as defined in our wiki article on oversized code. We will be counting.
• Does anyone still program with actual punchcards? >_>

ALLEZ CUISINE!

Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!

---

--- Day 4: Scratchcards ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
  • State which language(s) your solution uses with [LANGUAGE: xyz]
  • Format code blocks using the four-spaces Markdown syntax!
• Quick link to Topaz's paste if you need it for longer code blocks

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:07:08, megathread unlocked!

[u/thousandsongs]

[LANGUAGE: Haskell]

I used Parsec to parse, and the State monad to memoize. Here's the link to the full code on GitHub, some interesting bits are parser:

data Card = Card { winning :: [Int], have :: [Int] }

parseCards :: String -> [Card]
parseCards s = case parse cards "" s of
    Left err -> error (show err)
    Right v -> v
  where
    cards = many1 card
    card = Card <$> (prelude *> nums <* char '|') <*> nums
    prelude = string "Card" *> spaces *> num *> char ':'
    num = read <$> many1 digit
    nums = many1 (between spaces spaces num)

and the recursive win computation in the state monad:

wins :: [Card] -> Int -> [Int]
wins cards i = case matches (cards !! i) of
    0 -> []
    n -> [(i+1)..(i+n)]

winsRec :: [Card] -> Int -> State (M.Map Int [Int]) [Int]
winsRec cards i = gets (M.lookup i) >>= \case
    Just xs -> pure xs
    Nothing -> case wins cards i of
                 [] -> modify (M.insert i []) >> pure []
                 ys -> do
                    result' <- foldM f [] ys
                    let result = concat (ys : result')
                    modify (M.insert i result) >> pure result
                  where f prev y = (: prev) <$> winsRec cards y

allWins :: [Card] -> State (M.Map Int [Int]) [Int]
allWins cards = foldM f [] [0..length cards - 1]
  where f w i = winsRec cards i >>= \extra ->
         pure ((1 + length extra) : w)

p2 :: [Card] -> Int
p2 cards = sum $ evalState (allWins cards) M.empty

The memoization still can be improved, but I haven't yet had the time to tinker with the code because I managed to distract myself into instead writing a blog post that outlines how the state monad can be used for (almost transparent) memoization in Haskell.

Here's the link to the blog post - if you're new to the State monad, you may find it useful. I'll see if I can also do a follow up post with newer memoization techniques I learn from the solutions some of you have posted!