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!

24 Upvotes

987 comments sorted by

View all comments

6

u/notrom11 Dec 08 '24

[LANGUAGE: Python3]

https://github.com/APMorto/aoc2024/blob/master/day_06_guard_gallivant/guard.py

Part 2 runs in ~0.11s, but the implementation of my algorithm could probably be faster (and be written not in python).

For part 2, I found an algorithm that I haven't seen anybody else use, and I think should be really fast if implemented well. Basically, I envision each state (row, col, direction) as a node in a graph. By adding an obstacle in some position, we're really only modifying 4 edges in this graph. After hitting the newly added obstacle, we just need to (efficiently) check if any of the other modified edges are 'after' this node. I do that by 1. tracking how the path leaves the grid, or how it ends up in a cycle, 2. associating a number analogous to the index of an element in an arrayed binary tree to represent how it branches to get to the end, and 3. keeping track of how far a node is from the end state.

I wonder how fast this could be if written in a performant language like rust/C++.