Commit | Line | Data |
---|---|---|
7a710645 JK |
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))) |