On Day 11 monkeys stole our stuff :) There is a nice story on the puzzle page, but I will just put shorter version. So there are some monkeys and each one is inspecting our items. Those items are basically numbers and what monkeys do is to apply either addition or multiplication on such a number and then if new number is divisible by X pass it to monkey A and if divisible by Y pass it to monkey B.
All of this is specified in the input file:
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
Monkey 2:
Starting items: 79, 60, 97
Operation: new = old * old
Test: divisible by 13
If true: throw to monkey 1
If false: throw to monkey 3
Monkey 3:
Starting items: 74
Operation: new = old + 3
Test: divisible by 17
If true: throw to monkey 0
If false: throw to monkey 1
The task is to parse it, simulate 20 rounds and return how many times top monkey touched our items.
Here is the full code:
data = File.readlines("11.txt", chomp: true)
def parse_items(string)
match = string.match(/Starting items: (.+)/)
match[1].split(", ").map(&:strip).map(&:to_i)
end
def parse_operation(string)
match = string.match(/Operation: new = (.+)/)
lambda { |old| eval(match[1]) }
end
def parse_test(string)
match = string.match(/Test: divisible by (\d+)/)
match[1].to_i
end
def parse_true(string)
match = string.match(/If true: throw to monkey (\d+)/)
match[1].to_i
end
def parse_false(string)
match = string.match(/If false: throw to monkey (\d+)/)
match[1].to_i
end
index = 0
monkeys = []
while index < data.size
items = parse_items(data[index + 1])
operation = parse_operation(data[index + 2])
test = parse_test(data[index + 3])
if_true = parse_true(data[index + 4])
if_false = parse_false(data[index + 5])
monkeys.push({
items: items,
operation: operation,
test: test,
if_true: if_true,
if_false: if_false,
inspections: 0
})
index += 7
end
20.times do
monkeys.each do |monkey|
while monkey[:items].any?
item = monkey[:items].shift
item = monkey[:operation].call(item)
item = item / 3
if item % monkey[:test] == 0
monkeys[monkey[:if_true]][:items].push(item)
else
monkeys[monkey[:if_false]][:items].push(item)
end
monkey[:inspections] += 1
end
end
end
puts monkeys.map { |monkey| monkey[:inspections] }.sort[-2..-1].reduce(:*)
I am using a bunch of regular expressions to parse input data. To execute math operations I am using lambdas and eval. The variable passed to lambda is called old, so the evaled code will work, because it is also using the name old.
Now things are more difficult. Instead 20 we need to simulate 10000 rounds. If you change 20 to 10000 in the solution for Part A you can quickly notice the program will grind to a halt. This is because those numbers are getting insanely big. They never decrease, monkeys either add something or multiply and numbers get larger and larger. It was managable for 20 rounds.
Good news is we don’t need to know those full numbers. We only need to know if number is divisible by another number.
Let’s say we have a number 871, we need to multiply it by 139 and get modulo 17. We don’t need to multiply 871 by 139. We can just multiply 871 modulo 17 by 139.
irb(main):014:0> (871 * 139) % 17
=> 12
irb(main):015:0> ((871 % 17) * 139) % 17
=> 12
What if we want test modulo by different numbers, not just one. Well, you can do modulo by the product of all possible numbers:
irb(main):016:0> (871 * 139) % 7
=> 4
irb(main):017:0> (871 * 139) % 17
=> 12
irb(main):020:0> ((871 % (7 * 17)) * 139) % 7
=> 4
irb(main):021:0> ((871 % (7 * 17)) * 139) % 17
=> 12
Little disclaimer. I am no math expert. When solving this task I just thought that above is the case and it worked for this task.
Here is the full code:
require "debug"
data = File.readlines("11.txt", chomp: true)
def parse_items(string)
match = string.match(/Starting items: (.+)/)
match[1].split(", ").map(&:strip).map(&:to_i)
end
def parse_operation(string)
match = string.match(/Operation: new = (.+)/)
lambda { |old| eval(match[1]) }
end
def parse_test(string)
match = string.match(/Test: divisible by (\d+)/)
match[1].to_i
end
def parse_true(string)
match = string.match(/If true: throw to monkey (\d+)/)
match[1].to_i
end
def parse_false(string)
match = string.match(/If false: throw to monkey (\d+)/)
match[1].to_i
end
index = 0
monkeys = []
while index < data.size
items = parse_items(data[index + 1])
operation = parse_operation(data[index + 2])
test = parse_test(data[index + 3])
if_true = parse_true(data[index + 4])
if_false = parse_false(data[index + 5])
monkeys.push({
items: items,
operation: operation,
test: test,
if_true: if_true,
if_false: if_false,
inspections: 0
})
index += 7
end
10_000.times do |round|
monkeys.each do |monkey|
while monkey[:items].any?
item = monkey[:items].shift
item = monkey[:operation].call(item)
item = item % 9699690 # it is a product of all divisible numbers 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19
if item % monkey[:test] == 0
monkeys[monkey[:if_true]][:items].push(item)
else
monkeys[monkey[:if_false]][:items].push(item)
end
monkey[:inspections] += 1
end
end
end
puts monkeys.map { |monkey| monkey[:inspections] }.sort[-2..-1].reduce(:*)
9699690 is the product of all numbers from the input file used for modulo operation. It still took almost a minute to finish, but without modulo it slows down big time around round 60.