Advent of Code 2020

aoc2020.clj

(ns y2020.core
  (:require [clojure.edn :as edn]
            [clojure.string :as str]))

;; 202001
(let [input (->> (slurp "src/y2020/input202001") (re-seq #"\d+") (map edn/read-string) sort)
      f (fn [sum xs]
          (loop [[x & morex :as x'] xs
                 [y & morey :as y'] (reverse xs)]
            (when (and x morex)
              (cond
                (= sum (+ x y)) (* x y)
                (< sum (+ x y)) (recur x' morey)
                :else           (recur morex y')))))]
  [(f 2020 input)
   (loop [[a & more] input]
     (if-let [ans (f (- 2020 a) more)]
       (* a ans)
       (recur more)))])
;; [793524 61515678]


;; 202002
(let [input (->> (slurp "src/y2020/input202002") (re-seq #"[\d\w]+") (partition 4))
      f (fn [[a b c s]]
          (let [[a b] (map edn/read-string [a b])]
            (if (<= a (count (filter (set c) s)) b) true)))
      g (fn [[a b c s]]
          (let [[a b] (map #(dec (edn/read-string %)) [a b])
                c (first c)]
            (if (not= (= c (get s a)) (= c (get s b))) true)))]
  (map #(count (keep % input)) [f g]))
;; (515 711)


;; 202003
(let [input (->> (slurp "src/y2020/input202003") (re-seq #"[^\n]+"))
      len (count (first input))
      f (fn [step]
          (fn [line n]
            (get line (mod (* step n) len))))
      g (fn [[x y]] ((frequencies (map (f x) (rest (take-nth y input)) (rest (range)))) \#))]
  [(g [3 1]) (reduce * (map g [[1 1] [3 1] [5 1] [7 1] [1 2]]))])
;; [167 736527114]


;; 202004
(let [input (->> (slurp "src/y2020/input202004") (re-seq #"[\w#]+|\n\n") (partition-by #(= "\n\n" %)))
      f (fn [xs]
          (clojure.set/subset? #{"byr" "iyr" "eyr" "hgt" "hcl" "ecl" "pid"} (set (take-nth 2 xs))))
      g (fn [xs]
          (let [{:strs [byr iyr eyr hgt hcl ecl pid]} (into {} (map vec (partition 2 xs)))]
            (and byr (<= 1920 (edn/read-string byr) 2002)
                 iyr (<= 2010 (edn/read-string iyr) 2020)
                 eyr (<= 2020 (edn/read-string eyr) 2030)
                 hgt (if-let [[_ height unit] (re-matches #"(\d+)(cm|in)" hgt)]
                       (let [h (edn/read-string height)]
                         (or (and (= "cm" unit) (<= 150 h 193))
                             (and (= "in" unit) (<= 59 h 76)))))
                 hcl (re-matches #"#[0-9a-f]{6}" hcl)
                 ecl (#{"amb" "blu" "brn" "gry" "grn" "hzl" "oth"} ecl)
                 pid (re-matches #"^\d{9}" pid))))
      input (filter f input)]
  [(count input) (count (filter g input))])
;; [260 153]


;; 202005
(let [f #(if (= (inc %2) %1) %2 (reduced (inc %2)))
      input (->> (str/escape (slurp "src/y2020/input202005") {\B \1 \F \0 \R \1 \L \0})
                 (re-seq #"\w+")
                 (map #(Integer/parseInt % 2))
                 sort
                 reverse)]
  [(first input) (reduce f input)])
;; [864 739]


;; 202006
(let [input (-> (slurp "src/y2020/input202006") (str/split #"\n\n"))]
  [(reduce + (map #(count (set (str/replace % "\n" ""))) input))
   (reduce + (map #(->> (map set (str/split-lines %)) (reduce clojure.set/intersection) count) input))])
;; [6799 3354]


;; 202007
(let [input (->> (slurp "src/y2020/input202007")
                 (re-seq #"[^\n]+")
                 (map #(re-seq #"(\d+ )?(\w+ \w+)(?= bag)" %)))
      input1 (map (fn [[root & leaves]]
                    {:root (root 2) :leaves (set (map #(% 2) leaves))})
                  input)
      input2 (reduce (fn [m [root & leaves]]
                       (->> (into {} (for [[_ n name] leaves]
                                       [name (if (nil? n) 0 (edn/read-string n))]))
                            (assoc m (root 2))))
                     {"no other" 0}
                     input)
      f (fn [color-set]
          (set (for [{:keys [root leaves]} input1
                     :when (seq (clojure.set/intersection color-set leaves))]
                 root)))
      g (fn g [r [k v]]
          (if (= "no other" k) 0 (+ r v (* v (reduce g 0 (input2 k))))))]
  [(->> #{"shiny gold"}
        (iterate f)
        rest
        (take-while seq)
        (reduce clojure.set/union)
        count)
   (g -1 ["shiny gold" 1])])
;; [128 20189]


;; 202008
(let [input (->> (slurp "src/y2020/input202008")
                 (re-seq #"(\S+) (\S+)")
                 (mapv (fn [[_ op op1]] [op (edn/read-string op1)])))
      l (count input)
      f (fn [input mode]
          (->> {:i 0, :acc 0, :seen #{}}
               (iterate (fn [{:keys [i acc seen] :as state}]
                          (cond (= i l) acc
                                (seen i) (if (= :loop mode) acc nil)
                                :else (let [[op op1] (input i)]
                                        (merge (update state :seen #(conj % i))
                                               (condp = op
                                                 "nop" {:i (inc i)}
                                                 "acc" {:i (inc i) :acc (+ acc op1)}
                                                 "jmp" {:i (+ i op1)}))))))
               (drop-while map?)
               first))]
  [(f input :loop)
   (for [i (range (count input))
         :when (#{"nop" "jmp"} ((input i) 0))
         :let [input (update-in input [i 0] {"nop" "jmp", "jmp" "nop"})
               r (f input :bug)]
         :when r]
     r)])
;; [1200 (1023)]


;; 202009
(let [input (->> (slurp "src/y2020/input202009") (re-seq #"\d+") (mapv edn/read-string))
      p1 (loop [xs input]
           (let [top25 (subvec xs 0 25)
                 top25-set (into #{} top25)
                 n26 (xs 25)]
             (if (some #(and (top25-set %) (top25-set (- n26 %)) (not= % (- n26 %))) top25)
               (recur (subvec xs 1))
               n26)))
      p2 (loop [off0 0
                off1 2
                r (reduce + (subvec input off0 off1))]
           (cond (= r p1) (->> (subvec input off0 off1) sort ((juxt first last)) (reduce +))
                 (> r p1) (recur (inc off0) off1 (- r (input off0)))
                 (< r p1) (recur off0 (inc off1) (+ r (input off1)))))]
  [p1 p2])
;; [20874512 3012420]


;; 202010
;; xxxxxx:() x    x
;; xxxxx:(7) xxxxx x..xx x.x.x xx..x x.xxx xx.xx xxx.x
;; xxxx: (4) xxxx x..x x.xx xx.x
;; xxx:  (2) xxx x.x
;; xx:   (1) xx
(let [input (->> (slurp "src/y2020/input202010")
                 (re-seq #"\d+")
                 (map edn/read-string)
                 (cons 0)
                 sort
                 (partition 2 1)
                 (map #(- (second %) (first %))))
      {d1 1 d3 3} (frequencies input)
      options {4 7, 3 4, 2 2, 1 1}]
  [(* d1 (inc d3))
   (->> input
        (partition-by #(= 3 %))
        (map #(if (= 3 (first %)) 1 (options (count %))))
        (reduce *))])
;; [2484 15790581481472]


;; 202011
(let [input (slurp "src/y2020/input202011")
      input1 (str/split-lines input)
      max-y (count input1)
      max-x (count (first input1))
      seats-map (->> (re-seq #"." input)
                     (keep-indexed (fn [i cell]
                                     (if (not= cell ".")
                                       [[(mod i max-x) (quot i max-x)] cell])))
                     (into {}))
      seats (set (keys seats-map))
      adj-neighbors (fn [_ loc]
                      (for [a [-1 0 1]
                            b [-1 0 1]
                            :let [[x y :as xy] (map + loc [a b])]
                            :when (and (not= a b 0)
                                       (<= 0 x (dec max-x))
                                       (<= 0 y (dec max-y))
                                       (seats xy))]
                        xy))
      star-neighbors (fn [seats-map loc]
                       (for [a [-1 0 1]
                             b [-1 0 1]
                             :when (not= a b 0)
                             :let [r (->> (rest (range))
                                          (keep #(let [[x y :as xy] (->> (map * [a b] [% %]) (mapv + loc))
                                                       v (seats-map xy ".")]
                                                   (if (and (<= 0 x (dec max-x))
                                                            (<= 0 y (dec max-y)))
                                                     (if (#{"#" "L"} v) xy nil)
                                                     -1)))
                                          first)]
                             :when (not= -1 r)]
                         r))
      solution (fn [[neighbor-fn max-neighbor]]
                 (loop [seats-map seats-map]
                   (let [neighbor-coverage-map (->> seats
                                                    (filter #(= "#" (seats-map %)))
                                                    (mapcat #(neighbor-fn seats-map %))
                                                    frequencies)
                         changed-seats (keep #(let [n (neighbor-coverage-map % 0)]
                                                (cond (and (= "L" (seats-map %)) (= n 0))             [% "#"]
                                                      (and (= "#" (seats-map %)) (<= max-neighbor n)) [% "L"]))
                                             seats)]
                     (if (seq changed-seats)
                       (recur (into seats-map changed-seats))
                       (-> seats-map vals frequencies (get "#"))))))]
  (pmap solution [[adj-neighbors 4] [star-neighbors 5]]))
;; (2334 2100)


;; 202012
(let [input (->> (slurp "src/y2020/input202012") (re-seq #"\w+"))
      dir-map {90 [1 0], 180 [0 -1], 270 [-1 0], 0 [0 1]}
      f (fn [x] (reduce + (map #(Math/abs %) (:loc x))))
      ans1 (reduce (fn [{:keys [loc dir] :as state} instruction]
                     (let [v (edn/read-string (subs instruction 1))]
                       (case (first instruction)
                         \N (update state :loc #(map + % [0 v]))
                         \S (update state :loc #(map - % [0 v]))
                         \E (update state :loc #(map + % [v 0]))
                         \W (update state :loc #(map - % [v 0]))
                         \L (update state :dir #(mod (- % v) 360))
                         \R (update state :dir #(mod (+ % v) 360))
                         \F (update state :loc #(map + % (map * [v v] (dir-map dir)))))))
                   {:loc [0 0] :dir 90}
                   input)
      ans2 (reduce (fn [{:keys [loc way] :as state} instruction]
                     (let [v (edn/read-string (subs instruction 1))
                           [x y] way]
                       (case (first instruction)
                         \N (update state :way #(map + % [0 v]))
                         \S (update state :way #(map - % [0 v]))
                         \E (update state :way #(map + % [v 0]))
                         \W (update state :way #(map - % [v 0]))
                         \L (assoc  state :way (case v
                                                 90 [(- y) x]
                                                 180 [(- x) (- y)]
                                                 270 [y (- x)]))
                         \R (assoc  state :way (case v
                                                 270 [(- y) x]
                                                 180 [(- x) (- y)]
                                                 90 [y (- x)]))
                         \F (update state :loc #(map + % (map * way [v v]))))))
                   {:loc [0 0] :way [10 1]}
                   input)]
  (map f [ans1 ans2]))
;; (1645 35292)


;; 202013
(let [gcd (fn [a b] (if (= 0 b) a (recur b (mod a b))))
      lcm (fn [a b] (/ (* a b) (gcd a b)))
      f (fn [n [_ s]]
          (if s (let [x (edn/read-string s)] [x (mod (- (* x (quot n x)) n) x)])))
      [timestamp & buses1] (->> (slurp "src/y2020/input202013") (re-seq #"\d+") (map edn/read-string))
      buses2 (->> (slurp "src/y2020/input202013")
                  (re-seq #"(\d+)|x")
                  rest
                  (keep-indexed f))]
  [(->> (map #(vector (- % (mod timestamp %)) %) buses1) sort first (reduce *))
   ((reduce (fn [[factor1 t] [factor2 remainder2]]
              (loop [t t]
                (if (= (mod t factor2) remainder2)
                  [(lcm factor1 factor2) t]
                  (recur (+ t factor1))))) buses2) 1)])
;; [2935 836024966345345]


;; 202014
(let [input (->> (slurp "src/y2020/input202014") (re-seq #"(?:mask = (\w+))|(?:(\d+)\] = (\d+))"))
      power-of-2 (vec (take 36 (iterate #(* 2 %) 1)))  ;; [1 2 4 ... 2^35]
      f (fn [{:keys [mask mem] :as state} [_ bitmask mem-address v]]
          (if bitmask
            (assoc state :mask [(edn/read-string (str "2r" (str/replace bitmask "X" "0")))
                                (edn/read-string (str "2r" (str/escape bitmask {\1 \0, \X \1})))])
            (let [mem-address (edn/read-string mem-address)
                  pre-value (edn/read-string v)
                  post-value (bit-or (mask 0) (bit-and (mask 1) pre-value))]
              (assoc-in state [:mem mem-address] post-value))))
      g (fn [{:keys [mask mem] :as state} [_ bitmask mem-address v]]
          (if bitmask
            (assoc state :mask [;; turn on  0 bits
                                (edn/read-string (str "2r" (-> bitmask (str/escape {\1 \0, \X \0, \0 \1}))))
                                ;; turn on  1 bits
                                (edn/read-string (str "2r" (-> bitmask (str/replace "X" "0"))))
                                ;; turn off X bits
                                (edn/read-string (str "2r" (-> bitmask (str/escape {\0 \1, \X \0}))))
                                ;; bit-offset of X bits
                                (keep-indexed (fn [i x] (if (= x \X) (- 35 i))) bitmask)])
            (let [mem-address (edn/read-string mem-address)
                  value (edn/read-string v)
                  base-mem-address (bit-or (bit-and (mask 0) (bit-and (mask 2) mem-address))
                                           (bit-or  (mask 1) (bit-and (mask 2) mem-address)))]
              (->> (map power-of-2 (mask 3))
                   (reduce (fn [base offset] (mapcat #(vector % (+ % offset)) base)) [0])
                   (map (fn [offset] [(+ base-mem-address offset) value]))
                   (update state :mem into)))))]
  (map #(->> input (reduce % {:mem {}}) :mem vals (reduce +)) [f g]))
;; (17765746710228 4401465949086)


;; 202015
(let [input (->> (slurp "src/y2020/input202015") (re-seq #"\d+") (map edn/read-string))
      pos (reduce #(-> (update % :cnt inc)
                       (update %2 (fn [x] (if (nil? x) (list (:cnt %)) (take 2 (cons (:cnt %) x))))))
                  {:cnt 1}
                  input)
      f (fn [{:keys [pos n r]}]
          (let [x (if (and (pos r) (= 1 (count (pos r)))) 0 (reduce - (pos r)))
                n (inc n)]
            {:pos (update pos x #(if (nil? %) (list n) (take 2 (cons n %)))) :n n :r x}))
      g (fn [n]
          (->> {:pos pos :r (last input) :n (count input)}
               (iterate f)
               (drop (- n (count input)))
               first
               :r))]
  (mapv g [2020 30000000]))
;; [614 1065]


;; 202016
(let [parse
      (fn [{:keys [mode] :as state} line]
        (cond (re-seq #"your" line) (assoc state :mode :your)
              (re-seq #"nearby" line) (assoc state :mode :nearby)
              (= mode :fields) (let [[_ field-name n1 n2 n3 n4]
                                     (re-matches #"(.*): (\d+)-(\d+) or (\d+)-(\d+)" line)
                                     [n1 n2 n3 n4] (map edn/read-string [n1 n2 n3 n4])
                                     x [field-name (into #{} (concat (range n1 (inc n2)) (range n3 (inc n4))))]]
                                 (update state :fields conj x))
              (= mode :your)  (->> (re-seq #"\d+" line) (mapv edn/read-string) (assoc state :your))
              (= mode :nearby) (->> (re-seq #"\d+" line) (map edn/read-string) (update state :nearby conj))))
      f (fn [{:keys [fields nearby]}]
          (let [all-fields-set (reduce clojure.set/union (vals fields))]
            (->> (flatten nearby)
                 (remove all-fields-set)
                 (reduce +))))
      g (fn [{:keys [fields your nearby]}]
          (let [all-fields-set (reduce clojure.set/union (vals fields))
                valid-nearby (filter #(every? all-fields-set %) nearby)
                field-samples (apply map vector valid-nearby)]
            (loop [pending-nearby (mapcat (fn [[field range-set]]
                                            (map-indexed #(vector field % (every? range-set %2))
                                                         field-samples)) fields)
                   mapping {}]
              (if (seq pending-nearby)
                (let [new-mapping (into mapping
                                        (keep #(let [v (val %)]
                                                 (if (= 1 ((frequencies (flatten v)) true))
                                                   (->> v
                                                        (keep (fn [x] (if (= true (nth x 2)) [(x 0) (x 1)])))
                                                        first)))
                                              (group-by first pending-nearby)))
                      new-pending (remove #((set (vals new-mapping)) (% 1)) pending-nearby)]
                  (recur new-pending new-mapping))
                (reduce * (keep #(if (re-seq #"departure" (key %)) (your (val %))) mapping))))))
      input (->> (str/split (slurp "src/y2020/input202016") #"\n+")
                 (reduce parse {:fields {}, :your nil, :nearby [], :mode :fields}))]
  [(f input) (g input)])
;; [25895 5865723727753]


;; 202017
(let [input (slurp "src/y2020/input202017")
      input1 (str/split-lines input)
      max-x (count (first input1))
      cube3-map (->> (re-seq #"." input)
                     (keep-indexed (fn [i cell]
                                     (if (= cell "#")
                                       [(mod i max-x) (quot i max-x) 0]))))
      cube4-map (->> (re-seq #"." input)
                     (keep-indexed (fn [i cell]
                                     (if (= cell "#")
                                       [(mod i max-x) (quot i max-x) 0 0]))))
      offsets3 (for [x [-1 0 1], y [-1 0 1], z [-1 0 1] :when (not= 0 x y z)] [x y z])
      offsets4 (for [x [-1 0 1], y [-1 0 1], z [-1 0 1], w [-1 0 1] :when (not= 0 x y z w)] [x y z w])
      neighbor3 (fn [pos] (map #(map + pos %) offsets3))
      neighbor4 (fn [pos] (map #(map + pos %) offsets4))
      f (fn [neighbor-fn]
          (fn [s]
            (let [neighbors (->> (mapcat neighbor-fn s) frequencies)]
              (->> (keys neighbors)
                   (filter #(or (and (s %) (= 2 (neighbors %))) (= 3 (neighbors %))))
                   set))))]
  [(->> (set cube3-map) (iterate (f neighbor3)) (drop 6) first count)
   (->> (set cube4-map) (iterate (f neighbor4)) (drop 6) first count)])
;; [295 1972]


;; 202018
(let [input (->> (slurp "src/y2020/input202018") str/split-lines (map #(edn/read-string (str "(" % ")"))))
      f (fn f [xs]
          (let [new-xs (map #(if (list? %) (f %) %) xs)]
            (reduce (fn [r [op op1]] ((resolve op) r op1)) (first new-xs) (partition 2 (rest new-xs)))))
      g (fn g [xs]
          (->> (map #(if (list? %) (g %) %) xs)
               (partition-by #{'*})
               (remove #{'(*)})
               (map #(reduce + (remove #{'+} %)))
               (reduce *)))]
  (map #(reduce + (map % input)) [f g]))
;; (280014646144 9966990988262)


;; 202021
(let [input (->> (slurp "src/y2020/input202021")
                 (re-seq #"[^\n]+")
                 (map #(let [[ingredients _ allergens] (->> (re-seq #"\w+" %) (partition-by #{"contains"}))]
                         [(set ingredients) (set allergens)])))
      all-ingredients (reduce clojure.set/union (map first input))
      all-allergens (reduce clojure.set/union (map second input))
      possible-allergen-ingredient-mapping
      (for [allergen all-allergens]
        [allergen (reduce clojure.set/intersection (keep #(if ((second %) allergen) (first %)) input))])
      ingredients-with-allergen (reduce clojure.set/union (map second possible-allergen-ingredient-mapping))
      q1 (reduce + (map #(count (clojure.set/difference (first %) ingredients-with-allergen)) input))
      q2 (loop [possible-allergen-ingredient-mapping possible-allergen-ingredient-mapping
                allergen-ingredient-mapping {}]
           (if (seq possible-allergen-ingredient-mapping)
             (let [found-mapping (keep (fn [[allergen ingredients]]
                                         (if (= 1 (count ingredients)) [allergen (first ingredients)]))
                                       possible-allergen-ingredient-mapping)
                   found-ingredients (set (map second found-mapping))
                   new-possible-allergen-ingredient-mapping
                   (keep (fn [[allergen ingredients]]
                           (let [new-ingredients (clojure.set/difference ingredients found-ingredients)]
                             (if (seq new-ingredients)
                               [allergen new-ingredients])))
                         possible-allergen-ingredient-mapping)]
               (recur new-possible-allergen-ingredient-mapping
                      (into allergen-ingredient-mapping found-mapping)))
             (->> (sort allergen-ingredient-mapping) (map second) (str/join ","))))]
  [q1 q2])
;; [1679 "lmxt,rggkbpj,mxf,gpxmf,nmtzlj,dlkxsxg,fvqg,dxzq"]


;; 202022
(let [[p1 p2] (->> (str/split (slurp "src/y2020/input202022") #"\n\n")
                   (map #(into clojure.lang.PersistentQueue/EMPTY
                               (rest (map edn/read-string (re-seq #"\d+" %))))))
      score #(reduce + (map * % (range (count %) 0 -1)))
      q1 (loop [p1 p1, p2 p2]
           (let [head1 (peek p1)
                 head2 (peek p2)]
             (cond
               (nil? head1) p2
               (nil? head2) p1
               :else (cond (< head1 head2) (recur (pop p1) (conj (pop p2) head2 head1))
                           :else           (recur (conj (pop p1) head1 head2) (pop p2))))))
      q2 (((fn g [p1 p2]
             (loop [p1 p1, p2 p2, seen #{}]
               (let [head1 (peek p1)
                     head2 (peek p2)
                     p1' (pop p1)
                     p2' (pop p2)]
                 (cond
                   (seen [(seq p1) (seq p2)]) [:p1 p1]
                   (nil? head1) [:p2 p2]
                   (nil? head2) [:p1 p1]
                   (and (< head1 (count p1)) (< head2 (count p2)))
                   (let [[winner _] (g (into clojure.lang.PersistentQueue/EMPTY (take head1 p1'))
                                       (into clojure.lang.PersistentQueue/EMPTY (take head2 p2')))]
                     (cond (= :p2 winner)
                           (recur p1' (conj p2' head2 head1) (conj seen [(seq p1) (seq p2)]))
                           :else
                           (recur (conj p1' head1 head2) p2' (conj seen [(seq p1) (seq p2)]))))
                   :else (cond (< head1 head2)
                               (recur p1' (conj p2' head2 head1) (conj seen [(seq p1) (seq p2)]))
                               :else
                               (recur (conj p1' head1 head2) p2' (conj seen [(seq p1) (seq p2)])))))))
           p1 p2) 1)]
  (map score [q1 q2]))
;; (32815 30695)