| 1 | (asdf:load-system :adventofcode2020) |
| 2 | (in-package #:adventofcode2020) |
| 3 | (named-readtables:in-readtable :adventofcode2020) |
| 4 | |
| 5 | (defun parse-bag-rule (rule) |
| 6 | (cl-ppcre:all-matches-as-strings |
| 7 | "(^[a-z]+ [a-z]+|[0-9] [a-z]+ [a-z]+)" rule)) |
| 8 | |
| 9 | (defun add-reverse-rule (table rule) |
| 10 | (let ((outer-bag (first rule)) |
| 11 | (inner-bags (rest rule))) |
| 12 | (loop for num-bag in inner-bags |
| 13 | do (let ((bag (string-left-trim " 0123456789" num-bag))) |
| 14 | (setf (gethash bag table) |
| 15 | (adjoin outer-bag (gethash bag table) :test #'string=))) |
| 16 | finally (return table)))) |
| 17 | |
| 18 | (defun add-forward-rule (table rule) |
| 19 | (let ((outer-bag (first rule)) |
| 20 | (bag-with-count (lambda (bag) |
| 21 | (cl-ppcre:register-groups-bind |
| 22 | ((#'parse-integer count) bag-name) |
| 23 | ("([0-9]) ([a-z]+ [a-z]+)" bag) |
| 24 | (list bag-name count))))) |
| 25 | (setf (gethash outer-bag table) (mapcar bag-with-count (rest rule))) |
| 26 | table)) |
| 27 | |
| 28 | (defun make-rules-table (rules rule-type) |
| 29 | (let ((table (make-hash-table :test #'equal))) |
| 30 | (reduce rule-type rules :initial-value table))) |
| 31 | |
| 32 | (defun walk-rev-rules-table (table bag) |
| 33 | (let ((next (gethash bag table))) |
| 34 | (reduce λ(union _0 _1 :test #'string=) |
| 35 | (mapcar (curry #'walk-rev-rules-table table) next) |
| 36 | :initial-value next))) |
| 37 | |
| 38 | (defun walk-fwd-rules-table (table bag) |
| 39 | (let ((next (gethash bag table)) |
| 40 | (get-bag-count (lambda (bag-pair) |
| 41 | (if bag-pair |
| 42 | (destructuring-bind (bag-name count) bag-pair |
| 43 | (* count (walk-fwd-rules-table table bag-name))) |
| 44 | 0)))) |
| 45 | (reduce #'+ (mapcar get-bag-count next) |
| 46 | :initial-value 1))) |
| 47 | |
| 48 | (day 07 input |
| 49 | (let ((rules (mapcar #'parse-bag-rule (list-from input)))) |
| 50 | (part1 (-> rules |
| 51 | (make-rules-table #'add-reverse-rule) |
| 52 | (walk-rev-rules-table "shiny gold") |
| 53 | length)) |
| 54 | (part2 (-> rules |
| 55 | (make-rules-table #'add-forward-rule) |
| 56 | (walk-fwd-rules-table "shiny gold") |
| 57 | (1-))))) |
| 58 | |
| 59 | (def-suite day07) |
| 60 | (in-suite day07) |
| 61 | |
| 62 | (defvar *simple-rules* |
| 63 | '("light red bags contain 1 bright white bag, 2 muted yellow bags." |
| 64 | "dark orange bags contain 3 bright white bags, 4 muted yellow bags." |
| 65 | "bright white bags contain 1 shiny gold bag." |
| 66 | "muted yellow bags contain 2 shiny gold bags, 9 faded blue bags." |
| 67 | "shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags." |
| 68 | "dark olive bags contain 3 faded blue bags, 4 dotted black bags." |
| 69 | "vibrant plum bags contain 5 faded blue bags, 6 dotted black bags." |
| 70 | "faded blue bags contain no other bags." |
| 71 | "dotted black bags contain no other bags.")) |
| 72 | |
| 73 | (test parse-bag-rules |
| 74 | (is (equal |
| 75 | '(("light red" "1 bright white" "2 muted yellow") |
| 76 | ("dark orange" "3 bright white" "4 muted yellow") |
| 77 | ("bright white" "1 shiny gold") |
| 78 | ("muted yellow" "2 shiny gold" "9 faded blue") |
| 79 | ("shiny gold" "1 dark olive" "2 vibrant plum") |
| 80 | ("dark olive" "3 faded blue" "4 dotted black") |
| 81 | ("vibrant plum" "5 faded blue" "6 dotted black") |
| 82 | ("faded blue") |
| 83 | ("dotted black")) |
| 84 | (mapcar #'parse-bag-rule *simple-rules*)))) |
| 85 | |
| 86 | (test make-rev-rules-table |
| 87 | (is (equal |
| 88 | '("dotted black" ("vibrant plum" "dark olive") |
| 89 | "vibrant plum" ("shiny gold") |
| 90 | "dark olive" ("shiny gold") |
| 91 | "faded blue" ("vibrant plum" "dark olive" "muted yellow") |
| 92 | "shiny gold" ("muted yellow" "bright white") |
| 93 | "muted yellow" ("dark orange" "light red") |
| 94 | "bright white" ("dark orange" "light red")) |
| 95 | (hash-table-plist (make-rules-table (mapcar #'parse-bag-rule *simple-rules*) #'add-reverse-rule))))) |
| 96 | |
| 97 | (test walk-rev-rules-table |
| 98 | (is (equal |
| 99 | '("muted yellow" "bright white" "dark orange" "light red") |
| 100 | (walk-rev-rules-table (make-rules-table (mapcar #'parse-bag-rule *simple-rules*) #'add-reverse-rule) |
| 101 | "shiny gold")))) |
| 102 | |
| 103 | (defvar *more-rules* |
| 104 | '("shiny gold bags contain 2 dark red bags." |
| 105 | "dark red bags contain 2 dark orange bags." |
| 106 | "dark orange bags contain 2 dark yellow bags." |
| 107 | "dark yellow bags contain 2 dark green bags." |
| 108 | "dark green bags contain 2 dark blue bags." |
| 109 | "dark blue bags contain 2 dark violet bags." |
| 110 | "dark violet bags contain no other bags.")) |
| 111 | |
| 112 | (test make-fwd-rules-table |
| 113 | (is (equal |
| 114 | '("dotted black" nil |
| 115 | "faded blue" nil |
| 116 | "vibrant plum" (("faded blue" 5) ("dotted black" 6)) |
| 117 | "dark olive" (("faded blue" 3) ("dotted black" 4)) |
| 118 | "shiny gold" (("dark olive" 1) ("vibrant plum" 2)) |
| 119 | "muted yellow" (("shiny gold" 2) ("faded blue" 9)) |
| 120 | "bright white" (("shiny gold" 1)) |
| 121 | "dark orange" (("bright white" 3) ("muted yellow" 4)) |
| 122 | "light red" (("bright white" 1) ("muted yellow" 2))) |
| 123 | (hash-table-plist (make-rules-table (mapcar #'parse-bag-rule *simple-rules*) #'add-forward-rule)))) |
| 124 | (is (equal |
| 125 | '("dark violet" nil |
| 126 | "dark blue" (("dark violet" 2)) |
| 127 | "dark green" (("dark blue" 2)) |
| 128 | "dark yellow" (("dark green" 2)) |
| 129 | "dark orange" (("dark yellow" 2)) |
| 130 | "dark red" (("dark orange" 2)) |
| 131 | "shiny gold" (("dark red" 2))) |
| 132 | (hash-table-plist (make-rules-table (mapcar #'parse-bag-rule *more-rules*) #'add-forward-rule))))) |
| 133 | |
| 134 | (test walk-fwd-rules-table |
| 135 | (is (equal |
| 136 | 126 |
| 137 | (1- (walk-fwd-rules-table (make-rules-table (mapcar #'parse-bag-rule *more-rules*) #'add-forward-rule) |
| 138 | "shiny gold"))))) |
| 139 | |
| 140 | |
| 141 | (run! 'day07) |
| 142 | ; "([a-z]+ [a-z]+) bags contain ([0-9]+ [a-z]+ [a-z]+|no other) bag[s]?(?:, (?:([0-9]+ [a-z]+ [a-z]+) bag[s]?))*\." |