I'm working through 2022's Advent of Code and I'm on Day 11 part 2.
I have this solution:
(ns advent-of-code-2022.day11
(:require [taoensso.timbre :as log]))
(declare give-monkey-item)
(defrecord Monkey [items operation throw-item num-inspections])
(defn create-monkey [items operation divisor monkey-true monkey-false]
(->Monkey
items
operation
(fn [item monkeys]
(if (= (mod item divisor) 0)
(give-monkey-item item monkeys monkey-true)
(give-monkey-item item monkeys monkey-false)))
0))
(defn give-monkey-item [item monkeys catcher]
(update-in monkeys [catcher :items] #(conj % item)))
(defn throw-items [monkeys current-monkey]
(reduce (fn [monkeys item]
(-> item
(biginteger)
((.operation current-monkey))
((.-throw_item current-monkey) monkeys)))
monkeys
(.items current-monkey)))
(defn adjust-current-monkeys-inspections [monkeys current-monkey-index]
(let [current-monkey (get monkeys current-monkey-index)
num-items (count (.items current-monkey))]
(update-in monkeys [current-monkey-index :num-inspections] #(+ % num-items))))
(defn clear-current-monkeys-items [monkeys current-monkey-index]
(let [current-monkey (get monkeys current-monkey-index)
itemless-monkey (assoc current-monkey :items [])]
(assoc monkeys current-monkey-index itemless-monkey)))
(defn play-turn [monkeys current-monkey-index]
(let [current-monkey (get monkeys current-monkey-index)]
(-> monkeys
(throw-items current-monkey)
(adjust-current-monkeys-inspections current-monkey-index)
(clear-current-monkeys-items current-monkey-index))))
(defn play-round [monkeys]
(reduce (fn [monkeys monkey-index]
(play-turn monkeys monkey-index))
monkeys
(range (count monkeys))))
(defn play-rounds [monkeys num-rounds]
(reduce (fn [rounds round-number]
(log/info round-number)
(let [latest-monkeys (last rounds)]
(conj rounds (play-round latest-monkeys))))
[monkeys]
(range num-rounds)))
(defn calculate-monkey-business [monkeys num-rounds]
(let [rounds (play-rounds monkeys num-rounds)]
(->> (last rounds)
(map #(.-num_inspections %))
(sort)
(reverse)
(take 2)
(reduce *))))
I'm testing it using this code:
(ns advent-of-code-2022.day11-test
(:require [clojure.test :refer :all]
[advent-of-code-2022.day11 :refer :all]))
(def monkeys
[(create-monkey
[54 98 50 94 69 62 53 85]
(fn [old] (* old 13))
3 2 1)
(create-monkey
[71 55 82]
(fn [old] (+ old 2))
13 7 2)
(create-monkey
[77 73 86 72 87]
(fn [old] (+ old 8))
19 4 7)
(create-monkey
[97 91]
(fn [old] (+ old 1))
17 6 5)
(create-monkey
[78 97 51 85 66 63 62]
(fn [old] (* old 17))
5 6 3)
(create-monkey
[88]
(fn [old] (+ old 3))
7 1 0)
(create-monkey
[87 57 63 86 87 53]
(fn [old] (.pow old 2)) ; this is slow for big numbers
11 5 0)
(create-monkey
[73 59 82 65]
(fn [old] (+ old 6))
2 4 3)
])
(deftest day11-full-test-part2
(testing "day11-full-test-part2"
(is (= (calculate-monkey-business monkeys 10000) 10605))))
This tries to run for 10000 iterations, but around the 200th iteration the marked function (fn [old] (.pow old 2)) in the test code starts squaring very large BigIntegers and gets extremely slow. It is so slow that the program would probably take a few days to finish. If I replace .pow with a simple +, the program completes in a few seconds. .pow is the latest function I've tried; I started with a simple (* old old) and tried clojure.math.numeric-tower/expt as well, but all three have this problem.
Is there a way to square these large BigIntegers efficiently in Clojure?
Alan Thompson has some advice that will speed up your program a little. I doubt it will be as much as 1000x - for small numbers, it would probably be more like 100x compared to un-hinted .pow, and 2x compared to (* x x) - but even if it were, this will not be close to enough of a speedup to save you. In fact, as I will show in a moment, speed is not your only limiting factor!
You note that things get slow around the 200th iteration out of 10000, and predict a few days' running time. But you're looking at a process with exponential running time, and people tend to grossly underestimate how big an exponential formula will get. So I predict you will need a real algorithmic change, not just some fairy dust to sprinkle on the existing algorithm.
Why do I say it's exponential? Well, you have observed that the dominating factor is operations of the form x = x * x: squaring a number and then moving on. Of course because of all the monkey business not every round will involve squaring all the numbers, but that's what will dominate in making your numbers large. Imagine ten thousand rounds of just writing x = x * x, starting with an innocuous number like 2. You square 2 (2^1), then square the resulting 4 (2^2), then square the resulting 16 (2^4), then square the resulting 256 (2^8), and so on, squaring ten thousand times. That process computes 2^(2^10000): clearly exponential (in fact, superexponential, because the exponent itself grows exponentially).
Why is this a problem? Well, storing the exact binary representation of a number like 2^(2^10000) in your computer's memory is simply impossible. Storing such a number's exact binary representation anywhere in the entire universe is impossible: there's not nearly enough atoms to make up all the bits. Of course, I've overestimated by assuming that each round involves squaring the number; but you can expect around 20% of the numbers to be squared each round, because the monkey who tests for divisibility by 5 throws to the monkey who squares. This is still far outside the realm of possibility.
So any approach that uses a BigInteger to store the exact representation of this number is unworkable. Fortunately, there are some easy improvements to make that will let you perform this simulation lightning fast. I don't want to give away the whole thing, since much of the fun is solving the problems yourself. Here are a few hints, spoilered individually.
You don't need the exact values themselves at the end of the process.
You don't need the exact values during the process either
All you need is to tell whether they're divisible by some primes
Isn't it rather nice they never ask you to divide by something?
Have you considered modular arithmetic?