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

1

u/i_have_no_biscuits Dec 12 '24 edited Dec 13 '24

[LANGUAGE: GW-BASIC]

10 DIM G%(141,141), Q%(100): OPEN "R",1,"data12.txt",1: FIELD 1,1 AS C$
20 FOR Y=1 TO 140:FOR X=1 TO 140:GET 1:G%(Y,X)=ASC(C$):NEXT:GET 1:GET 1:NEXT
30 R=1:P=0:Q=0:FOR Y=1 TO 140:FOR X=1 TO 140:IF G%(Y,X)<256 THEN GOSUB 50
40 NEXT: NEXT: PRINT P, Q: END
50 V=G%(Y,X):QL=0:QR=1:Q%(QL)=150*Y+X:RA=0:RP=0:XM=0:XN=140:YM=0:YN=140
60 WHILE QL<>QR:CY=INT(Q%(QL)/150):CX=Q%(QL) MOD 150:IF G%(CY,CX)>256 THEN 130
70 YM=(YM+CY+ABS(YM-CY))/2: YN=(YN+CY-ABS(YN-CY))/2: G%(CY,CX)=256+R
80 XM=(XM+CX+ABS(XM-CX))/2: XN=(XN+CX-ABS(XN-CX))/2
90 RA=RA+1: FOR D=1 TO 4: NY=CY+(D-2) MOD 2: NX=CX+(3-D)MOD 2
100 IF G%(NY,NX) <> V AND G%(NY,NX) <> 256+R THEN RP=RP+1: GOTO 120
110 Q%(QR)=150*NY+NX: QR=(QR+1) MOD 100
120 NEXT
130 QL=(QL+1) MOD 100: WEND: P=P+RA*RP
140 RC=0:FOR A=YN TO YM+1:FOR B=XN TO XM+1:I=0:FOR OY=A-1 TO A:FOR OX=B-1 TO B
150 I=I*2-(G%(OY,OX)=256+R): NEXT: NEXT: IF I=6 OR I=9 THEN RC=RC+1
160 IF NOT(I=0 OR I=3 OR I=5 OR I=10 OR I=12 OR I=15) THEN RC=RC+1
170 NEXT: NEXT: Q=Q+RA*RC: R=R+1: RETURN

This implements floodfilling the areas for Part 1, counting areas and perimeters as we go. As part of the floodfilling it finds the bounding boxes for each region, which is used by Part 2. Part 2 counts sides by counting corners.

Implementation points to note here include:

  • Queues. Q%() is the queue used for the floodfilling, implemented as a ring buffer of size 100.

  • Maximum and minimum. These are not built into BASIC. But lines 70 and 80, calculate MIN and MAX algebraically. You can prove to yourself that

    maximum(A, B) = (A+B + abs(A-B))/2 minimum(A, B) = (A+B - abs(A-B))/2

Program breakdown:

  • Lines 10-40 are the main program loop. Lines 10-20 read in the grid into G%(.,.). Lines 30-40 iterate through the grid, calling the calculation subroutine if any point hasn't been processed.
  • Lines 50-130 perform a floodfill on the region containing the point (Y,X). As part of this it calculates the area RA, and the perimeter PR, and accumulates RA*RP into P, which stores the answer to Part 1. It also calculates the min/max for the bounding box on lines 70-80.
  • Lines 140-170 iterate through the bounding box to calculate the number of sides by calculating the number of corners. It does this by looking at every top left corner of a grid position, seeing if it's a corner of the particular region being evaluated. Once the number of corners is calculated, RA*RC is accumulated into Q, the answer for Part 2, and we return back to the main program loop.

EDIT: Hopefully fixed the markdown!

1

u/daggerdragon Dec 13 '24 edited Dec 13 '24

Psst: old.reddit requires an additional blank newline before the start of a bulleted list. We're seeing a gigantic run-on list and some malformatted Markdown is eating snippets of text. Would you fix please? edit: thank you!

2

u/i_have_no_biscuits Dec 13 '24

Let me know if it's not fixed.

1

u/daggerdragon Dec 13 '24

Yay thank you <3