:dependencies [[org.clojure/clojure "1.10.0"]
[org.clojure/core.match "0.3.0"]
[org.clojure/math.combinatorics "0.1.6"]
- [org.clojure/core.async "0.6.532"]]
+ [org.clojure/core.async "0.6.532"]
+ [org.clojure/data.priority-map "0.0.10"]]
:main ^:skip-aot adventofcode2019.core
:target-path "target/%s"
:profiles {:uberjar {:aot :all}})
[:require (adventofcode2019 day01 day02 day03 day04 day05
day06 day07 day08 day09 day10
day11 day12 day13 day14
- day16)])
+ day16 day18)])
(defn -main
([]
--- /dev/null
+(ns adventofcode2019.day18
+ [:require [adventofcode2019.lib :refer :all]
+ [adventofcode2019.intcode :as i]
+ [clojure.string :as str]
+ [clojure.set :as set]
+ [clojure.core.match :refer [match]]
+ [clojure.math.combinatorics :as combo]
+ [clojure.data.priority-map :refer [priority-map-by]]])
+
+(defn build-world [input]
+ (let [point-encode (->> input
+ (map-indexed
+ (fn [y xs]
+ (map-indexed
+ (fn [x c]
+ [c [x y]]) xs)))
+ (apply concat))
+ passages (->> point-encode
+ (filter #(= \. (first %)))
+ (map second)
+ (set))
+ interesting (->> point-encode
+ (filter #(and (not= \. (first %))
+ (not= \# (first %))))
+ (into {}))
+ dkeys (select-keys interesting (filter #(Character/isLowerCase %)
+ (keys interesting)))
+ doors (select-keys interesting (filter #(Character/isUpperCase %)
+ (keys interesting)))
+ player (interesting \@)]
+ {:p player
+ :t (apply conj passages player (vals dkeys))
+ :k dkeys
+ :d doors}))
+
+(defn path-between [trav point-a point-b]
+ (let [succ (fn [sn [x y]]
+ (filter (every-pred trav (complement sn))
+ [[(inc x) y] [(dec x) y]
+ [x (inc y)] [x (dec y)]]))
+ update-openl (fn [ol sn pt ds]
+ (reduce (fn [m p]
+ (assoc m p [ds (manhattan-distance p point-b)]))
+ ol (succ sn pt)))
+ openl (priority-map-by (fn [[ag ah] [bg bh]]
+ (compare (+ ag ah) (+ bg bh))))]
+ (loop [openl (assoc openl point-a
+ [0 (manhattan-distance point-a point-b)])
+ seen #{point-a}]
+ (cond
+ (contains? openl point-b) (first (openl point-b))
+ (empty? openl) ##Inf
+ :else (let [[point [dist _]] (peek openl)
+ seen (conj seen point)]
+ (recur (update-openl (pop openl) seen point (inc dist)) seen))))))
+
+(defn accessible [{player :p dkeys :k trav :t}]
+ (->> dkeys
+ (mmap (partial path-between trav player))
+ (remove #(= ##Inf (second %)))
+ (into {})))
+
+(defn acquire-all-keys [world]
+ (if (empty? (world :k)) 0
+ (let [accessible-keys (accessible world)
+ successor-world (fn [[kc ds]]
+ (let [kp (get-in world [:k kc])
+ dc (Character/toUpperCase kc)
+ dp (get-in world [:d dc])]
+ [ds (-> world
+ (assoc :p kp)
+ (update :t conj dp)
+ (update-in [:k] dissoc kc))]))
+ successors (map successor-world accessible-keys)
+ combine-levels (fn [[ds wo]] (+ ds (acquire-all-keys wo)))
+ ret (reduce min (map combine-levels successors))]
+ (clojure.pprint/pprint world)
+ (clojure.pprint/pprint ret)
+ ret)))
+
+(defn day18 []
+ (let [input (get-list-from-file (input-file))
+ world (build-world input)]
+ (part1 (acquire-all-keys world))
+ #_(part2)))
(ns adventofcode2019.lib
- [:require [clojure.string :as str]
- [clojure.edn :as edn]
- [clojure.java.io :as io]
- [clojure.java.shell :refer [sh]]])
+ [:require [clojure.string :as str]
+ [clojure.edn :as edn]
+ [clojure.java.io :as io]
+ [clojure.java.shell :refer [sh]]])
(defn get-list-from-file
([file-name]
- (str/split-lines (str/trim (slurp file-name))))
+ (str/split-lines (str/trim (slurp file-name))))
([file-name split-regex]
- (str/split (str/trim (slurp file-name)) split-regex)))
+ (str/split (str/trim (slurp file-name)) split-regex)))
(defn parse-int [n]
(let [n-val (edn/read-string n)]
(if (number? n-val)
- n-val
- (throw (Exception. "Not a number!")))))
+ n-val
+ (throw (Exception. "Not a number!")))))
(defmacro input-file []
(let [bottom-ns (last (str/split (str *ns*) #"\."))]
(str "resources/" bottom-ns)))
-(defn manhattan-distance [[ax ay] [bx by]]
+(defn manhattan-distance [[ax ay] [bx by]]
(+ (Math/abs (- ax bx))
(Math/abs (- ay by))))
(defn mmap [f m]
- (reduce-kv #(assoc %1 %2 (f %3)) {} m))
+ (zipmap (keys m) (map f (vals m))))
-(def part1
+(def part1
#(println (str "Part 1: " %)))
-(def part2
+(def part2
#(println (str "Part 2: " %)))
;; FIXME: this is still broken but i give up for now
--- /dev/null
+(ns adventofcode2019.day18-test
+ (:require [clojure.test :refer :all]
+ [adventofcode2019.day18 :refer :all]))
+
+(deftest test-build-world
+ (is (= {:p [5 1]
+ :t #{[1 1] [2 1] [4 1] [5 1] [6 1] [7 1]}
+ :k {\a [7 1], \b [1 1]}
+ :d {\A [3 1]}}
+ (build-world ["#########"
+ "#b.A.@.a#"
+ "#########"]))))
+
+(deftest test-pathing
+ (is (= 2 (path-between ((build-world ["#########"
+ "#b.A.@.a#"
+ "#########"]) :t)
+ [5 1] [7 1]))))
+
+(deftest test-accessible
+ (is (= {\a 2}
+ (accessible (build-world ["#########"
+ "#b.A.@.a#"
+ "#########"])))))
+
+(deftest examples
+ (is (= 8 (acquire-all-keys (build-world ["#########"
+ "#b.A.@.a#"
+ "#########"]))))
+ (is (= 86 (acquire-all-keys (build-world ["########################"
+ "#f.D.E.e.C.b.A.@.a.B.c.#"
+ "######################.#"
+ "#d.....................#"
+ "########################"]))))
+ (is (= 132 (acquire-all-keys (build-world ["########################"
+ "#...............b.C.D.f#"
+ "#.######################"
+ "#.....@.a.B.c.d.A.e.F.g#"
+ "########################"]))))
+ #_(is (= 136 (acquire-all-keys (build-world ["#################"
+ "#i.G..c...e..H.p#"
+ "########.########"
+ "#j.A..b...f..D.o#"
+ "########@########"
+ "#k.E..a...g..B.n#"
+ "########.########"
+ "#l.F..d...h..C.m#"
+ "#################"]))))
+ (is (= 81 (acquire-all-keys (build-world ["########################"
+ "#@..............ac.GI.b#"
+ "###d#e#f################"
+ "###A#B#C################"
+ "###g#h#i################"
+ "########################"])))))
projects / adventofcode2019.git / commitdiff