| 1 | (ns adventofcode2019.day18 |
| 2 | [:require [adventofcode2019.lib :refer :all] |
| 3 | [adventofcode2019.intcode :as i] |
| 4 | [clojure.string :as str] |
| 5 | [clojure.set :as set] |
| 6 | [clojure.core.match :refer [match]] |
| 7 | [clojure.math.combinatorics :as combo] |
| 8 | [clojure.data.priority-map :refer [priority-map-by]]]) |
| 9 | |
| 10 | (defn build-world [input] |
| 11 | (let [point-encode (->> input |
| 12 | (map-indexed |
| 13 | (fn [y xs] |
| 14 | (map-indexed |
| 15 | (fn [x c] |
| 16 | [c [x y]]) xs))) |
| 17 | (apply concat)) |
| 18 | passages (->> point-encode |
| 19 | (filter #(= \. (first %))) |
| 20 | (map second) |
| 21 | (set)) |
| 22 | interesting (->> point-encode |
| 23 | (filter #(and (not= \. (first %)) |
| 24 | (not= \# (first %)))) |
| 25 | (into {})) |
| 26 | dkeys (select-keys interesting (filter #(Character/isLowerCase %) |
| 27 | (keys interesting))) |
| 28 | doors (select-keys interesting (filter #(Character/isUpperCase %) |
| 29 | (keys interesting))) |
| 30 | player (interesting \@)] |
| 31 | {:p player |
| 32 | :t (apply conj passages player (vals dkeys)) |
| 33 | :k dkeys |
| 34 | :d doors})) |
| 35 | |
| 36 | (defn path-between [trav point-a point-b] |
| 37 | (let [succ (fn [sn [x y]] |
| 38 | (filter (every-pred trav (complement sn)) |
| 39 | [[(inc x) y] [(dec x) y] |
| 40 | [x (inc y)] [x (dec y)]])) |
| 41 | update-openl (fn [ol sn pt ds] |
| 42 | (reduce (fn [m p] |
| 43 | (assoc m p [ds (manhattan-distance p point-b)])) |
| 44 | ol (succ sn pt))) |
| 45 | openl (priority-map-by (fn [[ag ah] [bg bh]] |
| 46 | (compare (+ ag ah) (+ bg bh))))] |
| 47 | (loop [openl (assoc openl point-a |
| 48 | [0 (manhattan-distance point-a point-b)]) |
| 49 | seen #{point-a}] |
| 50 | (cond |
| 51 | (contains? openl point-b) (first (openl point-b)) |
| 52 | (empty? openl) ##Inf |
| 53 | :else (let [[point [dist _]] (peek openl) |
| 54 | seen (conj seen point)] |
| 55 | (recur (update-openl (pop openl) seen point (inc dist)) seen)))))) |
| 56 | |
| 57 | (defn accessible [{player :p dkeys :k trav :t}] |
| 58 | (->> dkeys |
| 59 | (mmap (partial path-between trav player)) |
| 60 | (remove #(= ##Inf (second %))) |
| 61 | (into {}))) |
| 62 | |
| 63 | (defn acquire-all-keys [world] |
| 64 | (if (empty? (world :k)) 0 |
| 65 | (let [accessible-keys (accessible world) |
| 66 | successor-world (fn [[kc ds]] |
| 67 | (let [kp (get-in world [:k kc]) |
| 68 | dc (Character/toUpperCase kc) |
| 69 | dp (get-in world [:d dc])] |
| 70 | [ds (-> world |
| 71 | (assoc :p kp) |
| 72 | (update :t conj dp) |
| 73 | (update-in [:k] dissoc kc))])) |
| 74 | successors (map successor-world accessible-keys) |
| 75 | combine-levels (fn [[ds wo]] (+ ds (acquire-all-keys wo))) |
| 76 | ret (reduce min (map combine-levels successors))] |
| 77 | (clojure.pprint/pprint world) |
| 78 | (clojure.pprint/pprint ret) |
| 79 | ret))) |
| 80 | |
| 81 | (defn day18 [] |
| 82 | (let [input (get-list-from-file (input-file)) |
| 83 | world (build-world input)] |
| 84 | (part1 (acquire-all-keys world)) |
| 85 | #_(part2))) |