--- /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
--- /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"
+ ))
+
+
--- 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