https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 16> :thread:
# advent-of-code
a
kodee happy 1
t
I liked this one 🙂 My biggest trouble was realizing when to terminate in part 1. Also, I implemented 
-
and 
|
the other way round. For part 2, my model made it easy to iterate all the starting points and doing 
maxOf
on the results 😌
m
My project is cursed and I can't seem to fix it 😞 Deleting the build files did it 😛 but I spend some time porting it over to a new project this morning haha
😢 1
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day16.kt pretty straightforward. would have been faster if I had copied helpers for this type of movement from previous years but oh well, at least I got it right on the first try
oh I should have copied from day 10…
b
my only hangup was that i didn't at first check if rays were repeating their paths... after that it solved pretty quick
although i may have been slowed down a bit by the fact that i might be slightly inebriated
p
j
yet another checkbox to AoC assessment form: • [✔️ ] forgot about changing one tiny 
-
to 
+
when copying case 
East
into 
West
, (this little maneuver costed me 51 years)
n
Yeah, pretty nice and simple. The issue I had was to understand that beams leaving the area simply disappear. I only got that from the sample.
j
I wonder if there’s chance for caching in part2, basically it is casting beam 440 times and much of it is going the same path…
m
Part 2, with some help from coroutines 😄
p
j
@Marcin Wisniowski did you notice any gain in speed? for me going mapParallel again took the same time or even slightly longer than sequential
m
Yes, with parallelization it takes 101ms, without 537ms. I'm losing most of the time in creating the lists and maps in the when statement instead of using 
when
statements inside, but this way they only take one line each. 😄
p
My speed up came when I split positions and directions for the visitatation tracking
j
@Marcin Wisniowski nice, you run it on Dispatchers.Default?
m
I don't set one, so the default from 
runBlocking
n
Difficulty is all over the map this year. I spent less time on this than I did on Day 1. Partly because it's such a classic AoC BFS pathfinding exercise.
In this (and many other) parallelization exercises, I don't get much if any benefit from coroutines over Java Streams. And while I always have to do a quick lookup for the right collector to use, there's much less setup than worrying about contexts and dispatchers.
> My speed up came when I split positions and directions for the visitatation tracking @Paul Woitaschek could you expound on that? I looked at your code and it looks like you have a different MutableSet for each Direction. I assume that's the optimization, but I'm curious why that works over using one Set holding a Pair.
e
runBlocking
doesn't create a multi-threaded dispatcher, you should use 
withContext(Dispatchers.Default)
or similar if you want to actually fork work
n
I wonder if there is a good caching strategy for this. Once a ray is on a particular path it's going to do the exact same thing over and over, and this could partially carry over to other starting states. But you would need to determine whether a beam ends or cycles rather than just letting the BFS peter out when all the spots have been visited.
p
This was the commit. With 4 sets its only a 1/4 of the things to check for the set https://github.com/PaulWoitaschek/AdventOfCode/commit/c56c360030c8de496039ab9dfb0d8f5f8fda6432
n
Maybe I'm just dense or lack the requisite CS chops but it's not obvious to me why that would be significantly faster. Is it just that the hash calculations are simpler/faster, and that there's fewer collisions?
p
I don't know, my knowledge is limited there. It's also no object allocations with that approach
n
meaning creating the Pair?
m
@ephemient I definitely get a speed up and definitely see all my CPU cores being at 100%, without setting a Dispatcher
p
Maybe that was a nonsene optimiziation. Now I’m running it in a loop and this time it doesn’t really provide much gain
j
The 
suspend
on 
main()
also can set up something.
g
I like when I do first part general enough to scale it in part 2. Here is my solution from today
m
I see what's going on, here is the doc for `async`:
If the context does not have any dispatcher nor any other ContinuationInterceptor, then Dispatchers.Default is used.
So if you use 
async
in a 
runBlocking
that doesn't set a Dispatcher, you will use 
Dispatcher.Default
and get multi-threading as expected.
p
My runBlockings async does not multi thread when I don't specify the dispatcher
j
Add suspend to your main
Or remove 😁
p
Huh, I only run things from my tests, no main 🤷
a
I did part 1, got it to pass on the test input and actual input. read part 2 and started refactoring part 1 to allow for reusable code, etc. before starting part 2. but now part 1 doesn't work and Ctrl+Z history isn't going back far enough 🤦
n
I always commit (but not push) after solving part 1, so that I have a reference point when refactoring
a
I've been doing commits after completing each day's part 2. (unless I've decided to do part 2 another time or not at all) today's part 2 seemed quite doable / clear so I didn't commit part 1 😭 I brought this on myself
j
changed my “visited” from MutableSet<Entry> to Array<IntArray>, added some bitwise operations, and that reduced the time by ~2/3 (from 500 to 160ms)
a
the part 2 is just running part 1 in a loop. It takes a few seconds but I'm sure it could be improved somehow https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day16.kt
a
but now part 1 doesn't work and Ctrl+Z history isn't going back far enough 🤦
solved! guess which dumb**s updated 
expectedOutput
to 51 for part 2 but in the part 1 test where it was supposed to be 46. that's 30 minutes I'm never getting back
m
I always commit (but not push) after solving part 1, so that I have a reference point when refactoring
I seem to be in the minority but I do part 1 and part 2 separately, in different files, with nothing shared. So Part 1 is always there when working on Part 2.
e
lasers are the same forwards and backwards, so if a laser exits the field in a certain location/direction, you don't have to test it coming back in from there. I tried it, which resulted in a small speed-up, but it's not very compatible with doing everything else in parallel so I dropped it later
a
did anyone do this with a network / graph? I assume this would become super-efficient if done that way. 1. each node would be the mirror/splitter/pass-throughs 
Pair(Point, incomingDirection)
◦ so each mirror/splitter would actually be 4 nodes, one for each incoming direction 2. each node would have exactly 4 connected nodes - which would be other mirrors/splitters/pass-throughs or the walls in the Up, Down, Left, Right directions 3. the 
weight
on each node would be the straight-line distance (xrange or yrange) to the next node/wall 4. calculating 
weightToWall
(starting null or 0) would then be a cumulative backfill and can be cached/saved/attribute, since it's unique for that Point from an incoming Direction. ie unique for each Node 5. additionally, the walls can also be made Nodes, but with only 1 connected node - either the opposite wall or any mirror/splitter/pass-through that comes before the opposite wall
e
Yes. That’s how you do it. You don’t need to visit any direction+position combo more than once. Keep track of yet-to-be-visited somewhere. If you keep them in a queue, that gets you breadth-first-search (BFS). It works instantly.
😊 1
And you don’t need to actually build a graph. Just keep track of visited and to-be-visited ray states.
✅ 1
K 1
c
Surprised part 2 allowed me to use my part 1 solution to brute force it. Part 1 itself was simple enough - spotted straight away to keep track of directions/positions i'd already done to avoid cycles. Beyond that wasn't really much to it especially when we've already had pipes which was similar.
Twice today defined a function within a function. Have been doing Java at work recently and i've really missed being able to do that.
https://github.com/CfGit12/aoc-2023/blob/main/src/main/kotlin/16.kt Potentially slightly long winded with the definition of objects but I think it makes the logic easy to follow.
e
I opted to use 4 matrices to track movements + direction. It is a compromise between memory and easier to solve in less time, and since the map is small it is not a problem. Although pure recursion is better, this second version only uses recursion when a divisor is reached and reduces the total time from 45 ms to 37 ms. https://github.com/bayesiano/AoC-2023/blob/master/src/main/kotlin/Day16b.kt
j
You can fit it into a single matrix, with a tiny bit of bitwise operations 🙂
e
Good idea! I'll try! 🙂 👍
I couldn't wait, your suggestion saves memory and reduces the total time from 37 ms to 14 ms. Thank you @Jakub Gwóźdź! 😃 https://github.com/bayesiano/AoC-2023/blob/master/src/main/kotlin/Day16c.kt
🙇 1
🙌 1
t
That was fun. I enjoyed this one a lot. My code at the start was a MESS but I managed to refactor into something I'm willing to show. For part 2, I just run part 1 over and over again for each entry point and direction. I'm not sure if there's a quicker way to do that, but it works fast enough for me as-is. • Blog • Code
b
Sane, exiting when required escaped me for far too long and I went down some dumb paths before the right one percolated into my consciousness.
o
Dfs https://github.com/Oziomajnr/AdventOfCodeSolutions/blob/main/solutions/src/2023/Day16.Kt I have been trying out other languages for these puzzles but Kotlin just has so many utilities.
12 Views
Open in Slack
PreviousNext
Powered by