https://kotlinlang.org logo
#advent-of-code
Title
# advent-of-code
p

Paul Woitaschek

12/10/2023, 6:49 AM
Day 10, if you’re stuck - no solutions 🎄 While debugging my code, I made this test case, sharing it if someone else gets stuck too 🧵
K 3
Copy code
F-7..
L-J..
.S-7.
.|.|.
.L-J.
.....
This should lead to a 4 for part 1
kodee loving 3
Okay, spoiler for part 2 (rot 13 it if you want to know it 😁 )
Copy code
<uggcf://ra.jvxvcrqvn.bet/jvxv/Cbvag_va_cbyltba>
thank you color 3
👍 1
a

andriyo

12/11/2023, 4:06 AM
@Paul Woitaschek that's 4 for Part 2? How?? I probably missed something in requirements
l

Lidonis Calhau

12/11/2023, 4:32 AM
Probably is 4 for Part 1
a

andriyo

12/11/2023, 4:33 AM
oh ok, that makes sense
it's just Part 1 is relatively straightforward .. Part 2 is apparently now
I was beginning to think about wrapping a map of a sphere or something 🙂
l

Lidonis Calhau

12/11/2023, 4:37 AM
Wow, I mean looking at solution thread there is wide variety of possible solution.
a

andriyo

12/11/2023, 4:38 AM
but there is a solution, right? just checking because my seemingly correct code doesn't work 🙂
l

Lidonis Calhau

12/11/2023, 4:39 AM
Ah yes but I mean people took different approach for the same result
I did the same as Paul. So you can look at his hint if you are stuck.
a

andriyo

12/11/2023, 4:43 AM
I didn't do anything fancy, just BFS
p

Paul Woitaschek

12/11/2023, 4:44 AM
Yes the test case was just for part 1 on a stupid thing I was stuck with which was not covered by the test input
a

andriyo

12/11/2023, 4:45 AM
ok, makes sense now - i was like where "4" is coming from? 4-th dimension or somethin? .. )
p

Paul Woitaschek

12/11/2023, 4:47 AM
What is your part 2 approach which isn't working?
a

andriyo

12/11/2023, 4:48 AM
i run BFS for points on the right side and on the left side of the path vector
if DFS hits the wall I know it's "outside"
p

Paul Woitaschek

12/11/2023, 4:50 AM
Did you account for the case that you can squeeze in through the pipes?
👍 1
|| || || This shouldn't block you going up
a

andriyo

12/11/2023, 4:51 AM
it doesn't
i just walk the path, and whenever I can start a dsf (from left or right) I do it
test cases work
any unusual test examples you can share?
p

Paul Woitaschek

12/11/2023, 4:55 AM
Construct a test case where there is a 3x3 free space inside
a

andriyo

12/11/2023, 4:58 AM
like this?
Copy code
F---7
|...|
S...|
|...|
L---J
p

Paul Woitaschek

12/11/2023, 4:59 AM
Yes
a

andriyo

12/11/2023, 4:59 AM
9
it's 9, right? )
p

Paul Woitaschek

12/11/2023, 5:00 AM
Yes ^^
a

andriyo

12/11/2023, 5:00 AM
yep, my algo works
p

Paul Woitaschek

12/11/2023, 5:01 AM
Now try a bigger one where there is an inner field only accessible by two adjacent vertical pipes
d

Dan Fingal-Surma

12/11/2023, 5:01 AM
this is the key test that needs to pass, from the description:
Copy code
..........
.S------7.
.|F----7|.
.||....||.
.||....||.
.|L-7F-J|.
.|..||..|.
.L--JL--J.
..........
the answer is 4
a

andriyo

12/11/2023, 5:02 AM
yeah, all the tests from description pass for me
@Paul Woitaschek you mean something like this?
Copy code
F---7
|...|
SF-7|
|L-J|
L---J
my code gives 9 because it calculates number of tiles inside big loop, regardless what's that is. Unless there is requirement somewhere not to count other inner loops, is there?
and the inner loop area is not connected with outside (nothing like || or = there)
i guess it's going to be my "the one that got away" 🙂 i'll try my luck with 11th day
d

Dan Fingal-Surma

12/11/2023, 5:37 AM
My solution only considers pipes in the path
a

andriyo

12/11/2023, 5:39 AM
mine too.. the problem for me that there is no test case for me that fails except the big one
d

Dan Fingal-Surma

12/11/2023, 5:45 AM
Why only left or right, not up or down?
(I used a diff algorithm)
a

andriyo

12/11/2023, 5:46 AM
what do you mean up or down?
d

Dan Fingal-Surma

12/11/2023, 5:46 AM
I don't fully understand your algo
i just walk the path, and whenever I can start a dsf (from left or right) I do it
a

andriyo

12/11/2023, 5:48 AM
oh.. clockwise and counterclockwise - from the left side of the path vecor and from the right side
left and right relative to direction
of the vector
d

Dan Fingal-Surma

12/11/2023, 5:48 AM
ah
a

andriyo

12/11/2023, 5:50 AM
and if DFS hits outside wall, it's outside of the loop. I know it's not the fastest and not mathy, but it works fast for the given input, just not the expected result 🙂
d

Dan Fingal-Surma

12/11/2023, 5:50 AM
how does it squeeze thru parallel pipes
guessing something is wrong with that part
i.e. doesn’t work for all cases
a

andriyo

12/11/2023, 5:54 AM
it doesn't need to squeeze, it initiates the DFS alongside the whole loop
d

Dan Fingal-Surma

12/11/2023, 5:56 AM
i don’t follow, how does it it reach an outside wall from the seemingly interior points here? DFS not only on open points presumably, how does it identify successor points?
Copy code
..........
.S------7.
.|F----7|.
.||....||.
.||....||.
.|L-7F-J|.
.|..||..|.
.L--JL--J.
..........
a

andriyo

12/11/2023, 5:57 AM
so there is a look, starting with S. imagine that there is right side and left-side DFS that begins at every point of the loop (every tile)
DFS stops only if it hits the loop itself or the wall
obviously accounting for already visited tiles etc
d

Dan Fingal-Surma

12/11/2023, 6:00 AM
I still don’t follow, it seems like if you start at any O point here it will stop bc it hits the pipes and never hits the wall
Copy code
..........
.S------7.
.|F-*--7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|..||..|.
.L--JL--J.
..........
looking from the * point for example
a

andriyo

12/11/2023, 6:01 AM
Copy code
..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|..||..|.
.L*-JL*-J.
..........
from * point, it will find internal area
d

Dan Fingal-Surma

12/11/2023, 6:01 AM
yes that’s not the problem, the problem is the O points
you said your code passes but i don’t understand how
why doesn’t it flag them as inside
a

andriyo

12/11/2023, 6:02 AM
i don't need to worry about that - as long as there is a single escape DFS that hits the outside wall, it's considerd outside-side
d

Dan Fingal-Surma

12/11/2023, 6:02 AM
what’s the DFS that hits the wall?
in this case
a

andriyo

12/11/2023, 6:04 AM
if you start with S moving right. your vector will be "->" on your left side there will be "outside" because there will be at least one branch of DFS that hits the outside wall
d

Dan Fingal-Surma

12/11/2023, 6:04 AM
yes that doesn’t explain why it detects all the O points as outside
a

andriyo

12/11/2023, 6:05 AM
because O-points will be on the left side
so they are marked as outside
d

Dan Fingal-Surma

12/11/2023, 6:05 AM
ahhh
I get it
you determine if L or R is outside
a

andriyo

12/11/2023, 6:05 AM
there could be only one outside
yep
d

Dan Fingal-Surma

12/11/2023, 6:06 AM
then you fill on the opposite side
a

andriyo

12/11/2023, 6:07 AM
yes, as soon as I know that certain side is "outside" side, I just stop DFS there
and just count all the tiles on "inside" side
d

Dan Fingal-Surma

12/11/2023, 6:12 AM
what do you get for this
Copy code
..........
.S-7......
.L7L7.....
.FJ.L7....
.L7F-J....
..LJ......
a

andriyo

12/11/2023, 6:14 AM
1 - is it correct?
d

Dan Fingal-Surma

12/11/2023, 6:14 AM
yes
checking what would happen if an open point never touched a | or -
a

andriyo

12/11/2023, 6:18 AM
my part 2 just works with list of coordinates. with two points I have a vector that I can rotate left or right. the only Char that I'm checking is that it's not a wall tile
d

Dan Fingal-Surma

12/11/2023, 6:19 AM
Are you counting interior points or are you counting exterior points and subtracting that and the pipe points from the total points?
a

andriyo

12/11/2023, 6:19 AM
counting interior tiles
d

Dan Fingal-Surma

12/11/2023, 6:20 AM
I guess both ways would give the same result since something is being incorrectly flagged
My thought was, from a L type point there are 2 points on one side and 0 on the other
As opposed to one on each side
a

andriyo

12/11/2023, 6:28 AM
my assumptions: 1. there are points that on two different sides (left and right) 2. those sides could be either "outside" or "inside" 3. if there is even a single point that is the wall, that makes the side's of the point an "outside"
4. all "inside" points are reachable from the loop, e.g. for point inside point A, there is point L on the loop that could DFS into it (where loop line is the only blocker for DFS)
d

Dan Fingal-Surma

12/11/2023, 6:36 AM
where’s your code
is your answer too high or too low?
(I assume too low)
i think it was just saying incorrect
d

Dan Fingal-Surma

12/11/2023, 6:40 AM
well i can run it on mine I suppose
a

andriyo

12/11/2023, 6:40 AM
"That's not the right answer."
thank you!
I thought there might be some "off by one" error and I tried +/-1 as the answers and It said that "Your answer looks like someone elses puzzle answer" ) funny )
d

Dan Fingal-Surma

12/11/2023, 6:44 AM
don’t write
KFunction1<Pos, Pos>
, write
(Pos) -> Pos
you’re 5 too low on my input
let me see if i can find which ones…
a

andriyo

12/11/2023, 6:46 AM
that's IDE"s func extract refactor - blame JetBrains folks ) but yeah, the code is not pretty
thanks - there must be some weird configuration of points/pipes
Copy code
countOnSide(
essentially returns a list of tile coordinates, you can see there what points are missing
d

Dan Fingal-Surma

12/11/2023, 7:06 AM
yeah i found the points for my input
trying to print
a 21 by 21 region, missed point in dead center
Copy code
--JLJF7L-7F-7||LJ|||
--7F-JL-7LJ.LJ|F7LJ|
7.LJF---JF7.F7LJL-7|
L-7FJ.F--JL7|L7F--JL
-7|L--JF7F7LJFJL---7
-JL----JLJL--JF-7F-J
----7F7F7.F-7.|FJL-7
-7F-J|||L7L7|FJL7F-J
7|L--J||FJFJLJF-JL-7
J|F7F-J|L7L-7FJF7F7|
7LJLJF-JFJ.FJL7|||LJ
L7F-7L7FJF7L-7||||F-
FJL7L7|L7||F7||||||F
L7FJFJ|.||||||||||||
-JL7L7|FJ|LJ||||LJLJ
7F7|FJ|L7|F-J|LJF---
J|LJL7|FJ||F7L-7L-7F
FJ.F7LJL7|LJL7FJF-J|
JF-JL---JL--7||.L-7|
-JF7F7F7F7F7||L7F-J|
F7|||||||LJLJ|FJL7FJ
bordered by L J 7 F
let me repro simplest
Copy code
..........
.S-7......
.L7L-7....
.FJ.FJ....
.L-7J.....
..LJ......
that has L J F 7 in the same pos
relative to
the missed point
a

andriyo

12/11/2023, 7:12 AM
ok, let me try that
wait, is it a valid input at all?
d

Dan Fingal-Surma

12/11/2023, 7:14 AM
oops wait
will fix
Copy code
..........
.S-7......
.L7L-7....
.FJ.FJ....
.L-7|.....
...LJ.....
that should work
now i realize i can run your code lol
it missed it
so, fix that
I’m guessing you aren’t looking out both “rights” at a turn
this point, you always approach head on and turn
that’s what I meant above,
My thought was, from a L type point there are 2 points on one side and 0 on the other
a

andriyo

12/11/2023, 7:19 AM
fixed it ) thanks you! I needed two turning vectors )
🎉 1
d

Dan Fingal-Surma

12/11/2023, 7:19 AM
yep
a

andriyo

12/11/2023, 7:20 AM
I should have tried that earlier when I saw that I get different result whn I attach turning vector to another point on a path vecotor
anyway, thank you so much for debugging it with your input and insights!
👍 1
d

Dan Fingal-Surma

12/11/2023, 7:21 AM
nice algo
a

andriyo

12/11/2023, 7:23 AM
i'm sure there are some O(1) mathy ones - but I didn't want to open wikipedia on weekend )
d

Dan Fingal-Surma

12/11/2023, 7:30 AM
I projected the path into a 2x size space and then used normal fill from (-1, -1) and then counted the even points that weren’t in the fill or path
19 Views