blob: be9008e03b0eb6fb2fa86573826d2af920aa6463 (
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
(ql:quickload '(fiveam str))
(defparameter eg-input "seeds: 79 14 55 13
seed-to-soil map:
50 98 2
52 50 48
soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15
fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4
water-to-light map:
88 18 7
18 25 70
light-to-temperature map:
45 77 23
81 45 19
68 64 13
temperature-to-humidity map:
0 69 1
1 0 69
humidity-to-location map:
60 56 37
56 93 4")
(defun translate (rules value)
(dolist (rule rules)
(destructuring-bind (dest source span) rule
(when (<= source value (+ source (1- span)))
(return-from translate (+ (- value source) dest)))))
value)
(defun segment-translate (rules segments)
(let ((sorted-rules (sort rules #'< :key #'cadr)))
(mapcan
(lambda (segment)
(destructuring-bind (start . end) segment
(loop for (dest-start source-start span) in sorted-rules
)))
segments)))
(sort '((50 98 2) (52 50 48)) #'< :key #'cadr)
(fiveam:test parts
(let ((rules '((50 98 2) (52 50 48))))
(fiveam:is (= 9 (translate rules 9)))
(fiveam:is (= 61 (translate rules 59)))
(fiveam:is (= 51 (translate rules 99)))))
(defun translator (translate-chain translator-rules)
(lambda (value)
(reduce
(lambda (acc fn)
(translate (gethash fn translator-rules) acc))
translate-chain
:initial-value value)))
(defun parser (lines)
(let (seeds
maps-stack
(translators (make-hash-table)))
(dolist (line lines)
(cond
((str:emptyp line))
((str:starts-with? "seeds:" line)
(setf seeds
(mapcar #'parse-integer (cdr (str:split-omit-nulls #\Space line)))))
((str:ends-with-p "map:" line)
(push (read-from-string line) maps-stack))
((push (mapcar #'parse-integer (str:split-omit-nulls #\Space line))
(gethash (car maps-stack) translators)))))
(values (translator
(nreverse maps-stack)
translators)
seeds)))
(defun solver1 (lines)
(multiple-value-bind (translator seeds) (parser lines)
(apply #'min (mapcar translator seeds))))
(defun solver2 (lines)
(multiple-value-bind (translator seeds) (parser lines)
(loop for (start span) on seeds by #'cddr
minimize (loop for i from start below (+ start span)
minimize (funcall translator i)))))
(fiveam:test solutions
(fiveam:is
(= 35
(solver1
(uiop:split-string eg-input :separator '(#\Newline)))))
(fiveam:is
(= 46
(solver2
(uiop:split-string eg-input :separator '(#\Newline)))))
(fiveam:is
(= 662197086
(solver1
(uiop:read-file-lines "input"))))
(fiveam:is
(= 52510809
(solver2
(uiop:read-file-lines "input")))))
|
