Commit | Line | Data |
---|---|---|
d0fc5e86 JK |
1 | (asdf:load-system :adventofcode2020) |
2 | (in-package #:adventofcode2020) | |
3 | (named-readtables:in-readtable fn-reader) | |
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]?))*\." |