X-Git-Url: http://git.jkinsey.net/?p=adventofcode2020.git;a=blobdiff_plain;f=src%2Fday07.lisp;fp=src%2Fday07.lisp;h=db50ca806cdc68a308d354f061f459b0dc585c64;hp=0000000000000000000000000000000000000000;hb=d0fc5e86a211060610de320334535324abd94a84;hpb=007500675a2dd10e250d3ad0588852ed6f9225a6

diff --git a/src/day07.lisp b/src/day07.lisp
new file mode 100644
index 0000000..db50ca8
--- /dev/null
+++ b/src/day07.lisp
@@ -0,0 +1,142 @@
+(asdf:load-system :adventofcode2020)
+(in-package #:adventofcode2020)
+(named-readtables:in-readtable fn-reader)
+
+(defun parse-bag-rule (rule)
+  (cl-ppcre:all-matches-as-strings 
+    "(^[a-z]+ [a-z]+|[0-9] [a-z]+ [a-z]+)" rule))
+
+(defun add-reverse-rule (table rule)
+  (let ((outer-bag (first rule))
+        (inner-bags (rest rule)))
+    (loop for num-bag in inner-bags
+          do (let ((bag (string-left-trim " 0123456789" num-bag)))
+               (setf (gethash bag table)
+                     (adjoin outer-bag (gethash bag table) :test #'string=)))
+          finally (return table))))
+
+(defun add-forward-rule (table rule)
+  (let ((outer-bag (first rule))
+        (bag-with-count (lambda (bag)
+                          (cl-ppcre:register-groups-bind 
+                            ((#'parse-integer count) bag-name)
+                            ("([0-9]) ([a-z]+ [a-z]+)" bag)
+                            (list bag-name count)))))
+    (setf (gethash outer-bag table) (mapcar bag-with-count (rest rule)))
+    table))
+
+(defun make-rules-table (rules rule-type)
+  (let ((table (make-hash-table :test #'equal)))
+    (reduce rule-type rules :initial-value table)))
+
+(defun walk-rev-rules-table (table bag)
+  (let ((next (gethash bag table)))
+    (reduce λ(union _0 _1 :test #'string=)
+            (mapcar (curry #'walk-rev-rules-table table) next)
+            :initial-value next)))
+
+(defun walk-fwd-rules-table (table bag)
+  (let ((next (gethash bag table))
+        (get-bag-count (lambda (bag-pair)
+                         (if bag-pair
+                             (destructuring-bind (bag-name count) bag-pair
+                               (* count (walk-fwd-rules-table table bag-name)))
+                             0))))
+    (reduce #'+ (mapcar get-bag-count next)
+            :initial-value 1)))
+
+(day 07 input
+  (let ((rules (mapcar #'parse-bag-rule (list-from input))))
+    (part1 (-> rules
+             (make-rules-table #'add-reverse-rule)
+             (walk-rev-rules-table "shiny gold")
+             length))
+    (part2 (-> rules
+             (make-rules-table #'add-forward-rule)
+             (walk-fwd-rules-table "shiny gold")
+             (1-)))))
+
+(def-suite day07)
+(in-suite day07)
+
+(defvar *simple-rules* 
+  '("light red bags contain 1 bright white bag, 2 muted yellow bags."
+    "dark orange bags contain 3 bright white bags, 4 muted yellow bags."
+    "bright white bags contain 1 shiny gold bag."
+    "muted yellow bags contain 2 shiny gold bags, 9 faded blue bags."
+    "shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags."
+    "dark olive bags contain 3 faded blue bags, 4 dotted black bags."
+    "vibrant plum bags contain 5 faded blue bags, 6 dotted black bags."
+    "faded blue bags contain no other bags."
+    "dotted black bags contain no other bags."))
+
+(test parse-bag-rules
+  (is (equal
+        '(("light red" "1 bright white" "2 muted yellow")
+          ("dark orange" "3 bright white" "4 muted yellow")
+          ("bright white" "1 shiny gold") 
+          ("muted yellow" "2 shiny gold" "9 faded blue")
+          ("shiny gold" "1 dark olive" "2 vibrant plum")
+          ("dark olive" "3 faded blue" "4 dotted black")
+          ("vibrant plum" "5 faded blue" "6 dotted black") 
+          ("faded blue")
+          ("dotted black"))
+        (mapcar #'parse-bag-rule *simple-rules*))))
+
+(test make-rev-rules-table
+  (is (equal
+        '("dotted black" ("vibrant plum" "dark olive") 
+          "vibrant plum" ("shiny gold")
+          "dark olive" ("shiny gold") 
+          "faded blue" ("vibrant plum" "dark olive" "muted yellow") 
+          "shiny gold" ("muted yellow" "bright white") 
+          "muted yellow" ("dark orange" "light red")
+          "bright white" ("dark orange" "light red"))
+        (hash-table-plist (make-rules-table (mapcar #'parse-bag-rule *simple-rules*) #'add-reverse-rule)))))
+
+(test walk-rev-rules-table
+  (is (equal
+       '("muted yellow" "bright white" "dark orange" "light red")
+        (walk-rev-rules-table (make-rules-table (mapcar #'parse-bag-rule *simple-rules*) #'add-reverse-rule)
+                          "shiny gold"))))
+
+(defvar *more-rules*
+  '("shiny gold bags contain 2 dark red bags."
+    "dark red bags contain 2 dark orange bags."
+    "dark orange bags contain 2 dark yellow bags."
+    "dark yellow bags contain 2 dark green bags."
+    "dark green bags contain 2 dark blue bags."
+    "dark blue bags contain 2 dark violet bags."
+    "dark violet bags contain no other bags."))
+
+(test make-fwd-rules-table
+  (is (equal
+        '("dotted black" nil 
+          "faded blue" nil 
+          "vibrant plum" (("faded blue" 5) ("dotted black" 6)) 
+          "dark olive" (("faded blue" 3) ("dotted black" 4)) 
+          "shiny gold" (("dark olive" 1) ("vibrant plum" 2)) 
+          "muted yellow" (("shiny gold" 2) ("faded blue" 9)) 
+          "bright white" (("shiny gold" 1)) 
+          "dark orange" (("bright white" 3) ("muted yellow" 4)) 
+          "light red" (("bright white" 1) ("muted yellow" 2)))
+        (hash-table-plist (make-rules-table (mapcar #'parse-bag-rule *simple-rules*) #'add-forward-rule))))
+  (is (equal
+        '("dark violet" nil 
+          "dark blue" (("dark violet" 2)) 
+          "dark green" (("dark blue" 2)) 
+          "dark yellow" (("dark green" 2)) 
+          "dark orange" (("dark yellow" 2)) 
+          "dark red" (("dark orange" 2)) 
+          "shiny gold" (("dark red" 2)))
+        (hash-table-plist (make-rules-table (mapcar #'parse-bag-rule *more-rules*) #'add-forward-rule)))))
+
+(test walk-fwd-rules-table
+  (is (equal
+        126
+        (1- (walk-fwd-rules-table (make-rules-table (mapcar #'parse-bag-rule *more-rules*) #'add-forward-rule)
+                               "shiny gold")))))
+
+
+(run! 'day07)
+; "([a-z]+ [a-z]+) bags contain ([0-9]+ [a-z]+ [a-z]+|no other) bag[s]?(?:, (?:([0-9]+ [a-z]+ [a-z]+) bag[s]?))*\."