--- a/.hgignore Sat Dec 07 18:41:35 2019 -0500
+++ b/.hgignore Sun Dec 08 13:47:53 2019 -0500
@@ -10,3 +10,4 @@
scratch.lisp
digraph.png
lisp.prof
+out/*
--- a/advent.asd Sat Dec 07 18:41:35 2019 -0500
+++ b/advent.asd Sun Dec 08 13:47:53 2019 -0500
@@ -25,6 +25,7 @@
:cl-digraph
:cl-digraph.dot
:cl-interpol
+ :cl-netpbm
:cl-ppcre
:iterate
:jpl-queues
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/data/2019/08.txt Sun Dec 08 13:47:53 2019 -0500
@@ -0,0 +1,1 @@
+001102222222222122222212222222122222222222222222220202220220222222222220022220202222222222211221212220220222222222222222222200222222222222222021222222120112222222222022222212222222222222222222222222220222220220222222222221022221202222222222200222212222222222222222222222222212222222222222222021222222102202222222222122222202222222022222222222222222220202221220212222222222222222202222222222220222222222220222222222220222222201222222222222222021222222101112222222222122222212222222122222222222222222220222220220222222222221222221202222222222201220222222222222222222220222222202222222222222222220222222011202222222222122222202222222022222222222220222222212220221212222222222222222202222222222210221212222220222222222221222222220222222222222222021222222010122222222222222222202222222022222222222220222220222220220222222222221222221202222222222200221212221222222222222220222222200212222222222222222222222011102222222222022222212222222222222222222222222220212220221222222222220222220212222222222202222222220221222222222222222222201222222222222222022222222002122222222222122222222222222222222222222222222220212222220212222022220022221212222222222221222202222220222222222222222222200222222222222222022222222110012222222222022222212222222122222222222220222220202222221222222222221022221112222220222222221222220220222222222221222222210222222222222222120222222002202222222222222222202222222222222222022222222222212222222202222222222022221112222221222202222202222221222222222221222222210202222220222222120222222000112222222222122222222222222222222222222221222220202222222202222022221222222202222221222221222222220210222222222222222222221212222221222222120222222012212222222222122222212222222022222222122220222222212221220212222222222022221102222222222222222222222222222222222221222222220212222221222222122222222220102222222222222222222222222222222222222222222220202222221222022022222122221222222221222221221222220211222222222221222222221212222220222222121222222012022222222222222222202222222122222222222222222201222021222212222022221022220212222220222210220222221210222222222220222222212202222221222222221222222000202222222222222222222222222222222222122222222200222120221202122122220222222002222222222201221212221211222122222220222222200202222222222222022222222012002222221222122222212222222222222222222222222200202220220212022122220222222222222220222201221202222201222022222220222222201202222221222222220222222011122222222222022222222222222122222222112220222222212122220202122022221222222222222222222210222202220200222222222220222222220202222221222222222222222122112220220222022222202222222122222222012221222202212222220212222122220022221002222221222212220212222202222022222221222222222222222220222222220222222022102221222222222220122222022022222222112220222211212121221202122122221122221212222221222220221212220211222122222222122222211202222221222222120222222000012222220222222220212222222222222222002222222200202121220212222222220222222002222220222220222222222200222022222021222222201212222220222222022222222122112220220222022222102222122222222222112222222222222221220202122222221122220112222220222222221222222211222002222122122222222202222220222222121222222001012222221222022220222222122222222220002222220221222120220222222022222022222122222222222201221212221221222002222221122222221212222222222222221222222010022220222222122222222222022022222221012222222201202021222222222222221222222102222220222222220212222201222022222221122222211212222220222222020222222021022222221222022221222222022022222220122221222210222221222222122222220222220002222222222220221212220211222012222222122222220202222220222222121220222102202221222222122222112222022222222222102221222221212221221202022222221222220002222220222200222202222212222212222221122222212212222220222222021222222201202220222222222222022222022022222222102222222221212020220222022022220220220112222222222201221212221202222122222121022222200202222222222222020220222112002220222222222220122222222222222222222221220210212121222222022122220222220122222221222221222212222220222022222120222222111212222222222222220221222102102221221222022222122222022022222220222221222201202221222202122122221120222022222222222212222202220210222002222120122222120202222221222222021220222122202221222222222221022222122122222202202220220221212222222222222022222221220012222221222210220222222210222202222122222222011202222220222222222222222100202220222222122220122222022122222200122222222202212122222212022022222022221102222222222221222222221220222202222120122222120222222221222222120221222012112220222222122221212222122022222221212210220201222120221202222122222220222112222222222222221202222201222022222221022222012202222221222222220222222112122220222222122221002222022222222222212221220212202122220222022122222120222012222222222221220222222212222002222220022222120212222222222222022222222202122220220222222220102222122022222220012221220222212221222222122222220120222212222221222222221212222000222122222122022222102212222222222222021220222121002222220222222221222222122222222211002210222210222221221202022022222022222112222220222221221222221120222012222022222222221202222222222222122221222220220222022222122222002222022022222212200220222221222021220202122122222022222202222220222201222202222200222122222121022222110222222222222222021220222210121220122222022221202222022222222201222211222211212020220212122122220022222212222220202200221202222100222222220120222222200222222220222222022221222200021221120222122222112222222122222202010211222222222020221202222222221220220122222222222202220222220011222002222121222222101222222222222222021222222022210222220222022022212222122122222222200222222200211122220222222222220222221222222221222202220222220011222122221121222222122222222220222222222022222212110221222222212022212222122122222222010212221202211020221212022122222222220002222222202220220212220111222002220120222222220222222221222222022121222221221220022222002021102222022022222202110200222212212122222222122122222022221212222222212221201222222111222002220121022222211212222220222222122122222022010222121222022022202222022222222202122211221220201222222202122222220220222102222220212201201222222000222122220222122222221212222220222222020121222222111220221222212020212222222222222220111222221220221121220212222022221121220222222222202200222222221002222012220220222222220222222222222222220021222001212121022222102022012222122222222220020212220201201120222202122222220221222012222222222221211202220022222002221220022222210202222221222222120220222010012121210222002121002222122122222211220211222201202222221212122122222121221212222221212221212222221002222222221120022222011202222221222222021020222221101022121222022122102222022022222211120211221201201221220202121202221120220112222220202220201222220120222222222120122222121202222222222222021220222001021020102222122020102222122022222201212220222211220021220222222122222122222002222221222212210222221212222012220020222222022222222222222222220020222020122021020222022220012222222122221220010222222201202020222212122202222122220122222222202222210212222001222002221121022222200212222221222222121122222222022021221222112021012222122202222210112211220221211022222212220222211022220202222222212210221222211222222012222022122222222202222221222222220122222200212221201222112022102222122122221200211212221211202221222212022112220020220002222221222202211222222011222102221022222222211222222222222222122222222102101020021222222222212222022122222202011212220211220220220212122002212121222122222220212212201202222111222012220221122222222202222220222222122022222221021122200222112122002222222222221201200202222212222022220212022102211021222212222222212221202202202211222122220221022222120222222221222222221121222021120222202222012221022222222112221212221222222201200220220212120112200021222102222222222211220222220111222112221121122222201202222221222221222121222212002121111222022220212222022100220211021201222211222222222222220022222121220122222222220220202212222022222022220122022222201212222222222222020220222212112222222222212020022222022101222222022202221222211222220222021002220120221122222220222211211212201012222022222020022222122212222221222220021222222221121022210222202120002222222010221210020210221201211220222202021112202121221022222221221210201202212212222122220020202222212212222220222222022220222021210220112222102121022222122002221200010210222220221021220212020222202122220212222222212211221112012010222022220220112222010202222222222222220020222010102122100222112121112222122222221210120211220222202121221222021222210021220222222221201201220102120011222102221120022222200212222220222220122121222000201022122222012022022222122202222200222210221222221022222222220112211022220012222221202211212202121220222222220120122222022202222221222221000221222012201022120222102122002222122200220201011201221221212122221202220102222120221012222221212201222222011200222002221020222222102212222222222222010020222110202120112222112021122222122012221201102202220222220122221212120012212022220012222220211212221122200021222122220222222222120222222222222220222022222102110220001222011022002222122021220200222220221200222120220202120212201022222222222221200211221101210202222102220021102222122202222221222221120020222201012220212222200221202222022001222221112222222222201221021202021202222021222002222220221200210222122210222022221220002222222202222220222222020022222022122220121222121122110222222111222212022222220221210221220212220122201022220122222221221222201012010020222201220120012222110202222222222221121222222221002222000222100021002222022120221212121200220200212221222212020002221220220202222220200222200201212011222111220020212222120222222221222220101220222210222020210222220220022222022022220220101221222212202120121212022002221020221022222220210212221201211211222211221020212222021212222222222202022021222020211221101212120020222222022022221220012212221201201121221202121212010022221222222222210221200102011010222112221021112222110222222221222221211120222110201222101212022121022222222002220201110220221220221022020202021222221221222102222222222201202221201221222120222020122222112222222221222222022022222011110222002212022122002222122022220212022212222221222121022212121102010121220022222221202200202200121221222200222222022222201212222221222220111022222001120220021212111121211222022000221210111210220212222121121221101112110020220112222211200212210020002012222202221220002222210222222222222222211021220101100222102202121022102222222211221201210220220210220221222202121222210120220212122222202212212120220222222112221222112222102222222222222212000120222202010022100212202222120222022222221201212212220220202022021221212202211020222212222200202220211111200110222022222222022222101202222220222200102120221022100222202212121220200222222122220200110211220211222120121212200022100020222112122211221220200221012100222111221220222222111202222220222220010120221121111022111212200022022222022002222222020011222210211021121211012002011021221112122211220202220101021021222202220220212222220202222222222201010121221022221222010200112220000222022020222222000021220210222022021210202122021121220022022211201201221002002220222121221020202222200212222222222220102022222210210221102210221220202222022012220221101022221211222122021212220022122022222202222211222221210102112010222000221122112222200212222222222211012022222111022220212200002121012222022011220211111200221202211021022220211202012022222122022202210201220002200221222102221022012222211222222222222202220120222012010120121222202121110222022201221200101112221201201222021201022112100222221112121202212201200210222211222001201120212222221212222221222212120122222002001221211221010222212222022121221212210211220211222221020220112202120021222012122202222210212120020110222002200020112222102222222220202200002021222210120120110202002021112222122100220212212100221211211020220210221102122120020122022212212200202002202102122101220121202222100202222222222212010121220010100021110221110220002222222022222210221020222211201121222201101102002122122102121210222222202202220010122011202222222222102212222220212220011022221020201221120222212021211222122220222221020221221212211020020212202222202010022012022211210210201000021120022202222022222222112222222220202222201220222122210210000201222221101222122221221211210021220210221021020212102202010102121012222200210222222011212002122200200022212222022202222222222212021122221001012222120211020002000222022222222210210020222201211121022211200222121120120122020222221202201100202101222001210220202222221222222222222011011121220000200021112201022221200222222022221222112122221211210022022210222012211210021022121222202201212110201210222012221120122222210222222220222002011220222121102012212220120101102222022220222212020011222210200020121221201222211010021222020220222212212212021220022221212020122222202212222220222221222022221201202112021210211111020222222111222222012010222200211111220220002022011010222102220210202210200220221122022200200021122222012222222221222202222021220220002121020211011122211222122001221202211110122220202002122221202202221222020022020201211222001122112021022200022122202222202212222222202102022120222221021011001201211012001222222121222210022102020201211211120220001122220201022122022201211221221112020002022022110221122122101212222221220101222122221011222102002212221210100222022102220201021220120222211100120200010212201100022102222200212220120112100112222011121222212122122212222220210012100021221122212012100222020122002022122220220202222021220201220002222221100212022220020212222220221201212000222020122211111221122122002212222220222102011122221100010002201212000221211102022010222202111102122111212110120212001112100112122202222212222212100022012020222101102022022222021222222221210222121222221022121122111221001022212002222022222221102211022021212200120222022222110010221102021201210212202001122202222201002222220022111222222221201100112222222210002202220221000112120122122012221201112121022110222010222102021022100220121122120220220211101221012010022122002022102222100202222221221202211221220001202000101221110122221022022100221212202221022122212002211212010212211221221212220220201222120101100000222201002220200022120222022221212101012220221000200002221220002001102202022021220211122121022212221011001000011222122022220102220211220222021022021200222101120021120122221210122221202022110120220220202212210212221221101002012020221210122222221011200102022101002202122220222002122210201221120210210221122210002022222020101210122220210121222220221120111202002202100222000202022110220210000211020002220200100222202012110121122012112200001211220210202201122210001221201121211200022220212200200021220112200201021211022122020102002012221202212211121212210020112221202202210102120022202220020210222102022120122002211210212122020202022220221200002121222110012022011200101111020212002000222220020000022112210121212112202122120120121222220212110222222111000202022210112012011220110200022220221222220220222112102121001110111211101200100101100021221220100112011012122210001121200210100221012022021120122201101201200011011102102000101101010012101021200211010
--- a/src/2016/days/day-05.lisp Sat Dec 07 18:41:35 2019 -0500
+++ b/src/2016/days/day-05.lisp Sun Dec 08 13:47:53 2019 -0500
@@ -1,32 +1,60 @@
(defpackage :advent/2016/05 #.cl-user::*advent-use*)
(in-package :advent/2016/05)
-(defun md5 (string)
- (bytes->hex (md5:md5sum-string string)))
+(defparameter *spinner* '#1=(#\◴ #\◷ #\◶ #\◵ . #1#))
+
+(defun string->bytes (string)
+ (map 'vector #'char-code string))
+
+(defun progress (i)
+ (format t "~C~C Iteration: ~D" #\Return (pop *spinner*) i)
+ (force-output))
+
+(defun good-hash-p (hash)
+ (and (zerop (aref hash 0))
+ (zerop (aref hash 1))
+ (zerop (ldb (byte 4 4) (aref hash 2)))))
(define-problem (2016 5) (data read-line) ("1a3099aa" "694190cd")
+ ;; This is ugly for performance. A prettier version takes over a minute, but
+ ;; this is around 20 seconds.
(iterate
+ (with remaining = 8)
(with part1 = (make-array 8 :element-type 'character :initial-element #\_ :fill-pointer 0))
(with part2 = (make-string 8 :initial-element #\_))
- (with remaining = 8)
- (with spinner = '#1=(#\◴ #\◷ #\◶ #\◵ . #1#))
(returning part1 part2)
+
+ ;; Instead create a fresh string of the entire ID every time, we keep
+ ;; a buffer and just replace the numeric portion on each iteration.
+ (with n = (length data))
+ (with buffer = (make-array 1024 :fill-pointer n :element-type '(unsigned-byte 8)))
+ (initially (replace buffer (string->bytes data)))
+
(for i :from 0)
- (for hash = (md5 (format nil "~A~D" data i)))
+ (for id = (string->bytes (princ-to-string i)))
+ (setf (fill-pointer buffer) (+ n (length id)))
+ (replace buffer id :start1 n)
+ (for hash = (md5:md5sum-sequence buffer))
+
(when (dividesp i 100000)
- (format t "~C~C Iteration: ~D" #\Return (pop spinner) i)
- (force-output))
- (when (str:starts-with-p "00000" hash)
+ (progress i))
+
+ (when (good-hash-p hash)
+ (for hex = (bytes->hex hash))
+
+ ;; We only need the first 8 results for part 1.
(when (< (length part1) 8)
- (vector-push (aref hash 5) part1))
- (let ((pos (digit-char-p (aref hash 5) 16)))
- (when (and (< pos (length part2))
- (char= (aref part2 pos) #\_))
- (setf (aref part2 pos) (aref hash 6))
+ (vector-push (aref hex 5) part1))
+
+ (let ((pos (digit-char-p (aref hex 5) 16))) ; hex digit -> array index
+ (when (and (< pos (length part2)) ; valid index
+ (char= (aref part2 pos) #\_)) ; not already seen
+ (setf (aref part2 pos) (aref hex 6))
(when (zerop (decf remaining))
(format t " Cracked.~%")
(finish))))
- (format t " [~A] / [~A]~%" part1 part2))))
+ (format t " [~A] / [~A]~%" part1 part2)
+ (progress i))))
--- a/src/2017/days/day-11.lisp Sat Dec 07 18:41:35 2019 -0500
+++ b/src/2017/days/day-11.lisp Sun Dec 08 13:47:53 2019 -0500
@@ -12,6 +12,15 @@
(defun distance (c1 &optional (c2 #(0 0 0)))
(/ (reduce #'+ (coord- c1 c2) :key #'abs) 2))
+(defun delta (direction)
+ (ecase direction
+ (:nw #(-1 0 1))
+ (:n #( 0 -1 1))
+ (:ne #( 1 -1 0))
+ (:se #( 1 0 -1))
+ (:s #( 0 1 -1))
+ (:sw #(-1 1 0))))
+
(define-problem (2017 11) (data read-comma-separated-values) (773 1560)
(iterate
(with pos = #(0 0 0))
--- a/src/2017/days/day-18.lisp Sat Dec 07 18:41:35 2019 -0500
+++ b/src/2017/days/day-18.lisp Sun Dec 08 13:47:53 2019 -0500
@@ -78,10 +78,11 @@
(setf (blocked a) t)
(rotatef a b))))))))
-(define-problem (2017 18) (data read-lines) (1187 5969)
- (setf data (map 'vector #'read-all-from-string data))
- (values (part1 data)
- (part2 data)))
+;; TODO finish this
+;; (define-problem (2017 18) (data read-lines) (1187 5969)
+;; (setf data (map 'vector #'read-all-from-string data))
+;; (values (part1 data)
+;; (part2 data)))
#; Scratch --------------------------------------------------------------------
@@ -104,3 +105,4 @@
"rcv b"
"rcv c"
"rcv d"))
+
--- a/src/2018/days/day-03.lisp Sat Dec 07 18:41:35 2019 -0500
+++ b/src/2018/days/day-03.lisp Sun Dec 08 13:47:53 2019 -0500
@@ -3,7 +3,7 @@
(named-readtables:in-readtable :interpol-syntax)
-(defstruct claim id left right top bottom)
+(defstruct (claim (:conc-name nil)) id left right top bottom)
(define-with-macro claim id left right top bottom)
(defun parse-claim (line)
--- a/src/2019/days/day-05.lisp Sat Dec 07 18:41:35 2019 -0500
+++ b/src/2019/days/day-05.lisp Sun Dec 08 13:47:53 2019 -0500
@@ -1,7 +1,7 @@
(defpackage :advent/2019/05 #.cl-user::*advent-use*)
(in-package :advent/2019/05)
-(define-problem (2019 5) (data read-numbers) (14522484 4)
+(define-problem (2019 5) (data read-numbers) (14522484 4655956)
(values
(car (last (gathering
(advent/intcode:run data :input (constantly 1) :output #'gather))))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/2019/days/day-08.lisp Sun Dec 08 13:47:53 2019 -0500
@@ -0,0 +1,45 @@
+(defpackage :advent/2019/08 #.cl-user::*advent-use*)
+(in-package :advent/2019/08)
+
+(defun read-layer (stream width height)
+ (let-result (layer (make-array (list height width)))
+ (do-range ((y 0 height)
+ (x 0 width))
+ (setf (aref layer y x) (read-char stream)))))
+
+(defun read-image (stream width height)
+ (iterate (until (char= #\newline (peek-char nil stream nil #\newline)))
+ (collect (read-layer stream width height))))
+
+(defun count-digit (layer digit)
+ (iterate (for d :across-flat-array layer)
+ (counting (char= digit d))))
+
+(defun pixel-color (layers y x)
+ (iterate (for layer :in layers)
+ (thereis (ecase (aref layer y x)
+ (#\2) ; transparent
+ (#\1 1)
+ (#\0 0)))))
+
+(defun decode-image (layers)
+ (destructuring-bind (height width) (array-dimensions (first layers))
+ (let-result (image (make-array (list width height)))
+ (do-range ((y 0 height)
+ (x 0 width))
+ (setf (aref image x y)
+ (pixel-color layers y x))))))
+
+(define-problem (2019 8) (stream) (1806)
+ (let ((image (read-image stream 25 6)))
+ (netpbm:write-to-file "out/2019-08.pbm" (decode-image image)
+ :if-exists :supersede
+ :format :pbm)
+ (iterate
+ (for layer :in image)
+ (finding (* (count-digit layer #\1)
+ (count-digit layer #\2))
+ :minimizing (count-digit layer #\0)))))
+
+
+#; Scratch --------------------------------------------------------------------