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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
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
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 ^^’
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
