Write a program that outputs all possibilities to put a + or - or nothing between the numbers 1-9 (in order) such that the result is 100. For example:
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
The function should output a list of strings with these formulas.
Hint: this is a recursive problem. Use divide and conquer.
| (ns pf.hundred | |
| (:gen-class) | |
| (:require [clojure.string :as str])) | |
| (defn int-join [nums] | |
| (->> nums | |
| reverse | |
| (map-indexed #(* (int (Math/pow 10 %1)) %2)) | |
| (reduce +))) | |
| (defn groupings [nums] | |
| (loop [idx 1 | |
| acc nil] | |
| (if (<= idx (count nums)) | |
| (let [[head tail] (split-at idx nums) | |
| head (int-join head) | |
| tail-groupings (or (groupings tail) [[]])] | |
| (recur | |
| (inc idx) | |
| (concat acc (map (fn [grouping] | |
| (concat [head] grouping)) | |
| tail-groupings)))) | |
| acc))) | |
| (defn ops | |
| "Turns `nums`, a seq of numbers, into a vector of “ops”, where each “op” is a | |
| two-element vector whose first element is either + or - (the Clojure core | |
| functions. The first number is always given a + operation. | |
| Example: | |
| (ops [1 2]) ; => [[[+ 1] [+ 2]], [[+ 1] [- 2]]" | |
| ([nums] | |
| (let [[head & tail] nums] | |
| (when head | |
| (ops [[[+ head]]] tail)))) | |
| ([acc nums] | |
| (if (seq nums) | |
| (recur | |
| (mapcat (fn [op-chain] | |
| [(conj op-chain [+ (first nums)]) | |
| (conj op-chain [- (first nums)])]) | |
| acc) | |
| (rest nums)) | |
| acc))) | |
| (defn add [ops] | |
| (reduce (fn [sum [op n]] (op sum n)) | |
| 0 | |
| ops)) | |
| (defn result->str [[ops rhs]] | |
| (let [lhs (->> ops | |
| (mapcat (fn [[op n]] [(get {+ "+" - "-"} op) n])) | |
| (drop 1))] | |
| (format "%s = %s" (str/join \space lhs) rhs))) | |
| (defn -main [] | |
| (let [results (->> (range 1 10) | |
| groupings | |
| (mapcat ops) | |
| (map (juxt identity add)) | |
| (filter (fn [[_ sum]] (= sum 100))))] | |
| (doseq [result results] | |
| (println (result->str result))))) |
| ;; sequence of nums (non-empty) | |
| ;; target is the desired number | |
| ;; returns a list of formulas | |
| (defn sum-to [nums target] | |
| (let [[f & rst] nums] | |
| (cond | |
| (not (empty? rst)) | |
| (let [[sec & srst] rst] | |
| (concat | |
| (map #(str (Math/abs f) " + " %) | |
| (sum-to | |
| rst | |
| (- target f))) | |
| (map #(str (Math/abs f) " - " %) | |
| (sum-to | |
| (cons (- sec) srst) | |
| (- target f))) | |
| (sum-to | |
| (cons (Long/parseLong (str f sec)) srst) | |
| target))) | |
| (= f target) | |
| [(str (Math/abs f))] | |
| :else | |
| []))) | |
| (sum-to (range 1 10) 100) |
| (ns adv.res100) | |
| (defn add [number expr] | |
| (let [lst (last expr) | |
| new-expr [(conj expr \+ number) | |
| (conj expr \- number)]] | |
| (if (number? lst) | |
| (conj new-expr (assoc expr | |
| (dec (count expr)) | |
| (+ number (* 10 lst)))) | |
| new-expr))) | |
| (defn calc [expr] | |
| (first (reduce (fn [[acc sign] el] | |
| (if (number? el) | |
| [(+ acc (* sign el)) +1] | |
| [acc (if (= \+ el) 1 -1)])) | |
| [0 +1] | |
| expr))) | |
| (defn add-multiple [exprs number] | |
| (mapcat (partial add number) exprs)) | |
| (defn run [] | |
| (->> (range 2 10) | |
| (reduce add-multiple [[1]]) | |
| (filter #(= 100 (calc %))) | |
| (map (partial apply str)))) |
| ;; https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-352-tip-use-the-right-kind-of-comment-for-the-job/ | |
| ;; | |
| ;; Write a program that outputs all possibilities to put a + or - or nothing between the | |
| ;; numbers 1-9 (in order) such that the result is 100. For example: | |
| ;; | |
| ;; 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 | |
| ;; The function should output a list of strings with these formulas. | |
| ;; We need to evaluate all the solutions so no need to be lazy. The fn-prev-x is like a | |
| ;; reducing function, where prev is the previous result (a vector) and x is the new item to | |
| ;; be considered. It should return a new "prev" result or accumuation of numbers. | |
| (defn expand-nums [fn-prev-x coll] | |
| (letfn [(gen [acc prev coll] | |
| (if (seq coll) | |
| (-> acc | |
| (gen (conj prev (first coll)) (rest coll)) | |
| (gen (fn-prev-x prev (first coll)) (rest coll))) | |
| (conj acc prev)))] | |
| (when (seq coll) | |
| (gen () [(first coll)] (rest coll))))) | |
| (defn combine-prev [prev x] | |
| (conj (pop prev) (+ x (* 10 (peek prev))))) | |
| (defn neg-prev [prev x] | |
| (conj prev (- x))) | |
| (defn eval-candidate [xs] | |
| (reduce + 0 xs)) | |
| (defn solutions [] | |
| (let [negs #(expand-nums neg-prev %) | |
| nums #(expand-nums combine-prev %) | |
| hundred? #(= (eval-candidate %) 100)] | |
| (into () (comp (mapcat nums) (mapcat negs) (filter hundred?)) (list (range 1 10))))) | |
| (defn print-solution [xs] | |
| (print (first xs)) | |
| (doseq [x (rest xs)] | |
| (if (neg? x) | |
| (print " -" (- x)) | |
| (print " +" x))) | |
| (print " = 100")) | |
| (defn print-solutions [] | |
| (doseq [xs (solutions)] | |
| (print-solution xs) | |
| (println))) | |
| (defn str-solutions [] | |
| (map (fn [xs] | |
| (with-out-str | |
| (print-solution xs))) | |
| (solutions))) | |
| #_ (pprint (str-solutions)) | |
| #_ | |
| ("1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100" | |
| "1 + 2 + 34 - 5 + 67 - 8 + 9 = 100" | |
| "1 + 23 - 4 + 5 + 6 + 78 - 9 = 100" | |
| "1 + 23 - 4 + 56 + 7 + 8 + 9 = 100" | |
| "12 + 3 + 4 + 5 - 6 - 7 + 89 = 100" | |
| "12 - 3 - 4 + 5 - 6 + 7 + 89 = 100" | |
| "12 + 3 - 4 + 5 + 67 + 8 + 9 = 100" | |
| "123 - 4 - 5 - 6 - 7 + 8 - 9 = 100" | |
| "123 + 4 - 5 + 67 - 89 = 100" | |
| "123 + 45 - 67 + 8 - 9 = 100" | |
| "123 - 45 - 67 + 89 = 100") |
| ;; Version 1 (solves the problem in phases): | |
| (ns sum-100) | |
| (defn ndigits [x] | |
| (if (= 0 x) 1 (inc (int (Math/log10 x))))) | |
| (defn combine-digits [x y] | |
| (+ (* x (int (Math/pow 10 (ndigits y)))) y)) | |
| (defn expressions | |
| ([] | |
| (expressions 1)) | |
| ([n] | |
| (if (= 9 n) | |
| ['(9)] | |
| (mapcat (fn [expr] | |
| [(conj expr '+ n) | |
| (conj expr '- n) | |
| (conj (rest expr) (combine-digits n (first expr)))]) | |
| (expressions (inc n)))))) | |
| (defn infix->prefix [expr] | |
| (if (= 1 (count expr)) | |
| (first expr) | |
| (let [[x op y & rest] expr] | |
| (recur (conj rest (list op x y)))))) | |
| (defn expr->str [expr] | |
| ;; just drop the enclosing parens (expr is a list of numbers & symbols) | |
| (let [s (str expr)] | |
| (subs s 1 (dec (count s))))) | |
| (->> (expressions) | |
| (filter #(= 100 (eval (infix->prefix %)))) | |
| (map expr->str)) | |
| ;; And here's my compact solution that generates the combinations, evaluates the sums, and produces the string expressions all together: | |
| (ns sum-100-2) | |
| (defn expressions | |
| ([] | |
| (expressions 1)) | |
| ([digit] | |
| (if (= digit 9) | |
| [["9" 9 9]] | |
| (mapcat (fn [[expr sum first-val]] | |
| [[(str digit " + " expr) (+ sum digit) digit] | |
| [(str digit " - " expr) (-> sum (- first-val) (+ (- digit first-val))) digit] | |
| (let [ndigits (inc (int (Math/log10 first-val))) | |
| val (* digit (int (Math/pow 10 ndigits)))] | |
| [(str digit expr) (+ sum val) (+ val first-val)])]) | |
| (expressions (inc digit)))))) | |
| (->> (expressions) | |
| (filter #(= 100 (second %))) | |
| (map #(first %))) |
| ;; Complete solution: https://github.com/shofel/purely-functional-sum100 | |
| ;;; | |
| ;;; @see https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-352-tip-use-the-right-kind-of-comment-for-the-job/ | |
| ;;; | |
| ;;; Write a program that outputs all possibilities to put a + or – or | |
| ;;; nothing between the numbers 1-9 (in order) such that the result | |
| ;;; is 100. For example: | |
| ;;; | |
| ;;; 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 | |
| ;;; | |
| ;;; The function should output a list of strings with these formulas. | |
| ;;; | |
| (ns clj-digitsto100.core | |
| (:require [clojure.string :as str] | |
| [taoensso.tufte | |
| :as tufte | |
| :refer (defnp p profile)])) | |
| ;;; As task mentions, the output should be a list of strings. | |
| ;;; Let's make it as the last step. | |
| ;;; Then what's the first? | |
| ;; Basically, we should make a couple of things: | |
| ;; - the first is decision taking: choose one of three options | |
| ;; - provide inputs for those decisions | |
| ;; - accumulate taken decisions | |
| ;; Ok, then. The input is digits from 1 to 9. | |
| ;; What is the output? | |
| ;; - a list of all decisions taken? | |
| ;; - a list of digits and signs between them? | |
| ;; | |
| ;; The first option will require merging back with digits. | |
| ;; The second option contain all the info. But `|` changes the number | |
| ;; of elements. | |
| ;; | |
| ;; To not be affected by this, let's use a sequence with all | |
| ;; the digits and ops between them. | |
| (defn | | |
| "An operator which represents decision to glue two digits. | |
| @example (= (| 1 2) 12)" | |
| [x y] | |
| (+ (* 10 x) y)) | |
| ;;; | |
| ;;; Decode | | |
| ;;; | |
| (declare decode|') | |
| (defn decode| | |
| "Apply `decode|'` to a list" | |
| [x] | |
| (apply decode|' x)) | |
| (defnp decode|' | |
| "Make expression with all the `|` applied" | |
| ([] []) | |
| ([x] [x]) | |
| ([x op y & tail] | |
| (condp = op | |
| | (decode| (cons (| x y) tail)) | |
| (concat [x op] (decode| (cons y tail)))))) | |
| ;;; | |
| ;;; Decode + - | |
| ;;; | |
| (defn sum' | |
| "Given a list like [- 2 + 3 ...], | |
| make a list of numbers with + or - sign." | |
| [xs] | |
| (->> xs | |
| (partition-all 2) | |
| (map (fn [[op digit]] (op digit))) | |
| (apply +))) | |
| (comment | |
| ;; perf of sum(map (comp eval seq))ming [- 2 + 3 ...] | |
| (defn sample | |
| "Pairs of a sign and a number." | |
| [n] | |
| (repeat n [+ n])) | |
| (defn perf | |
| [f] | |
| (time (dotimes [_ 100] | |
| (->> (sample 10) | |
| (map f) | |
| (apply +)))) ) | |
| ; Elapsed time: 1530.837363 msecs | |
| (perf (comp eval seq)) | |
| ; Elapsed time: 0.860691 msecs | |
| (perf (fn [[op digit]] (op digit))) | |
| (defnp -eval [& args] (apply eval args)) | |
| (defnp -seq [& args] (apply seq args)) | |
| ;; What is slow:`comp` `eval` or `seq` ?? | |
| ;; | |
| ;; pId nCalls 50% ≤ Mean Clock Total | |
| ;; defn_-eval 1,000 1.60ms 1.63ms 1.63s 99% | |
| ;; defn_-seq 1,000 1.20μs 1.64μs 1.64ms 0% | |
| (profile | |
| {} | |
| (dotimes [_ 100] | |
| (let [xs (sample 10) | |
| numbers (map | |
| (comp -eval -seq) | |
| xs) | |
| sum (apply + numbers)] | |
| sum))) | |
| ) | |
| (declare reduce+-') | |
| ;; TODO find the better way | |
| ;; - a function in core? | |
| ;; - pattern matching syntax? | |
| (defn reduce+- | |
| "Adapter for reduce+-' for easier pattern matching" | |
| [x] | |
| (apply reduce+-' x)) | |
| (defnp plus | |
| [& xs] | |
| (apply + xs)) | |
| (defnp reduce+-' | |
| "Apply + and - in a given seq." | |
| ([] 0) | |
| ([x] x) | |
| ([x & xs] | |
| (p :plus-body (+ x (sum' xs))))) | |
| ;;; | |
| ;;; Combine `decode|` and `reduce+-`. | |
| ;;; It's the final decode. | |
| ;;; | |
| (defn decode | |
| "Which number is represented by the sequence?" | |
| [xs] | |
| (-> xs | |
| decode| | |
| reduce+-)) | |
| ;; It'd be easier to have two different lists: | |
| ;; - one with digits from 1 to 9 | |
| ;; - one with taken decisions | |
| ;; Then zip them, and reduce to a number. | |
| (defn hundred? | |
| "Check if all taken decisions lead to the sum of 100" | |
| [expression] | |
| (-> expression | |
| decode | |
| (= 100))) | |
| ;;; At this point we are ready to get the right solutions from a list | |
| ;;; of solutions. Let's generate all solutions and take correct ones. | |
| (defn append-tails | |
| [head tails] | |
| (let [heads (repeat (count tails) head)] | |
| (map conj heads tails))) | |
| (defn combinations | |
| "Generate all combinations for a given alphabet of a given length" | |
| ([length alphabet] | |
| (condp = length | |
| (combinations [[]] length alphabet))) | |
| ([heads length alphabet] | |
| (if (zero? length) heads | |
| (combinations | |
| (mapcat | |
| #(append-tails % alphabet) | |
| heads) | |
| (dec length) | |
| alphabet)))) | |
| ;;; TODO seq of ops to expression | |
| ;;; TODO generate and filter | |
| (defn ops->expression | |
| [xs] | |
| (concat [1] | |
| (mapcat vector xs (range 2 10)))) | |
| (defn expr->chars | |
| [xs] | |
| (let [opchars {- " - " | |
| + " + " | |
| | "" }] | |
| (map | |
| #(get opchars % %) | |
| xs))) | |
| (defn render-expression | |
| [expr] | |
| (-> expr | |
| expr->chars | |
| (str/join))) | |
| (defn render-single-solution | |
| [s] | |
| (-> s | |
| render-expression | |
| (str " = 100"))) | |
| ;;; TODO make expression ops always looking well | |
| (defn -main | |
| [] | |
| (->> | |
| (combinations 8 [+ | -]) | |
| (map ops->expression) | |
| (filter hundred?) | |
| (map render-single-solution) | |
| (map println))) | |
| #_(-main) | |
| ;;; Profile | |
| (tufte/add-basic-println-handler! | |
| {:format-pstats-opts {:columns [:n-calls :p50 :mean :clock :total] | |
| :format-id-fn name}}) | |
| ;;; perf | |
| (comment | |
| (defn -combos | |
| [] | |
| (combinations 8 [+ | -])) | |
| ;; Combinations is fast, lets measure the rest. | |
| ; 0s: -combos | |
| (time (->> (-combos) | |
| doall | |
| (take 0))) | |
| (def combos (-combos)) | |
| ;; 0s: ops->expression | |
| (time (->> combos | |
| (map ops->expression) | |
| doall | |
| (take 0))) | |
| ;; ?s: sum numbers | |
| (time (dotimes [n 10e3] | |
| (sum' (interleave | |
| (repeat n :+) | |
| (repeat n n))))) | |
| ) | |
| #_ | |
| (do | |
| (defn expressions | |
| [] | |
| (map ops->expression | |
| (combinations 8 [+ | -]))) | |
| ;; 35s: filter hundred? | |
| (profile | |
| {} | |
| (take 0 (doall | |
| (filter hundred? (expressions)))))) | |
| ;; Answer | |
| #_((1 + 2 + 3 - 4 + 5 + 6 + 7 | 8 + 9) | |
| (1 + 2 + 3 | 4 - 5 + 6 | 7 - 8 + 9) | |
| (1 + 2 | 3 - 4 + 5 + 6 + 7 | 8 - 9) | |
| (1 + 2 | 3 - 4 + 5 | 6 + 7 + 8 + 9) | |
| (1 | 2 + 3 + 4 + 5 - 6 - 7 + 8 | 9) | |
| (1 | 2 + 3 - 4 + 5 + 6 | 7 + 8 + 9) | |
| (1 | 2 - 3 - 4 + 5 - 6 + 7 + 8 | 9) | |
| (1 | 2 | 3 + 4 - 5 + 6 | 7 - 8 | 9) | |
| (1 | 2 | 3 + 4 | 5 - 6 | 7 + 8 - 9) | |
| (1 | 2 | 3 - 4 - 5 - 6 - 7 + 8 - 9) | |
| (1 | 2 | 3 - 4 | 5 - 6 | 7 + 8 | 9)) | |
| ;; Formatted answer | |
| #_(list | |
| "1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100" | |
| "1 + 2 + 34 - 5 + 67 - 8 + 9 = 100" | |
| "1 + 23 - 4 + 5 + 6 + 78 - 9 = 100" | |
| "1 + 23 - 4 + 56 + 7 + 8 + 9 = 100" | |
| "12 + 3 + 4 + 5 - 6 - 7 + 89 = 100" | |
| "12 + 3 - 4 + 5 + 67 + 8 + 9 = 100" | |
| "12 - 3 - 4 + 5 - 6 + 7 + 89 = 100" | |
| "123 + 4 - 5 + 67 - 89 = 100" | |
| "123 + 45 - 67 + 8 - 9 = 100" | |
| "123 - 4 - 5 - 6 - 7 + 8 - 9 = 100" | |
| "123 - 45 - 67 + 89 = 100") |