src/day07.lisp

   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]?))*\."