# HG changeset patch # User Steve Losh # Date 1576345635 18000 # Node ID 03d0cc3a648f8649eadd8f8eb6bb9d1435bd5e0f # Parent 491cb9e150967cfd66f103e3e9905b6062ccc305 2019/14 diff -r 491cb9e15096 -r 03d0cc3a648f data/2019/14.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/data/2019/14.txt Sat Dec 14 12:47:15 2019 -0500 @@ -0,0 +1,58 @@ +8 SPJN, 2 LJRB, 1 QMDTJ => 1 TFPRF +111 ORE => 5 GCFP +5 NGCKP => 6 QXQZ +21 RGRLZ => 7 DKVN +2 DCKF => 9 FCMVJ +7 SGHSV, 4 LZPCS => 9 DQRCZ +4 QNRH => 8 WGKHJ +135 ORE => 6 BPLFB +4 SPJN, 1 DCKF, 9 KJVZ, 1 DKVN, 4 ZKVPL, 11 TFPRF, 1 CWPVT => 8 BVMK +8 TGPV, 4 MQPLD => 2 SPFZ +11 QMDTJ, 15 LVPK, 5 LZPCS => 3 KJVZ +2 RNXF, 3 MKMQ => 6 LJRB +11 RKCXJ, 4 BJHW, 2 DKDST => 3 QNRH +3 NZHP, 1 QMDTJ => 9 BCMKN +10 DQRCZ, 1 GBJF => 7 RGRLZ +2 WLKC, 1 GBJF, 7 SPJN => 5 GBWQT +4 TGPV, 1 LTSB => 2 LZPCS +6 LJRB => 4 LQHB +3 LZPCS, 3 MDTZL, 12 DLHS => 2 CBTK +1 TGPV, 1 CQPR => 9 XQZFV +26 FSQBL => 8 HQPG +9 LQHB => 1 GBJF +7 NGCKP => 5 WLKC +9 DKDST, 1 XQZFV => 9 TPZBM +144 ORE => 9 RNXF +1 LJRB => 6 CQPR +9 MKMQ, 12 RNXF => 9 JWPLZ +5 LZPCS, 28 QMDTJ, 1 QNRH => 5 LVPK +5 TGPV, 1 HQPG => 6 FCBLK +8 LVPK, 9 DQRCZ, 1 MDTZL => 6 DCKF +1 RKCXJ, 2 LZPCS, 13 LJNJ => 1 QWFG +4 DKDST, 1 XQZFV, 10 NSXFK => 4 JRDXQ +7 QWFG, 1 BVMK, 4 BJHW, 21 QNSWJ, 3 FBTW, 3 FCBLK, 59 SPFZ, 4 GBWQT => 1 FUEL +28 LZPCS, 17 NGCKP, 1 MQPLD => 5 MDTZL +1 FCBLK, 5 WGKHJ => 7 ZKVPL +7 LJNJ => 9 BLDJP +11 FSQBL, 2 BCMKN, 1 CBTK => 9 CWPVT +1 BJHW => 1 MQPLD +11 SGHSV, 3 LJNJ => 1 NGCKP +2 FSQBL, 7 FCBLK, 1 CQPR => 4 RKCXJ +1 JRDXQ => 4 SGHSV +107 ORE => 6 MKMQ +1 DQRCZ, 3 QMDTJ, 9 XQZFV => 4 FZVH +6 NSXFK, 1 MKMQ => 6 DLHS +4 CQPR, 1 RNXF, 1 HQPG => 5 DKDST +9 RNXF => 8 LTZTR +1 LTSB, 8 BLDJP => 4 SPJN +1 FCBLK => 4 LJNJ +1 NGCKP => 3 NZHP +11 LZPCS, 22 DQRCZ, 1 QWFG, 1 QXQZ, 6 DKVN, 16 FZVH, 3 MQPLD, 23 HQPG => 3 QNSWJ +26 DLHS, 1 NSXFK => 9 BJHW +3 FCBLK, 10 HQPG => 3 LTSB +10 LTZTR, 13 JWPLZ, 16 FSQBL => 4 TGPV +11 LTSB, 1 XQZFV, 3 DQRCZ => 4 CZCJ +1 HQPG, 12 XQZFV, 17 TPZBM => 6 QMDTJ +2 LTZTR => 7 FSQBL +1 GCFP, 5 BPLFB => 1 NSXFK +3 KJVZ, 1 QXQZ, 6 DKDST, 1 FCMVJ, 2 CZCJ, 1 QNRH, 7 WLKC => 4 FBTW diff -r 491cb9e15096 -r 03d0cc3a648f package.lisp --- a/package.lisp Fri Dec 13 13:51:53 2019 -0500 +++ b/package.lisp Sat Dec 14 12:47:15 2019 -0500 @@ -69,6 +69,16 @@ :astar + :defpackage* + + :gethash-arbitrary + :pophash + + :ensure-edge + + :bisect-integers-left + :bisect-integers-right + )) (eval-when (:compile-toplevel :load-toplevel :execute) diff -r 491cb9e15096 -r 03d0cc3a648f src/2019/days/day-13.lisp --- a/src/2019/days/day-13.lisp Fri Dec 13 13:51:53 2019 -0500 +++ b/src/2019/days/day-13.lisp Sat Dec 14 12:47:15 2019 -0500 @@ -1,4 +1,4 @@ -(defpackage :advent/2019/13 #.cl-user::*advent-use*) +(advent:defpackage* :advent/2019/13) (in-package :advent/2019/13) (defun tile (val) diff -r 491cb9e15096 -r 03d0cc3a648f src/2019/days/day-14.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/2019/days/day-14.lisp Sat Dec 14 12:47:15 2019 -0500 @@ -0,0 +1,95 @@ +(advent:defpackage* :advent/2019/14) +(in-package :advent/2019/14) + +(defun parse-chem (chemicals) + (iterate (for ((#'parse-integer amount) (#'symb name)) + :matching "(\\d+) (\\w+)" :against chemicals) + (collect (cons name amount)))) + +(defun parse-line (line) + (destructuring-bind (inputs output) (ppcre:split "=>" line) + (values (first (parse-chem output)) + (parse-chem inputs)))) + +(defun parse-data (data) + "Parse `data` into a hash table of reactions and a digraph. + + The resulting hash table will look like: + + RESULT ::= {element: REACTION, …} + REACTION ::= (amount-produced . INPUTS) + INPUTS :: (INPUT*) + INPUT ::= (element . amount-required) + + " + (iterate (with graph = (digraph:make-digraph)) + (for line :in data) + (for (values (out . out-amount) inputs) = (parse-line line)) + (iterate (for (in . nil) :in inputs) + (ensure-edge graph in out)) + (collect-hash (out (cons out-amount inputs)) :into reactions) + (returning reactions graph))) + +(defun requirements (element amount reactions) + "Return the requirements to produce `amount` of `element` via `reactions`. + + The result will be an alist of `(input-element . input-amount)`. + + " + (destructuring-bind (produced-amount . inputs) (gethash element reactions) + (let ((n (ceiling amount produced-amount))) + (iterate + (for (el . amount) :in inputs) + (collect (cons el (* n amount))))))) + +(defun ore-required (reactions graph &optional (fuel 1)) + "Return the amount of ore required to produce `fuel` fuel." + (iterate + (with needed = (make-hash-table)) + (initially (setf (gethash 'fuel needed) fuel)) + (for next :in (digraph:topological-sort graph)) + (for (values el amount found) = (pophash needed next)) + (cond + ((not found)) + ((eql el 'ore) (return amount)) + (t (iterate + (for (input . in-amount) :in (requirements el amount reactions)) + (incf (gethash input needed 0) in-amount)))))) + +(define-problem (2019 14) (data read-lines) (502491 2944565) + (multiple-value-bind (reactions graph) (parse-data data) + (values (ore-required reactions graph) + (bisect-integers-left + (lambda (fuel) + (<= (ore-required reactions graph fuel) 1000000000000)) + 0 1000000000000)))) + + + +#; Scratch -------------------------------------------------------------------- + +(run '( + "10 ORE => 10 A" + "1 ORE => 1 B" + "7 A, 1 B => 1 C" + "7 A, 1 C => 1 D" + "7 A, 1 D => 1 E" + "7 A, 1 E => 1 FUEL" + )) + +(run '( + "2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG" + "17 NVRVD, 3 JNWZP => 8 VPVL" + "53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL" + "22 VJHF, 37 MNCFX => 5 FWMGM" + "139 ORE => 4 NVRVD" + "144 ORE => 7 JNWZP" + "5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC" + "5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV" + "145 ORE => 6 MNCFX" + "1 NVRVD => 8 CXFTF" + "1 VJHF, 6 MNCFX => 4 RFSQX" + "176 ORE => 6 VJHF" + )) + + diff -r 491cb9e15096 -r 03d0cc3a648f src/utils.lisp --- a/src/utils.lisp Fri Dec 13 13:51:53 2019 -0500 +++ b/src/utils.lisp Sat Dec 14 12:47:15 2019 -0500 @@ -75,6 +75,12 @@ :type "txt")) +(defmacro defpackage* (name &body body) + `(defpackage ,name + (:use :cl :losh :iterate :advent :advent.quickutils) + ,@body)) + + ;;;; Readers ------------------------------------------------------------------ (defun read-numbers-from-string (line) (mapcar #'parse-integer (ppcre:all-matches-as-strings "-?\\d+" line))) @@ -594,6 +600,137 @@ :format :pbm)))) +(defun gethash-arbitrary (hash-table) + (maphash (lambda (k v) + (return-from gethash-arbitrary (values k v t))) + hash-table) + (values nil nil nil)) + +(defun pophash (hash-table &optional (key nil key?)) + (multiple-value-bind (k v found) (if key? + (multiple-value-bind (v found) + (gethash key hash-table) + (values key v found)) + (gethash-arbitrary hash-table)) + (if found + (progn (remhash k hash-table) + (values k v t)) + (values nil nil nil)))) + + +(defun ensure-edge (digraph pred succ) + (digraph:insert-vertex digraph pred) + (digraph:insert-vertex digraph succ) + (digraph:insert-edge digraph pred succ)) + + +(defun bisect-integers-left (predicate low high) + "Bisect the integers `[low, high]` with `predicate` and return the LEFT element. + + You can think of this function as partitioning the integers from `low` to + `high` (inclusive) into two halves: those that satisfy `(predicate x)` and + those that don't, and then selecting the element on the LEFT side of the + split: + + satisfying not statisfying + [.......... ...............] + ^ + | + result + + If no integers in the range satisfy the predicate, `nil` will be returned. + + Examples: + + (bisect-integers-left (lambda (x) (< x 3)) 0 9) ; => 2 + ; sat not-sat + ; [012|345789] + ; ^ + ; result + + (bisect-integers-left (lambda (x) (<= x 7)) 0 9) ; => 7 + ; sat not-sat + ; [0123457|89] + ; ^ + ; result + + (bisect-integers-left (lambda (x) (<= x 100)) 0 9) ; => 9 + ; sat not-sat + ; [012345789|] + ; ^ + ; result + + (bisect-integers-left (lambda (x) (< x -1)) 0 9) ; => nil + ; sat not-sat + ; [|012345789] + ; no result + + " + (assert (<= low high)) + (when (funcall predicate low) + (recursively ((low low) + (high high)) + (if (= low high) + low + (let ((mid (+ low (ceiling (- high low) 2)))) + (if (funcall predicate mid) + (recur mid high) + (recur low (1- mid)))))))) + +(defun bisect-integers-right (predicate low high) + "Bisect the integers `[low, high]` with `predicate` and return the RIGHT element. + + You can think of this function as partitioning the integers from `low` to + `high` (inclusive) into two halves: those that satisfy `(predicate x)` and + those that don't, and then selecting the element on the RIGHT side of the + split: + + satisfying not statisfying + [.......... ...............] + ^ + | + result + + If all integers in the range satisfy the predicate, `nil` will be returned. + + Examples: + + (bisect-integers-right (lambda (x) (< x 3)) 0 9) ; => 3 + ; sat not-sat + ; [012|345789] + ; ^ + ; result + + (bisect-integers-right (lambda (x) (<= x 7)) 0 9) ; => 8 + ; sat not-sat + ; [0123457|89] + ; ^ + ; result + + (bisect-integers-right (lambda (x) (< x -1)) 0 9) ; => 0 + ; sat not-sat + ; [|012345789] + ; ^ + ; result) + + (bisect-integers-right (lambda (x) (<= x 100)) 0 9) ; => nil + ; sat not-sat + ; [012345789|] + ; no result + + " + (assert (<= low high)) + (when (not (funcall predicate high)) + (recursively ((low low) + (high high)) + (if (= low high) + low + (let ((mid (+ low (floor (- high low) 2)))) + (if (funcall predicate mid) + (recur (1+ mid) high) + (recur low mid))))))) + + ;;;; A* Search ---------------------------------------------------------------- (defstruct path state