From 7a710645a2234dcb568c2e971b5b0367217d0ea8 Mon Sep 17 00:00:00 2001 From: Jack Kinsey Date: Thu, 19 Dec 2019 17:00:36 -0500 Subject: [PATCH] Add broken day18pt1 --- project.clj | 3 +- src/adventofcode2019/core.clj | 2 +- src/adventofcode2019/day18.clj | 85 ++++++++++++++++++++++++++++ src/adventofcode2019/lib.clj | 24 ++++---- test/adventofcode2019/day18_test.clj | 54 ++++++++++++++++++ 5 files changed, 154 insertions(+), 14 deletions(-) create mode 100644 src/adventofcode2019/day18.clj create mode 100644 test/adventofcode2019/day18_test.clj diff --git a/project.clj b/project.clj index 6de5bc2..d498865 100644 --- a/project.clj +++ b/project.clj @@ -6,7 +6,8 @@ :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}}) diff --git a/src/adventofcode2019/core.clj b/src/adventofcode2019/core.clj index 6ab7f7c..3c17879 100644 --- a/src/adventofcode2019/core.clj +++ b/src/adventofcode2019/core.clj @@ -2,7 +2,7 @@ [:require (adventofcode2019 day01 day02 day03 day04 day05 day06 day07 day08 day09 day10 day11 day12 day13 day14 - day16)]) + day16 day18)]) (defn -main ([] diff --git a/src/adventofcode2019/day18.clj b/src/adventofcode2019/day18.clj new file mode 100644 index 0000000..cbe88c9 --- /dev/null +++ b/src/adventofcode2019/day18.clj @@ -0,0 +1,85 @@ +(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))) diff --git a/src/adventofcode2019/lib.clj b/src/adventofcode2019/lib.clj index 4b424a8..e81b306 100644 --- a/src/adventofcode2019/lib.clj +++ b/src/adventofcode2019/lib.clj @@ -1,35 +1,35 @@ (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 diff --git a/test/adventofcode2019/day18_test.clj b/test/adventofcode2019/day18_test.clj new file mode 100644 index 0000000..e962b49 --- /dev/null +++ b/test/adventofcode2019/day18_test.clj @@ -0,0 +1,54 @@ +(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################" + "########################"]))))) -- 2.38.5