Here is one approach. Start with an array of expressions and an array of values. Initially, the expressions is just the String value of the values:
let expressions = ["1", "2", "3", "4"]
let values = [1, 2, 3, 4]
Pick two expressions (for example "1" and "2", and a binary operator ("+"), and combine them creating an expressions and values with 3 values:
expressions = ["3", "4", "(1 + 2)"]
values = [3, 4, 3]
Repeat this process combining again two of the expressions with an operation:
expressions = ["3", "(4 + (1 + 2))"]
values = [3, 7]
Finally, combine the last two expressions with "+":
expressions = ["(3 + (4 + (1 + 2)))"]
values = [10]
Once you reach a single expression, check to see if the value matches your target.
The following is a recursive function that tries all combinations of values and operations to create the expressions in search of a target:
import Foundation
// An array of tuples containing an operator name and a closure
// that performs the operation
let ops: [(name: String, function: (Double, Double) -> Double)] = [
("+", { $0 + $1 }),
("-", { $0 - $1 }),
("*", { $0 * $1 }),
("/", { $0 / $1 }),
("^", { pow($0, $1) })
]
func compute(expressions: [String], values: [Double], target: Double) {
// base case of the recursion: if there is only one
// expression and one value, check if the value is the
// target value we're looking for and print the expression
// and value if the target is matched
if expressions.count == 1 {
if values[0] == target {
print("\(expressions[0]) = \(values[0])")
}
} else if expressions.count >= 2 {
// loop through all of the expressions choosing each
// as the first expression
for idx1 in expressions.indices {
// copy the expressions and values arrays so that
// we can remove the expression and value
// without modifying the original arrays
// which will be needed for the next try
var expcopy = expressions
var valcopy = values
let exp1 = expcopy.remove(at: idx1)
let val1 = valcopy.remove(at: idx1)
// loop through the remaining expressions to find
// the second one
for idx2 in expcopy.indices {
// again, copy the arrays to keep from modifying
// the originals while searching
var expcopy2 = expcopy
var valcopy2 = valcopy
let exp2 = expcopy2.remove(at: idx2)
let val2 = valcopy2.remove(at: idx2)
// now try all possible operations to combine
// the two expressions
for op in ops {
// use the closure to compute the value
let value = op.function(val1, val2)
// combine the expressions into a new string
// expression with the operator in the
// middle and surrounded by () if this is
// not the top level expression
var exp = "\(exp1) \(op.name) \(exp2)"
if !expcopy2.isEmpty {
exp = "(\(exp))"
}
// now that we've reduced the number of
// expressions by 1, recurse by calling
// compute again on the reduced list of
// expressions
compute(expressions: expcopy2 + [exp], values: valcopy2 + [value], target: target)
}
}
}
}
}
// This helper function creates the array of expressions from
// the array of values, and then calls the main function above
// to do the real work
func search(values: [Double], target: Double) {
compute(expressions: values.map { String($0) }, values: values, target: target)
}
Example 1:
search(values: [1, 2, 3, 4], target: 121)
Output:
(1.0 - (3.0 * 4.0)) ^ 2.0 = 121.0
((3.0 * 4.0) - 1.0) ^ 2.0 = 121.0
(1.0 - (4.0 * 3.0)) ^ 2.0 = 121.0
((4.0 * 3.0) - 1.0) ^ 2.0 = 121.0
Example 2:
search(values: [1, 2, 3], target: 1)
Output:
3.0 / (1.0 + 2.0) = 1.0
(1.0 + 2.0) / 3.0 = 1.0
3.0 - (1.0 * 2.0) = 1.0
(1.0 ^ 2.0) ^ 3.0 = 1.0
(1.0 * 3.0) - 2.0 = 1.0
2.0 - (1.0 ^ 3.0) = 1.0
(1.0 ^ 3.0) ^ 2.0 = 1.0
3.0 / (2.0 + 1.0) = 1.0
(2.0 + 1.0) / 3.0 = 1.0
(2.0 - 1.0) ^ 3.0 = 1.0
3.0 - (2.0 * 1.0) = 1.0
3.0 - (2.0 / 1.0) = 1.0
3.0 - (2.0 ^ 1.0) = 1.0
1.0 ^ (2.0 + 3.0) = 1.0
1.0 ^ (2.0 - 3.0) = 1.0
1.0 ^ (2.0 * 3.0) = 1.0
1.0 ^ (2.0 / 3.0) = 1.0
1.0 ^ (2.0 ^ 3.0) = 1.0
2.0 / (3.0 - 1.0) = 1.0
(3.0 - 1.0) / 2.0 = 1.0
(3.0 * 1.0) - 2.0 = 1.0
(3.0 / 1.0) - 2.0 = 1.0
(3.0 ^ 1.0) - 2.0 = 1.0
1.0 ^ (3.0 + 2.0) = 1.0
1.0 * (3.0 - 2.0) = 1.0
1.0 / (3.0 - 2.0) = 1.0
1.0 ^ (3.0 - 2.0) = 1.0
(3.0 - 2.0) * 1.0 = 1.0
(3.0 - 2.0) / 1.0 = 1.0
(3.0 - 2.0) ^ 1.0 = 1.0
1.0 ^ (3.0 * 2.0) = 1.0
1.0 ^ (3.0 / 2.0) = 1.0
1.0 ^ (3.0 ^ 2.0) = 1.0
Eliminating Duplicate Solutions
With 4 or more values, or even with fewer values that aren't unique, you can end up with duplicate expressions. The way to eliminate the duplicates is to use a Set<String> to keep track of the expressions you've already found and check if that set contains your new expression before printing it as a new solution.
import Foundation
// An array of tuples containing an operator name and a closure
// that performs the operation
let ops: [(name: String, function: (Double, Double) -> Double)] = [
("+", { $0 + $1 }),
("-", { $0 - $1 }),
("*", { $0 * $1 }),
("/", { $0 / $1 }),
("^", { pow($0, $1) })
]
func compute(expressions: [String], values: [Double], target: Double, solutions: inout Set<String>) {
// base case of the recursion: if there is only one
// expression and one value, check if the value is the
// target value we're looking for and print the expression
// and value if the target is matched and we don't already
// have that expression in our set of solutions
if expressions.count == 1 {
if values[0] == target && !solutions.contains(expressions[0]) {
print("\(expressions[0]) = \(values[0])")
solutions.insert(expressions[0])
}
} else if expressions.count >= 2 {
// loop through all of the expressions choosing each
// as the first expression
for idx1 in expressions.indices {
// copy the expressions and values arrays so that
// we can remove the expression and value
// without modifying the original arrays
// which will be needed for the next try
var expcopy = expressions
var valcopy = values
let exp1 = expcopy.remove(at: idx1)
let val1 = valcopy.remove(at: idx1)
// loop through the remaining expressions to find
// the second one
for idx2 in expcopy.indices {
// again, copy the arrays to keep from modifying
// the originals while searching
var expcopy2 = expcopy
var valcopy2 = valcopy
let exp2 = expcopy2.remove(at: idx2)
let val2 = valcopy2.remove(at: idx2)
// now try all possible operations to combine
// the two expressions
for op in ops {
// use the op's function to compute the value
let val = op.function(val1, val2)
// combine the expressions into a new string
// expression with the operator in the
// middle and surrounded by () if this is
// not the top level expression
var exp = "\(exp1) \(op.name) \(exp2)"
if !expcopy2.isEmpty {
exp = "(\(exp))"
}
// now that we've reduced the number of
// expressions by 1, recurse by calling
// compute again on the reduced list of
// expressions
let newexp = expcopy2 + [exp]
let newval = valcopy2 + [val]
compute(expressions: newexp, values: newval, target: target, solutions: &solutions)
}
}
}
}
}
// This helper function creates the array of expressions from
// the array of values, creates a Set to hold the solutions, and
// then calls the main function above to do the real work
func search(values: [Double], target: Double) {
// create a set to keep track of solutions found so far
var solutions = Set<String>()
compute(expressions: values.map { String($0) }, values: values, target: target, solutions: &solutions)
print("\n\(solutions.count) unique solutions were found")
}
Example:
search(values: [2, 2, 1], target: 5)
Output:
1.0 + (2.0 + 2.0) = 5.0
(2.0 + 2.0) + 1.0 = 5.0
1.0 + (2.0 * 2.0) = 5.0
(2.0 * 2.0) + 1.0 = 5.0
1.0 + (2.0 ^ 2.0) = 5.0
(2.0 ^ 2.0) + 1.0 = 5.0
2.0 + (2.0 + 1.0) = 5.0
(2.0 + 1.0) + 2.0 = 5.0
2.0 + (1.0 + 2.0) = 5.0
(1.0 + 2.0) + 2.0 = 5.0
10 unique solutions were found
