this post was submitted on 12 Dec 2024
16 points (94.4% liked)

Advent Of Code

920 readers
60 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 18 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
[email protected]
[email protected]
[email protected]
16
🌻 - 2024 DAY 12 SOLUTIONS -🌻 (programming.dev)
submitted 6 days ago by [email protected] to c/[email protected]
24 comments fedilink hide all child comments
 

Day 12: Garden Groups

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

you are viewing a single comment's thread
view the rest of the comments
[–] mykl 4 points 5 days ago* (last edited 14 hours ago) (1 children)

Uiua

~~Takes about 3 seconds to solve both parts for live data, caused primarily by my terrible fill function in FieldCoords which repeatedly refills and dedups already discovered cells. I promised myself when I wrote it that I would revisit it, but I really can't be bothered right now. Sorry Kai.~~

LATE EDIT: Thanks to Quant for the inspiration to revisit this. With his code snippet and the realisation that I should normalise all fields to remove wasted space, runtime is now down to 55ms.

Data ← ⊜∘⊸≠@\n "AAAA\nBBCD\nBBCC\nEEEC"
N₄     ← [¯1_0 1_0 0_¯1 0_1]               # Four orthogonal neighbours.
Fences ← /+/+=0≡(⬚0⊡+N₄¤)⊙¤⊚.°⊚            # Fences for a field, by looking for edges.
Cs     ← [0 1 1 0 1 0 2 1 1 2 0 1 0 1 1 0] # Number of corners keyed by bitarray of 2x2 grid.
Sides  ← /+♭⬚0⧈(⊡:Cs°⋯♭)2_2°⊚              # Add border, look for corners in 2x2 windows.

# Use `classify` to find fields, then normalise to 0_0.
Fields ← ≡⍚(-¤⊸/↧)⊜□:⇡△.+1⍜♭⊛Data # Thanks to Quant!

/+×≡◇⊃⧻Fences Fields
/+×≡◇⊃⧻Sides Fields
[–] [email protected] 2 points 21 hours ago (1 children)

I found multidimensional markers for partition to work really well for finding the fields: Areas ← ⊜□:⇡△.+1⍜♭⊛ It just groups the other array's contents according to adjacent markers, horizontally and vertically. Took me quite a bit to figure out what's actually happening in the example in the documentation ^^'

[–] mykl 2 points 18 hours ago* (last edited 18 hours ago) (1 children)

Ooh, interesting, I'll have to give that a try. Thanks!

(edit) Wow, that replaced my three lines of overly complex code without a hitch. classify is an operator I never really got the point of before. Beautiful.

Data ← ⊜∘⊸≠@\n "AAAA\nBBCD\nBBCC\nEEEC"
N₄     ← [¯1_0 1_0 0_¯1 0_1]               # Four orthogonal neighbours.
Fences ← /+≡(/+=0⬚0⊡+N₄¤)⊙¤⊚.°⊚            # Fences for a field, by looking for edges.
Cs     ← [0 1 1 0 1 0 2 1 1 2 0 1 0 1 1 0] # Number of corners keyed by bitarray of 2x2 grid.
Sides  ← /+/+⧈(⊡:Cs°⋯♭)2_2⌝↘¯1_¯1⌝↘1_1°⊚   # Add border, look for corners in 2x2 windows.

Fields ← ⊜□:⇡△.+1⍜♭⊛Data

/+×≡◇⊃⧻Fences Fields
/+×≡◇⊃⧻Sides Fields
[–] [email protected] 2 points 16 hours ago (1 children)

Nice :D
How's the speed now?

[–] mykl 1 points 15 hours ago* (last edited 14 hours ago)

1.8s now. 99% of that in Sides. I've just had an idea though... ~~maybe too late for today though!~~

edit: prepending ≡⍚(-¤⊸/↧) toFields spared me from manipulating hundreds of irrelevant 0's, so time is very good now at 55ms.