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

Part 1

Description

Solution

Elf k delivers 10 × k presents to houses k, 2k, 3k and so on. So house n is visited by every elf whose number divides n, and the presents it gets are 10 × (the sum of the divisors of n).

First I checked this on a small table in Sheet1. Rows 1 to 25 are the elves (A1:A25), and each row lists the houses that elf visits:

B1: =$A1*COLUMN()

This is elf × 2, elf × 3 and so on up to × 25, and column A itself is elf × 1. For each house n (column A again), AA:AY looks for n in each column and returns the row where it appears. That row is the elf who visits n:

AA1: =IFERROR(MATCH($A1,A$1:A$25,0),0)
AZ1: =SUM(AA1:AY1)

AZ is the sum of the elves who reach the house, which is the sum of its divisors. For example, AZ24 = 60 (1+2+3+4+6+8+12+24), and 10 × AZ gives the presents. The first nine houses give 10, 30, 40, 70, 60, 120, 80, 150 and 130, which matches the example in the puzzle.

A table like that can’t cover hundreds of thousands of houses. So for the real input I made a formula that works out one house at a time. Type the house number in A5: 

B5: =LET(Num, A5,
         All, SEQUENCE(Num),
         Factors, FILTER(All, MOD(Num, All)=0),
         10*SUM(Factors))

All is 1 to the house number, Factors keeps the ones that divide it evenly, and the answer is 10 times their sum. 

To find the first house that reaches my input, I used a macro. Elf n always reaches house n and delivers 10 × n, so the answer can’t be higher than input ÷ 10. The macro adds up every elf’s presents for every house up to that limit:

Public Sub Day20Part1()
    Dim target As Long, limit As Long, elf As Long, house As Long
    Dim presents() As Long
    target = 29000000                 ' replace with your puzzle input
    limit = target \ 10 + 1
    ReDim presents(1 To limit)
    For elf = 1 To limit
        For house = elf To limit Step elf
            presents(house) = presents(house) + elf * 10
        Next house
    Next elf
    For house = 1 To limit
        If presents(house) >= target Then
            Debug.Print house, presents(house)
            Exit Sub
        End If
    Next house
End Sub

Then I typed the house it printed into A5, and B5 confirmed it gets at least my input in presents.

Part 2

Description

Solution

Now each elf only visits 50 houses and delivers 11 presents per house. So elf k reaches house n only if n ≤ 50 × k, which means k ≥ n / 50. I added that filter to the formula:

B7: =LET(Num, A7,
         All, SEQUENCE(Num),
         Factors, FILTER(All, MOD(Num, All)=0),
         Cap, FILTER(Factors, Factors>=(A7/50)),
         11*SUM(Cap))

For the search I turned the loops around. For each house, I try the multipliers 1 to 50. If j divides the house, then elf house ÷ j reaches it as its j-th house, and delivers 11 × that elf number:

Public Sub Day20Part2()
    Dim target As Long, cap As Long, house As Long, j As Long, total As Long
    target = 29000000                 ' replace with your puzzle input
    cap = 50
    For house = 1 To target
        total = 0
        For j = 1 To cap
            If house Mod j = 0 Then total = total + 11 * (house \ j)
        Next j
        If total >= target Then
            Debug.Print house, total
            Exit Sub
        End If
    Next house
End Sub

This only does 50 checks per house, so it finishes quickly. I typed the house it printed into A7 to confirm with B7.