Clojure

After ages and ages, I finally got into a new language. On the pretext of preparing for a brown bag session with the team, I started reading about Clojure and all of its benefits. The brown bag went off decently enough – I re-used Rich Hickey’s slides and talked about functional programming, Java inter-op and mainly the concurrency mechanisms. While preparing, I copy-pasted several bits of code, ran them etc and started getting a feel for the language. But the penny really dropped at the very end of the session when I was asked to write a simple hello world…and couldn’t! I later found (def hello (fn [] “Hello world”)) on the clojure website and promptly sent it off to the guys

Since I wasn’t totally put off by the language and even somewhat impressed by it, I decided I needed to do some hands-on development to learn the intricacies of the language. To begin with, I stayed away from all the concurrency constructs and picked a problem to try and tackle the functional elements – a sudoku problem solver. Its most likely not the most efficient algorithm though I might try to parallelize it.

• My “grid” is actually just a vector of 81 elements.
• Rows, columns and sub-grids are views of the appropriate indices on the vector.
• setup-grid sets up the problem.
• solve uses brute-force in a depth-first manner to solve the puzzle.

Having written no automated tests (lots of manual testing via the REPL while writing the code only), I tested it out with two examples from websudoku. The first was the “easy level” and took 98.684439 msecs whereas the “evil level” took 1139.137917 msecs. Here are the two examples:

Easy

3 - 8 2 9 1 - - -
1 7 9 - - - 2 6 -
- - - - - 6 1 - -
8 - 5 1 - - 6 - -
- - - 6 3 9 - - -
- - 6 - - 8 3 - 2
- - 1 5 - - - - -
- 5 4 - - - 8 1 7
- - - 8 1 7 4 - 6

Evil

- - 2 - - - - - 6
5 4 - 9 - - 2 - -
- - - 8 2 - - - -
- 5 - - - - 7 - -
- - 4 7 1 6 5 - -
- - 1 - - - - 8 -
- - - - 9 2 - - -
- - 9 - - 7 - 4 8
4 - - - - - 1 - -

And if you are interested, the code: (and yes, I know there are a lot of brackets)

(def size 9)
(def sqrt (Math/sqrt size))
(def values
  (loop [c 1 v (set [])]
    (if (> c size)
      v
      (recur (inc c) (conj v (str c))))))

(defn index [x y]
  (+ (* x size) y))

(defn place [grid x y]
  (-> grid (nth (index x y))))

(defn assign [grid x y val]
  (assoc grid (index x y) (str val)))

(defn setup-base-grid []
  (vec (take (* size size) (cycle [nil]))))

(defn setup-grid [init-setup]
  (loop [grid (setup-base-grid) ks (keys init-setup) vs (vals init-setup)]
    (if (and ks vs)
      (recur (assign grid ((first ks) 0) ((first ks) 1) (first vs)) (next ks) (next vs))
      grid)))

(defn row [grid x]
  (let
    [start (* x size)
     end (+ start size)]
    (subvec grid start end)))

(defn col [grid y]
  (loop [c 0 v []]
    (if (>= c size)
      v
      (recur (inc c) (conj v (place grid c y))))))
(defn sub-grid [grid x y]
  (let
    [startx (* x sqrt)
     endx (+ startx sqrt)
     starty (* y sqrt)
     endy (+ starty sqrt)]
    (loop [c startx v []]
      (if (>= c endx)
        (vec v)
        (recur (inc c) (concat v (subvec (row grid c) starty endy)))))))

(defn pretty-print [grid]
  (loop [c 0 out ""]
    (if (>= c size)
      (println (.replace (.replace (.replace out "nil" "-") "[" "") "]" ""))
      (recur (inc c) (str out (println-str (row grid c)))))))

(defn missing [section]
  (clojure.set/difference values (set section)))

(defn solve
  ([grid] (solve grid 0))
  ([grid counter]
      (if (>= counter (* size size))
        grid
        (if (grid counter)
          (solve grid (inc counter))
          (let
            [row-number (quot counter size)
             col-number (rem counter size)
             sub-grid-number [(quot row-number sqrt) (quot col-number sqrt)]]
           (loop [possibles (seq (missing (clojure.set/union (row grid row-number) (col grid col-number) (sub-grid grid (sub-grid-number 0) (sub-grid-number 1)))))]
             (if (nil? (first possibles))
               nil
               (let [possible-grid (solve (assign grid row-number col-number (first possibles)) (inc counter))]
                 (if (nil? possible-grid)
                   (recur (next possibles))
                   possible-grid)))))))))

Advertisement