Clojurians Log v2

The sun will eat the Earth before you finish 😄

Someone estimated that their implementation would've taken the age of the observable Universe. Human beings don't handle exponential growth very well.

Hint: memoization

Hint: how relevant is the position of the stones?

dont really care about the positions, do I ? e.g. 0 -> 1 -> 2024 -> 20, 24, that's going to go from 1 stone to 2 stones, regardless of its position.

I’d never heard of this lang, I’m guessing its APL like.

certainly looks like it

but now at least it all makes sense

😉

UIUA is really cool language (if you are into the APL-like world at all) and is actively developed.

Finally did it. My god. This is terrible code. I missed something obvious and I'm anxious to discover what.

I just couldn't figure out how to have a clean history. The fact that I need to store the number of steps remaining was fucking with me. Ended up storing the tree. I don't think it's the way to go. Posting the code to shame myself into cleaning it up ><

OH so my whole code can be replaced by a one-liner because I didn't think of just counting at each step instead of storing the result. Cool cool cool cool. Godammit.

memoized recursion https://github.com/tschady/advent-of-code/blob/main/src/aoc/2024/d11.clj

hah, ya memoize isn’t saving me much since it only operates at that level. frequencies is better (and faster). it was a reflex from looking at the problem. memoize only useful if you run the problem multiple times.

memoizing the recursion relation seems ideologically better, I went with frequences as others have pointed out. https://github.com/tildedave/advent-of-code/blob/main/src/advent2024/day11.clj#L45-L56

Here’s todays: https://github.com/bhauman/adv2024/blob/main/src/adv2024/day11/sol.clj

~340ms for part 2

used recursion and memoize

managed to get ~448 µs (on 10yo machine) for part 2 with quite clean Clojure: https://github.com/vollcheck/aoc/blob/master/src/y24/day11.clj#L49

btw I examinated splitting number as string vs use of Math/pow, quot and rem and the latter is 2x faster on average

I know what I have to do, but my brain doesn't wanna.@malaingreclement try taking notes of your thought process so you can go back after and see what was leading you down the wrong path! Sometimes the thing that throws you off is a couple of steps before it actually happens and it's almost impossible to see that after it happens

I got pretty tripped up on checking the number of digits. Kept getting weird edge cases (log 1, log 10)... I even tried to find a closed form solution but this isn't project euler 🤣

My solution was able to rebuild the whole tree... Which is stupid, but yeah, I simply didn't keep in mind the goal of the exercise.

https://github.com/rjray/advent-2024-clojure/blob/master/src/advent_of_code/day11.clj I'm just sick over part 2. Like many, I brute-forced part 1 but realized almost immediately that it wouldn't work for part 2. So I got the idea to just keep a count of how many stones of each number there were in a given state and produce the next state from that. I didn't have to preserve any past state this way, and a (reduce + (vals <final>)) would give me my answer. But it didn't work; I kept getting answers wildly too high (I was only running part 2 for 25 blinks and comparing it to the brute-force part 1 answer). After about 2 hours and 40 minutes (11:40PM local time) I gave up and went to bed. This morning, I tried some other things with identical results. I believed in the algorithm, so I just yanked out the code and re-implemented it. Now, I was getting answers too low, but only slightly. Stepping each implementation through progressively more iterations, I finally found the last bug: when accounting for a split stone, if the two splits were the same number I was only counting one stone, not two. Problem solved, but still annoyed with myself.

As a fellow "stuck on an idea", you have all my compassion. Congrats on solving it!

@j3k.walczak (take (inc times)) last -> (drop times) first

split string + join - 250ms

This might err {L n R n} when L=R

Custom memoization after half of the day of (over)thinking. https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2024/day11.clj

memoized recursion too here! shortest code this year so far

(def count-stones
  (memoize
   (fn [n x]
     (if (zero? n)
       1
       (let [stone-length (count (str x))]
         (cond
           (zero? x)
           (count-stones (dec n) 1)

           (even? stone-length)
           (+ (count-stones (dec n) (parse-long (subs (str x) 0 (/ stone-length 2))))
              (count-stones (dec n) (parse-long (subs (str x) (/ stone-length 2) stone-length))))

           :else
           (count-stones (dec n) (* 2024 x))))))))

(def initial-stones (read-string (format "[%s]" (slurp "2024/11.in"))))
(reduce + (map (partial count-stones 25) initial-stones))
(reduce + (map (partial count-stones 75) initial-stones))

hah, practically identical to @roklenarcic

@tws I think memoize does prune a lot of steps even on the first, cold run

edit: i should benchmark memoization vs. frequencies

aha, yeah. thought about it harder and frequencies is definitely less computation. clever

@tws That’s not true. I wrote both and memoization beats frequencies.

I’ll retract these statements 🙂 Depends on how you define level

Here’s with memoization: https://gist.github.com/RokLenarcic/6caca85b7be6ba642b20ef70ffdd51fe Here’s without: https://gist.github.com/RokLenarcic/d154a81f747da21cf0ce63352870050c You can try it yourself. It varies a lot based on how hot the hotspot code is.

But I could optimize frequencies more. Remove merge with and use a transient and merge directly into it.

I’m having a hard time intuiting why the frequencies approach works. I understand its implementation but I’m having a hard time seeing the equivalence in the two methods.

you can think about it like a compaction of the list, e.g. if you have a 1024 in your list, it always becomes 10 24 in the next version of the list, and this happens whether there's 1 or 50.

so instead of 1024 .... 1024 ... 1024 ... 1024 ... you store {1024 4} etc

The key to that approach is that ordering doesn't actually matter despite the text saying it does. E: Regardless of what approach is more efficient in terms of time, the freqs approach does have the advantage of using constant stack space.

OK I got it. I was picturing it the frequency execution incorrectly.

Man, this one is so hard to give hints for without giving everything away! I just saw frequencies and TBH that was enough for me to both get the basic idea, and try out a simple naive implementation of the idea, which worked immediately.

My solution (came out pretty clean, I personally think, though not the shortest):

(ns advent-24.day-11
  (:require [clojure.string :as str]))

(defn parse-d11-input [fname]
  (->> (str/split (first (str/split-lines (slurp fname))) #"\s+")
       (mapv #(parse-long %))))

(defn d11-1-blink [stones]
  (reduce
    (fn [v stone]
      (cond
        (= 0 stone) (conj v 1)

        (even? (count (str stone)))
        (let [len (/ (count (str stone)) 2)
              sstone (str stone)
              l (parse-long (subs sstone 0 len))
              r (parse-long (subs sstone len))]
          (conj v l r))

        :else (conj v (* 2024 stone))))
    []
    stones))

(defn d11-2-blink [stone-freqs]
  (reduce
    (fn [m [stone freq]]
      (cond
        (= 0 stone) (update m 1 (fnil #(+ % freq) 0))

        (even? (count (str stone)))
        (let [len (/ (count (str stone)) 2)
              sstone (str stone)
              l (parse-long (subs sstone 0 len))
              r (parse-long (subs sstone len))]
          (-> m
              (update l (fnil #(+ % freq) 0))
              (update r (fnil #(+ % freq) 0))))

        :else (update m (* 2024 stone) (fnil #(+ % freq) 0))))
    {}
    stone-freqs))

(comment
  ;; Parsing input
  (def i (parse-d11-input "resources/input_11"))
  ;; Part 1
  (->> i
       (iterate d11-1-blink)
       (take 26)
       (last)
       (count))
  ;; Part 2
  (->> (frequencies i)
       (iterate d11-2-blink)
       (take 76)
       (last)
       (vals)
       (reduce +))
  )

@zengxh (= L R) is handled on prev line: (= L R) {L (* 2 n)}

Of course I missed that. You are right. @misha

https://gist.github.com/RokLenarcic/6caca85b7be6ba642b20ef70ffdd51fe

These are getting into oneliner territory. Yesterday too

https://gitlab.com/maximoburrito/advent2024/-/blob/main/src/day11/main.clj

how fast does it calculate (on empty cache)?

"Elapsed time: 213.921853 msecs"

(time (p2 input)) “Elapsed time: 114.840958 msecs”

I think that subs is faster than splitting string into a sequence and then reassembling it

Guys, any clues for part 2?

the usual crap

I cannot be more specific without telling everything, it’s so simple

Think about what’s the usual thing we do in AoC in those situations

@zelark Since this is the solution thread already, consider the example of [125 17] Then consider what you would have gotten for just [125] and just for [17]

frequencies! https://github.com/erdos/advent-of-code/blob/master/2024/day11.clj

Best case: "Elapsed time: 0.343692 msecs"

@erdos that’s even better

I did two implementations, with an explanation about memoizing results manually vs using Clojure's built-in support. • Blog: https://github.com/abyala/advent-2024-clojure/blob/main/docs/day11.md • Code: https://github.com/abyala/advent-2024-clojure/blob/main/src/advent_2024_clojure/day11.clj • Code with built-in memoization: https://github.com/abyala/advent-2024-clojure/blob/main/src/advent_2024_clojure/day11_memo.clj

thanks @erdos, when you said frequencies I got it

The old good frequencies, how could I miss it

I'm stumped. I know what I have to do, but my brain doesn't wanna. I know I have to account for the states repeating, and memoize that, but for some reason, I'm stuck on how to store the cache in a way that makes sense.

This is intensely frustrating.

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

@malaingreclement I see, I felt almost the same until freqs shed some light. Also I took a small break to restart my brain.

I don't see how frequencies applies to caching 😕 Like, yeah, I can count things that repeat and simplify the tree, but the naive implem doesn't work with a starting root of 0 on depth 75, so I'm struggling. I might just need to take a small break.

frequencies applies not to caching, but to reducing repeating stones, take a brake and mull it over

I think I pigeon-holed myself in a mapcat hell and it's not helping ^^. Imma come back to this later.