On this page:
<day20>
20.1 What’s the first house that gets the target number of presents?
<day20-setup>
<day20-q1>
20.2 What’s the first house that gets the target number of presents, if each elf delivers 11 gifts to 50 houses?
<day20-q2>
20.3 Testing Day 20
<day20-test>
7.1

20 Day 20

 (require aoc-racket/day20) package: aoc-racket

The puzzle. Our input is a target number of presents, in this case 36000000.

20.1 What’s the first house that gets the target number of presents?

We’re asked to imagine infinite elves delivering presents to an infinite sequence of houses. (Already I like this puzzle.) The first elf delivers a present to every house equal to 10 times his number (= 10); the second elf, 20 gifts to every second house; the nth elf, 10n gifts to every nth house.

Math jocks will notice that the elf behavior roughly describes a Sieve of Eratosthenes. Each house is visited by elf n only if n is a divisor of the house number. (Houses that are primes are therefore only visited by the first elf.) Might there be a Racket function that finds the divisors of a number? Why, yes — it’s called divisors. We can use it to find the numbers of the elves that visit a house, and loop through house numbers till we reach the target. (The 10-gift multiplier is arbitrary.)

(require racket rackunit (only-in math divisors))
(provide (all-defined-out))

(define (q1 input-str)
  (define target-gifts (read (open-input-string input-str)))
  (define gifts-per-elf 10)
  (for/first ([house-number (in-naturals)]
              #:when (let* ([elves (divisors house-number)]
                            [elf-gifts
                             (apply + (map (curry * gifts-per-elf) elves))])
                       (>= elf-gifts target-gifts)))
             house-number))

20.2 What’s the first house that gets the target number of presents, if each elf delivers 11 gifts to 50 houses?

Going with the math-jock vibe, what this condition means is that the highest-numbered house the nth elf will visit is 50n. So the answer for this question is like the first, but we’ll filter the list of elves using this condition.

(define (q2 input-str)
  (define target-gifts (read (open-input-string input-str)))
  (define gifts-per-elf 11)
  (for/first ([house-number (in-naturals)]
              #:when (let* ([elves (divisors house-number)]
                            [elves (filter
                                    (λ(e) (<= house-number (* 50 e))) elves)]
                            [elf-gifts
                             (apply + (map (curry * gifts-per-elf) elves))])
                       (>= elf-gifts target-gifts)))
             house-number))

20.3 Testing Day 20

(module+ test
  (define input-str (file->string "day20-input.txt"))
  (check-equal? (q1 input-str) 831600)
  (check-equal? (q2 input-str) 884520))