Day 15

Here we have a pair of sequences that are being generated by two machines. The machines have different initial values. They then each multiply their values by specific factors, take a remainder from a common divisor, and then check the last 16 bits.

In [1]:
fct_a = 16807
start_a = 634
fct_b = 48271
start_b = 301
divisor = 2147483647
divisor2 = 2 ** 16
In [2]:
def fmt_bits(x):
    x = bin(x)[2:]
    x = '0'*(16-len(x)) + x
    return(x)
    
fmt_bits(2 ** 16 -1 )
Out[2]:
'1111111111111111'

So... I'm guessing we're not supposed to actually run the 40 million checks... but we could try

In [3]:
matches = 0
a = start_a
b = start_b
for i in range(4 * (10 ** 7)):
    a *= fct_a
    b *= fct_b
    a = a % divisor 
    b = b % divisor
    bin_a = bin(a)[2:]
    if (a% divisor2)== (b % divisor2):
        matches += 1
matches
Out[3]:
573

Well.. okay. I suspect that there is some repeating cycle where the same pattern will show up over and over.

Part 2

Now we've changed the logic a bit and we will keep a sequence going for each generator of multiples of 4 for a and multiples of 8 for b. We'll then compare those sequences one by one.

In [4]:
matches = 0
a = start_a
b = start_b
list_a = []
list_b = []
hits = [0, 0]
while min(hits) < 5*10**6:
    a *= fct_a
    b *= fct_b
    a = a % divisor 
    b = b % divisor
    if a % 4 == 0 :
        list_a.append(a)
        hits[0] = hits[0] + 1
    if b % 8 == 0 :
        list_b.append(b)
        hits[1] = hits[1] + 1

for a, b in zip(list_a, list_b):
    if (a% divisor2)== (b % divisor2):
        matches += 1
matches
Out[4]:
294

mmmm yea so I feel like this one was supposed to be solved in a fancier way but... not sure that I see it.