Clojurians Log v2

https://gitlab.com/maximoburrito/advent2024/-/blob/main/src/day16/main.clj The sad thing is that I promised I wouldn't stay up extra late this year. So when after and hour and half I wasn't sure why my part2 wasn't working, I did actually go to bed. But, I couldn't sleep so I came back to finish it. The funny thing is I had the right answer all along, but I thought it was wrong because I got confused about which sample data I was testing against.... Wheee... Anyway - super slow and super ugly:

Couldn’t be worse than me lol, more than 3 hour solve

https://github.com/dgtized/advent-of-code/blob/master/2024/src/day16/reindeer_maze.clj#L1 -- The first part I just re-used a*-search I cobbled together last year for day17, and re-used the same trick of including position, direction, and cost in the successor state of each graph node to search. For the 2nd part I used the very cludgy and slow trick of taking each position in the existing best path, and one by one replacing that position with a blocker and recalculating if there is another path with equal cost to the initial best path. Then I just union together the set of all nodes in all of those paths. I suspect this would not work in all cases but works for the examples and my input, though at a very slow ~216s runtime.

Good ol' Dijkstra. During my testing, I saw that I always arrive facing North to the end, so I put it as a shortcut in my code. Could break on some input. Easy to fix but it makes the code ugly (well, uglier), so I don't wanna :P

Also internet went down for 2h, so I couldn't submit my answer 😞

Takes less than half a second for me for part2.

And the way I’ve solved it is by calculating the cost from each position to start and to end. And if the sum of that = cost of shortest path then the position is on one of the shortest paths.

loop recur "Elapsed time: 8350.083833 msecs" total

"Elapsed time: 1065.230333 msecs" for p1 w/o dragging paths along, so something clever could be done with {[xy dir] lowest-score} cheaper than 7 seconds

incredibly satisfying. out-of-the-box A* worked for part 1, for part 2 I pulled the goal-score map from the A* search and used that to cut-off the all paths DFS enumeration logic. ~2 second for p2 [I'm not re-optimizing my A* search 😅) https://github.com/tildedave/advent-of-code/blob/main/src/advent2024/day16.clj#L90-L137

(my solution relies on a generalized A* search that I used for older AoCs too)

Dijkstra runs in 340ms for part1 and 2 at the same time. Build the map of cost and then just rebuild the path with a reverse bfs.

still stuck at part 1 😞 implemented Dijkstra which works for both examples but not the actual input

any idea/hint of things to check?

Yes.

Pure dijkstra doesn't work if you don't consider same coordinates with different direction as different costs.

could be indeed, im not confident about that part. thanks

Modified Dijkstra with storing all alternative paths (ie. when next is visited and the cost is the same). Around 250ms for both parts together. https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2024/day16.clj

https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_16.clj

very nice and short

https://gist.github.com/RokLenarcic/fcfa3417b7620ea22751d074911aa233

And here’s todays: https://github.com/bhauman/adv2024/blob/main/src/adv2024/day16/sol.clj It’s very similar to the frequencies implementation for the stones on day 11, Edit: the above has been re-implemented with djikstra’s.

Here is todays, loosely based on my solution for 2023, day 17, runs in about 800ms https://github.com/ChrisBlom/advent-of-code/blob/master/src/adventofcode/2024/day16.clj Part 1 is just dijkstra's shortest path, tracking best scores by [position direction] Part 2 modifies some of the pruning to keep paths with equals scores in the search space

yeah I wish I had used dijkstra’s instead of some weird derivative of it that I cobbled together I kept telling myself “oh this will work fine”. That voice in my head is nothing but trouble.

@jvuillermet I think I started with the same approach as yours, which made the score a bit awkward to compute, but had a 💡 moment and the code now works for me. spoiler: consider the state can transition from [[13 1] :e] to [[13 1] :n] and so on, not just between positions

finally!

@felipecortezfi Congrats! Just fyi, there are queues in clojure, and also there is if you need.

@malaingreclement, I reviewed your solution — it’s really nice! That’s how I wanted to solve it, but I got confused while constructing prev map, so I changed my approach. Basically, it might run even faster (~2x), if we get rid of dist cause we already have everything in prev map. I wrote a variation https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_16_fast.clj

@malaingreclement I know about PersistentQueue, but I wouldn't be able to get the lowest-cost position using it, right? it feels a bit dirty using a java mutable data structure, but imo in this case it just reads so well. didn't know about data.priority-map though!

Oh yeah totally, I was just letting you know. Also priority-maps are not mutable, and a mutable data structure makes complete sense in Dijkstra. In general, I wish transients existed for more data types, and I wish something like update! for transient map-like structures was a thing. Like, when you're iterating on states, you do not want to be re-generating copies of immutable structures every steps.

https://www.twitch.tv/timpote

dunno. I brute forced with simple clojure, takes 13s.

part1 is like 10s, second 8. I suppose that in 2015, Eric was not as experienced in puzzle making and it's less guaranteed to have an elegant solution.

I found it in my archive

;; 

(defn factors [n]
  (into (sorted-set)
        (comp (filter #(zero? (rem n %)))
              (mapcat #(-> [% (/ n %)])))
        (range 1 (inc (Math/sqrt n)))))

;; part 1
(time (let [limit (/ 34000000 10)]
        (->> (pmap #(-> [% (reduce + (factors %))]) (iterate inc 1))
             (some (fn [[_ presents :as t]] (when (>= presents limit) t))))))

;; part 2
(time (let [limit (/ 34000000 11)]
        (->> (pmap
              #(-> [% (reduce + (filter (fn [n] (>= (* n 50) %)) (factors %)))])
              (iterate inc 1))
             (some (fn [[_ presents :as t]] (when (>= presents limit) t))))))

That was my first try. With pmap and everything. But my computer is not powerful enough for it, it takes forever.

(defn- score [mult elves]
  (reduce + 0 (map #(* mult %) elves)))

(defn- elves
  "Return set of elf numbers that visit `house`.  Elves visit each
  house evenly divisible by itself, up to `limit` deliveries."
  [limit house]
  (remove #(> house (* limit %)) (math-util/factors house)))

(defn- solve
  "Returns lowest house number of house to get at least `present-target`."
  [present-target score-mult elf-limit]
  (->> (range)
       (map (partial elves elf-limit))
       (map (partial score score-mult))
       (take-while (partial > present-target))
       count))

(defn part-1 [input] (solve input 10 Integer/MAX_VALUE))

(defn part-2 [input] (solve input 11 50))

no pmap

guess the only optimization is i stop looking for factors of N at sqrt.

Oh I know where I went wrong lmao.

and some laziness

I was iterating on (range 1 (N/2)) and on modulo == 0, only keeping one of the factors ...

In effect taking twice as long on every number.

I recognized this as the sigma function from number theory (part 1) which has a closed form solution. https://github.com/tildedave/advent-of-code/blob/main/src/advent2015/day20.clj

I believe part 2 is roughly brute force

https://en.wikipedia.org/wiki/Divisor_function

let me check

(time (p1 input))
"Elapsed time: 302.587625 msecs"
=> 776160
(time (p2 input))
"Elapsed time: 186.372542 msecs"
=> 786240

Thanks @tildedave, I'll read up on the sigma function !

that’s just bruteforce, non-parallel

I think that in 2015 the only one in 20-25 day range that was quite hard was 23 part 2

since you basically have figure out what the program does

day 19 was the worst that year iirc