A library to make certain number from some numbers.

make_number.clj

(ns
 ^{:author "OGINO Masanori"
   :see-also [["http://www.cs.nott.ac.uk/~gmh/book.html" "Programming in Haskell"]]
   :doc "A library to make certain number from some numbers.

This library solves a well-known problem called \"Ten Puzzle\" or \"Countdown
Problem\", but the target number is not limited to 10.  You can get any integer
or rational number.  Also, the number of source numbers is not limited to 4.
Note that source numbers are *not always* used once, but never or once.

The algorithm of this library is based on chapter 11 in \"Programming in
Haskell\" by Graham Hutton.  According to the citation, the original paper is
also written by him."}
  make-number
  (:use [clojure.contrib.combinatorics :only (subsets lex-permutations)]))

(def ^{:private true} operators ['+ '- '* '/])

(defn- valid?
  "Returns true if op with x and y is valid, else false."
  [op x y]
  (case op
    + (and (not= x 0) (not= y 0) (<= x y))
    - true
    * (and (not= x 1) (not= y 1) (<= x y))
    / (and (not= y 1) (not= y 0))))

(defn- apply-op
  "Applies operator op to x and y."
  [op x y]
  (case op
    + (+ x y)
    - (- x y)
    * (* x y)
    / (/ x y)))

(defn- choices
  "Returns permutations of subsets of coll."
  [coll]
  (mapcat lex-permutations (set (subsets coll))))

(defn- split
  "Returns all patterns to split coll into two colls."
  [coll]
  (map #(split-at % coll) (range 1 (count coll))))

(defn- combine
  "Returns all valid expressions with certain expressions."
  [[l x] [r y]]
  (for [op operators :when (valid? op x y)]
    [(list op l r) (apply-op op x y)]))

(defn- results
  "Returns pairs of expressions using some numbers in coll and their values."
  [coll]
  (if (= (count coll) 1)
    [[(first coll) (first coll)]]
    (for [[ls rs] (split coll)
          :let [lres (results ls) rres (results rs)]
          lx lres
          ry rres
          res (combine lx ry)]
       res)))

(defn make-number
  "Returns a list of expressions using some numbers in coll which equals n."
  [coll n]
  (for [choice (choices coll)
        [e m] (results choice)
        :when (= m n)]
    e))

(comment
;; If you do (load-file "make_number.clj"), call make-number/make-number instead
;; of make-number.  Also, you can do (use 'make-number) and then you can call
;; make-number directly.
(make-number [7 7 7 9 11 11] 218/100)
(make-number [1 1 6 11 12 13] 314/100)
)