On Day 15 we are working with number generators. We have two generators that start with given numbers as input. In each iteration, generator multiplies its value by fixed number and keeps the reminder of diving by 2147483647.
We need to count how many times lowest 16 bits matched for both generators after 40 million iterations.
Here is the solution:
a = 65
b = 8921
count = 0
40_000_000.times do
a = (a * 16807) % 2147483647
b = (b * 48271) % 2147483647
if a & 0xffff == b & 0xffff
count += 1
end
end
puts count
a and b are the starting numbers given as input. The solution is trivial, we just iterate 40 million times and count how many times values matched (16 lowest bits). Maybe not optimal solution, but runs in 2-3 seconds so I think it is fine.
In the second part the rules are a bit different. Generators still generate numbers in the same way, but generator A only hands down numbers divisible by 4 and generator B numbers divisible by 8. This means that when one generator has valid number another one may not have anything to compare to.
We need to store results from both generators and only compare numbers when we have results from both. Here is the solution:
a = 65
b = 8921
count = 0
a_values = []
b_values = []
iterations = 0
while true
a = (a * 16807) % 2147483647
b = (b * 48271) % 2147483647
a_values.push(a) if a % 4 == 0
b_values.push(b) if b % 8 == 0
while a_values.size > 0 && b_values.size > 0
a_val = a_values.shift
b_val = b_values.shift
iterations += 1
if a_val & 0xffff == b_val & 0xffff
count += 1
end
if iterations >= 5_000_000
break
end
end
if iterations >= 5_000_000
break
end
end
puts count
We are storing results in two different arrays and only when both have values we compare them. This is again maybe not optimal solution, but 4 seconds seems fine to me. I think there are some arithmetic tricks you can do to get faster answers, but didn’t have time to figure it out. Yet.