Summary for those just joining us:
Advent of Code is an annual Christmas themed coding challenge that runs from December 1st until christmas. Each day the coding problems get progressively harder. We have a leaderboard and pretty good turnout, so feel free to hop in at any time and show your stuff!
Whether you have a single line monstrosity or a beautiful phone book sized stack of OOP code, you can export it in a nice little image for sharing at https://carbon.vercel.app
What did you think about today's problem?
Our Code is 2416137-393b284c (No need to share your profile, you have the option to join anonymously if you don't want us to see your github)
Jump in the discussion.
No email address required.
Still waiting on yesterday's part 2 to complete and now the flood fill is taking forever. This sucker better not hit a recursion limit.
Worked but I ended up mathmaxxing:
Jump in the discussion.
No email address required.
How long will you have to wait for that brute force![:marseysmug2: :marseysmug2:](https://i.rdrama.net/e/marseysmug2.webp)
Jump in the discussion.
No email address required.
It finished like a minute later and Pick-Shoelace took care of part 2 so![:scoot: :scoot:](https://i.rdrama.net/e/scoot.webp)
Jump in the discussion.
No email address required.
how u get area
Jump in the discussion.
No email address required.
Some big brain shit (credit definitely not mine):
Shoelace Algorithm
Pick's Theorem
You get the interior area with shoelace; there are a bunch of different versions, I did
x[i] × (y[i+1] - y[i-1])
for every
i
, so if you have14
corners you do it fori
=1
to14
inclusive. Thei+1
andi-1
bits wrap around if they go out of range,x
andy
are the corner coords. Add them all up and halve the result and that's your [interior] area. Then use Pick's to get the total area:area = 1 + <shoelace area> + (perimeter ÷ 2)
where
perimeter
is the sum of your borders.(If you read the explanation it talks about the number of dots on the perimeter, we're viewing it as there being a dot in the centre of every pixel, but it works out as just adding the lengths)
Jump in the discussion.
No email address required.
Okay so I am a midwit, but why do u need Pick's Theorem if Shoelace gives you the area?
Jump in the discussion.
No email address required.
Shoelace gives you the number of unit squares in the polygon, when you need the number of integer points in or on it.
For example: a 2x4 rectangle has an area of 8, but contains 15 integer points.
Jump in the discussion.
No email address required.
More options
Context
Area != #integer points inside.
Easiest example is the unit square. It has 4 integer points inside (the corners), but an area of only 1.
Jump in the discussion.
No email address required.
More options
Context
Shoelace gives the area of a slightly different shape. Put a dot at the centre of each pixel, draw infinitely thin lines connecting them - the original border shrunk half a pixel in every direction. Pick's takes this area and factors in the missing half-pixel border area.
Specifically Pick's says
I = A - B/2 + 1
, whereI
is the number of dots inside the shoelace shape (or the total interior pixel count),A
is the shoelace area (no intuitive pixel equivalent, but can calc from pixel corner coords), andB
is the perimeter of the shoelace shape (or the pixel count of the border).Since the AoC question includes the border pixels, you add another
B
and you haveans = A + B/2 + 1
, whereA
is shoelace andB
is perimeter.Jump in the discussion.
No email address required.
More options
Context
More options
Context
More options
Context
More options
Context
More options
Context
More options
Context
More options
Context