Clojurians Log v2

nothing like a good night of sleep and reading the word "manhattan" here

First find the path. For each step in the path search if 2/20 steps away there's a step in the path and calculate the savings. 25s is too slow....

I started by solving it as path finding in a big graph, but it turned out, only the original path needs to be found and the rest can be calculated by just "jumping around" in the grid. https://github.com/erdos/advent-of-code/blob/master/2024/day20.clj

Just finished, yeah, that was my conclusion as well. "jump around" and if you land on the path, you're golden. Really glad I took the time to "generify" my a-star the other day.

Well, I'm dumb. I misunderstood part1 as being able to go through 2 walls. Now that I've got that fixed up, I think I'm going to make good on my promise not to obsess too much and get some sleep. Wheee

Good night!

But seeing part2, I guess I can see why they might have worded it that way. Anyway....

Yeah, my dumb mistakes mean I only just got part 1 done. I think I'll sleep on part 2 for now.

It runs in about 2 seconds for both parts. I wonder how to speed it up without using pmap. https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_20.clj

Takes 8 seconds for me, but it seems that my generic function that sums two points like so (mapv + p1 p2) is quite slow compared to doing it by hand

That's why I rewrote it like this one day

(defn plus [[^long x ^long y] [^long dx ^long dy]]
  [(+ x dx) (+ y dy)])

Unfortunately this is used all over my solutions last 10 years and I cannot know for sure that it’s always long, cannot even be sure that only 2 or 3 dimensions are always used

rewrote it to

(defn p-sum
  "Sum two points"
  [p1 p2]
  (case (min (count p1) (count p2))
    2 [(+ (p1 0) (p2 0))
       (+ (p1 1) (p2 1))]
    3 [(+ (p1 0) (p2 0))
       (+ (p1 1) (p2 1))
       (+ (p1 2) (p2 2))]
    (mapv + (or p1 (repeat 0)) (or p2 (repeat 0)))))

still 20 times faster than just the last mapv here

btw one thing that really sucks about mapv is that if you have more than 1 sequence as input it will do (vec (map which is way slower

(nth vek idx) must be faster than (vek idx)

Really? My criterium tests showed that they are about the same

https://gist.github.com/RokLenarcic/7cbeabd51bf36da6572bd7cc689afd23

call on vec calls nth, so it at least 1 fn call faster (until it is jit optimized away)

ok

https://gist.github.com/DeLaGuardo/d474eb7c0414941d8889bcd46be1a392

OK I did this with reverse dijkstra from the end node, then BFS from each path entry, counting each non-wall I ended at to get the distance. had some counting bugs by complicating the BFS a bit. it's pretty slow (26s) so I imagine there is a more efficient algorthmic approach than I'm using. https://github.com/tildedave/advent-of-code/blob/main/src/advent2024/day20.clj

yeah, maybe I can just get all the nodes within a certain manhattan distance and count that way

great code @malaingreclement! Easy to follow. Do you prefer (- (- a b) c) over (- a b c) or forgot about it? I'm quite happy when I can do that with + or >

I tend to write it in the first form when I'm in the flow because that's how I think, and then correct it when re-reading. The version on my github has the second form: https://github.com/Maravedis/advent_code/blob/master/src/advent_of_code/2024/20.clj

Also a-star is completely overkill here. From what I understood, there is only one path in this, so you can just literally follow the dots.

But it saved me from having to write two lines of code, so you know 😛

A* when there is one path is just DFS ;-)

It's all graph traversal algorithms, really, since you're walking what effectively is a linked list. It trivializes everything.

I managed to waste 30min because my manhattan distance was wrong (abs in the wrong place) since few days back. Only now it mattered but in a tricky way.. My frequency map was correct for the highest distance saved cheats so took me a while to look there:face_palm:

hmm.. after pointing out the shorter subtraction code, I just noticed I do (= [x y] [0 0]) and you do (= 0 x y)

@roklenarcic thanks for pointing out the perf issue with mapv + I would never have expected it to be the slow part. went from 6s to 3s 😞

And here’s todays. https://github.com/bhauman/adv2024/blob/main/src/adv2024/day20/sol.clj I just got all the points on the track in the manhattan dist and worked from there.

10 seconds for part 2. I’m definitely doing some extra work but meh ….

I definitely didn’t like how this was day was specified.

spent too much time on part 1 and ran out of energy. maybe tomorrow. today was tough

so... close...

that was me for about an hour 😅

reminder that this exists: https://akovantsev.github.io/corpus/clojure-slack/adventofcode it is https://clojurians-log.clojureverse.org/adventofcode as a single file with extra search/navigation

Makes total sense to go the last five days here 😃 . And I don’t think there will be a huge exodus. At least not very quickly.

That said, Zulip has much less features than Slack, but it also has some nice things, like spoiler-support. So you can mark part of a message as spoiler and people will have to expand it to see. Could come in pretty handy for AOC next year 😃

It's also very very easy to make dedicated threads for different days, and have threads for people who need help/hints but don't want to get spoiled.