Overview
Context
Changes
Added day08.rkt version [dacd83].
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
|
#lang racket
(require rackunit)
(define input (file->list "day08-input.txt"))
;; Returns (values metadata lst-remainder)
(define (sum-of-metadata lst [metas '()])
(match-define (list children metacount) (take lst 2))
(define remainder (drop lst 2))
(cond
[(= 0 children) (values (append metas (take remainder metacount)) (drop remainder metacount))]
[else
(define-values (new-metas new-rest)
(for/fold ([metas-accum metas]
[rest-lst remainder])
([c (in-range children)])
(sum-of-metadata rest-lst metas-accum)))
(values (append new-metas (take new-rest metacount)) (drop new-rest metacount))]))
(define (day08-part1 lst)
(define-values (metas _) (sum-of-metadata lst))
(apply + metas))
(module+ test
(define example '(2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2))
(check-equal? (day08-part1 example) 138) ; Matches example result on AoC website
(check-equal? (time (day08-part1 input)) 40908) ; Correct answer for part 1
; Example input from reddit that helped me finish
; Illustrates problem of zero-element children
(define reddit-example '(2 2 1 1 0 0 10 0 2 20 30 40 50))
(check-equal? (day08-part1 reddit-example) 150))
;; Per Part 2, when a node has children its metadata are read as references to the values of those
;; children nodes, and its value is the some of the values of the children referred to.
;; This function applies the problem-specified rules for reading and scoring metadata with child nodes:
(define (ref-and-sum child-vals refs)
(define (ref n)
(cond [(zero? n) 0] ; “A metadata entry of 0 refers to nothing”
[(> n (length child-vals)) 0] ; “If a referenced child node does not exist, skip it.”
[else (list-ref child-vals (sub1 n))]))
(apply + (map ref refs))) ; “A child node can be referenced multiple times”
;; Returns (values node-value remaining-lst)
(define (node-value lst)
(match-define (list children metacount) (take lst 2))
(define remainder (drop lst 2))
(cond
[(= children 0) (values (apply + (take remainder metacount)) (drop remainder metacount))]
[else
(define-values (child-values new-rest)
(for/fold ([vals-accum '()]
[rest-lst remainder])
([c (in-range children)])
(let-values ([(child-val next-rest) (node-value rest-lst)])
(values (append vals-accum (list child-val)) next-rest))))
(values (ref-and-sum child-values (take new-rest metacount)) (drop new-rest metacount))]))
(define (day08-part2)
(let-values ([(answer _) (node-value input)])
answer))
(module+ test
(check-equal? (time (day08-part2)) 25910)) ; Correct answer for part 2
|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |