From c999ec812427df83f4e7c22b00b1abd8c04ef310 Mon Sep 17 00:00:00 2001
From: Clyne Sullivan <clyne@bitgloo.com>
Date: Sun, 12 Dec 2021 19:10:39 -0500
Subject: day12: fast, parallel part 2
---
day12/part2.clj | 98 +++++++++++++++++++++++++++++----------------------------
1 file changed, 50 insertions(+), 48 deletions(-)
diff --git a/day12/part2.clj b/day12/part2.clj
index 0be59b7..06b2bcd 100644
--- a/day12/part2.clj
+++ b/day12/part2.clj
@@ -1,48 +1,50 @@
- (require '[clojure.string :as str])
-
- ; Build list of cave connections:
- (def caves (->> (slurp "./in")
- (str/split-lines)
- (map #(str/split % #"-"))
- (map (partial map str))
- (#(concat % (map reverse %)))
- ))
-
- ; Try to help execution speed by memoizing cave searches:
- (def search-caves
- (memoize (fn [id]
- (filter #(= (first %) id) caves))))
-
- ; Given current path 'path', return a list of valid paths that branch
- ; from 'path'. Note, paths are stored in reverse order.
- (defn get-caves-forward [path]
- (map #(cons (second %) path)
- (filter
- (fn [cv]
- (and
- ; Do not return to start
- (not (str/starts-with? (second cv) "start"))
- (or
- ; Always allow uppercase paths
- (< (int (first (second cv))) 96)
- (let [lw (filter #(= (str/lower-case %) %) path)]
- (or
- ; Allow lowercase paths that have never been visited
- (= 0 (count (filter #(= % (second cv)) path)))
- ; Allow one duplicate if there are none yet
- (= 0 (- (count lw) (count (distinct lw)))))))))
- ; Only work with paths that we connect to
- (search-caves (first path))
- )))
-
- (loop [paths (get-caves-forward ["start"]) complete-paths []]
- (let [branches (->> paths
- (map get-caves-forward)
- (apply concat))
- complete-branches (concat complete-paths
- (filter #(= (first %) "end") branches))
- next-paths (filter #(not= (first %) "end") branches)]
- (if (empty? next-paths)
- (println (count complete-branches))
- (recur next-paths complete-branches))))
-
+(require '[clojure.string :as str])
+(require '[clojure.core.reducers :as r])
+
+; Build list of cave connections:
+(def caves (->> (slurp "./in")
+ (str/split-lines)
+ (map #(str/split % #"-"))
+ (map (partial map str))
+ (#(concat % (map reverse %)))
+ ))
+
+; Try to help execution speed by memoizing cave searches:
+(def search-caves
+ (memoize (fn [id]
+ (filter
+ #(and (= (first %) id)
+ (not (str/starts-with? (second %) "start")))
+ caves
+ ))))
+
+; Given current path 'path', return a list of valid paths that branch
+; from 'path'. Note, paths are stored in reverse order.
+(defn get-caves-forward [path]
+ (r/map #(cons (second %) path)
+ (r/filter
+ (fn [cv]
+ (or
+ ; Always allow uppercase paths
+ (< (int (first (second cv))) 96)
+ ; Or, allow lowercase paths that have never been visited
+ (not-any? #(= % (second cv)) path)
+ ; Or, allow one duplicate if there are none yet
+ (apply distinct? (filter #(= (str/lower-case %) %) path))))
+ ; Only work with paths that we connect to
+ (search-caves (first path))
+ )))
+
+(loop [paths (into [] (get-caves-forward ["start"])) complete-paths 0]
+ (let [results (->> paths
+ (r/mapcat get-caves-forward)
+ (r/foldcat)
+ (r/reduce
+ (fn [r b] (if (not= (first b) "end")
+ (update r :next-paths #(conj % b))
+ (update r :complete-counts inc)))
+ {:next-paths [] :complete-counts complete-paths}))]
+ (println (results :complete-counts))
+ (when-not (empty? (results :next-paths))
+ (recur (results :next-paths) (results :complete-counts)))))
+
--
cgit v1.2.3