numbers test - first attempt

gistfile1.clj

; start a repl (lein repl) then paste in the following:

(defn calculate-all [input]
  (defn calculate-item [idx item]
    (let [split (split-at idx input)
          actual-before (set (first split))
          needed-before (set (range 1 item))]
      (clojure.set/superset? actual-before needed-before)))
  (map-indexed calculate-item input))

(calculate-all '(2 1 3 5 4))

(calculate-all '(2 1 3 5 4 8 7 6))

(calculate-all (shuffle (range 1 50)))

(calculate-all (shuffle (range 1 500)))

; this gets slows with a big range (1000 +)







(ns codility-clj.core-test
  (:require [clojure.test :refer :all]
            [codility-clj.core :refer :all]
            [clojure.pprint :refer [pprint]]))

; approach one - basic approach using sets and creating new sets with all items
(defn calculate-all [input]

  (defn calculate-item [idx item]
    (let [split (split-at idx input)
          actual-before (set (first split))
          needed-before (set (range 1 item))]
      (clojure.set/superset? actual-before needed-before)))

  (map-indexed calculate-item input))

(deftest approach-one
  (testing "test case one"
    (let [input '(2 1 3 5 4)
          output (calculate-all input)]
      (is (= '(false true true false true) output))))

  (testing "test case two"
    (let [input '(2 1 3 5 4 8 7 6)
          output (calculate-all input)]
      (is (= '(false true true false true false false true) output)))))

;approach two - uses similar algorithm to quick-find 
; updates all connected nodes (to right) when adding a node - this is slower than attempt one

(def nodes (atom {}))

(defn values-not-nil? [x y]
  (and (not (nil? x)) (not (nil? y))))

(defn connected? [x y] 
  (let [n @nodes 
        xv (get n x) 
        yv (get n y)] 
    (and (values-not-nil? xv yv) (= xv yv))))

(defn connect! [x y]
  (let [n @nodes 
        xv (get n x) 
        yv (get n y)]
    (when (values-not-nil? xv yv)
      (swap! nodes assoc x yv))))

(defn connect-to-previous! [x]
  (connect! x (- x 1)))

(defn connect-to-nodes-on-right! [x]
  (let [n @nodes
        value-of-next-node (get n (+ x 1))
        new-val-of-x (get n x)
        entries-to-update (select-keys n (for [[k v] n :when (= v value-of-next-node)] k))]
    (doseq [k (keys entries-to-update)]
      (swap! nodes assoc k new-val-of-x))))

(defn add-node-to-map! [x]
  (swap! nodes assoc x x))

(defn add-node! [x]
  (add-node-to-map! x)  
  (connect-to-previous! x)
  (connect-to-nodes-on-right! x)
  (connected? 1 x))

(deftest approach-two
  (testing "add a node"
    (reset! nodes {})
    (add-node! 2)
    (is (= @nodes {2 2})))

  (testing "connect nodes"
    (reset! nodes {1 1, 2 2})
    (connect! 1 2)
    (is (= @nodes {1 2, 2 2})))

  (testing "only connect to nodes that exist"
    (reset! nodes {1 1, 2 2})
    (connect! 2 1)
    (connect! 2 3)
    (is (= @nodes {1 1, 2 1})))

  (testing "connected? returns false when not connection exists"
    (reset! nodes {1 1 2 2})
    (is (= false (connected? 1 2))))

  (testing "connected? returns true when nodes connected"
    (reset! nodes {1 2, 2 2})
    (is (= true (connected? 1 2))))

  (testing "node connects to previous node when added"
    (reset! nodes {})
    (add-node! 1)
    (add-node! 2)
    (is (= @nodes {1 1, 2 1})))

  (testing "node connects to both previous and next node when added"
    (reset! nodes {})
    (add-node! 1)
    (add-node! 3)
    (is (= @nodes {1 1, 3 3}))
    (add-node! 2)
    (is (= @nodes {2 1, 1 1, 3 1})))

  (testing "nodes to the right are all changed to match"
    (reset! nodes {})
    (add-node! 1)
    (add-node! 3)
    (add-node! 4)
    (is (= @nodes {1 1, 3 3, 4 3}))
    (add-node! 2)
    (is (= @nodes {2 1, 1 1, 3 1, 4 1})))

  (testing "add returns connected state"
    (reset! nodes {})
    
    (is (= false (add-node! 2)))
    (is (= true (add-node! 1)))
    (is (= true (add-node! 3)))
    (is (= false (add-node! 5)))
    (is (= true (add-node! 4)))))




; approach three - using quick union algorithm
; this one connects the roots of the nodes so has far less to update, results in more steps
; when finding but far less writes than approach two


(defn find-root [i] 
  (let [v (get @nodes i)] 
    (loop [i v]
      (if (= i v) 
        v 
        (recur v)))))

(defn connect-roots! [x y]
  (let [root-x (find-root x)
        root-y (find-root y)]
    (connect! root-x root-y)))

(defn roots-connected? [x y]
  (let [root-x (find-root x)
        root-y (find-root y)]
    (connected? root-x root-y)))

(defn add-node3! [x]
  (add-node-to-map! x)
  (connect-to-previous! x)
  (connect-roots! x (- x 1))
  (connect-roots! x (+ x 1))
  (roots-connected? 1 x))

; (defn pprint-nodes [] 
;   (pprint (sort-by key < @nodes)))


(defn tidy-output [x]
  (let [output (clojure.string/replace x "\"Elapsed time: " "")
        output (clojure.string/replace output " msecs\"\n" "")]
    (Double/parseDouble output)))

(deftest approach-three
  (testing "add a node"
    (reset! nodes { 0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6, 7 7, 8 8, 9 9 })
    (connect-roots! 4 3)
    (is (= @nodes { 0 0, 1 1, 2 2, 3 3, 4 3, 5 5, 6 6, 7 7, 8 8, 9 9 }))

    (connect-roots! 3 8)
    (is (= @nodes { 0 0, 1 1, 2 2, 3 8, 4 3, 5 5, 6 6, 7 7, 8 8, 9 9 }))

    (connect-roots! 6 5)
    (is (= @nodes { 0 0, 1 1, 2 2, 3 8, 4 3, 5 5, 6 5, 7 7, 8 8, 9 9 }))

    (is (= false (roots-connected? 9 4)))

    (connect-roots! 9 4)
    (is (= @nodes { 0 0, 1 1, 2 2, 3 8, 4 3, 5 5, 6 5, 7 7, 8 8, 9 8 }))

    (is (= true (roots-connected? 9 4))))

  (testing "connect on add"
    (reset! nodes {})
    (is (= false (add-node3! 2)))
    (is (= true (add-node3! 1)))
    (is (= true (add-node3! 3)))
    (is (= false (add-node3! 5)))
    (is (= true (add-node3! 4))))

  (defn time-for-entries [num-entries]
    (tidy-output (with-out-str (time (doall (for [x (shuffle (range 1 num-entries))] (add-node3! x)))))))

  (testing "with 500 entries"
    (let [time-taken (time-for-entries 500)]
      (println "time for 400 in milliseconds = " time-taken)
      (is (< time-taken 1000))))

  (testing "with 5000 entries"
    (let [time-taken (time-for-entries 5000)]
      (println "time for 5000 in milliseconds = " time-taken)
      (is (< time-taken 1000))))

  (testing "with 50000 entries"
    (let [time-taken (time-for-entries 50000)]
      (println "time for 50000 in milliseconds = " time-taken)
      (is (< time-taken 1000))))

  (testing "with 500,000 entries"
    (let [time-taken (time-for-entries 500000)]
      (println "time for 500,000 in milliseconds = " time-taken)
      (is (< time-taken 2000))))

  ; took 20 seconds
  ; (testing "with 5,000,000 entries"
  ;   (let [time-taken (time-for-entries 5000000)]
  ;     (println "time for 5,000,000 in milliseconds = " time-taken)
  ;     (is (< time-taken 5000))))

  )