This part 2 really ended me. I realized early on (relatively speaking) that I had to do the ray casting thing, but when my first attempt didn't work, I got in my head that I had to do a horizontal and a vertical ray and then only consider the points that are in both. I wasted hours on that. This insight to only consider the 'F' and '7' corners really saved me. This works because if you intersect a horizontal section of the pipe and go from outside to inside or vice versa, it has to be either FJ (going up towards the right) or L7 (going down towards the right), so you only count one of the corners and change the in/out state. On the other hand if you intersect a U-shaped section of the path, it will be either LJ (upright U) or F7 (upside down U), so you either count both corners or neither, and it doesn't change the in/out state.
Ah right. Because an s shaped joint means you're crossing over while a u means you end up on the same side. That makes sense. Today's was definitely my longest solve+video so far.
The other way to consider this property is if you shift the ray down by like a fraction of a unit, then the ray will intersect with the pipe pieces slightly below the midpoint, which means it'll never interesct with the -, L and J pieces, since those are all above the midpoint, and thus you only have to consider the |, F and 7 pieces, and now you're back to the easy version of the problem were every intersection you run into is purely vertical (since you hit hit the vertical pieces of the F and 7 pieces too).
That assumption is always valid. Every move is one grid space up or down. To get back to Start, you have to make the opposite one-unit move at some point. The description helpfully reminds us that the distance is the same, no matter which way you get to the furthest point. If there were diagonals, and they counted as one move, then it would be harder.
Unicode has a set of “box drawing” characters that include horizontal and vertical lines going through the center of the character, corners, and tees. I replaced part of my input with those characters, just to make sure I was understanding how pipes connected. It was much easier to look at because the lines all aligned.
For part 2, I decided to construct a new grid “zoomed in” by a factor of 2, so it contained the original integer-valued coordinates, plus integers+0.5. I traced the shape of the loop into this new grid. Then I started at a point outside the original bounds, and did a depth first search to find everything reachable. The unmarked points at integer coordinates are the “inside”; just count them up. To avoid having to constantly check bounds, I created a margin of two spaces around the “zoomed in” grid. The outer edge got marked as “not inside”. I started my search just inside that outer border (between it and the original pipe grid). Shockingly, it worked on the first try.
In pip_line it's incorrect to count 'S' as 'crossing'. You should substitute 'S' with the correct pipe to finish the loop. After that it will work as it should.
For the crossing I ended up considering vertical crossings as "when do you have both up and down" as a "cross the line". So if you see a | you have a clear crossing (up and down), however if you see a └ then the next one would be either ┐ in which case you have a crossing (up and down) or ┘ in which case you do not have a crossing (the line goes back up, so nothing crosses over). Same with ┌ and either ┘ or ┐ following. For the scan algorithm then you have "up" and "down" as separate bools, if both are true you are inside, if one of then is true you are in a pipe (waiting for the next corner), if both are false you are outside. maybe this explanation helps.
The reason your grouping works (F is ┌ and 7 is ┐): these always come in pairs. so you are counting any ┌ followed by ┘ (nothing undoes the F) and the ┐ undoes a previous ┌ or does not undo (but triggers) a previous z . ┌┘ => count + 1 (due start F, did not count J) ┌┐=> count + 2 (both F and 7) └┐=> count + 1 (due to end 7, did not count start L) └┘ => count (you did not count J or L) It is guaranteed to work because they are paired, however I find it hard to reason about it in that way... kept my code tracking up and down separately.
For part 2 (Spoilers): I modified my output of 1 to create an ordered list of pipe segments that would create a loop. I then traveled around the loop. Keeping track of the number of Left and Right turns I was able to determine if it was going Clockwise or Counter Clockwise. At each step of the way I would make note of the Right and Left tile coordinates (before and after turns). If the loop was traveled Clockwise then all right side tiles mark Interior Regions. If it was Counter Clockwise, then all Left tiles were interior. All that was needed after that was to check all the neighbors of my "Inside" tiles and fill in the ones that were not already accounted for, or part of the pipe, and add them to the count.
For part 2 I replaced the starting tile with the actual pipe, moved once through the loop to remember grid positions belonging to the loop, then replaced all unconnected pipes with ground. Then from the outermost border of the grid I filled in all connected ground tiles with an "outside" marker. This leaves some pockets of ground that are not directly connected, but should still be considered "outside", as in one of the later examples. To get those, I picked a new start position in the loop that is close to a border and thus touches a tile marked "outside". As a direction I picked the where "outside" is on the left, at this new starting position with respect to the direction. Then I did another run around the loop, while always marking the left area of the current tile as "outside" (and anything connected to those). Note that right turns have two tiles on the left of the path, one when considering the entry direction, and another when considering the exit direction. Took me hours to solve, but happy to have got it.
Part2 can be solved by applying the shoelace algorithm and Pick's theorem. The shoelace algorithm gives an area enclosed by the loop which Pick's theorem relates to the enclosed tiles, if the enclosing polygon has only coordinates that are natural numbers, which is the case here.
what I did for part two was traverse the pipe once from a single direction and then mark every tile not part of the main pipe as either left or right since each tile can only be one since the it's a non intersecting closed loop, I then expanded out the left and right tiles to any adjacent non loop tiles and got two areas one for inside and one for outside. Then I checked if one of the sides had ever touched the edge of the grid, and if one did then that side needs to be the outside half. If it never touched the edge I checked which area contained points that are touching the edge which would be the outside. All in all one of the harder days I think.
I did the same as this but got hung up on the corners needing to be marked in/out on two edges. Eventually found it with gruesome amounts print and finally finding the difference of all marked squares and that left 10 that had escaped and got it from there. Curious if you had any trouble with corners or handled it some other way?
@@chrismitchelmore9379 I created a bunch of enums and a function that mapped a pipe tile and a source direction into the left tiles (if any) and the right tiles (if any) was very verbose but it was all just about intuiting what would count as left and right while traversing the plane
I started solving this one very late, and knew I was in for a challenge when I saw the length of this video in my feed. Part 1 was not bad, took me a bit to handle all the direction detections but thats entirely because I operated on the raw string the whole time. Part 2 was quite hard, it was immediately obvious I needed this ray algorithm but the U corners stomped me. I ended up with a much more complicated ruleset and Im mad i couldn't figure out this one. I saved the last L/F and counted 7/J based on what was saved. Also, your rule for S only works by chance here, in my solution i recovered the original pipe behind it before starting the rest of the part 2 calculations.
Comment contains part 2 spoilers. I actually didnt use the jordan curve theorem, because I thought that calculating the interseciton of thousands of lines with a ray would be annoying to code and would take long. Instead, I expanded the grid so that each original symbol is actually 3x3 square: - becomes --- F becomes F- | and so on. In this new grid, you can just floodfill and it goes through the small spaces between pipes. Then, just count up the # of unfilled, "real" (not added) squares and you are done.
For the PIP algorithm, you could traverse the map diagonally to avoid having a pipe on an edge. Otherwise, the algorithm should also work if you ignore F, and 7 and consider crossing the edge for L and J. I really enjoy following your videos. It's funny to see the different approaches to the same problem: I would have went for a flood fill algorithm on part one starting for S. Pushing positions at the back of a deque with a minimum number of positions from S.
Part 1 was OK but part 2... really hard to figure out. Nice video though, I was on the right track but not as fluent in graphics algorithms unfortunately
L, J, and - are NOT crossings, they are edges (yeah I know I’m incredibly late to the party with this comment but I didn’t see it posted already). So because you are calculating horizontally, those don’t “count”. If you were traversing vertically for some reason, then |, F, and 7 would be the edges and not a crossing.
Before starting this I spent the longest time finding better characters to represent the pipe types '\u2503', ┃ '\u2501', // ━ '\u250F', ┏ '\u2513', ┓ '\u2517', ┗ '\u251B', ┛
This part 2 really ended me. I realized early on (relatively speaking) that I had to do the ray casting thing, but when my first attempt didn't work, I got in my head that I had to do a horizontal and a vertical ray and then only consider the points that are in both. I wasted hours on that.
This insight to only consider the 'F' and '7' corners really saved me. This works because if you intersect a horizontal section of the pipe and go from outside to inside or vice versa, it has to be either FJ (going up towards the right) or L7 (going down towards the right), so you only count one of the corners and change the in/out state. On the other hand if you intersect a U-shaped section of the path, it will be either LJ (upright U) or F7 (upside down U), so you either count both corners or neither, and it doesn't change the in/out state.
Ah right. Because an s shaped joint means you're crossing over while a u means you end up on the same side. That makes sense.
Today's was definitely my longest solve+video so far.
The other way to consider this property is if you shift the ray down by like a fraction of a unit, then the ray will intersect with the pipe pieces slightly below the midpoint, which means it'll never interesct with the -, L and J pieces, since those are all above the midpoint, and thus you only have to consider the |, F and 7 pieces, and now you're back to the easy version of the problem were every intersection you run into is purely vertical (since you hit hit the vertical pieces of the F and 7 pieces too).
I just made the assumption that my pipe in part 1 was even and just counted all pipe segments and divided by 2 to get the furthest point way
That assumption is always valid. Every move is one grid space up or down. To get back to Start, you have to make the opposite one-unit move at some point. The description helpfully reminds us that the distance is the same, no matter which way you get to the furthest point. If there were diagonals, and they counted as one move, then it would be harder.
I did it that way too
Unicode has a set of “box drawing” characters that include horizontal and vertical lines going through the center of the character, corners, and tees. I replaced part of my input with those characters, just to make sure I was understanding how pipes connected. It was much easier to look at because the lines all aligned.
Absolutely this. I implemented that as a method on my PipeType enum that I called to_box_drawing_char.
For part 2, I decided to construct a new grid “zoomed in” by a factor of 2, so it contained the original integer-valued coordinates, plus integers+0.5. I traced the shape of the loop into this new grid. Then I started at a point outside the original bounds, and did a depth first search to find everything reachable. The unmarked points at integer coordinates are the “inside”; just count them up.
To avoid having to constantly check bounds, I created a margin of two spaces around the “zoomed in” grid. The outer edge got marked as “not inside”. I started my search just inside that outer border (between it and the original pipe grid).
Shockingly, it worked on the first try.
I'm truly enjoying your series and and learning so many tricks from you. Thank you!
In pip_line it's incorrect to count 'S' as 'crossing'. You should substitute 'S' with the correct pipe to finish the loop. After that it will work as it should.
Ah yeah that makes sense. I wonder how many inputs have S that doesn't count.
Ah, I missed that! I got lucky with my input.
For the crossing I ended up considering vertical crossings as "when do you have both up and down" as a "cross the line". So if you see a | you have a clear crossing (up and down), however if you see a └ then the next one would be either ┐ in which case you have a crossing (up and down) or ┘ in which case you do not have a crossing (the line goes back up, so nothing crosses over). Same with ┌ and either ┘ or ┐ following.
For the scan algorithm then you have "up" and "down" as separate bools, if both are true you are inside, if one of then is true you are in a pipe (waiting for the next corner), if both are false you are outside.
maybe this explanation helps.
The reason your grouping works (F is ┌ and 7 is ┐): these always come in pairs. so you are counting any ┌ followed by ┘ (nothing undoes the F) and the ┐ undoes a previous ┌ or does not undo (but triggers) a previous z .
┌┘ => count + 1 (due start F, did not count J)
┌┐=> count + 2 (both F and 7)
└┐=> count + 1 (due to end 7, did not count start L)
└┘ => count (you did not count J or L)
It is guaranteed to work because they are paired, however I find it hard to reason about it in that way... kept my code tracking up and down separately.
For part 2 (Spoilers):
I modified my output of 1 to create an ordered list of pipe segments that would create a loop. I then traveled around the loop. Keeping track of the number of Left and Right turns I was able to determine if it was going Clockwise or Counter Clockwise. At each step of the way I would make note of the Right and Left tile coordinates (before and after turns). If the loop was traveled Clockwise then all right side tiles mark Interior Regions. If it was Counter Clockwise, then all Left tiles were interior. All that was needed after that was to check all the neighbors of my "Inside" tiles and fill in the ones that were not already accounted for, or part of the pipe, and add them to the count.
For part 2 I replaced the starting tile with the actual pipe, moved once through the loop to remember grid positions belonging to the loop, then replaced all unconnected pipes with ground. Then from the outermost border of the grid I filled in all connected ground tiles with an "outside" marker. This leaves some pockets of ground that are not directly connected, but should still be considered "outside", as in one of the later examples.
To get those, I picked a new start position in the loop that is close to a border and thus touches a tile marked "outside". As a direction I picked the where "outside" is on the left, at this new starting position with respect to the direction. Then I did another run around the loop, while always marking the left area of the current tile as "outside" (and anything connected to those). Note that right turns have two tiles on the left of the path, one when considering the entry direction, and another when considering the exit direction.
Took me hours to solve, but happy to have got it.
Part2 can be solved by applying the shoelace algorithm and Pick's theorem. The shoelace algorithm gives an area enclosed by the loop which Pick's theorem relates to the enclosed tiles, if the enclosing polygon has only coordinates that are natural numbers, which is the case here.
what I did for part two was traverse the pipe once from a single direction and then mark every tile not part of the main pipe as either left or right since each tile can only be one since the it's a non intersecting closed loop, I then expanded out the left and right tiles to any adjacent non loop tiles and got two areas one for inside and one for outside.
Then I checked if one of the sides had ever touched the edge of the grid, and if one did then that side needs to be the outside half.
If it never touched the edge I checked which area contained points that are touching the edge which would be the outside.
All in all one of the harder days I think.
I did the same as this but got hung up on the corners needing to be marked in/out on two edges. Eventually found it with gruesome amounts print and finally finding the difference of all marked squares and that left 10 that had escaped and got it from there.
Curious if you had any trouble with corners or handled it some other way?
@@chrismitchelmore9379 I created a bunch of enums and a function that mapped a pipe tile and a source direction into the left tiles (if any) and the right tiles (if any) was very verbose but it was all just about intuiting what would count as left and right while traversing the plane
Nice I did something similar, but checked if I went clockwise or counterclockwise to know which side was in the loop.
I started solving this one very late, and knew I was in for a challenge when I saw the length of this video in my feed.
Part 1 was not bad, took me a bit to handle all the direction detections but thats entirely because I operated on the raw string the whole time.
Part 2 was quite hard, it was immediately obvious I needed this ray algorithm but the U corners stomped me.
I ended up with a much more complicated ruleset and Im mad i couldn't figure out this one.
I saved the last L/F and counted 7/J based on what was saved.
Also, your rule for S only works by chance here, in my solution i recovered the original pipe behind it before starting the rest of the part 2 calculations.
yeah, S needs to be replaced with the appropriate joint for a "full" solution that doesn't somewhat accidentally work.
Comment contains part 2 spoilers.
I actually didnt use the jordan curve theorem, because I thought that calculating the interseciton of thousands of lines with a ray would be annoying to code and would take long. Instead, I expanded the grid so that each original symbol is actually 3x3 square:
- becomes ---
F becomes
F-
|
and so on.
In this new grid, you can just floodfill and it goes through the small spaces between pipes. Then, just count up the # of unfilled, "real" (not added) squares and you are done.
wouldn't a 2x2 square be enough?
For the PIP algorithm, you could traverse the map diagonally to avoid having a pipe on an edge. Otherwise, the algorithm should also work if you ignore F, and 7 and consider crossing the edge for L and J.
I really enjoy following your videos. It's funny to see the different approaches to the same problem: I would have went for a flood fill algorithm on part one starting for S. Pushing positions at the back of a deque with a minimum number of positions from S.
Ah diagonally! That would've made a lot of sense!
I probably would've ended up flood filling too if I hadn't remembered pip could apply.
Part 1 was OK but part 2... really hard to figure out. Nice video though, I was on the right track but not as fluent in graphics algorithms unfortunately
L, J, and - are NOT crossings, they are edges (yeah I know I’m incredibly late to the party with this comment but I didn’t see it posted already). So because you are calculating horizontally, those don’t “count”. If you were traversing vertically for some reason, then |, F, and 7 would be the edges and not a crossing.
Before starting this I spent the longest time finding better characters to represent the pipe types
'\u2503', ┃
'\u2501', // ━
'\u250F', ┏
'\u2513', ┓
'\u2517', ┗
'\u251B', ┛
Part 2 refers to Point in Polygon, see en.m.wikipedia.org/wiki/Point_in_polygon