Skip to content

Instantly share code, notes, and snippets.

@Engelberg
Last active January 5, 2017 09:30
Show Gist options
  • Save Engelberg/939e617747da4faabdbcc6ca8891705a to your computer and use it in GitHub Desktop.
Save Engelberg/939e617747da4faabdbcc6ca8891705a to your computer and use it in GitHub Desktop.
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
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