blob: 28103ecaa2e1e89d9b8053f7e053bac1ee3b6234 (
plain)
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
68
69
70
|
(define-module (day22)
#:use-module (ice-9 rdelim)
#:use-module (srfi srfi-1)
#:use-module (srfi srfi-89)
#:use-module (srfi srfi-145)
#:use-module (srfi srfi-158))
(define (evolve n)
(assume (integer? n) "n must be an integer." n)
(define n1 (logand #xffffff (logxor n (ash n 6))))
(define n2 (logxor n1 (ash n1 -5)))
(logand #xffffff (logxor n2 (ash n2 11))))
(define (call^ n f x)
(assume (and (integer? n) (not (negative? n)))
"n must be a nonnegative integer." n)
(if (zero? n)
x
(call^ (- n 1) f (f x))))
(define (answer n)
(call^ 2000 evolve n))
(define* (part1 (port (current-input-port)))
(let iter ((sum 0))
(define line (read-line port))
(if (or (eof-object? line) (string=? "" line))
sum
(iter (+ sum (answer (or (string->number line)
(error "Not a number." line))))))))
(define +dp-dimensions+ '((-9 9) (-9 9) (-9 9) (-9 9)))
(define (dp-table? obj)
(and (array? obj) (equal? (array-dimensions obj) +dp-dimensions+)))
(define (make-dp-table)
(apply make-typed-array 'u16 0 +dp-dimensions+))
(define (generate-prices secret)
(gtake (make-unfold-generator (lambda (n) #f)
(lambda (n) (modulo n 10))
evolve
secret)
2001))
(define (dp-add-sequence! dp secret)
(define visited (apply make-typed-array 'b #f +dp-dimensions+))
(define gen (generate-prices secret))
(define (iter prev d3 d2 d1)
(define next (gen))
(unless (eof-object? next)
(let ((d0 (- next prev)))
(when (and d3 (not (array-ref visited d3 d2 d1 d0)))
(array-set! dp (+ next (array-ref dp d3 d2 d1 d0)) d3 d2 d1 d0)
(array-set! visited #t d3 d2 d1 d0))
(iter next d2 d1 d0))))
(iter (gen) #f #f #f))
(define (dp-max dp)
(apply max (concatenate (concatenate (concatenate (array->list dp))))))
(define* (part2 (port (current-input-port)))
(define dp (make-dp-table))
(let iter ()
(define line (read-line port))
(if (or (eof-object? line) (string=? "" line))
(dp-max dp)
(begin (dp-add-sequence! dp (string->number line))
(iter)))))
|
