Advent of Code: Day 20

Source

Part 1: P(n) is defined such that for each number i, add 10i to any number divisible by i. Find the first value n such that P(n) is at least a given target number.

Let’s throw some memory (and numpy) at it:

target = int(sys.argv[1])

presents = numpy.zeros(target)

for i in range(1, target):
    presents[i::i] += 10 * i

for i in range(len(presents)):
    if presents[i] >= target:
        print(i)
        sys.exit(0)

It barely makes it in under a minute, but it does. You can speed it up even more if you guess on where the answer will be an initialize to only the first numpy.zeros(target / 10). In only shaves off about 1/6 of the time on my run though, so I’m not sure it’s worth it.

Part 2: Do the same thing, only use 11i instead of 10i but only to the first 50 multiples.

Nothing much changes:

target = int(sys.argv[1])

presents = numpy.zeros(target / 10)

for i in range(1, target):
    presents[i:i*50:i] += 11 * i

for i in range(len(presents)):
    if presents[i] >= target:
        print(i)
        sys.exit(0)