03d0cc3a648f

2019/14
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Sat, 14 Dec 2019 12:47:15 -0500
parents 491cb9e15096
children 81b47667837b
branches/tags (none)
files data/2019/14.txt package.lisp src/2019/days/day-13.lisp src/2019/days/day-14.lisp src/utils.lisp

Changes

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