day19: complete, though slow

2 files changed, 158 insertions, 72 deletions

diff --git a/day19/part1.clj b/day19/part1.clj
deleted file mode 100644
index 25122da..0000000
--- a/day19/part1.clj
+++ /dev/null
@@ -1,72 +0,0 @@
-(require '[clojure.core.reducers :as r])
-(require 'clojure.string)
-
-(defn build-scanner-reports [input-lines]
-  (loop [scanners [] rem-input input-lines]
-    (if (empty? rem-input)
-      scanners
-      (let [[this nxt] (split-with (comp not empty?) rem-input)]
-        (recur
-          (->> (rest this)
-               (map #(read-string (clojure.string/join ["[" % "]"])))
-               (conj scanners))
-          (rest nxt))))))
-
-(defn all-orientations [[x y z]]
-  (map (fn [[i j k]] [(* x i) (* y j) (* z k)])
-       '([1 1 1] [-1 1 1] [1 -1 1] [-1 -1 1] [1 1 -1] [-1 1 -1] [1 -1 -1] [-1 -1 -1])))
-
-(defn group-orientations [lst]
-  (for [i (range 0 8)] (map #(nth % i) lst)))
-
-(defn scanner-orientations [scanner]
-  (group-orientations (map all-orientations scanner)))
-
-(defn add-coordinate [[a b c] [d e f]] [(+ a d) (+ b e) (+ c f)])
-
-(defn add-coordinate-lists [l1 l2]
-  (for [i (range 0 (count l1))]
-    (for [j (range 0 (count l2))]
-      (add-coordinate (nth l1 i) (nth l2 j)))))
-
-(defn compare-scanners [s1 s2]
-  (let [o1 [s1];(scanner-orientations s1)
-        o2 (scanner-orientations s2)]
-    (for [o o1 p o2]
-      (add-coordinate-lists o p))))
-
-(defn check-beacon-coord [scanner coord index]
-  (not (empty? (filter #(= coord %) (map #(nth % index) scanner)))))
-
-(defn beacon-coord-match? [req coord compared-scanners]
-  (let [cnt (count (first (first compared-scanners)))]
-    (< (dec req)
-       (reduce
-         (fn [tot n]
-           (cond-> tot
-             (and (< tot req)
-                  (reduce
-                    #(or %1 %2)
-                    (map #(check-beacon-coord % coord n) compared-scanners)))
-             inc))
-         0
-         (range 0 cnt)))))
-
-(->> (slurp "./in")
-     (clojure.string/split-lines)
-     (build-scanner-reports)
-     ((fn [scanners]
-       (for [s1i  (range 0 (count scanners))
-             s2   (drop (inc s1i) scanners)
-             :let [res (compare-scanners (nth scanners s1i) s2)]]
-         (let [cnt (count (first (first res)))]
-           (into '()
-             (r/fold
-               r/cat
-               (fn [final c]
-                 (cond-> final
-                         (beacon-coord-match? 4 c res)
-                         (r/append! c)))
-               (into [] (distinct (nth (iterate (partial reduce concat) res) 2)))))))))
-     (println))
-
diff --git a/day19/partboth.clj b/day19/partboth.clj
new file mode 100644
index 0000000..4de2c42
--- /dev/null
+++ b/day19/partboth.clj
@@ -0,0 +1,158 @@
+(require '[clojure.core.reducers :as r])
+(require 'clojure.string)
+
+(defn build-scanner-reports
+  "Splits slurped, split-lines'd input by scanner."
+  [input-lines]
+  (loop [scanners [] rem-input input-lines]
+    (if (empty? rem-input)
+      scanners
+      (let [[this nxt] (split-with (comp not empty?) rem-input)]
+        (recur
+          (->> (rest this)
+               (map #(read-string (clojure.string/join ["[" % "]"])))
+               (conj scanners))
+          (rest nxt))))))
+
+(defn point-add      [[a b c] [d e f]] [(+ a d) (+ b e) (+ c f)])
+
+(defn orient [[x y z] [[a b c] [d e f] [g h i]]]
+  [(+ (* x a) (* y d) (* z g)) (+ (* x b) (* y e) (* z h)) (+ (* x c) (* y f) (* z i))])
+
+(defn scanner-orientation [report or-index]
+  (let [or-vec [[[1 0 0]  [0 1 0]  [0 0 1]]
+                [[1 0 0]  [0 0 -1] [0 1 0]]
+                [[1 0 0]  [0 -1 0] [0 0 -1]]
+                [[1 0 0]  [0 0 1]  [0 -1 0]]
+                [[-1 0 0] [0 -1 0] [0 0 1]]
+                [[-1 0 0] [0 0 -1] [0 -1 0]]
+                [[-1 0 0] [0 1 0]  [0 0 -1]]
+                [[-1 0 0] [0 0 1]  [0 1 0]]
+                [[0 0 -1] [1 0 0]  [0 -1 0]]
+                [[0 1 0]  [1 0 0]  [0 0 -1]]
+                [[0 0 1]  [1 0 0]  [0 1 0]]
+                [[0 -1 0] [1 0 0]  [0 0 1]]
+                [[0 0 1]  [-1 0 0] [0 -1 0]]
+                [[0 1 0]  [-1 0 0] [0 0 1]]
+                [[0 0 -1] [-1 0 0] [0 1 0]]
+                [[0 -1 0] [-1 0 0] [0 0 -1]]
+                [[0 -1 0] [0 0 -1] [1 0 0]]
+                [[0 0 1]  [0 -1 0] [1 0 0]]
+                [[0 1 0]  [0 0 1]  [1 0 0]]
+                [[0 0 -1] [0 1 0]  [1 0 0]]
+                [[0 0 1]  [0 1 0]  [-1 0 0]]
+                [[0 -1 0] [0 0 1]  [-1 0 0]]
+                [[0 0 -1] [0 -1 0] [-1 0 0]]
+                [[0 1 0]  [0 0 -1] [-1 0 0]]]
+        chosen (get or-vec or-index)]
+    (map #(orient (map - %) chosen) report)))
+
+(defn scanner-orientations
+  "Builds list of scanner reports adjusted for all possible orientations."
+  [report]
+  (for [or-vec [[[1 0 0]  [0 1 0]  [0 0 1]]
+                [[1 0 0]  [0 0 -1] [0 1 0]]
+                [[1 0 0]  [0 -1 0] [0 0 -1]]
+                [[1 0 0]  [0 0 1]  [0 -1 0]]
+                [[-1 0 0] [0 -1 0] [0 0 1]]
+                [[-1 0 0] [0 0 -1] [0 -1 0]]
+                [[-1 0 0] [0 1 0]  [0 0 -1]]
+                [[-1 0 0] [0 0 1]  [0 1 0]]
+                [[0 0 -1] [1 0 0]  [0 -1 0]]
+                [[0 1 0]  [1 0 0]  [0 0 -1]]
+                [[0 0 1]  [1 0 0]  [0 1 0]]
+                [[0 -1 0] [1 0 0]  [0 0 1]]
+                [[0 0 1]  [-1 0 0] [0 -1 0]]
+                [[0 1 0]  [-1 0 0] [0 0 1]]
+                [[0 0 -1] [-1 0 0] [0 1 0]]
+                [[0 -1 0] [-1 0 0] [0 0 -1]]
+                [[0 -1 0] [0 0 -1] [1 0 0]]
+                [[0 0 1]  [0 -1 0] [1 0 0]]
+                [[0 1 0]  [0 0 1]  [1 0 0]]
+                [[0 0 -1] [0 1 0]  [1 0 0]]
+                [[0 0 1]  [0 1 0]  [-1 0 0]]
+                [[0 -1 0] [0 0 1]  [-1 0 0]]
+                [[0 0 -1] [0 -1 0] [-1 0 0]]
+                [[0 1 0]  [0 0 -1] [-1 0 0]]]]
+    (map #(orient (map - %) or-vec) report)))
+
+(defn scanner-build-potential-links
+  "Builds a list for each s2 orientation that contains lists of each s1 point
+   added to the corresponding s2 point."
+  [s1 s2]
+  (for [s2-or (scanner-orientations s2)]
+    (for [i (range 0 (count s1))]
+      (for [j (range 0 (count s2-or))]
+        (point-add (nth s1 i) (nth s2-or j))))))
+
+(defn scanner-find-connection
+  "Attempt to determine if s1 and s2 are linked through common beacons."
+  [s1 s2]
+  (let [potential-links (as-> (scanner-build-potential-links s1 s2) $
+                              (for [i (range 0 (count $))] [i (nth $ i)]))]
+    (filter some?
+      (map
+        (fn [[orientation link]]
+          (let [distinct-points (into [] (distinct (reduce concat link)))
+                link-results
+                (into '()
+                  (r/fold (quot (count distinct-points) 16) r/cat
+                    (fn [pcoll point]
+                      (if-not (empty? pcoll)
+                        pcoll
+                        (let [occurrance-count (reduce
+                                                 #(cond-> %1
+                                                    (not (empty? (filter (partial = point) %2)))
+                                                    inc)
+                                                 1 link)]
+                          (cond-> pcoll (> occurrance-count 11) (r/append! point)))))
+                    distinct-points))]
+            (when (not (empty? link-results))
+              [orientation (first link-results)])))
+        (into [] potential-links)))))
+
+(defn scanner-merge
+  "Merges the report of linked scanner s2 into scanner s1."
+  [s1 s2 s2-or s2-coord]
+  (let [s2-ored (scanner-orientation s2 s2-or)]
+    (distinct (concat s1 (map #(point-add s2-coord (map - %)) s2-ored)))))
+
+(def reports (->> (slurp "./in")
+                  (clojure.string/split-lines)
+                  (build-scanner-reports)
+                  (vec)))
+
+(let [[beacon-count scanner-coords]
+      (loop [new-reps reports sc-coords '([0 0 0]) i (range 1 (count reports))]
+        (println "Trying" (first i) (map count new-reps))
+        (if (nil? (first i))
+          ; reached end (uh oh?)
+          [(count new-reps) sc-coords]
+          ; scan for links to report i
+          (let [found (scanner-find-connection (first new-reps)
+                                               (get new-reps (first i)))]
+            (if (empty? found)
+              ; no match, move to next i
+              (recur new-reps sc-coords (rest i))
+              (do (println "  Found" found)
+              (recur
+                (-> new-reps
+                  ; replace index zero with merged report
+                  (assoc 0 (scanner-merge (first new-reps)
+                                          (get new-reps (first i))
+                                          (first (first found))
+                                          (second (first found))))
+                  ; remove report we pulled from
+                  (#(concat (subvec % 0 (first i))
+                            (subvec % (inc (first i)))))
+                  ; back to vector
+                  (vec))
+                (conj sc-coords (second (first found)))
+                ; begin new scan
+                (range 1 (count new-reps))))))))]
+  (println "Part 1:" beacon-count)
+  (println "Part 2:"
+    (apply max
+      (for [p1 scanner-coords p2 scanner-coords :when (not= p1 p2)]
+        (apply + (map #(Math/abs %) (point-add (map - p1) p2)))))))
+