Advent of Code Day 20–Counting Presents

Day 20’s puzzle at Advent of Code was in one sense very simple, but if you weren’t careful, you’d create a solution that took ages. In today’s video, I explain how I initially came up with a very slow solution, and then showed some ways that dramatically speeded it up.

Here’s my first C# version, that uses a naive algorithm to calculate the presents for each house. Even trying to optimize by excluding houses without multiple prime factors from the search space didn’t really make up for how slow the present counting was.

Func<int,int> presentsForHouse = house => Enumerable.Range(1,house)
                                    .Where(elf => house % elf == 0)
                                    .Sum() * 10;
Func<int, int> presentsForHouseB = house => Enumerable.Range(1, house)
                                     .Where(elf => house % elf == 0 && house / elf <= 50)
                                     .Sum() * 11;

var fact = (2*3*5*7*11);
Enumerable.Range(1, 10000000)
    .Where(n => n % fact == 0)
    .Select(h => new { House = h, Presents = presentsForHouse(h) })
    .First(h => h.Presents >= 36000000).Dump("a");

var factB = (2 * 2 * 2 * 3 * 3);
Enumerable.Range(700000, 10000000)
    .Where(n => n % factB == 0)
    .Select(h => new { House = h, Presents = presentsForHouseB(h) })
    .First(h => h.Presents >= 36000000).Dump("b");

So in my F# version, I used a more intelligent approach, getting all the factors of the house number in order to work out which elf visited. The factors function is based on one by Jeff on the Advent of Code subreddit. I left in my optimization of only testing likely houses from C#. Overall this factors optimization sped up the calculation of part b’s answer from 18 minutes down to under a second!

let factors number = seq {
    for divisor in 1.. (float >> sqrt >> int) number do
        let a,b = number%divisor, number/divisor
        if a = 0 then
            yield divisor
            if not (divisor = b) then
                yield b }
                
let presentsForHouseA house = 
    factors house
    |> Seq.sum 
    |> ((*) 10)

let presentsForHouseB house = 
    factors house
    |> Seq.filter (fun factor -> house/factor <= 50)
    |> Seq.sum 
    |> ((*) 11)

let search target func testSeq =
    testSeq
    |> Seq.map (fun house -> (house, (func house)))
    |> Seq.find (fun (h,p) -> p > target) |> fst

let target = 36000000

let testNums rstart factor = 
    seq { for n in rstart..target do if n % factor = 0 then yield n }

testNums 700000 (2*3*5*7*11)
|> search target presentsForHouseA 
|> printfn "a: %d" //831600

testNums 700000 (2*2*2*3*3)
|> search target presentsForHouseB 
|> printfn "b: %d" // 884520

But what’s interesting is that there is a much simpler way to solve this problem which also happens to perform very fast. Annoyingly it’s the first solution I turned to, but then abandoned quickly. Basically, have an array of presents for each house, and then for each elf, update the total for all the houses they visit. This works almost as fast as the optimized F# solution, and could be optimised further if necessary by stopping as soon as any house has more than the target number of presents, and reducing the number of houses calculated as it is overkill to try so many. But here’s this solution in C#, and well done to r_sreeram who used it to get first place on the leaderboard.

var target = 36000000;
var houses = new int[target/10 + 1];
for (int elf = 1; elf < houses.Length; elf++)
    for (int house = elf; house < houses.Length; house+=elf)
        houses[house] += elf * 10;
for (int house = 1; house < houses.Length; house++)
    if (houses[house] > target) { house.Dump("a"); break; }

houses = new int[target/11 + 1];
for (int elf = 1; elf < houses.Length; elf++)
    for (int house = elf, n = 0; house < houses.Length && n < 50; house+=elf, n++)
        houses[house] += elf * 11;
for (int house = 1; house < houses.Length; house++)
    if (houses[house] > target) { house.Dump("b"); break; }