Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Twenty four using partitions
(ns twentyfour.core
(:use clojure.math.combinatorics))
(def ops ['+ '- '* '/])
(def commutative #{'+ '*})
;; We can generate all the possible expressions efficiently with combinatorics' partitions
;; partitions automatically handles duplicates for us, which keeps the process efficient
(defn expressions [nums]
(if (= (count nums) 1) nums
(for [[left right] (partitions nums :min 2 :max 2),
left-expr (expressions left),
right-expr (expressions right),
op ops,
expr (if (or (commutative op) (= left-expr right-expr))
[(list op left-expr right-expr)]
[(list op left-expr right-expr) (list op right-expr left-expr)])]
expr)))
;; Try (expressions [1 2 3]) at the REPL to see what output the above function produces
;; Then try an expression with duplicate values like (expressions [1 1 2])
(defn solutions [nums target]
(for [expr (expressions nums)
:when (= target (try (eval expr)
(catch ArithmeticException e nil)))]
expr))
;; That concise solution will solve any problem in a few seconds, but we can do better.
;; You can make this dramatically faster by memoizing the evaluation process, like so...
(defn fast-eval [e]
(cond
(number? e) e
(symbol? e) (eval e)
:else
(let [[op e1 e2] e,
op (fast-eval op),
e1 (fast-eval e1),
e2 (fast-eval e2)]
(when (and e1 e2 (not (and (= op /) (= e2 0)))) ; disallow divide by zero
(op e1 e2)))))
(def fast-eval (memoize fast-eval))
;; Now just replace the call to eval in solutions with a call to fast-eval and see how much faster it goes.
(defn solutions [nums target]
(for [expr (expressions nums)
:when (= target (fast-eval expr))]
expr))
;; Left as an exercise for the reader: make more robust with clojure.core.memoize or dynamic variables so cache doesn't
;; get too large when applied to a large number of problems, or alternatively,
;; combine fast-eval with expressions by altering expressions to produce [expression result] pairs.
@viebel

This comment has been minimized.

Copy link

viebel commented Jan 5, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.