Skip to content

Instantly share code, notes, and snippets.

@gdeer81
Created November 29, 2017 19:41
Show Gist options
  • Save gdeer81/4c2dd0060809da69bbe4ed599b7f74bd to your computer and use it in GitHub Desktop.
Save gdeer81/4c2dd0060809da69bbe4ed599b7f74bd to your computer and use it in GitHub Desktop.
My over-engineered solution to a deceptively simple problem
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; string s = "123456789"
;; int target = 100
;; how many combinations of +/- give you the target int?
;; + and - can be inserted at any index
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;helper functions;;;;;;
(defn str->vec
"converts a string of consecutive numbers to a vector of individual numbers
ex: 123 -> [1 2 3]"
[s] (mapv #(Integer/valueOf (str %)) s))
(defn append-digit-to-number
"takes a number multiplies it by 10 and adds the digit
ex: append 4 to 123
123 * 10 = 1230
1230 + 4 = 1234"
[num digit]
(->> num
(* 10)
(+ digit)))
(defn sum-matches-target?
"takes a collection where the head element represents the sum and a target number
returns true if the sum equals the target
ex: [100 foo bar baz] 100 = true
[99 foo bar baz] 100 = false"
[[sum & _] target] (= target sum))
(defn sum-matches-100?
"takes a collection and calls sum-matches-target? with the target being 100"
[coll] (sum-matches-target? coll 100))
(defn filter-sum-matches-100
"takes a collection of collections and filters out the ones where the sum matches 100"
[coll] (filter sum-matches-100? coll))
(defn filter-sum-matches-n
"takes a collection of collections and filters out the ones where the sum matches the target"
[coll target] (filter #(sum-matches-target? % 100) coll))
(defn lasts
"returns a lazy sequence of the last element of every collection
it's like last but for multiple collections"
[coll] (map last coll))
(defn stringify-all
"takes a collection of collections and returns a lazy sequence of strings
by applying str to every collection
ex: [[1 2 3] [9 1 1] [4 0 4]] -> [\"123\" \"911\" \"404\"]"
[coll] (map (partial apply str) coll))
;;;;;heavy lifting functions;;;;;;
(defn permutation-triad
"takes a vector with the current state and the next digit in the list
returns a triad of vectors that represent a possibility
v1 contains the result of subtracting the digit from the current summation the sign (+ or -) represented as -1 or 1 and the string representation of the sign and digit conjd onto the results accumulator
v2 contains the same thing as v1 except using the + sign
v3 contains the results of adding the diff (with the sign changed) of the next permutation with the current one
the operation + or -
the digit permutation
and the results with the next digit appended"
[[summation operation current-permutation result] digit]
[[(- summation digit) -1 digit (conj result "-" digit)]
[(+ summation digit) 1 digit (conj result "+" digit)]
[(+ summation (* operation (- (append-digit-to-number current-permutation digit) current-permutation)))
operation
(append-digit-to-number current-permutation digit)
(conj result digit)]])
(defn permutation-list
"generates the list of permutations by concatenating the permutation triads"
[coll digit]
(mapcat permutation-triad coll (repeat digit)))
(defn valid-formula-list
"takes a collection of numbers and a filter function
returns the list of arithmetic formulas that satisfy the filter function"
([[head & tail] filter-fn]
(->> (reduce permutation-list [[head head head [head]]] tail)
(filter-fn)
lasts
stringify-all)))
(defn permutations-to-n
"takes a string of consecutive numbers and a target
returns all the possible permutations of + and - that will equal the target"
[s target]
(valid-formula-list (str->vec s) #(filter-sum-matches-n % target)))
(defn count-of-permutations-to-n
"takes a string of consecutive numbers and a target
tells you how many permutations to the target there are"
[s target] (count (permutations-to-n s target)))
(defn permutations-to-100
"takes a string of consecutive numbers and returns all the possible permutations
of + and - that will equal 100"
[s] (valid-formula-list (str->vec s) filter-sum-matches-100))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;Finaly the function that does what the problem was asking for;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defn count-of-permutations-to-100
"takes a string of consecutive numbers and tells you how many permutation to 100 there are"
[s] (count (permutations-to-100 s)))
;;;;;and using that function to solve the problem;;;;
(count-of-permutations-to-100 "123456789")
;;;exercise for the reader. write specs for this mess
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment