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.
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.
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!
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!
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
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).
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?
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.
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 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.
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!
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 😸
@@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
@@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
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
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 :)
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.
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...
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!
@@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...
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?
![[LIVE] : ONE ลุมพินี 90 | คู่เอก "ก้องไกล vs แอนตาร์"](http://i.ytimg.com/vi/VugIvOstzRI/mqdefault.jpg)
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.
Exactly my path to the solution as well. 😊
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.
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!
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!
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.
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
Really intersting one.. loving watching these each day
Today, I definitely learned something!
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).
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?
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.
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#
Oh, that's interesting!
@@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.
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!
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 😸
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.
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
Same for part 1, but for part 2 I almost instantly ran out of memory just trying to calculate the outline 😅
how to compute if it is inside or outside?
@@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
@@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
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
I love these videos man. Would you mind letting me know how you make your VScode look like that, it looks epic.
My font is Monaspace Radon and I'm using the GitHub Dark theme with the Material icon theme
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 :)
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.
I didn't know about either of the formulas/theorems unfortunately... but I managed to solve part 2 using coordinate compression
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...
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!
@@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...
Again, shoelace and pick win this battle!
❤
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?
Different users have different inputs
@@hyper-neutrino Ah interesting. Didn't know that. Thanks.