Skip to content

Instantly share code, notes, and snippets.

@mikeananev
Created February 11, 2023 17:00
Show Gist options
  • Save mikeananev/cfd25ce81560dee7298d04b6e39ef816 to your computer and use it in GitHub Desktop.
Save mikeananev/cfd25ce81560dee7298d04b6e39ef816 to your computer and use it in GitHub Desktop.
Find minimal result from applying all permutations of operations to all permutations of numbers
;; Find minimal result from applying all permutations of operations to all permutations of numbers
(defn remove-first [pred s]
(lazy-seq
(when-let [[x & xs] (seq s)]
(cond (pred x) xs
:else (cons x (remove-first pred xs))))))
(defn permutations [s]
(lazy-seq
(if (next s)
(for [head s
tail (permutations (remove-first #{head} s))]
(cons head tail))
[s])))
(defn find-min [coll ops]
(for [[a b c] (permutations coll)
[op1 op2] (permutations ops)]
{:result ((eval op2) ((eval op1) a b) c)
:nums [a b c]
:ops [op1 op2]}))
(def v [2 3 4])
(def ops '(* + -))
(sort-by :result (find-min v ops))
;; =>
;;({:result -6, :nums [2 4 3], :ops [- *]}
;; {:result -4, :nums [2 3 4], :ops [- *]}
;; {:result -2, :nums [3 4 2], :ops [- *]}
;; {:result 1, :nums [2 3 4], :ops [+ -]}
;; {:result 1, :nums [2 4 3], :ops [- +]}
;; {:result 1, :nums [3 2 4], :ops [+ -]}
;; {:result 1, :nums [3 4 2], :ops [- +]}
;; {:result 2, :nums [2 3 4], :ops [* -]}
;; {:result 2, :nums [3 2 4], :ops [* -]}
;; {:result 2, :nums [4 3 2], :ops [- *]}
;; {:result 3, :nums [2 3 4], :ops [- +]}
;; {:result 3, :nums [2 4 3], :ops [+ -]}
;; {:result 3, :nums [4 2 3], :ops [+ -]}
;; {:result 3, :nums [4 3 2], :ops [- +]}
;; {:result 4, :nums [3 2 4], :ops [- *]}
;; {:result 5, :nums [2 4 3], :ops [* -]}
;; {:result 5, :nums [3 2 4], :ops [- +]}
;; {:result 5, :nums [3 4 2], :ops [+ -]}
;; {:result 5, :nums [4 2 3], :ops [* -]}
;; {:result 5, :nums [4 2 3], :ops [- +]}
;; {:result 5, :nums [4 3 2], :ops [+ -]}
;; {:result 6, :nums [4 2 3], :ops [- *]}
;; {:result 10, :nums [2 3 4], :ops [* +]}
;; {:result 10, :nums [3 2 4], :ops [* +]}
;; {:result 10, :nums [3 4 2], :ops [* -]}
;; {:result 10, :nums [4 3 2], :ops [* -]}
;; {:result 11, :nums [2 4 3], :ops [* +]}
;; {:result 11, :nums [4 2 3], :ops [* +]}
;; {:result 14, :nums [3 4 2], :ops [* +]}
;; {:result 14, :nums [3 4 2], :ops [+ *]}
;; {:result 14, :nums [4 3 2], :ops [* +]}
;; {:result 14, :nums [4 3 2], :ops [+ *]}
;; {:result 18, :nums [2 4 3], :ops [+ *]}
;; {:result 18, :nums [4 2 3], :ops [+ *]}
;; {:result 20, :nums [2 3 4], :ops [+ *]}
;; {:result 20, :nums [3 2 4], :ops [+ *]})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment