Unable to load image

rDrama Advent of Code Day 18: Network Engineering Edition

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?

https://adventofcode.com/2023

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)

36
Jump in the discussion.

No email address required.

https://files.catbox.moe/fhyl9h.jpg

https://files.catbox.moe/btjujo.jpg

my best result ever, shoutout to whoever mentioned point in polygon a couple days ago, I just import solution'd and it runs instantly. I didn't even figure out why the area calculation was off until after I finished, I just subtracted my calculated area from the provided example's correct answer, and saw that it was about half the perimeter's length. For p1 I didn't even figure that out, I iterated across every integer coordinate in the bounding rectangle and summed whether they were inside the polygon, then added that to the perimeter length lmfao

there's still hope, fellow brainlets

Jump in the discussion.

No email address required.

>shoutout to whoever mentioned point in polygon a couple days ago

:marseywav#e2:

Jump in the discussion.

No email address required.

>I iterated across every integer coordinate in the bounding rectangle and summed whether they were inside the polygon

how

can u post code

Jump in the discussion.

No email address required.

Posting code on a mobile is painful, but here's the process:

>Generate coordinate tuple list for the polygon's sides

>Make shapely polygon object from list

>For each xy on the grid make a shapely Point object

>Call polygon.contains(point) to figure out if it's inside. Count positives for the area in pixels

Of course that's retarded and won't work for Part 2, so just use the proper theorum of polygon area + half polygon perimeter +1 to convert geometry based area to touched pixels

Jump in the discussion.

No email address required.

>tfw you realize that the distances are sufficiently small to brute force with your less-than-optimal algorithim

:marseysmu#g:

Jump in the discussion.

No email address required.

Part 1 - N*N grid plus floodfill

Part 2 - :marseycry: and searching for area of irregular polygon formula which ends up being 10x simpler than the dumb way

https://i.rdrama.net/images/17028934351863134.webp

Jump in the discussion.

No email address required.

I did part 1 the basic way, but I was :marseybrainlet: for part 2 and forgot

a. The need to use Pick's Thm

b. The name of Pick's Thm

https://i.rdrama.net/images/17028798975794928.webp

Jump in the discussion.

No email address required.

I solved it without using any theorems. :marseyking:

Jump in the discussion.

No email address required.

I didn't even know about Pick's theorem until today. Neat :marseyneat:

https://i.rdrama.net/images/17029360647746112.webp

Jump in the discussion.

No email address required.

What language is that?

Jump in the discussion.

No email address required.

>Oh this is basically an exercise in knowing the shoelace formula

>Spend hours debugging until realizing it's only calculating the inside area and not the perimeter squares :marseyfacepalm:

https://i.rdrama.net/images/17029343767189593.webp

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:

⎕PP←20
r←' '(≠⊆⊢)¨⊃⎕NGET'18.in'1
d←(0 1)(1 0)(0 ¯1)(¯1 0)
N←≢l←⍎¨2⊃¨r
c←+\l×{d⊃⍨'RDLU'⍳⊃⍵}¨r
A←{(2÷⍨+/⍺)+1+2÷⍨|+/⍵∘{i j←1+(≢⍺)|0 ¯2+⍵ ⋄ 2⊃⍵⊃⍺×(1⊃j⊃⍺)-1⊃i⊃⍺}¨⍳≢⍵}
⎕←l A c
N←≢l←{16⊥¯1+⍵⍳⍨⎕D,⎕C⎕A}¨(⊂2+⍳5)∘⌷¨3⊃¨r
c←+\l×{d⊃⍨1+⍎2⊃⌽3⊃⍵}¨r
⎕←l A c
Jump in the discussion.

No email address required.

How long will you have to wait for that brute force :marseysmug2:

Jump in the discussion.

No email address required.

It finished like a minute later and Pick-Shoelace took care of part 2 so :scoot:

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 have 14 corners you do it for i=1 to 14 inclusive. The i+1 and i-1 bits wrap around if they go out of range, x and y 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.

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.

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, where I 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), and B 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 have ans = A + B/2 + 1, where A is shoelace and B is perimeter.

Jump in the discussion.

No email address required.

can someone please explain to me how to get the friggen area ??

https://i.rdrama.net/images/1702915550489999.webp

This may be like the 3rd or 2nd time I've hit a brick wall for these puzzles because idfk how to get the area.

I have it so I get a padding on all four edges bcuz I thought it would help me somehow but I can't wrap my head around how to do this with just if and for loops.

Jump in the discussion.

No email address required.

Jump in the discussion.

No email address required.

Never heard of this, neato

Jump in the discussion.

No email address required.

I'll try understanding this.

I guess what I really want to know, is how can I check to see whether an arbitrary point A and B situated within the enclosure is unobstructed.

e: or alternatively, if the paint bucket tool was used on the enclosure, or if the enclosure were filled with a pixel-like liquid.

e: if I start from a known outside and given that the only consecutive #'s are horizontal, I can verify that I am inside of the loop by shooting a beam until I get a # immediately followed by a . as when it's a vertical, and I'd be on the inside of the enclosure.

Jump in the discussion.

No email address required.

Once you know the area, the answer easily follows from https://en.wikipedia.org/wiki/Pick%27s_theorem

Jump in the discussion.

No email address required.

Jump in the discussion.

No email address required.

Link copied to clipboard
Action successful!
Error, please refresh the page and try again.