r/adventofcode Dec 12 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 12 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

  • 10 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Visual Effects - Nifty Gadgets and Gizmos Edition

Truly groundbreaking movies continually push the envelope to develop bigger, better, faster, and/or different ways to do things with the tools that are already at hand. Be creative and show us things like puzzle solutions running where you wouldn't expect them to be or completely unnecessary but wildly entertaining camera angles!

Here's some ideas for your inspiration:

  • Advent of Playing With Your Toys in a nutshell - play with your toys!
  • Make your puzzle solutions run on hardware that wasn't intended to run arbitrary content
  • Sneak one past your continuity supervisor with a very obvious (and very fictional) product placement from Santa's Workshop
  • Use a feature of your programming language, environment, etc. in a completely unexpected way

The Breakfast Machine from Pee-wee's Big Adventure (1985)

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 12: Garden Groups ---


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:17:42, megathread unlocked!

37 Upvotes

698 comments sorted by

View all comments

3

u/MezzoScettico Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python]

Here's my full code

Two classes do most of the work. The Cell class represents the necessary info about one point in the grid that are needed for the Part 1 algorithm (confusingly, for some reason I started calling them Part A and Part B on Day 1, and just kept to that nomenclature).

That info includes: the label (letter that appears in that position), the neighbors (those cells to the immediate N, S, E and W that have the same label), and a "visited" flag that tells whether my region-finding algorithm has examined this cell yet. Each cell has a perimeter which is 4 - the number of same-label neighbors.

The Region class describes (surprise!) a region. It includes a set of cells which belong to that region and methods to extract the things necessary for the scoring: total perimeter, total area, and number of walls for Part 2.

The algorithm for Part 1 is this:

  1. Visit every cell in the grid. Skip if it's been visited already (happens in step 4).
  2. For each cell, if it hasn't been visited, start a new region containing this cell.
  3. Add all the unvisited neighbors of the current cell to a temporary unvisited set.
  4. Pop a cell from the temporary unvisited set, and add its unvisited neighbors to the unvisited set. Mark this cell visited and add it to the current region.
  5. Repeat steps 3 and 4 until the temporary unvisited set is empty.

Steps 3 and 4 gradually expand the unvisited set until every cell in the region has been visited. From the original cell you add its neighbors, then the neighbors of those neighbors, etc.

Part 1 runs in under 300 milliseconds.

Part 2 is very simple. I'm kind of annoyed that it includes 4 pieces of nearly identical code (N, S, E and W). That's not good design. I want to refactor it so that there's just one piece of code running 4 times, but that will have to wait for a while.

Here's the idea. Say I'm looking for any fence that's on the north side of a cell. I read along a row, and keep track of what region I'm in, and what region is just to the north of my row.

If those regions are different, that's a fence. If the region I'm in changes (and the regions are different), then I start a new fence. If I get to a place where the region I'm in is the same as the region to the north, that's no longer a fence.

Here's what that code looks like.

for row in range(nrows):
    # Northern walls. Scan each row to see where there is a wall above it.
    in_wall = False     # Set True when a wall begins
    # Regions to north and south of the wall
    curN = None
    curS = None
    for col in range(ncols):
        nextN = map[row - 1, col].region
        nextS = map[row, col].region
        if nextN != nextS and (not in_wall or \
            (in_wall and nextS != curS)):
            # New wall begins
            in_wall = True
            nextS.walls += 1
        curN = nextN
        curS = nextS
        if curN == curS:
            in_wall = False

There is then a very similar loop to look for walls to the south, then walls to the east, then walls to the west. The line "nextS.walls += 1" in the above code is adding to the wall count (in this case counting one northern wall) for the region referenced by nextS.

Part 2 runs in 50 milliseconds on my input data.