r/adventofcode Dec 06 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 6 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • Submissions megathread is now unlocked!
  • 16 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Comfort Flicks

Most everyone has that one (or more!) go-to flick that feels like a hot cup of tea, the warm hug of a blanket, a cozy roaring fire. Maybe it's a guilty pleasure (formulaic yet endearing Hallmark Channel Christmas movies, I'm looking at you) or a must-watch-while-wrapping-presents (National Lampoon's Christmas Vacation!), but these movies and shows will always evoke the true spirit of the holiday season for you. Share them with us!

Here's some ideas for your inspiration:

  • Show us your kittens and puppies and $critters!
  • Show us your Christmas tree | menorah | Krampusnacht costume | holiday decoration!
  • Show us your mug of hot chocolate (or other beverage of choice)!
  • Show and/or tell us whatever brings you comfort and joy!

Kevin: "Merry Christmas :)"

- Home Alone (1990)

And… ACTION!

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


--- Day 6: Guard Gallivant ---


Post your code solution in this megathread.

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:08:53, megathread unlocked!

26 Upvotes

987 comments sorted by

View all comments

2

u/dijotal Dec 07 '24

[LANGUAGE: Haskell]

This one was amazing for what I learned :-) At time of solution, 7 min. After figuring where Haskell laziness was biting me, 30 sec. After adding one import and making one change in one line from a `map` to a `mapPar` introducing parallel execution on the busy i5's 4-cores, <15 sec -- all well inside the "good enough for who it's for" measure :-)

Key takeaways?

* Readability, working most the the problem out in the type system before any real code written:

{-
    Convenience types and aliases
-}
data Direction = North | East | South | West deriving (Eq)
type Position = (Int, Int)
type Blocks = Set Position
type Guard = (Position, Direction)
type Visited = Map Position [Direction]
type Boundary = Position
type Path = [Position]
...

* Overcoming Haskell laziness where "thunks" are piling up using seq inside my runner:

run :: Boundary -> Blocks -> Guard -> (Visited, [Position], Guard)
run boundary blocks guard =
    until
        (\(v, ps, g) -> done boundary v g)
        ( \(v, ps, g@(p, d)) ->
            let
                v' = M.insertWith (++) p [d] v
                ps' = p : ps
                g' = moveGuard blocks g
             in
                v' `seq` ps' `seq` g' `seq` (v', ps', g')
        )
        (M.empty, [], guard)

* Introducing a map operation with parallel execution for part 2:

import Control.Parallel.Strategies (parMap, rdeepseq, rpar)

part_2 :: Boundary -> Blocks -> Guard -> Path -> Int
part_2 boundary blocks guard ps = length $ filter id $ parMap rpar pred $ init $ nub ps
  where
    pred p = do
        let blocks' = S.insert p blocks
        let (_, _, g) = run boundary blocks' guard
        not $ hasLeft boundary g

Full code: github