Skip to content

Instantly share code, notes, and snippets.

@viebel
Forked from Engelberg/core.clj
Last active January 5, 2017 09:30
Show Gist options
  • Save viebel/54a9699398205a3ed41fc881a4232e08 to your computer and use it in GitHub Desktop.
Save viebel/54a9699398205a3ed41fc881a4232e08 to your computer and use it in GitHub Desktop.
Twenty four using partitions
;; Live demo with klipse - http://app.klipse.tech/?cljs_in.gist=viebel/54a9699398205a3ed41fc881a4232e08&eval_only=1
(ns twentyfour.core
(:require [clojure.math.combinatorics :refer [partitions]]))
(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])
;; 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...
(def symbol->func {'+ + '- - '* * '/ /})
(defn fast-eval [e]
(cond
(number? e) e
(symbol? e) (symbol->func 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.
(solutions [6 6 5 2] 17)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment