--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/data/2016/10.txt Sat Dec 14 20:00:14 2019 -0500
@@ -0,0 +1,231 @@
+value 61 goes to bot 209
+bot 200 gives low to bot 40 and high to bot 141
+bot 197 gives low to bot 202 and high to bot 65
+bot 19 gives low to bot 170 and high to bot 120
+bot 25 gives low to bot 8 and high to bot 193
+bot 151 gives low to bot 100 and high to bot 188
+bot 187 gives low to bot 89 and high to bot 142
+bot 40 gives low to bot 85 and high to bot 172
+bot 55 gives low to bot 94 and high to bot 2
+bot 149 gives low to bot 57 and high to bot 75
+value 37 goes to bot 97
+bot 140 gives low to bot 29 and high to bot 71
+bot 77 gives low to bot 7 and high to bot 86
+bot 189 gives low to bot 62 and high to bot 168
+value 67 goes to bot 4
+bot 194 gives low to output 9 and high to bot 74
+bot 46 gives low to bot 96 and high to bot 187
+bot 93 gives low to bot 82 and high to bot 108
+bot 18 gives low to output 5 and high to bot 78
+bot 37 gives low to bot 1 and high to bot 101
+bot 28 gives low to bot 65 and high to bot 87
+bot 146 gives low to bot 117 and high to bot 6
+bot 6 gives low to bot 22 and high to bot 134
+bot 207 gives low to bot 20 and high to bot 135
+bot 29 gives low to bot 126 and high to bot 157
+bot 126 gives low to bot 146 and high to bot 131
+bot 23 gives low to bot 138 and high to bot 173
+bot 92 gives low to bot 60 and high to bot 171
+bot 177 gives low to bot 203 and high to bot 28
+value 47 goes to bot 167
+bot 190 gives low to bot 68 and high to bot 133
+bot 56 gives low to bot 191 and high to bot 146
+bot 75 gives low to bot 5 and high to bot 92
+value 11 goes to bot 136
+bot 4 gives low to bot 136 and high to bot 55
+bot 143 gives low to bot 109 and high to bot 125
+bot 14 gives low to bot 90 and high to bot 184
+bot 100 gives low to bot 156 and high to bot 188
+bot 65 gives low to bot 49 and high to bot 87
+bot 180 gives low to bot 95 and high to bot 56
+bot 155 gives low to bot 196 and high to bot 41
+bot 154 gives low to bot 153 and high to bot 25
+value 17 goes to bot 48
+bot 10 gives low to bot 124 and high to bot 177
+bot 188 gives low to bot 137 and high to bot 106
+bot 138 gives low to bot 182 and high to bot 93
+bot 119 gives low to bot 118 and high to bot 206
+bot 208 gives low to bot 70 and high to bot 45
+bot 114 gives low to bot 204 and high to bot 19
+bot 141 gives low to bot 172 and high to bot 1
+value 53 goes to bot 153
+bot 71 gives low to bot 157 and high to bot 163
+bot 48 gives low to bot 200 and high to bot 123
+bot 96 gives low to bot 86 and high to bot 187
+bot 169 gives low to output 19 and high to output 11
+value 41 goes to bot 99
+bot 134 gives low to bot 13 and high to bot 112
+bot 113 gives low to bot 128 and high to bot 11
+bot 95 gives low to bot 186 and high to bot 191
+bot 105 gives low to bot 125 and high to bot 90
+bot 204 gives low to bot 122 and high to bot 19
+bot 193 gives low to bot 38 and high to bot 116
+bot 67 gives low to output 6 and high to bot 18
+value 71 goes to bot 52
+bot 159 gives low to output 8 and high to bot 175
+bot 121 gives low to bot 42 and high to bot 109
+bot 43 gives low to output 12 and high to bot 194
+bot 76 gives low to bot 147 and high to bot 190
+bot 79 gives low to bot 108 and high to bot 147
+bot 163 gives low to bot 91 and high to bot 24
+bot 44 gives low to bot 75 and high to bot 182
+bot 205 gives low to bot 159 and high to bot 0
+value 23 goes to bot 70
+bot 103 gives low to bot 69 and high to bot 127
+bot 106 gives low to bot 199 and high to bot 64
+bot 202 gives low to bot 11 and high to bot 49
+bot 84 gives low to bot 25 and high to bot 185
+bot 116 gives low to bot 179 and high to bot 176
+bot 160 gives low to bot 18 and high to bot 50
+value 2 goes to bot 130
+bot 128 gives low to bot 24 and high to bot 51
+value 5 goes to bot 200
+bot 78 gives low to output 18 and high to bot 169
+bot 109 gives low to bot 81 and high to bot 12
+bot 83 gives low to bot 71 and high to bot 162
+bot 101 gives low to bot 119 and high to bot 32
+bot 53 gives low to bot 31 and high to bot 181
+bot 133 gives low to bot 139 and high to bot 114
+bot 122 gives low to bot 41 and high to bot 170
+bot 33 gives low to bot 161 and high to bot 151
+bot 206 gives low to bot 53 and high to bot 178
+bot 153 gives low to bot 167 and high to bot 8
+bot 195 gives low to bot 0 and high to bot 69
+bot 172 gives low to bot 84 and high to bot 66
+bot 142 gives low to bot 190 and high to bot 133
+bot 107 gives low to bot 162 and high to bot 113
+bot 3 gives low to bot 63 and high to bot 189
+bot 167 gives low to bot 4 and high to bot 16
+value 13 goes to bot 150
+bot 131 gives low to bot 6 and high to bot 36
+bot 145 gives low to bot 72 and high to bot 166
+bot 170 gives low to bot 98 and high to bot 120
+bot 13 gives low to bot 74 and high to bot 149
+bot 186 gives low to output 1 and high to bot 104
+bot 90 gives low to bot 140 and high to bot 83
+bot 30 gives low to output 14 and high to bot 67
+bot 66 gives low to bot 185 and high to bot 118
+bot 165 gives low to output 0 and high to bot 159
+bot 88 gives low to bot 56 and high to bot 126
+bot 21 gives low to bot 79 and high to bot 76
+bot 127 gives low to bot 15 and high to bot 204
+bot 49 gives low to bot 145 and high to bot 58
+bot 86 gives low to bot 21 and high to bot 89
+bot 164 gives low to bot 26 and high to bot 180
+bot 203 gives low to bot 197 and high to bot 28
+value 43 goes to bot 40
+bot 35 gives low to bot 148 and high to bot 111
+bot 47 gives low to bot 207 and high to bot 161
+bot 50 gives low to bot 78 and high to bot 169
+bot 185 gives low to bot 193 and high to bot 102
+bot 32 gives low to bot 206 and high to bot 199
+bot 175 gives low to output 3 and high to bot 158
+bot 157 gives low to bot 131 and high to bot 91
+bot 98 gives low to bot 67 and high to bot 160
+bot 52 gives low to bot 150 and high to bot 207
+bot 22 gives low to bot 194 and high to bot 13
+bot 198 gives low to bot 44 and high to bot 138
+bot 64 gives low to bot 35 and high to bot 111
+bot 129 gives low to bot 183 and high to bot 132
+bot 120 gives low to bot 160 and high to bot 50
+bot 87 gives low to bot 58 and high to bot 46
+value 31 goes to bot 85
+value 59 goes to bot 39
+bot 2 gives low to bot 143 and high to bot 105
+bot 8 gives low to bot 16 and high to bot 38
+bot 60 gives low to output 10 and high to bot 165
+bot 15 gives low to bot 155 and high to bot 122
+bot 70 gives low to bot 174 and high to bot 45
+bot 73 gives low to bot 105 and high to bot 14
+bot 42 gives low to bot 164 and high to bot 81
+bot 20 gives low to bot 123 and high to bot 80
+bot 108 gives low to bot 144 and high to bot 61
+bot 1 gives low to bot 66 and high to bot 119
+bot 132 gives low to bot 198 and high to bot 23
+bot 17 gives low to bot 2 and high to bot 73
+bot 191 gives low to bot 104 and high to bot 117
+bot 62 gives low to bot 107 and high to bot 115
+bot 168 gives low to bot 115 and high to bot 197
+bot 161 gives low to bot 135 and high to bot 151
+bot 117 gives low to bot 43 and high to bot 22
+value 3 goes to bot 208
+bot 81 gives low to bot 180 and high to bot 88
+bot 184 gives low to bot 83 and high to bot 107
+bot 16 gives low to bot 55 and high to bot 17
+bot 152 gives low to output 20 and high to bot 186
+bot 102 gives low to bot 116 and high to bot 31
+bot 61 gives low to bot 195 and high to bot 103
+bot 38 gives low to bot 17 and high to bot 179
+bot 178 gives low to bot 181 and high to bot 35
+bot 34 gives low to bot 39 and high to bot 42
+bot 162 gives low to bot 163 and high to bot 128
+bot 63 gives low to bot 184 and high to bot 62
+bot 148 gives low to bot 59 and high to bot 10
+value 19 goes to bot 208
+bot 124 gives low to bot 168 and high to bot 203
+bot 179 gives low to bot 73 and high to bot 110
+bot 123 gives low to bot 141 and high to bot 37
+bot 45 gives low to bot 27 and high to bot 33
+bot 7 gives low to bot 173 and high to bot 21
+value 29 goes to bot 34
+bot 174 gives low to bot 99 and high to bot 27
+bot 68 gives low to bot 103 and high to bot 139
+bot 173 gives low to bot 93 and high to bot 79
+bot 54 gives low to bot 3 and high to bot 59
+bot 11 gives low to bot 51 and high to bot 145
+bot 176 gives low to bot 110 and high to bot 3
+bot 9 gives low to bot 23 and high to bot 7
+bot 182 gives low to bot 92 and high to bot 82
+bot 125 gives low to bot 12 and high to bot 140
+bot 94 gives low to bot 121 and high to bot 143
+bot 201 gives low to bot 158 and high to bot 155
+bot 31 gives low to bot 176 and high to bot 54
+bot 74 gives low to output 16 and high to bot 57
+bot 111 gives low to bot 10 and high to bot 177
+bot 196 gives low to output 15 and high to bot 30
+bot 150 gives low to bot 48 and high to bot 20
+bot 112 gives low to bot 149 and high to bot 44
+bot 118 gives low to bot 102 and high to bot 53
+bot 136 gives low to bot 209 and high to bot 94
+bot 158 gives low to output 17 and high to bot 196
+bot 39 gives low to bot 130 and high to bot 164
+bot 144 gives low to bot 205 and high to bot 195
+bot 80 gives low to bot 37 and high to bot 156
+bot 91 gives low to bot 36 and high to bot 129
+bot 135 gives low to bot 80 and high to bot 100
+bot 57 gives low to output 4 and high to bot 5
+bot 99 gives low to bot 52 and high to bot 47
+bot 58 gives low to bot 166 and high to bot 46
+bot 130 gives low to bot 97 and high to bot 26
+bot 139 gives low to bot 127 and high to bot 114
+bot 89 gives low to bot 76 and high to bot 142
+bot 156 gives low to bot 101 and high to bot 137
+bot 104 gives low to output 2 and high to bot 43
+bot 26 gives low to bot 152 and high to bot 95
+bot 137 gives low to bot 32 and high to bot 106
+bot 171 gives low to bot 165 and high to bot 205
+bot 5 gives low to output 7 and high to bot 60
+bot 36 gives low to bot 134 and high to bot 183
+bot 85 gives low to bot 154 and high to bot 84
+value 73 goes to bot 154
+bot 82 gives low to bot 171 and high to bot 144
+bot 192 gives low to bot 132 and high to bot 9
+bot 209 gives low to bot 34 and high to bot 121
+bot 110 gives low to bot 14 and high to bot 63
+bot 51 gives low to bot 192 and high to bot 72
+bot 41 gives low to bot 30 and high to bot 98
+bot 115 gives low to bot 113 and high to bot 202
+bot 0 gives low to bot 175 and high to bot 201
+value 7 goes to bot 174
+bot 24 gives low to bot 129 and high to bot 192
+bot 12 gives low to bot 88 and high to bot 29
+bot 147 gives low to bot 61 and high to bot 68
+bot 199 gives low to bot 178 and high to bot 64
+bot 59 gives low to bot 189 and high to bot 124
+bot 181 gives low to bot 54 and high to bot 148
+bot 97 gives low to output 13 and high to bot 152
+bot 166 gives low to bot 77 and high to bot 96
+bot 69 gives low to bot 201 and high to bot 15
+bot 183 gives low to bot 112 and high to bot 198
+bot 27 gives low to bot 47 and high to bot 33
+bot 72 gives low to bot 9 and high to bot 77
--- a/package.lisp Sat Dec 14 12:47:15 2019 -0500
+++ b/package.lisp Sat Dec 14 20:00:14 2019 -0500
@@ -33,6 +33,7 @@
:y
:nth-digit
:unique
+ :positions
:positions-if
:digits
:fresh-vector
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/2016/days/day-10.lisp Sat Dec 14 20:00:14 2019 -0500
@@ -0,0 +1,85 @@
+(advent:defpackage* :advent/2016/09)
+(in-package :advent/2016/09)
+
+
+(defun parse-line (line)
+ (or (ppcre:register-groups-bind
+ ((#'parse-integer value bot))
+ ("value (\\d+) goes to bot (\\d+)" line)
+ `(input ,value (:bot . ,bot)))
+ (ppcre:register-groups-bind
+ ((#'parse-integer sender)
+ (#'ensure-keyword lo-type) (#'parse-integer lo)
+ (#'ensure-keyword hi-type) (#'parse-integer hi))
+ ("bot (\\d+) gives low to (bot|output) (\\d+) and high to (bot|output) (\\d+)" line)
+ `(send ,sender (,lo-type . ,lo) (,hi-type . ,hi)))
+ (error "Bad line: ~S" line)))
+
+(defun make-buckets (instructions type)
+ (make-array (_ instructions
+ (tree-collect (lambda (node)
+ (and (consp node) (eql (car node) type)))
+ _)
+ (extremum _ #'> :key #'cdr)
+ (1+ (cdr _)))
+ :initial-element nil))
+
+(defun filter-instructions (instructions type)
+ (_ instructions
+ (remove type _ :test-not #'eql :key #'car)
+ (mapcar #'rest _)))
+
+(define-condition* bot-comparison () (actor lo hi))
+
+(defun run-bots (instructions)
+ (let ((bots (make-buckets instructions :bot))
+ (outputs (make-buckets instructions :output))
+ (input-instructions (filter-instructions instructions 'input))
+ (send-instructions (alexandria:alist-hash-table
+ (filter-instructions instructions 'send))))
+ (flet ((dest (type)
+ (ecase type
+ (:bot bots)
+ (:output outputs))))
+ (iterate
+ (for (value (nil . id)) :in input-instructions)
+ (push value (aref bots id)))
+ (iterate
+ (for ready = (positions 2 bots :key #'length))
+ (while ready)
+ (iterate
+ (for id :in ready)
+ (for ((lo-type . lo-id) (hi-type . hi-id)) = (gethash id send-instructions))
+ (for (a b) = (aref bots id))
+ (for lo = (min a b))
+ (for hi = (max a b))
+ (signal 'bot-comparison :actor id :lo lo :hi hi)
+ (push lo (aref (dest lo-type) lo-id))
+ (push hi (aref (dest hi-type) hi-id))
+ (setf (aref bots id) nil))))
+ outputs))
+
+(define-problem (2016 10) (data read-lines) (157 1085)
+ (let ((part1 nil))
+ (handler-bind ((bot-comparison
+ (lambda (c)
+ (when (and (= (lo c) 17)
+ (= (hi c) 61))
+ (setf part1 (actor c))))))
+ (let ((outputs (run-bots (mapcar #'parse-line data))))
+ (values part1
+ (* (first (aref outputs 0))
+ (first (aref outputs 1))
+ (first (aref outputs 2))))))))
+
+
+#; Scratch --------------------------------------------------------------------
+
+(run '(
+ "value 5 goes to bot 2"
+ "bot 2 gives low to bot 1 and high to bot 0"
+ "value 3 goes to bot 1"
+ "bot 1 gives low to output 1 and high to bot 0"
+ "bot 0 gives low to output 2 and high to output 0"
+ "value 2 goes to bot 2"
+ ))
--- a/src/utils.lisp Sat Dec 14 12:47:15 2019 -0500
+++ b/src/utils.lisp Sat Dec 14 20:00:14 2019 -0500
@@ -479,6 +479,30 @@
:key key
:initial-value nil))))
+(defun positions (item sequence &key (start 0) end key (test #'eql))
+ "Return a fresh list of all positions of `item` in `sequence`.
+
+ Like `cl:position`, but returns a list of all the results.
+
+ Example:
+
+ (positions 3 #(\"foo\" \"a\" \"b\" \"bar\") :key #'length)
+ ; =>
+ (0 3)
+
+ "
+ (let ((pos start))
+ (nreverse (reduce (lambda (result value)
+ (prog1 (if (funcall test item value)
+ (cons pos result)
+ result)
+ (incf pos)))
+ sequence
+ :start start
+ :end end
+ :key key
+ :initial-value nil))))
+
(defun digits (n &key (radix 10) from-end (result-type 'list))
"Return a fresh list of the digits of `n` in base `radix`.
--- a/vendor/make-quickutils.lisp Sat Dec 14 12:47:15 2019 -0500
+++ b/vendor/make-quickutils.lisp Sat Dec 14 20:00:14 2019 -0500
@@ -9,8 +9,8 @@
:curry
:deletef
:ensure-gethash
+ :equivalence-classes
:extremum
- :equivalence-classes
:flatten-once
:hash-table-keys
:hash-table-values
@@ -19,6 +19,7 @@
:read-file-into-string
:removef
:symb
+ :tree-collect
:with-gensyms
)
--- a/vendor/quickutils.lisp Sat Dec 14 12:47:15 2019 -0500
+++ b/vendor/quickutils.lisp Sat Dec 14 20:00:14 2019 -0500
@@ -2,7 +2,7 @@
;;;; See http://quickutil.org for details.
;;;; To regenerate:
-;;;; (qtlc:save-utils-as "quickutils.lisp" :utilities '(:COMPOSE :COPY-HASH-TABLE :CURRY :DELETEF :ENSURE-GETHASH :EXTREMUM :EQUIVALENCE-CLASSES :FLATTEN-ONCE :HASH-TABLE-KEYS :HASH-TABLE-VALUES :ONCE-ONLY :RCURRY :READ-FILE-INTO-STRING :REMOVEF :SYMB :WITH-GENSYMS) :ensure-package T :package "ADVENT.QUICKUTILS")
+;;;; (qtlc:save-utils-as "quickutils.lisp" :utilities '(:COMPOSE :COPY-HASH-TABLE :CURRY :DELETEF :ENSURE-GETHASH :EQUIVALENCE-CLASSES :EXTREMUM :FLATTEN-ONCE :HASH-TABLE-KEYS :HASH-TABLE-VALUES :ONCE-ONLY :RCURRY :READ-FILE-INTO-STRING :REMOVEF :SYMB :TREE-COLLECT :WITH-GENSYMS) :ensure-package T :package "ADVENT.QUICKUTILS")
(eval-when (:compile-toplevel :load-toplevel :execute)
(unless (find-package "ADVENT.QUICKUTILS")
@@ -14,11 +14,11 @@
(when (boundp '*utilities*)
(setf *utilities* (union *utilities* '(:MAKE-GENSYM-LIST :ENSURE-FUNCTION :COMPOSE
- :COPY-HASH-TABLE :CURRY :DELETEF :ENSURE-GETHASH :EXTREMUM
- :EQUIVALENCE-CLASSES :FLATTEN-ONCE :MAPHASH-KEYS
+ :COPY-HASH-TABLE :CURRY :DELETEF :ENSURE-GETHASH
+ :EQUIVALENCE-CLASSES :EXTREMUM :FLATTEN-ONCE :MAPHASH-KEYS
:HASH-TABLE-KEYS :MAPHASH-VALUES :HASH-TABLE-VALUES
:ONCE-ONLY :RCURRY :WITH-OPEN-FILE* :WITH-INPUT-FROM-FILE
- :READ-FILE-INTO-STRING :REMOVEF :MKSTR :SYMB
+ :READ-FILE-INTO-STRING :REMOVEF :MKSTR :SYMB :TREE-COLLECT
:STRING-DESIGNATOR :WITH-GENSYMS))))
(eval-when (:compile-toplevel :load-toplevel :execute)
(defun make-gensym-list (length &optional (x "G"))
@@ -136,6 +136,32 @@
(values (setf (gethash ,key ,hash-table) ,default) nil))))
+ (defun equivalence-classes (equiv seq)
+ "Partition the sequence `seq` into a list of equivalence classes
+defined by the equivalence relation `equiv`."
+ (let ((classes nil))
+ (labels ((find-equivalence-class (x)
+ (member-if (lambda (class)
+ (funcall equiv x (car class)))
+ classes))
+
+ (add-to-class (x)
+ (let ((class (find-equivalence-class x)))
+ (if class
+ (push x (car class))
+ (push (list x) classes)))))
+ (declare (dynamic-extent (function find-equivalence-class)
+ (function add-to-class))
+ (inline find-equivalence-class
+ add-to-class))
+
+ ;; Partition into equivalence classes.
+ (map nil #'add-to-class seq)
+
+ ;; Return the classes.
+ classes)))
+
+
(defun extremum (sequence predicate &key key (start 0) end)
"Returns the element of `sequence` that would appear first if the subsequence
bounded by `start` and `end` was sorted using `predicate` and `key`.
@@ -180,32 +206,6 @@
:end end)))))
- (defun equivalence-classes (equiv seq)
- "Partition the sequence `seq` into a list of equivalence classes
-defined by the equivalence relation `equiv`."
- (let ((classes nil))
- (labels ((find-equivalence-class (x)
- (member-if (lambda (class)
- (funcall equiv x (car class)))
- classes))
-
- (add-to-class (x)
- (let ((class (find-equivalence-class x)))
- (if class
- (push x (car class))
- (push (list x) classes)))))
- (declare (dynamic-extent (function find-equivalence-class)
- (function add-to-class))
- (inline find-equivalence-class
- add-to-class))
-
- ;; Partition into equivalence classes.
- (map nil #'add-to-class seq)
-
- ;; Return the classes.
- classes)))
-
-
(defun flatten-once (list)
"Flatten `list` once."
(loop :for x :in list
@@ -379,6 +379,25 @@
(values (intern (apply #'mkstr args))))
+ (defun tree-collect (predicate tree)
+ "Returns a list of every node in the `tree` that satisfies the `predicate`. If there are any improper lists in the tree, the `predicate` is also applied to their dotted elements."
+ (let ((sentinel (gensym)))
+ (flet ((my-cdr (obj)
+ (cond ((consp obj)
+ (let ((result (cdr obj)))
+ (if (listp result)
+ result
+ (list result sentinel))))
+ (t
+ (list sentinel)))))
+ (loop :for (item . rest) :on tree :by #'my-cdr
+ :until (eq item sentinel)
+ :if (funcall predicate item) collect item
+ :else
+ :if (listp item)
+ :append (tree-collect predicate item)))))
+
+
(deftype string-designator ()
"A string designator type. A string designator is either a string, a symbol,
or a character."
@@ -423,8 +442,8 @@
`(with-gensyms ,names ,@forms))
(eval-when (:compile-toplevel :load-toplevel :execute)
- (export '(compose copy-hash-table curry deletef ensure-gethash extremum equivalence-classes
+ (export '(compose copy-hash-table curry deletef ensure-gethash equivalence-classes extremum
flatten-once hash-table-keys hash-table-values once-only rcurry read-file-into-string
- removef symb with-gensyms with-unique-names)))
+ removef symb tree-collect with-gensyms with-unique-names)))
;;;; END OF quickutils.lisp ;;;;