]> localhost Git - adventofcode2019.git/blob - src/adventofcode2019/day18.clj
Add broken day16pt2
[adventofcode2019.git] / src / adventofcode2019 / day18.clj
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)))