Task 20

Thorn Thaler - <

2025-07-25

1 Setup

1.1 Libraries

library(httr)
library(xml2)
library(magrittr)
library(dplyr)
library(purrr)
library(stringr)

1.2 Retrieve Data from AoC

session_cookie <- set_cookies(session = keyring::key_get("AoC-GitHub-Cookie"))
base_url <- paste0("https://adventofcode.com/", params$year, "/day/", params$task_nr)
puzzle <- GET(base_url,
              session_cookie) %>% 
  content(encoding = "UTF-8") %>% 
  xml_find_all("///article") %>% 
  lapply(as.character)

parse_puzzle_data <- function(text_block = readClipboard()) {
  29000000L
}

puzzle_data <- local({
  GET(paste0(base_url, "/input"),
      session_cookie) %>% 
    content(encoding = "UTF-8") %>% 
    parse_puzzle_data()
})

2 Puzzle Day 20

2.1 Part 1

2.1.1 Description

— Day 20: Infinite Elves and Infinite Houses —

To keep the Elves busy, Santa has them deliver some presents by hand, door-to-door. He sends them down a street with infinite houses numbered sequentially: 1, 2, 3, 4, 5, and so on.

Each Elf is assigned a number, too, and delivers presents to houses based on that number:

  • The first Elf (number 1) delivers presents to every house: 1, 2, 3, 4, 5, ….
  • The second Elf (number 2) delivers presents to every second house: 2, 4, 6, 8, 10, ….
  • Elf number 3 delivers presents to every third house: 3, 6, 9, 12, 15, ….

There are infinitely many Elves, numbered starting with 1. Each Elf delivers presents equal to ten times his or her number at each house.

So, the first nine houses on the street end up like this: 

House 1 got 10 presents.
House 2 got 30 presents.
House 3 got 40 presents.
House 4 got 70 presents.
House 5 got 60 presents.
House 6 got 120 presents.
House 7 got 80 presents.
House 8 got 150 presents.
House 9 got 130 presents.

The first house gets 10 presents: it is visited only by Elf 1, which delivers 1 * 10 = 10 presents. The fourth house gets 70 presents, because it is visited by Elves 1, 2, and 4, for a total of 10 + 20 + 40 = 70 presents.

What is the lowest house number of the house to get at least as many presents as the number in your puzzle input?

2.1.2 Solution

The number of presents is 10 times the sum of all divisors. That is, we need to get all divisors of the number multiplied by 10, sum them up and check if it is greater or equal the number. However since the sequence is not monotonously decreasing, a simple binary search won’t do and we have to iterate. Since iterations is not one of R’s strength, we fall back to C++. To get the number of divisors. we look up all numbers between 1 and the square root of n and add the reciprocal number (unless it is the exact square root).

#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#else
#include <iostream>
#endif

int get_sum_of_divisors(unsigned int num, unsigned int limit = -1) {
  int sum = 0;
  for (unsigned int i = 1U; i * i <= num; ++i) {
    if (num % i == 0) {
      unsigned int j = num / i;
      if (j <= limit) {
        sum += i;
      }
      if (i != j && i <= limit) {
        // add reciprocal value unless n = i ^ 2
        sum += j;
      }
    }
  }
  return sum;
}

// [[Rcpp::export]]
unsigned int find_house_number(unsigned int num,
                               unsigned int reward = 10,
                               unsigned int limit = -1) {
  int i = 1;
  while (reward * get_sum_of_divisors(i, limit) < num) {
    i++;
  }
  return i;
}

#ifdef STANDALONE
int main() {
  std::cout << "House Number: " << find_house_number(130, 10, -1) << std::endl;
}
#endif
find_house_number(puzzle_data)
## [1] 665280

2.2 Part 2

2.2.1 Description

— Part Two —

The Elves decide they don’t want to visit an infinite number of houses. Instead, each Elf will stop after delivering presents to 50 houses. To make up for it, they decide to deliver presents equal to eleven times their number at each house.

With these changes, what is the new lowest house number of the house to get at least as many presents as the number in your puzzle input?

2.2.2 Solution

We simply need to provide a different rewrad and set a limit on the divisors to get the result.

find_house_number(puzzle_data, 11L, 50L)
## [1] 705600