Solution for Advent of Code 2017 - Day 15: Dueling Generators

Link to the puzzle text

Part 1

In this puzzle, we have two generators of random numbers. We should let them generate several million numbers each, check the lower 16 bits if they match and count the number of matches. Both generators use the same method of generating, multiplying with a factor and calculating a mod.

While a cleaner solution would be two generators using yield, we simply implemented the sequence. For getting the lower 16 bits, we can logical and (& sign)  the number of 16 ones.

def count_matches(a, b, limit):
    matches = 0
    for i in range(limit + 1):
        a = (a * a_factor) % mod
        b = (b * b_factor) % mod
        lower_a = a & (2 ** 16 - 1)
        lower_b = b & (2 ** 16 - 1)
        if lower_a == lower_b:
            matches += 1
    return matches 

Part 2

In part 2, we should still count the number of matches, but the generators now function slightly different. Both now only output if the number is a multiple of either 4 or 8 respectively.

We reused the count_matches function and added a flag for the mode. We can then just loop until our number is a multiple and keep the rest the same.

...
a = (a * a_factor) % mod
while (a % 4) != 0:
    a = (a * a_factor) % mod
...

Link to my solutions