Skip to content

Instantly share code, notes, and snippets.

@nyuichi
Created May 25, 2011 14:58
Show Gist options
  • Save nyuichi/991124 to your computer and use it in GitHub Desktop.
Save nyuichi/991124 to your computer and use it in GitHub Desktop.
Sisoku@Clojure with formatting
(use 'clojure.contrib.combinatorics)
; How to use
; (sisoku-solve [7 7 7 9 11 11] 218/100)
; (sisoku-solve [1 1 6 11 12 13] 314/100)
(defn drop-nth [n coll]
(concat (take n coll)
(drop (inc n) coll)))
(defn comb [n m]
(combinations (range n) m))
(def comb (memoize comb))
(defn choose-2 [coll n m]
(let [a (nth coll n)
b (nth coll m)
rest (drop-nth n (drop-nth m coll))]
[a b rest]))
(defn choose-2-in-order [coll]
(for [[a b] (comb (count coll) 2)]
(choose-2 coll a b)))
(defn single? [coll]
(empty? (rest coll)))
(defn insert [v coll]
(let [[head tail] (split-with #(< v %) coll)]
(concat head [v] tail)))
(defmacro forcat [seq-exprs body-expr]
`(apply concat (for ~seq-exprs ~body-expr)))
(defmacro go [op a b]
`(let [r# (~op ~a ~b)
n# (insert r# ~'coll)
s# (sisoku n# ~'answer)]
(if (empty? s#)
s#
(map #(conj % ~b ~a (str '~op)) s#))))
(defn sisoku
"Return a sequence of answers"
[seeds answer]
(if (single? seeds)
(if (= (first seeds) answer)
[seeds]
[])
(forcat [[a b coll] (choose-2-in-order seeds)]
(concat (go + a b)
(go - a b)
(go - b a)
(go * a b)
(when-not (zero? b)
(go / a b))
(when-not (zero? a)
(go / b a))))))
(def sisoku (memoize sisoku))
(defn transform [coll]
(map (fn [c] [c (str c)]) coll))
(defn search [[[c cs] & coll] key]
(if c
(if (= c key)
cs
(search coll key))))
(defn remove [key [[c cs] & coll]]
(if c
(if (= c key)
coll
(cons [c cs] (remove key coll)))))
(defn sisoku-format* [seeds result]
(if (single? result)
(second (first seeds))
(let [entry (take 3 result)
a (nth entry 1)
b (nth entry 2)
op (nth entry 0)
a-r (search seeds a)
b-r (search seeds b)
r (case op
"+" (+ a b)
"-" (- a b)
"/" (/ a b)
"*" (* a b))
r-r (str "(" a-r op b-r ")")
seeds (cons [r r-r] (remove a (remove b seeds)))]
(sisoku-format* seeds (drop 3 result)))))
(defn sisoku-format [seeds result]
(let [seeds (transform seeds)]
(sisoku-format* seeds result)))
(defn sisoku-solve [seeds answer]
(doseq [r (sisoku seeds answer)]
(println (sisoku-format seeds r))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment