▼Advent of Code:   solutions & explanations
►20 Day 20
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>
6.3.90.900
  top  ← prev  up  next → 

20 Day 20

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

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

<day20> ::=
<day20-setup>
<day20-q1>
<day20-q2>
<day20-test>

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.)

<day20-setup> ::=
(require racket rackunit (only-in math divisors))
(provide (all-defined-out))

<day20-q1> ::=
(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.

<day20-q2> ::=
(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

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

  top  ← prev  up  next →