--- /dev/null
+(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]?))*\."
projects / adventofcode2020.git / blobdiff