Solution for Advent of Code 2015 - Day 20: Infinite Elves and Infinite Houses

Link to the puzzle text

Part 1

In this puzzle elves are delivering presents to houses. Each elf is numbered and only visits houses which are a multiple of its number. We are asked to find the first house getting a certain number of presents.

The less memory-intensive algorithm would be to invert the problem. For each house, we are summing up the presents delivered to it by the elves. This is simply the sum of the divisors * 10. Alternatively we can simply iterate over the elves and distribute the presents for each elf. The second algorithm has a better runtime behaviour and since the input is relatively small memory was not an issue. 

num_presents = numpy.zeros((input // 10,))
for elfnum in range(1, input // 10):
    num_presents[elfnum:(input // 10):elfnum] += elfnum * 10

We are initialiazing an array for the number of presents received by each house. For each elf, we add its presents to each house. The addition to the presents array is done via a list slice, where the rarely-used third parameter controls the stride. After the loop, we search for the lowest house number with more than our input number of presents.

Part 2

The second part changes two things. First each elf only distributes to 50 houses at maximum. Secondly each elf delivers 11 instead of 10 times its number. Our function from part 1 needs to be changed only slightly to accomodate this:

num_presents = numpy.zeros((input // 11,))
for elfnum in range(1, input // 11):
    num_presents[elfnum:50 * elfnum:elfnum] += elfnum * 11

Link to my solutions