https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 6> (spoilers) :thread:
# advent-of-code
a
m
Part 2
This was a pretty good day for me, everything worked first try, which is unusual. 😄
🤩 1
r
Very similar solution from my side
p
there were today two corner cases to remember about, and actually I faced them both only in part 2 😄 well constructed input it was 😄
m
Brute force on part 2. • My rotateright() function actually rotated left which costed me a point • Tried to do a smart strategy in part 2 at first where I count overlaps, but that does not deal with edge cases
Day 6 Michael.cpp
m
Ohh I placed on the global leaderboard today, can't believe it!
🥳 13
m
congrats!
thank you color 1
d
That was a fun one! Need to clean it up. Restricted the set of points to try placing obstacles at — only where the guard went in part 1.
m
Copy code
Solution for Day6: 
---------Part 1-----------
time: 1.062500ms
answer: 5461
---------Part 2-----------
time: 1.691950900s
answer: 1836
---------Total-----------
time: 1.693013400s
---------End-----------
This is painful though haha, part2 is a snail 🐌
d
Ah yes I'm running it from the beginning each time and you can instead skip to the state right before the guard would run into the obstacle.
Time to make my State class immutable 😂
a
ok, glad I'm not the only one who shamefully brute-forced part 2 🤣 😭
same 5
s
Also brute-forced. Thanks to the younger me for writing the 
Direction
class https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/year2024/Day06.kt
a
but it's pretty brute forcing 😛
p
image.png
d
I mean, at least it’s not brute forcing all points in the grid
a
@Dan Fingal-Surma wrt whose solution? hehe, brute forcing "all points on the grid" vs brute forcing "all the 'Floor' points on the grid" is not that different I'm brute forcing "all the 'Floor' points on the grid" 😭 (ie non-preset obstacles and non-starting position of guard) my input had 16,061 floor points and 838 preset obstacles; so skipping the presets is just a 5% improvement
e
Day6.kt brute force with parallelization
d
My attempt at memoizing was way way slower because the state is expensive to copy (because of the visited set) — I think brute force is easier and works just fine even without parallelization
j
Not sure if brute forcing, but for part 2 I'm testing only the positions found during part 1. There probably is a place for introducing dynamic programming, but IntelliJ Profiller says I'm already around half a second, so - maybe in the evening.
Untitled.kt
d
Yes that seems best
m
image.png
d
I was able to clean up my code more by eliminating the State class using Marcin’s “if loop return null else return visited” trick
j
you don't need to collect visited at all for part2 (except the initial list of possible places)
d
(thought I could have just had a Pair<Set<Guard>, Boolean> originally as well)
you still need to track visited to tell if it’s a loop — you just don’t need to look at it after
j
nope 🙂
just track the turns
d
oh right
e
.asFlow().flatMapMerge { flow { ... } }
will parallelize on multiplatform (
.parallelStream()
is JVM-only)
d
you just need to see if it gets back to the start
j
your set would be way smaller and quicker
that also no. the cycle might be excluding the first position
d
hmm
what do you mean track turns then
m
@ephemient as flow requires non-stdlib kotlin and I'm working on the JVM anyways
j
see my code above - I'm testing (and putting into "visited") only the positions where I'm turning
d
New code Edit: made more cleanups below
Ah, I see — that doesn’t seem like it saves much, and prevents code reuse for me
I see, you extracted the track function
j
Profiller said I went from 1.75s to 0.55s 🙂
👍 1
introducing 
asFlow().flatMapMerge
reduced to 329ms 🙂
p
I spent far too long debugging why my loop detection wasn't working when I was stopping on the first location that did get added to the (at the time, empty) set... 🤦‍♂️
Day06.kt
d
Real new code
a
@Jakub Gwóźdź providing the optimisations today 👏
but for part 2 I'm testing only the positions found during part 1.
and
I'm testing (and putting into "visited") only the positions where I'm turning
wrt that second one, while saving & checking only turnings, overlap can still occur before. but that saves A LOT of memory at the expense of just a few more steps: for example, in the example, last grid has:
Copy code
....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
.+----++#.
#+----++..
......#O..
the two `+`'s near the bottom 
O
wouldn't trigger loop-check but the following right-turn upwards (on the left side) would trigger the loop-check.
using the "only visited paths from part 1" optimisation for part 2: instead of 16,000 floor points it's now 4500-ish, so a ~75% reduction.
Copy code
part Two Time: 19.456338800s
part Two Optimised Time: 4.388765400s
77.4% time improvement but I did not memoize turning paths, etc.
Why does the Lambda Receiver format need the type?
Copy code
.map(Pair<Point, Direction>::first)
as in, why doesn't just this work?
Copy code
.map(Pair::first)
j
Yeah, my set of "visited turns" is storing "current + next" pair, to make sure it's not signaling cycles too quickly
😎 1
b
does the 
flatMapMerge
not do anything on the jvm? (parallelStream did speed up my solve)
oh i had to set the dispatcher
n
Another one that took me way longer than many of you. Granted, I did not start till a couple hours ago, and I finished maybe an hour ago. The basics were coded very quickly but it took me far too long to figure out that there was an issue if you turn and a wall is right there. Then it took me a long time again to remember that my "obstacle" is virtual and I had to test for the situation where you turn and immediately face the obstacle. 5 seconds on my old R2600X with no optimizations. Immediately threw in async/await and got down to 2 seconds. Then got online and applied @Jakub Gwóźdź's optimizations, bringing it down to about half a second. I've got a R5700X on order, should arrive from Ali next week. It'll be fun to be able to throw a couple more powerful cores at these problems.
j
One more thing to consider when applying "store only the turns" optimization: we can reduce the number of stored elements by 75% if we store only turns from UP to RIGHT. The result is still correct, but the hashset lookups are reduced to 1/4. But it does not affect the total time in any measurable way.
r
I just used all visited nodes from part1, one by one added blockers on each node, walk the path. While walking, if same node and same direction exists - it forms a loop. Might be better efficient solutions, but works!
p
j
Ok, with a bit of cache, I managed to come down with part 2 to 75ms. Single threaded ofc. Code tomorrow, after a cleanup, it's an ugly mess.
Or... I'm not going to make this pretty anymore. Commit introducing hashing and decreasing time from ~280 to ~70ms is here.
m
^ Refactored for speed 🙂
p
No caches used - just a liberal sprinkling of bit twidling...
Copy code
Warming up 1 puzzles over 5s for year 2024 day 6...
Warmup finished after 5.001846250s with 790 iterations
year 2024 day 6 part 1
	 Fast took 105.876us 👑: 5409
year 2024 day 6 part 2
	 Fast took 5.656859ms 👑: 2022
or swapping 
parMap{}.count{}
for simple 
count{}
Copy code
year 2024 day 6 part 2
	 Fast took 35.759518ms 👑: 2022
Untitled
👏 2
n
A little Rust religion for y'all: there was a subtle (to me) bug in my movement function that prevented me from getting the right answer when I started the guard immediately behind the obstacle in part 2. Once I figured that out, I added the optimization and improved times by 40%. But then I was coding the change in Rust and it refused to compile because I was using a non-atomic array to track whether an obstacle was already placed previously. So I tried running the Kotlin solution a few more times and half the time it was right and half the time it was one off. Race condition! One that I didn't notice with Kotlin and literally refused to let me run in Rust. Chalk one up for fearless concurrency!
n
Hi, I would appreciate, if someone could have a look on my solution. It is working quite fast, but my loop-detection is somehow wrong. https://github.com/123niel/advent-24/blob/main/src/Day06.kt For the test input, it works fine
j
it looks ok, but you can add to (and test) 
visited
only when the direction is UP . also, I'm not sure how this 
com.toldoven.aoc.notebook.AocClient
works, but if it just downloads the url as a string, then at the end of 
val lines = aoc.input().lines()
you'll get an empty string, which will mess with your 
Boundaries(Point(0, 0), Point(lines.first().lastIndex, lines.lastIndex))
n
Thanks for the reply!
you can add to (and test) 
visited
only when the direction is UP
why is that? A loop can also be closed going in any other direction, can't it? concerning the library: It is great for solving aoc with notebooks: https://github.com/Toldoven/aoc-kotlin-notebook. The downloaded input is sanitized correctly
j
why is that? A loop can also be closed going in any other direction, can't it?
Sure, but after max 3 next turns it will be a turn UP 🙂 so you'll sacrifice three more iterations but save 75% cache operations
n
Okay, I get that. But caching is not the problem here, as it runs in ~1s. The result is wrong, about 100 to small
j
Part1 is ok?
n
yes
I optimised it to only add obstructions on the paths of part1. I checked all posibilities before, which gave me the same output. So my guess is the loop detection must be wrong
j
Loop detection looks ok, I’d debug the inbounds detection
n
I thought of optimizing only for UP but my move function does a complete U-turn if there are walls in front and to the right, so I’d have to rewrite that. Do you save significant time over just recording the turns?
n
@Jakub Gwóźdź just solved it with a colleague. I didn't check for multiple turns on the same position
👍 1
j
really? your visited had pair(pos, direction)
n
No, the loop and boundary check was correct but the movement wasn't. It was possible to walk over an obstruction because it didn't check if there was another one after turning once.
j
aaaah ok. strange it didn't happen in part1. anyway I avoided it by having my "step" doing either "move" or "turn", never both 🙂
32 Views
Open in Slack
PreviousNext
Powered by