Fork me on GitHub
<
2022-12-11
>
ryan echternacht06:12:28

Anyone have thoughts on the handling the massive numbers generated by day 11?

ryan echternacht06:12:44

this is definitely where I'm weakest for AOC

Andrew Byala06:12:22

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

Andrew Byala06:12:58

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

Andrew Byala06:12:01

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.

1
Apple06:12:51

thx for the tip. problem solved!

🎉 1
robertfw07:12:42

Thanks for the tip!

😆 2
wevrem08:12:31

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.

👍 2
1
Callum Oakley09:12:56

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)

1
alekszelark10:12:30

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

Callum Oakley12:12:51

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``
which is an absurdly astronomical number (about 3x10^300 digits)

marcofiset15:12:04

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

Felipe16:12:54

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`

norman07:12:59

Day 11 - Solutions

norman07:12:08

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...

wevrem07:12:33

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

🙌 1
Andrew Byala07:12:51

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.mdhttps://github.com/abyala/advent-2022-clojure/blob/main/src/advent_2022_clojure/day11.clj

Callum Oakley09:12:52

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 😅

alekszelark10:12:40

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

alekszelark10:12:58

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

✔️ 3
Casey14:12:04

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

alekszelark14:12:40

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``````

Felipe15:12:04

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

Vincent Olesen15:12:11

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

Callum Oakley17:12:53

@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))))``````

1
zamansky18:12:16

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 🙂

👍 1
Joe Dumont20:12:05

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

Alex Alemi22:12:55

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

bhauman03:12:10

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)``````

bhauman03:12:21

wevrem04:12:34

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

😂 1
mbjarland10:12:59

``````(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}``````

nooga11:12:11

uh I don't like today's problem at all 😛

💯 2
nooga11:12:42

I can write compilers and golf, don't ask me to do modulo arithmetic

💯 4
alekszelark12:12:56

totally agree

Sam Ritchie14:12:08

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

wevrem17:12:12

I may be in the minority, but I actually liked today’s problem. It’s not a bad thing to have some knowledge of modular arithmetic in your bag of tricks, and it’s at least as important as code golf.

3
solf18:12:31

I would like if people keep talks specifics about a day inside the daily thread, some people (like me) is behind on the daily puzzles

zamansky18:12:41

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

solf18:12:38

Thanks 👍

Mark Wardle19:12:40

Yes sorry I thought this was todays thread - deleted.