Created
April 28, 2017 02:31
-
-
Save gja/7833c4e0c7b3130ffc7ce81a2b9dcfa5 to your computer and use it in GitHub Desktop.
Find the shortest path to a certain volume
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn- neighboring-edges [node capacity] | |
(for [i (range (count capacity)) | |
j (range (count capacity)) | |
:when (not= i j)] | |
(let [total-amount (+ (get node i) (get node j)) | |
amount-in-j (min total-amount (get capacity j)) | |
amount-in-i (- total-amount amount-in-j)] | |
{:node (assoc node i amount-in-i j amount-in-j) | |
:pour [i j]}))) | |
(defn- next-state [capacity {:keys [queue paths]}] | |
(when-let [node (first queue)] | |
(let [new-edges (remove #(contains? paths (:node %)) (neighboring-edges node capacity))] | |
{:queue (into (pop queue) (map :node new-edges)) | |
:paths (reduce #(assoc %1 (:node %2) (conj (paths node) %2)) paths new-edges)}))) | |
(defn find-way-to-fill-to-capacity [initial-state capacity desired] | |
(->> {:queue (conj clojure.lang.PersistentQueue/EMPTY initial-state) | |
:paths {initial-state [{:node initial-state :starting true}]}} | |
(iterate (partial next-state capacity)) | |
(take-while #(not-empty (:queue %))) | |
(some (fn [{:keys [queue paths]}] | |
(let [node (first queue)] | |
(when (some #(= desired %) node) | |
(paths node))))))) |
Author
gja
commented
Apr 28, 2017
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment