(asdf:load-system :adventofcode2020)
(in-package #:adventofcode2020)
(named-readtables:in-readtable :adventofcode2020)

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