https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 10> :thread:
# advent-of-code
a
m
I'm not sure my approach is the best but it worked. 😄
j
I'm still struggeling with part2
m
Part 1
Got a lot of mileage from my pre-made geometry code like 
Point
, 
Direction
, and their methods.
Part 2
🙌 1
j
What does the move and reverse function look like, would you like to share?
j
Stokes Theorem to the rescue 🙂
j
Oh man for part2 I messed up the 3x3 expansion
j
Same, I had a bug in my expansion code and took me an hour to find out why my resulting map looked so strange. Then you change one +1 and everything just works 😅
n
Stokes Theorem to the rescue 🙂
I just googled that. Suffice it to say that neither Mr. Stokes nor his theorem will be coming to my rescue any time soon. My knight in shining armor (BFS) was slow to arrive (750ms) and has a bad case of acne (spaghetti code), but he did (eventually) slay the dragon.
m
f
hey! You guessed it! @Olaf Gottschalk 😉 #maze
j
after parsing (which is boring) and getting the list of all moves, the only hard part was to figure out how to remove pipes. The rest is a very simplified Stokes, and it’s not the first time it’s been useful in AoC :)
stokes.kt
d
That was a fun one
I just projected the path into a double-sized space, and filled from (-1, -1)
then counted lattice points not in the fill or the path
need to clean up the code
p
This was surprisingly hard for me. My approach was: 1. find the loop a. This was working nicely on the test input but caused a stack overflow on the real input. b. First time in my career that I had to make something tailrec 2. Iterate over all points of the bounding square. a. Filter out the loop points b. Learn about raycasting 🙈 c. https://en.wikipedia.org/wiki/Ray_casting d. Let chatGPT generate a bunch of test cases e. https://github.com/PaulWoitaschek/AdventOfCode/blob/07e62d40186db7733c326cd063afc56233a3d70d/library/src/test/kotlin/aoc/library/PointTest.kt#L[…]92 Solution https://github.com/PaulWoitaschek/AdventOfCode/blob/07e62d40186db7733c326cd063afc56233a3d70d/2023/src/main/kotlin/aoc/year2023/Day10.kt Question: Was this overkill? Is there a simpler approach?
m
I "doubled" my graph basically, floodfilled, and then checked on those the 'rounded' down points. algorithm takes a while to floodfill an entire board, but the printed result looks cool though 😂
👍 2
d
p
Ah the joys of ANSI colours and box-drawing chars
Day10.kt
Day10.kt
m
@Jakub Gwóźdź your solution is wild, it appears I need to read up on stokes 😮
d
hot code my part 2 takes about 20ms if you start from having the path (cold start, bit under 200ms)
Huh, I thought about counting the intersections first but I must have done it wrong
because it didn’t work for me
Oh I only did vertical and horizontal rays, which you can see doesn’t work on the test input
oh are you ray tracing from a given point p to every point in the path?
My code basically says “computer, enhance” 🤣
p
Yeah conceptually expanding the loop to account for parallel pipes was easy for my brain to grok this morning.
and I've done enough BFS in my AoC history that reaching for it for flooding is reflex.
e
p
I see edge-cases 😄
e
for part 2, instead of looping over points, I loop over corners
from the different approaches I was playing around with, it seemed like the simplest
d
I am trying to understand how this works
Copy code
fun part2(input: Input) = input.fold(0 to 0) { (sum, d), move ->
    when (move) {
        N -> sum to d + 1
        S -> sum to d - 1
        W -> sum - d to d
        E -> sum + d to d
    }
}.first.absoluteValue - (input.size / 2) + 1
Jakub’s solution
where input is the path
The line integral of a vector field over a loop is equal to its _curl_ through the enclosed surface.
r
I believe its shortest distance from one pipe to other pipe? for part 1, once the connection b/w pipe is formed, as it forms a loop
e
I didn't want to think about whether
Copy code
.F7
FSJ
LJ.
counted as a closed loop for the purposes of stoke's…
I guess it doesn't actually happen in our input though
r
I mean looking at the first test i/p
Copy code
.....
.S-7.
.|.|.
.L-J.
.....
row(2,1) -> | can be more than 1 steps from source, if other path is considered (S -> 7 -> | -> J -> - <L-|)
j
@Dan Fingal-Surma basically I'm counting the area adding function values when moving right and subtracting when moving left. Moving up and down just modifies the function value. The trickery is in removing pipes, figuring the pattern required 2 hours of tries and errors 😁
d
yeah I just grokked that 🙂
r
Looking at the Paul's approach - https://kotlinlang.slack.com/archives/C87V9MQFK/p1702202052972279?thread_ts=1702184405.460639&cid=C87V9MQFK Isn't it guarenteed, it will form a loop, once you find the correct pipe for 
S
which will connect to two neighbouring pipes 🤔
m
Thanks @Jakub Gwóźdź for the hint towards Stokes I implemented mine from scratch as well, and now ours look awfully similiar 😂 https://github.com/mdekaste/AdventOfCode2023/blob/master/src/main/kotlin/day10/Day10.kt
K 1
n
Part 2 was tough, glad I managed to come up with a solution on my own I added an extra symbol near every input symbol. Each extra symbol is basically a tile, which is indicating if the adjacent pipes of the main loop are connected there. So this input:
Copy code
...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........
became this:
Copy code
.~.~.~.~.~.~.~.~.~.~.
~~~~~~~~~~~~~~~~~~~~~
.~S=-=-=-=-=-=-=-=7~.
~~!~~~~~~~~~~~~~~~!~~
.~|~F=-=-=-=-=-=7~|~.
~~!~!~~~~~~~~~~~!~!~~
.~|~|~.~.~.~.~.~|~|~.
~~!~!~~~~~~~~~~~!~!~~
.~|~|~.~.~.~.~.~|~|~.
~~!~!~~~~~~~~~~~!~!~~
.~|~L=-=7~.~F=-=J~|~.
~~!~~~~~!~~~!~~~~~!~~
.~|~.~.~|~.~|~.~.~|~.
~~!~~~~~!~~~!~~~~~!~~
.~L=-=-=J~.~L=-=-=J~.
~~~~~~~~~~~~~~~~~~~~~
.~.~.~.~.~.~.~.~.~.~.
Tiles 
~
indicate that we can go there from any adjacent tile that is not connected to the main loop. And tiles 
!
and 
=
mean that we can’t – the pipes of the main loop are connected there. I used this transformed map of tiles to find out if it is possible to squeeze between the pipes in places where they might be connected.
j
I just realized that my approach would fail if main cycle had nested pipes inside:
Copy code
S----7
|.F7.|
|.LJ.|
L----J
Correct answer is 4, my algorithm gives 8 😞
j
@Jakub Gwóźdź mark all pipes not reachable from S as .
m
if I understand the assignment correctly, all pipes not part of the main pipe, may be ignored. If you had 'broken' pipe pieces inside your main nest, they would still be filled
j
Ah yes indeed. So I'm safe then 😁
e
oh. I could totally do even-odd for part 2… I thought of it during the challenge, but discarded the idea because it would run into problems with all the other junk in the way. but if I just filter that out, it would work
j
@ephemient to count if a point is inside the loop? I did that yes, and am fairly happy with the code, although I see other more elegant code here. https://github.com/JBeet/MyAdventOfCode2023/blob/main/src/aoc10/Day10.kt
d
For my solution of part 2, I have calculated the surface of the pipeline (irregular polygon) and subtracted all the pipes that make the pipeline divided by 2.
🙌 1
d
I did it via area of the polygon. See Greens’ theorem (generalises as Stokes). but you have to take into account the perimeter…specifically half the perimeter.
➕ 1
👍 1
j
@Dave ha! Good to know that there's a nice specialization of Stokes, didn't know that even if that was the case I was always implementing 😁
e
rewrote my solution to use even-odd. it could be a functional fold but there's multiple pieces of state to be passed between loop iterations, so `var`s it is
k
So this is a way to solve part 2:
Copy code
val perimeter = cycle.size
val area = cycle.zip(cycle.drop(1) + cycle.take(1)) { a, b -> a.x * b.y - a.y * b.x }.sum().abs() / 2
val points = area - perimeter / 2 + 1
🤯 2
I am using a 
Point
class but 
Pair
would work too, just use 
first
and 
second
instead
It uses the shoelace method for the area and Pick's theorem for the interior points
p
It's incredible how many different solution approaches we have - and from how many I never have heard about
m
I rewrote my solution and it now looks like this:
Copy code
override fun part1(): Int = points.size / 2

override fun part2() = points.plus(points.first())
    .zipWithNext { (y1, x1), (_, x2) -> (x2 - x1) * y1 }
    .sum() - part1() + 1
where points is a list of all the points of the pipeline in order. "area of n-sided polygon" generalizes nicely in a strict 2D world
very nice 2
💯 1
❤️ 1
d
Screenshot 2023-12-10 at 19.10.51.png
r
so... is this considered 'cheating'? 😛
Untitled.kt
m
I would say it's considered using the right tool for the job, well done. 😄
😎 1
yes black 3
t
Part 1
Part 2
k
First part was relatively straight-forward but i had to do a bit of reading on the second part... it took a while 😅
e
my code today has gone through 3 approaches: 1. part 1: BFS from the start until running out of pipes to visit; part 2: DFS flood fill on dual coordinates 2. part 1: linear walk of path (/ 2 for answer); part 2: linear scan counting even/odd crossings, still O(input size) 3. part 2: shoelace formula to calculate area, pick's theorem to count internal points, O(path length) ≤ O(input size)
n
@Jakub Gwóźdź Earlier I Googled Stokes', and staring down that wall of calculus made me decide I could never understand it. But applying your algorithm to simple polygons made it quite explicable. Not Stokes' or Green's or whatnot, which is still Greek to me, but how that algo calculates area.
👍 1
t
For part 1: I realized that all traversals of the pipe must be an even number and that the farthest would therefore be half of the total distance. For part 2: I mimic the right-hand rule and do a flood-fill of some arbitrary side of the pipeline after removing all non-pipe parts from the grid. - Code - Blog
d
Does Jakub's code relate to the Shoelace formula and Pick's theorem?
e
Jakub uses Stokes with a constant field to get the area, then Pick's the same
👍 2
l
Do you think the puzzle using pipe is a hint for using point-in-polygon (PIP) method ? https://en.wikipedia.org/wiki/Point_in_polygon
e
my second approach is effectively ray casting so it's possible, but not the only solution
j
What I love most about discussions like this is how I switch my thinking from "mine is the brilliantest idea" to "hey, there are other brilliantest ideas, which are also great to learn about" 🙂
l
Yes that’s why this channel is so cool. I always discover new way to solve the problem or new Kotlin stuff I didn’t know about.
💯 3
a
hi all, I've spent too much time on Part 2 😞 my approach was to do two perpendicular vectors (left and right) that go alongside of loop path vector and DFS all tiles on both sides. If DFS detects a wall, then it stops and indicate that side as "outside". Only "inside" tiles are counted. so it's kinda geometrical approach. The issue I spent time on was a subtle one. If there is a sharp angle, rotating vectors might miss some tiles inside. My answer was off by like 5. The fix was to attach perpendicular (turning) vectors at the beginning and the end of loop path vector (not only at the start as I did initially). https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day10.kt and as usual, no mutable data structures, no recursion. PS Kudos to @Dan Fingal-Surma for helping debugging my code!
w
The idea I came up with for part 2 is the following: - Determine the rotation sign of the enclosing path. The full circle makes a total rotation of either + or - 2 * PI. - All regions that are inside this enclosing path at some point have a bordering coordinate which makes a perpendicular angle with the enclosing path (i.e. this angle is +/- PI / 2) - The sign of this angle should be the opposite to the sign of the full revolution angle (see above) that the enclosing path makes. If this is true, then the region is inside, otherwise the region is outside. - We count the sizes of the visited locations within valid enclosed sections and add them all up together to get to the result.
It’s crazy how many different approaches can be used: • Stokes/shoelace/picks theorem • Expanding tiles (putting empty spaces in between the pipes) • Point in polygon (odd number of intersections) • My approach with the sign of the direction angles • Path finding approaches trying to determine inside and outside
m
Late to the party, but still. Had almost no time to work in it yesterday, and then I spent two hours of back and forth only to discover that I had glossed over the fact that for part 2 not only dot tiles count as tiles 😉 https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2023/day10.kt
My simple idea for part 2: I walk the enclosing path and in each corner, I put the tiles surrounding it in two sets (either left or right), including even one row/column of tiles outside the grid. When that is done, I’m expanding each of these two sets to add all adjacent tiles. Then the enclosed one is the one without any tiles outside the grid.
p
As a followup on yesterday stream chat, I've tried the just two traces per line approach inspired by Sebastian and it works like a charm 😄 https://github.com/glubo/adventofcode/blob/main/src/main/kotlin/cz/glubo/adventofcode/day10/Day10.kt (my original solution was to flood 2x2 zoomed tiles from outside, which was way slower than this O(N*M) )
k
37 Views
Open in Slack
PreviousNext
Powered by