I really dislike these puzzles. About to search the Googles for someone who cares more about finding the trick than I. 🙂

It has something to do with the fact that all of the "divisible by" tests are with prime numbers.

Got it. It's related to the Chinese Remainder Theorem. I don't remember exactly how it works, but this is what I did: When reducing your worry, for part 1, do what you did. For part 2, take the remainder of your item worry amount by the product of all of the test divisors across all monkeys.

thx for the tip. problem solved!

Woot!

Thanks for the tip!

I don’t think this is related to Chinese Remainder Theorem. At least, you don’t apply the Chinese Remainder Theorem in order to solve it. The trick is we can reduce the large numbers modulo the LCM of all the monkey’s divisors, without invalidating any of the monkey’s division checks. The monkey’s divisors don’t need to be prime for this modulo LCM approach to work. But since they are all prime, the LCM is simply the product. The CRT, btw, is about finding a number that satisfies a set of remainder constraints, whereas this problem is about divisibility constraints.

imagine instead that there was only one check: “is the worry divisible by 12?” then it’s fairly clear that there’s no reason to store worry greater than 12, you can apply mod 12 after every step since it doesn’t change the result of the test. we can do something similar with multiple tests, but we have to find a mod to apply which won’t change the results of any of the tests. this needs to be a number that is divisible by all the tests, the smallest of which is the LCM (but any common multiple will do)

I wonder is there some other way to solve it within reasonable time?

I’d imagine not. napkin justification: I assume all the inputs have the new = old * old operation. say an item hits that operation every 10 rounds, then in 10000 rounds you square an items worry 1000 times, which if an item starts with worry 2 lands you with worries of

2^2^1000

I genuinely enjoyed today's problem, I think it may be my favorite this year so far... except for part 2 😄

I thought I had understood how the modulo thing works, but I still can't explain why ((big-x mod y) * (big-x mod y)) divisible by z is equivalent to (big-x * big-x) mod y divisible by z

ok got it https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication

https://gitlab.com/maximoburrito/advent2022/-/blob/main/src/day11/main.clj I really don't enjoy the aoc problems that have a math trick in them. Thankfully this was a somewhat obvious one, but still...

Ran fast enough with memoization. https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2022/day_11_monkeys.clj [Edit] — had to go back and make sure sample puzzles (with only 4 monkeys instead of 8) also worked.

Write-up complete. May this be the only "you'll never get it if you don't know the gimmick" problem of the season! • https://github.com/abyala/advent-2022-clojure/blob/main/docs/day11.md • https://github.com/abyala/advent-2022-clojure/blob/main/src/advent_2022_clojure/day11.clj

https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2022/11.clj I’ll take maths tricks over “reverse engineer this pseudo assembly” any day 😅

https://github.com/zelark/AoC-2022/blob/master/src/zelark/aoc_2022/day_11.clj

@U01HHBJ56J1 my code is pretty the same as yours this time 🙂

hate the problems which require modulo arithmetic knowledge

Very similar to some above, I think we’re influencing each other? I don’t like my parse-op yet. https://github.com/tschady/advent-of-code/blob/main/src/aoc/2022/d11.clj

AOC rule #7: if the numbers get too big, there’s a mod with primes

Had to learn the trick from the other thread 😞 Not a big fan of the math trick ones. Not my best today. https://github.com/Ramblurr/advent-of-code/blob/main/src/aoc/2022/day11.clj

practiced in writing a better op fn, dnk how to make it better

(defn make-op-fn [s]
  (let [[_ _ x op y] (->> s (re-seq #"\w+|\+|\*") (map symbol))]
    (-> (list 'fn [x] (list op x (cond-> y (not= x y) (-> name parse-long))))
        (eval))))

((make-op-fn "Operation: new = old * 3") 5) ; => 15
((make-op-fn "Operation: new = old + 5") 5) ; => 10
((make-op-fn "Operation: new = old + old") 21) ; => 42

took me ~2 hours to finally get the trick after I realized all the div checks were for primes. first idea was to store the factorization of the number, but that wouldn't work with sums. turns out it was much simpler than that https://github.com/FelipeCortez/advent-of-code/blob/master/2022/11.clj

Was happy with the parsing, but I think round could need a cleanup. https://github.com/volesen/aoc2022/blob/main/day11/day11.clj

https://github.com/benjamin-asdf/advent-of-code/blob/master/src/Y2022/day11-part2.clj messy, part 2 in a separate file.

@U067R559Q rather than parsing everything to symbols and then re-parsing the numbers as longs, you could read-string from the start? I’d never touch it in production code, so it’s easy to forget that it exists, but I find it really useful for AoC. this is what I ended up with:

(let [[a op b] (map read-string (re-seq #"old|\+|\*|\d+" line))]
  (eval (list 'fn ['old] (list op a b))))

Add me to the didn't love today club. My solution like a lot of others here - Solved part 1 just using straightforward simulation as others have. Wrote and tested part 2 using mod on he product of the test divisors (also as others have done). Started it running and waited. And waited Started to try to figure out how to improve things when I got an answer and entered it. On a lark, I decided to run the code through Babashka for a lark. The part 2 solution that took minutes and minutes completed in half a second 🙂

@U04575QMU2K I like your simple and self-documenting parsing strategy.

Some confessions for today. Originally I skipped writing a parser and just wrote some edn for my input (though I've gone back and written a parser), and second instead of generalizing my solution and piping through the worry-manager, I just made it a var and used a binding to set it to mod appropriately for part-2. Not sure how guilty I should feel about that second one. https://github.com/alexalemi/advent/blob/main/2022/clojure/p11.clj

Geez that sucked https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day11/sol.clj

yeah, its tough moving one mental model of AOC from pure data structure manipulation to this type of solution, anyone else implement these?

(defn modulo* [a b m]
  (mod (* (mod a m) (mod b m)) m))

(defn modulo+ [a b m]
  (mod (+ (mod a m) (mod b m)) m)

had to look them up

@U064J0EFR well maybe it sucked, but hey you had occasion to write a function called monkey-around 😆

https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2022/day11.clj

(ns aoc.day-11
  (:require [clojure.string :refer [join split]]))

(defn parser [acc [_ & r]]
  (let [is (drop-last 4 r)
        [[o _ & a] d t f] (take-last 4 r)
        a  (when (not= (first a) \o) (parse-long (join a)))]
    (conj acc {:is (vec is)                                      ;; items
               :ac 0                                             ;; activation count
               :dv d                                             ;; divisor
               :op #(({\+ + \* *} o) % (or a %))                 ;; operation
               :tx #(if (zero? (mod % d)) t f)})))               ;; transfer

(let [data (->> (split (slurp "data/2022_11") #"\n\n")
                (map #(re-seq #"[*+] ?(?:\d+|old)|[\d]+" %))
                (map (fn [c] (map #(or (parse-long %) %) c)))
                (reduce parser []))
      ixs  (range (count data))
      mod* (reduce * (map :dv data))                             ;; limit int sizes, mod with * of dv
      turn (fn [d ms mi]
             (let [{:keys [op tx is]} (nth ms mi)
                   throw (fn [a i]
                           (let [i  (mod (quot (op i) d) mod*)
                                 di (tx i)]
                             (-> (update-in a [mi :is] (comp vec rest))
                                 (update-in [mi :ac] inc)
                                 (update-in [di :is] conj i))))]
               (reduce throw ms is)))
      res  (fn [d] (iterate #(reduce (partial turn d) % ixs) data))]
  (prn {:one (->> (nth (res 3) 20) (map :ac) (sort >) (take 2) (reduce *))
        :two (->> (nth (res 1) 10000) (map :ac) (sort >) (take 2) (reduce *))}))
;; {:one 100345, :two 28537348205}

totally agree

https://github.com/sicmutils/sicmutils/blob/main/src/sicmutils/modint.cljc

if you want to push some work into a type, given ModInt a try!

https://github.com/sicmutils/sicmutils/blob/main/test/sicmutils/modint_test.cljc#L61

Sorry - I meant to put it under the thread- I goofed.

Thanks 👍

Yes sorry I thought this was todays thread - deleted.