You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
72 lines
3.3 KiB
72 lines
3.3 KiB
#lang scribble/lp2


@(require scribble/manual aocracket/helper)




@aoctitle[20]




@defmodule[aocracket/day20]




@link["http://adventofcode.com/day/20"]{The puzzle}. Our @linkrp["day20input.txt"]{input} is a target number of presents, in this case @racket[36000000].






@chunk[<day20>


<day20setup>


<day20q1>


<day20q2>


<day20test>]




@isection{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 @link["http://practicaltypography.com/theinfinitepixelscreen.html"]{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 @italic{n}th elf, 10@italic{n} gifts to every @italic{n}th house.




Math jocks will notice that the elf behavior roughly describes a @link["https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes"]{Sieve of Eratosthenes}. Each house is visited by elf @italic{n} only if @italic{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 @iracket[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 10gift multiplier is arbitrary.)




@chunk[<day20setup>


(require racket rackunit (onlyin math divisors))


(provide (alldefinedout))


]




@chunk[<day20q1>




(define (q1 inputstr)


(define targetgifts (read (openinputstring inputstr)))


(define giftsperelf 10)


(for/first ([housenumber (innaturals)]


#:when (let* ([elves (divisors housenumber)]


[elfgifts


(apply + (map (curry * giftsperelf) elves))])


(>= elfgifts targetgifts)))


housenumber))]








@isection{What's the first house that gets the target number of presents, if each elf delivers 11 gifts to 50 houses?}




Going with the mathjock vibe, what this condition means is that the highestnumbered house the @italic{n}th elf will visit is 50@italic{n}. So the answer for this question is like the first, but we'll @iracket[filter] the list of elves using this condition.




@chunk[<day20q2>




(define (q2 inputstr)


(define targetgifts (read (openinputstring inputstr)))


(define giftsperelf 11)


(for/first ([housenumber (innaturals)]


#:when (let* ([elves (divisors housenumber)]


[elves (filter


(λ (e) (<= housenumber (* 50 e))) elves)]


[elfgifts


(apply + (map (curry * giftsperelf) elves))])


(>= elfgifts targetgifts)))


housenumber))




]








@section{Testing Day 20}




@chunk[<day20test>


(module+ test


(define inputstr (file>string "day20input.txt"))


(checkequal? (q1 inputstr) 831600)


(checkequal? (q2 inputstr) 884520))]






