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 inFieldCoordswhich 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 FieldsI 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.
classifyis 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 FieldsNice :D
How’s the speed now?
1.8s now. 99% of that in
Sides. I’ve just had an idea though…maybe too late for today though!edit: prepending
≡⍚(-¤⊸/↧)toFieldsspared me from manipulating hundreds of irrelevant 0’s, so time is very good now at 55ms.Damn that’s a lot time saved. I love how unassuming the addition looks for how great an effect it has
It was a real D’oh! moment when I visualised the data I was generating and saw all the zeros stretching across the page.