Advent of Code 2023 Day 18: Lavaduct Lagoon

แชร์
ฝัง
  • เผยแพร่เมื่อ 5 ธ.ค. 2024

ความคิดเห็น • 38

  • @DannyvanKooten
    @DannyvanKooten 11 หลายเดือนก่อน +13

    Nice. Loved your explanation of Pick's theorem. I kind of stumbled upon it by accident. Was using shoe-lace for the area, but noticed it was off by close to half the line length (boundary points), then played around with it and noticed subtracting half resulted in an off-by one error. Added the 1 and tada, accidental Pick's Theorem, haha.

    • @yordiverkroost
      @yordiverkroost 11 หลายเดือนก่อน +1

      Exactly my path to the solution as well. 😊

  • @amar-vt6wr
    @amar-vt6wr 11 หลายเดือนก่อน +2

    I didn't know about Shoelace formula, this makes it so much simpler. I used flood fill to get the first part, but just kinda gave up on part 2. Anyway, glad I learned something new.

  • @olatrials
    @olatrials 11 หลายเดือนก่อน +3

    At around 3:05 you mention that it's not easy to add the extra half block width around the perimeter because of the inwards/outwards turns and how they add/remove quarter blocks. I would turn it around and say that's exactly what makes this easy! At least that's what intuitively gave me my solution. As there will always be exactly four more inwards turns (because it's a loop), these add up to exactly one extra block, and the rest of the extra width is just perimeter divided in half, because we only want to add a half block of width. So we still end up at shoelace area + (perimeter / 2) + 1 intuitively without even having to know about Pick's!

    • @hyper-neutrino
      @hyper-neutrino  11 หลายเดือนก่อน +1

      Yep, good observation! I should've noticed this from my formula as i + b = A - b/2 + 1 + b is just A + b/2 + 1, lol. I will have to revisit that in my stream as it makes the need for Pick's Theorem obsolete here, and one less thing we need to rely on is always better. But I suppose knowing it never hurts!

    • @Volganian
      @Volganian 11 หลายเดือนก่อน +1

      Did the same, because I just felt that all the corners will have an opposite, given that this is a loop. I've tried perimeter / 2 + 1 and that was it.

  • @fedora-p5w
    @fedora-p5w 11 หลายเดือนก่อน +1

    I arrived at Pick's by noticing that for a square the area of "half cells" is (Po-4)/2 + 1 and Po = Pi + 4 (P=Perimeter, i=inner, o=outer). Intuitively it works for any shape on a grid.
    So the area we need to add is Pi/2 + 1.
    We get A + b/2 + 1 which is the same as A - b/2 + 1 + b

  • @eavdmeer
    @eavdmeer 11 หลายเดือนก่อน

    Today, I definitely learned something!

  • @turbogamerxd329
    @turbogamerxd329 11 หลายเดือนก่อน +1

    This was again a great video!
    I unfortunately don't know all these formulas (well I'm a first semester Computer Engineering student) so I have to simulate and thus brutforce most stuff (which sometimes isn't viable) and I also have problems recognizing recursivity in problems.
    But this problem was the hardest yet I was able of solving on my own. Part 1 was pretty easy to simulate but for Part 2 I has to redo almost everything of my code but I was able to write a script that needs 55s to calculate the result (on an i9-12900H).
    Until now I needed inspiration for the problems for the days 5, 12 and 17. For each of them I watched you video on it until I thought I was able to form an approach for the problem.
    For days 5 and 12 I needed help with part 2, on day 17 I only needed help with part 1 and was able to modify the code to calculate part 2. In contrast to your solution I didn't check if the crucible already made 4 movements in the same direction before it was allowed to turn again but had it 'jump' those 4 required movements. This needed some more maths on getting the correct heatloss but at least I got the solution.
    So yeah thanks for the great videos!

    • @code-kiwi
      @code-kiwi 11 หลายเดือนก่อน

      I could have written your message.
      Personally, I'm always surprised by the speed and brevity of solutions proposed by more experienced people.
      It's sometimes frustrating to see that I've spent six hours trying to solve a problem on my own, writing hundreds of lines of code, while some people could solve it in ten lines written with a cup of coffee in one hand and petting their cat with the other 😸

    • @raidensama1511
      @raidensama1511 11 หลายเดือนก่อน +1

      Remember for most of the AOC problems there will be some math equation that will help. It’s just a matter of finding the right equation.

  • @sourishsharma17
    @sourishsharma17 11 หลายเดือนก่อน +1

    Epic video (as usual)! This series is great for upping my skills, defo the best AoC YTber out there (and I'm subbed to practically all of them).
    One question - in what situations would a complex number representation of coords be better?

    • @hyper-neutrino
      @hyper-neutrino  11 หลายเดือนก่อน +1

      I find complex numbers to only really be useful when your primary usage of the coordinates is just the numerical values and you need to do a lot of translations/rotations. If you're mostly using them as indexes on a grid, the conversion is usually more inconvenient.

  • @plizbeavailable
    @plizbeavailable 11 หลายเดือนก่อน

    Really clean solution - thank so much for the explanation. However, I notice that your code in git hub does not have any comments to refer to these theorem (pick's and shoelace); I thought it might be a good addition to an already lean mean solution (I know it would help me a lot).

  • @TheWoodinator
    @TheWoodinator 11 หลายเดือนก่อน

    Really intersting one.. loving watching these each day

  • @gima123123
    @gima123123 11 หลายเดือนก่อน

    At 2:42 You say we can't apply sholace theorem directly. How did you arrive at this conclusion? I got lost for multiple hours with this. Was there something in the excercise description that gave you a hint? I was thinking of coordinates as lines or that what is it to say that they go trough the middle of the squares not outher border? I'm so confused how people get to this conclusion, though I saw others commenting they stubled on this by trying random outputs instead of realising this as you did. Any comments on this highly appreciated! Keep up the nice videos :)

    • @hyper-neutrino
      @hyper-neutrino  11 หลายเดือนก่อน +1

      I have experience with grid problems and know by intuition that representing cells as points has the issue that the points lie in the center of the cell and your boundary path may not line up nicely with the resulting blocks' boundary. Not sure how to explain I'd come to this conclusion though :P but basically I just have experience and know that the perimeter would go through the middle of the boundary instead of around the outside of the boundary itself.

  • @BlazzaBlu
    @BlazzaBlu 11 หลายเดือนก่อน

    Looks like I'm going to have to rely on your videos every day from now on... I struggled for a while with the shoelace theory after watching your example, because of differences in language (I'm using my companies own language which is based on uniBASIC and not familiar with Python) I was getting the absolute value of every step in the loop, instead of adding it all together and getting the absolute value of the total.
    Nice that it still calculated in 0.06 seconds, as opposed to yesterday's solution that's been running for about 3 hours now...

    • @hyper-neutrino
      @hyper-neutrino  11 หลายเดือนก่อน +1

      The intuition behind shoelace formula is that for each edge, we can draw lines down from both endpoints to the x axis to get a trapezoid. Then, each positive component is where the edge is "going right" and when the edge is "going left", we need to subtract the area under the shape so we get a negative component. Hopefully that makes why it's important that some components are negative and you take the absolute value of the final result more intuitive!

    • @BlazzaBlu
      @BlazzaBlu 11 หลายเดือนก่อน

      @@hyper-neutrino yeah, my part 1 iteration I ran through the coords first to get max and min x and y values, then made the starting point the absolute values of the minimum (+1) and the total width and height would become the max + abs(min). I could visualize that there must be something *like* the shoelace formula to calculate the area, but didn't know the name and sure as hell couldn't work it out for myself 🤣
      Now, if only I can solve day 17...

  • @myththelegendtyson
    @myththelegendtyson 11 หลายเดือนก่อน +3

    I love these videos man. Would you mind letting me know how you make your VScode look like that, it looks epic.

    • @hyper-neutrino
      @hyper-neutrino  11 หลายเดือนก่อน

      My font is Monaspace Radon and I'm using the GitHub Dark theme with the Material icon theme

  • @dylans8786
    @dylans8786 11 หลายเดือนก่อน +1

    What you are calling the shoelace theorem is a special case of Green’s Thereom from multi variable calculus. Let L=0 and M = x.
    en.wikipedia.org/wiki/Green's_theorem?wprov=sfti1#

    • @hyper-neutrino
      @hyper-neutrino  11 หลายเดือนก่อน +1

      Oh, that's interesting!

    • @dylans8786
      @dylans8786 11 หลายเดือนก่อน

      @@hyper-neutrino Green’s theorem equates the double integral inside a simple closed curve to a line integral around it. It is really a two dimensional analogue of the fundamental theorem of calculus.

  • @rastislavsvoboda4363
    @rastislavsvoboda4363 11 หลายเดือนก่อน +2

    amazing|
    for P1 I did flood fill
    for P2 I stored intervals of trenches per row and computed if I'm inside or outside
    it computes for 30 sec ;-0

    • @BlazzaBlu
      @BlazzaBlu 11 หลายเดือนก่อน

      Same for part 1, but for part 2 I almost instantly ran out of memory just trying to calculate the outline 😅

    • @juan-tj1xf
      @juan-tj1xf 11 หลายเดือนก่อน

      how to compute if it is inside or outside?

    • @BlazzaBlu
      @BlazzaBlu 11 หลายเดือนก่อน

      @@juan-tj1xf keep track of direction of travel, when you're going up, the tile to your left will be inside, the tile on your right will be outside. Or opposite if you're going anti-clockwise. When you do flood fill you'll be able to tell of you got it backwards or not based on if the tiles on the edge of your grid are marked as inside or outside

    • @rastislavsvoboda4363
      @rastislavsvoboda4363 11 หลายเดือนก่อน

      @@juan-tj1xf
      so I store for row r data where trenches are, for example [(10,11), (15,20), (30,31)]
      inclusive start, exclusive end
      now for each row you start with is_inside = False
      you add 11-10
      and now you compute if there is a cross (usually first and last interval - is crossed) bug generally
      trenches are continuous, so there will be exactly 2 continuations either both on row-1 or both on row+1 or one on r-1 and one on r+1
      if there is a cross, you negate is_inside
      you store end of previous interval
      you proceed to next interval
      if you are inside, you add interval_start - prev_interval_end
      for rr in range(min_r, max_r + 1):
      intervals = sorted(ROWS[rr])
      prev_e = None
      # starting outside
      is_inside = False
      for (s, e) in intervals:
      # has it dig above at the range start/end?
      has_up = is_set(s, ROWS[rr - 1]) or is_set(e - 1, ROWS[rr - 1])
      # has it dig bellow at the range start/end?
      has_down = is_set(s, ROWS[rr + 1]) or is_set(e - 1, ROWS[rr + 1])
      # it is crossing if dig "continues" above and bellow
      is_cross = has_up and has_down
      if prev_e is not None and is_inside:
      # if we are inside, count also from previous interval end to this start pos
      res += s - prev_e
      # add count for this interval from start (inclusive) to end (exclusive)
      res += e - s
      prev_e = e
      if is_cross:
      # flip flag if we crossed
      is_inside = not is_inside

    • @rastislavsvoboda4363
      @rastislavsvoboda4363 11 หลายเดือนก่อน

      2 continuations I mean where horizontal dig starts and ends
      if it is just 1m wide, it is "same" spot, here you see some possible arrangements
      top 2 "are crossing", bottom 2 are not (at row with xxx)
      x
      x
      x
      x
      xxx
      x
      x x
      xxx
      xxx
      x x

  • @CAG2
    @CAG2 11 หลายเดือนก่อน

    I didn't know about either of the formulas/theorems unfortunately... but I managed to solve part 2 using coordinate compression

  • @枯萎の花
    @枯萎の花 11 หลายเดือนก่อน +1

    Again, shoelace and pick win this battle!

  • @keving9440
    @keving9440 11 หลายเดือนก่อน

    First of all thank you for your explantions. It helped me a lot.
    Now to the confusing part: I tried to reimplement your Python code for part 1 in Golang.
    But it gave me a different solution on the real input, so I was sure that my code is wrong. My code gave me a total of 68115 and not 35991. But then, I ran your python code and got the same result of 68115. And even more confusing, it was correct and gave me a star on aoc website. So what's going on here?
    Do they change input after some time?

    • @hyper-neutrino
      @hyper-neutrino  11 หลายเดือนก่อน +1

      Different users have different inputs

    • @keving9440
      @keving9440 11 หลายเดือนก่อน

      @@hyper-neutrino Ah interesting. Didn't know that. Thanks.

  • @benjaminwurmli3341
    @benjaminwurmli3341 11 หลายเดือนก่อน