ShareMyScreen/AdventOfCode/2022/11/MonkeyInTheMiddleJP
Entire solution
i11=: freads'11.txt'
NB. parse, and set worry, tft, mig, cts globals
init=: {{
NB. assume monkey num 0-based and in order.
NB. 5 x #monkeys boxes; 0 worry; 1 inspect; 2 test; 3 true; 4 false
bx =: |: }."1 (<;._1;._2~ LF2&E.) LF([,,~) y
worry =: ".@(17&}.)&.> {. bx NB. num worry boxes
mig =: 0$a: NB. monkey inspection gerunds
for_ix. i.{:$bx do.
NB. assume ops 100% J (e.g. no /)
mig =: mig , 3 : ((('old';' y ') rplc ~ 18&}.)>ix{1{bx)`''
end.
dft =: |: ".@({:&.;:)&> 2 4 3{b NB. Nx3 divisor/false/truex
cts =: 0#~#dft NB. treated item counts
#dft NB. return # monkeys
}}
NB. Monkey function: y: monkey number
monkey =: {{
cts=: ( cts +&(y&{) #&>worry ) y}cts NB. update counts
for_it. >y{worry do. NB. distribute items
nv=. <.@%&3 (mig@.y) it NB. new value
dest=. nv (}.@] {~ 0=(|~{.)) y{dft NB. destination ~ test
NB. append nv to worry of dest
worry =: (nv ,~&.> dest{worry) dest} worry
end.
worry=: a: y}worry NB. zap list as done.
y NB. return monkey number for iteration
}}
busy=: {{*/2{.\:~cts}}
NB. note: depends on non-specified order of execution of "0!
part1=:busy@:(monkey"0^:20)@i.@init
NB. part B: no more 3%~, 10000 rounds instead of 20
run=: {{
wmp =. |: ; (,.&.> <"0@i.@#) worry NB. worry-monkey pairs
mod =. */mods=.{."1 dft NB. global modulo and seperate moduli
des =. }."1 dft NB. destinations for results: 0 and 1, for each monkey
for_ix. x (*$i.@]) y do. NB. loop over all monkeys x times
nn =.#vix=. ix I.@:= {:wmp NB. indexes into wmp where monkey=ix
if. nn=0 do. continue. end. NB. skip if monkey has no items
dest=. (ix{des) {~ 0=(ix{mods)&| NB. verb: destination based on test (on new val y)
NB. what to insert as values and monkeys
what=. vix (, dest)@(mod | mig@.ix@({ {.)) wmp
where=. 0 1 >@,@{@; vix NB. where in wmp to insert
wmp=. what where} wmp NB. perform actual update
cts=: (nn+ix{cts) ix} cts NB. update counts
end.
*/2{.\:~cts NB. return 2 most busy monkeys
}}
part2=:10000&run@init
(part1;part2)i11
The data
Monkeys are playing a game with the items from your backpack. Each monkey has some items, and the amount you are worried about each item is listed (the worry level). Then the monkey inspect the item, changing the worry level, and decides to which monkey to throw the item next. Each monkey takes its turn and this continues in a number of rounds.
The given test data is as follows:
Monkey 0:
Starting items: 79, 98
Operation: new = old * 19
Test: divisible by 23
If true: throw to monkey 2
If false: throw to monkey 3
Monkey 1:
Starting items: 54, 65, 75, 74
Operation: new = old + 6
Test: divisible by 19
If true: throw to monkey 2
If false: throw to monkey 0
...
Different monkeys are separated with empty lines; it appears the monkeys come in order. For each monkey, there are 5 lines:
- the worry levels for the items the monkey has
- the operation performed on the item's worry level before inspection
- the test performed (always divisibility)
- the destination if the test is true
- the destination if the test is false
Part 1
As there are quite a bit of parameters to pass around, I chose to store state in globals. init does the parsing, first boxing each line for each monkey. Worry level parsing is simple: discard the text and convert to numbers under open. Then, I want to store the inspection operation in gerunds, so I can select the right one to run from an array; this is done easiest in an explicit loop, because it involves applying the explicit definition conjunction (:). dft defines for each monkey the divisor for the divisibility test, the destination when false and the destination when true; cts keeps track of the item counts for each monkey.
init=: {{
NB. assume monkey num 0-based and in order.
NB. 5 x #monkeys boxes; 0 worry; 1 inspect; 2 test; 3 true; 4 false
bx =: |: }."1 (<;._1;._2~ LF2&E.) LF([,,~) y
worry =: ".@(17&}.)&.> {. bx NB. num worry boxes
mig =: 0$a: NB. monkey inspection gerunds
for_ix. i.{:$bx do.
NB. assume ops 100% J (e.g. no /)
mig =: mig , 3 : ((('old';' y ') rplc ~ 18&}.)>ix{1{bx)`''
end.
dft =: |: ".@({:&.;:)&> 2 4 3{b NB. Nx3 divisor/false/truex
cts =: 0#~#dft NB. treated item counts
#dft NB. return # monkeys
}}
This line is interesting:
mig =: mig , 3 : ((('old';' y ') rplc ~ 18&}.)>ix{1{bx)`''
In order to put verbs in a list, one needs to turn them into gerunds, which allows you to treat verbs as nouns, like passing them to other verbs or putting them in lists. 3 : literal defines an explicit verb, with the literal as body; I create the body by replacing old with y, assuming there is no division (which would error if it happened to be present). Once this verb is created, the conjunction Tie (`) turns it into a gerund, with as right argument the empty list, adding the verb on the left to the empty list of gerunds. Gerunds are not a separate type in J, they are just boxes, and for the empty list, J does not distinguish between types (mostly), so is easy to type and understand.
For part 1, my initial idea of just simulating each monkey in turn proved sufficiently performant. I wrote a monkey verb that takes as argument the monkey number (0-based), and uses that to index into the various arrays created by init before. At the start of each turn, it updates the counts of the monkey adding the number of the items it has in stock. After that, it loops over all items, finding the new worry value nv for each item and the destination monkey dest based on the divisibility test and destinations encoded in dft. Lastly, the item is added to the end of the destination monkey's inventory.
monkey =: {{
cts=: (cts +&(y&{) #&>worry ) y}cts NB. update counts for this monkey
for_it. >y{worry do. NB. distribute items
nv=. <.@%&3 (mig@.y) it NB. new value
dest=. nv (}.@] {~ 0=(|~{.)) y{dft NB. destination ~ test
NB. append nv to worry of dest
worry =: (nv ,~&.> dest{worry) dest} worry
end.
worry=: a: y}worry NB. zap list as done.
y NB. return monkey number for iteration
}}
Gerund creation was discussed above, but how do we use gerunds? The above verb shows one use: mig@.y. There's two conjunctions that are specifically designed to work on gerunds: atdot|Agenda (@.) and Evoke gerund (`:). Here, agenda is the one to use: it allows to pick a verb from a gerund (in this casemig) by specifying it's index (here y) in the list (@. has other uses, like recursion, etc).
After executing the monkey verb for each monkey for 20 rounds, I should get the product of the item counts of the two busiest monkeys, which translates literally:
busy=: {{*/2{.\:~ct}}
Piecing together the parts defined:
NB. note: depends on non-specified order of execution of "0!
part1=:busy@:(monkey"0^:20)@i.@init
Last thing I would note: It is important (in general, but especially when writing J) to be explicit about your assumptions: It aids tremendously if you wrote code that fails, or even worse, it works on the test input, but not on your own input. J's terseness is not an excuse to skip on comments: I would have been unable to understand my own code if not documented.
In this solution, I made several assumptions (all of which I noted when writing the code):
- The monkeys are presented in order and their numbering is 0 based.
- Theres no division in the monkey verbs (I hope it's the same for your input; otherwise, add
;'/';'%'to the rplc call in init). - The code relies on the undocumented (and thus not guaranteed) order of execution for the monkey verbs at rank 0. This behaviour could change if the implementation changes (e.g. if ever rank is parallelised, for instance).
Part 2
Part two removes the limitation of the worry levels by dividing by 3 and rounding down, causing the worry levels to soar quickly. Additionally, 10000 rounds are run, instead of the 20 rounds of part 1. This happens often in AoC: the first part asks for a solution; the second pushes the solution so that merely bruteforceing it won't work.
I don't recall exactly why, but my initial attempt to apply the reasoning of part 1 to part 2 failed to complete in a time what appeared reasonable to me. Now, retrying the following completes in 3.5s on my phone (I don't know what went wrong before):
monkey2 =: {{
cts=: (cts +&(y&{) #&>worry ) y}cts NB. update counts for this monkey
for_it. >y{worry do. NB. distribute items
nv=. 9699690 | (mig@.y) it NB. new value (for me, 9699690 is */{."1 dft)
dest=. nv (}.@] {~ 0=(|~{.)) y{dft NB. destination ~ test
NB. append nv to worry of dest
worry =: (nv ,~&.> dest{worry) dest} worry
end.
worry=: a: y}worry NB. zap list as done.
y NB. return monkey number for iteration
}}
busy@:(monkey2"0^:10000)@i.@init i11
Anyway, my patience ran out, and I decided to rewrite the code for speed. Looking at the monkey verb above, several things are likely slowing down the process (these considerations generally apply, not only for this problem):
- The items are treated one by one in a loop, while they could be treated all at once (how, see below).
- The worry lists are emptied, recreated and appended to at every item. It would be better if I could just create a single array, updating values, rather than creating/destroying/changing sizes.
Two important things can be noted in this problem:
- Although the problem explicitly states the items are appended to the end of the monkey's list, the order actually does not matter as all the items are treated anyway in the same single turn. So instead of keeping a list of values for every monkey, I can keep a list of (worry value, monkey index) pairs (stored in wmp).
- The only tests are divisibility tests, and the values are low. Additionally, the value itself does not matter; only its divisibility. I can thus do all operations on values modulo the product of all divisors in order to keep the worry values integers. in my input they were all prime numbers (something I took as a further hint for using their product as modulo).
The implementation is as follows:
run=: {{
wmp =. |: ; (,.&.> <"0@i.@#) worry NB. worry-monkey pairs
mod =. */mods=.{."1 dft NB. global modulo and seperate moduli
des =. }."1 dft NB. destinations for results: 0 and 1, for each monkey
for_ix. x (*$i.@]) y do. NB. loop over all monkeys x times
nn =.#vix=. ix I.@:= {:wmp NB. indexes into wmp where monkey=ix
if. nn=0 do. continue. end. NB. skip if monkey has no items
dest=. (ix{des) {~ 0=(ix{mods)&| NB. verb: destination based on test (on new val y)
NB. what to insert as values and monkeys
what=. vix (, dest)@(mod | mig@.ix@({ {.)) wmp
where=. 0 1 >@,@{@; vix NB. where in wmp to insert
wmp=. what where} wmp NB. perform actual update
cts=: (nn+ix{cts) ix} cts NB. update counts
end.
*/2{.\:~cts NB. return 2 most busy monkeys
}}
run uses the same initialisation as part 1. The code loops over every monkey index ix x times (in this case 10000 times). vix keeps the indices (into wmp) of the worry values that are in the current monkey's possession. If the monkey does not have any items, continue. skips the current loop iteration (I did not check the actual speedup though). Based on the current monkey's modulo and destinations, the verb dest determines the actual destination based on the new value. I like to split complex amends into "what", "where" and "wherein" (if present) parts. This makes it handier to think about, and, I think it has a higher likelihood of ending up doing the amend in place. I tried making them verbs and that was effectively slower.
As you can see, run treats all items for a single monkey at once, and only updates the values and destinations in wmp, rather than manipulating each monkey's list.
As all processing is done in run, there's no need to use busy:
part2=:10000&run@init
Eventually, my rewriting efforts were rewarded: the initial 3.5s runtime was reduced to 0.66s (5x speed up).