fork download
copy 
  1. (ns challenge-0152.core
  2.   (:require [clojure.set :refer [union]]
  3.             [clojure.java.io :refer [reader]]
  4.             [clojure.string :refer [join]])
  5.   (:gen-class))
  6.  
  7. (defn make-letter-range [num]
  8.   (map char
  9.        (take num
  10.              (range (int \a)
  11.                     (inc (int \z))))))
  12.  
  13. (defn process-node [line letter-range]
  14.   (let [distances (re-seq #"[\d-]+" line)]
  15.     (loop [distance (first distances)
  16.            more-distances (next distances)
  17.            node2 (first letter-range)
  18.            more-nodes (next letter-range)
  19.            result {}]
  20.       (let [new-result (if (pos? (Integer. distance))
  21.                          (conj result {node2 (Integer. distance)})
  22.                          result)]
  23.         (if more-distances
  24.           (recur (first more-distances)
  25.                  (next more-distances)
  26.                  (first more-nodes)
  27.                  (next more-nodes)
  28.                  new-result)
  29.           new-result)))))
  30.  
  31. (defn make-graph [matrix]
  32.   (let [letter-range (make-letter-range (count matrix))]
  33.     (loop [line (first matrix)
  34.            more-lines (next matrix)
  35.            node1 (first letter-range)
  36.            more-nodes (next letter-range)
  37.            result {}]
  38.       (let [node-result {node1 (process-node line letter-range)}
  39.             new-result (conj result node-result)]
  40.         (if more-lines
  41.           (recur (first more-lines)
  42.                  (next more-lines)
  43.                  (first more-nodes)
  44.                  (rest more-nodes)
  45.                  new-result)
  46.           new-result)))))
  47.  
  48. (defn make-edge-map [map]
  49.   (loop [vertice (first map)
  50.          xs (next map)
  51.          processed #{}
  52.          result {}]
  53.     (let [new-edges (for [edge (val vertice)
  54.                           :when (not (contains? processed (key edge)))]
  55.                       [[(key vertice) (key edge)] (val edge)])]
  56.       (if xs
  57.         (recur (first xs)
  58.                (next xs)
  59.                (conj processed (key vertice))
  60.                (if (seq new-edges)
  61.                  (into result new-edges)
  62.                  result))
  63.         (reduce conj result new-edges)))))
  64.  
  65. (defn minimal-spanning-tree [graph]
  66.   (let [edge-map (make-edge-map graph)
  67.         sorted-edge-map (into (sorted-map-by (fn [k1 k2]
  68.                                                (compare [(edge-map k1) k1]
  69.                                                         [(edge-map k2) k2])))
  70.                               edge-map)]
  71.     (loop [sets (apply conj (for [node (make-letter-range (count graph))]
  72.                               {node #{node}}))
  73.            result {}
  74.            [[node1 node2] distance] (first sorted-edge-map)
  75.            xs (next sorted-edge-map)]
  76.       (if (= (sets node1) (sets node2))
  77.         (if xs
  78.           (recur sets result (first xs) (next xs))
  79.           result)
  80.         (let [new-result (conj result {(str node1 node2) distance})
  81.               nodes-union (union (sets node1) (sets node2))
  82.               new-sets (apply conj sets (for [node nodes-union]
  83.                                           {node nodes-union}))]
  84.           (if xs
  85.             (recur new-sets new-result (first xs) (next xs))
  86.             new-result))))))
  87.  
  88. (defn -main [& args]
  89.   (with-open [input (reader *in*)]
  90.     (let [mst (minimal-spanning-tree (make-graph (rest (line-seq input))))
  91.           distance (reduce #(+ %1 (val %2)) 0 mst)]
  92.       (println distance)
  93.       (println (join " " (keys mst))))))
  94.  
  95. (-main)
Success #stdin #stdout 1.74s 389120KB
comments ()
stdin
copy 
8
-1,11,9,6,-1,-1,-1,-1
11,-1,-1,5,7,-1,-1,-1
9,-1,-1,12,-1,6,-1,-1
6,5,12,-1,4,3,7,-1
-1,7,-1,4,-1,-1,2,-1
-1,-1,6,3,-1,-1,8,10
-1,-1,-1,7,2,8,-1,6
-1,-1,-1,-1,-1,10,6,-1
stdout
copy 
32
hg fc da db ed fd ge
https://ideone.com/RTEDTU
language:
Clojure (clojure 1.10.0)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!