Is there a way in Swift to calculate all of the possible ways 3 numbers can be added, multiplied, subtracted or divided. Including parentheses

user_12657268 0
Viewed 292

I am developing a game in Xcode and need to figure out all of the possible mathematical outcomes of 3 numbers. The player is trying to use the three numbers to get as close as possible to a Target number. For example, if the target was 10 and your three numbers were 8, 6 and 4 you could use 8 + 6 - 4. If the target number was 12, you could use 8*6/4 and get 12. I am currently manually running through 142 possible combinations and storing the results in an array:

resultsArray[0] = firstNum+secondNum+thirdNum; 
resultsArray[1] = firstNum+secondNum-thirdNum; 
resultsArray[2] = firstNum+secondNum*thirdNum; 
resultsArray[3] = firstNum+secondNum/thirdNum; 
...
resultsArray[143] = thirdNum/(secondNum-firstNum);

I am then checking the array for the closest correct answer like so:

let x = 10 //target number
let closest = resultsArray.enumerated().min( by: { abs($0.1 - x) < abs($1.1 - x) } )!
correctAnswer = resultsArray[closest.offset]

It works, except for a divide by zero error.

I know there is a better way but I have scoured the web and come up empty handed. Any ideas?

kotlin combinations permutation swift
1 Answers

This was a fun problem that let's you use Swift's capabilities of custom enums, optionals, Sets, higher order functions (map) and the ability to return multiple values from a function.

144 equations! Even if we had the code, it would be hard to confirm you have covered everything. And the divide by zero is a tricky situation that requires special attention.

Here is my take on this problem. The goals of my solution are:

  1. Break it down into easily verifiable steps
  2. Avoid divide by zero
  3. Avoid fractional calculations
  4. Avoid negative numbers
  5. Display the equations in human readable form
  6. Find all equations that are closest to the target
// Generate all 6 permuations of the 3 numbers.
// Use Set() to remove duplicates
func permuteNumbers(_ a: Int, _ b: Int, _ c: Int) -> [(Int, Int, Int)] {
    return Set([[a, b, c],
                [a, c, b],
                [b, a, c],
                [b, c, a],
                [c, a, b],
                [c, b, a]]).map { ($0[0], $0[1], $0[2]) }
}

enum Operation: String, CaseIterable {
    case addition = "+"
    case subtraction = "-"
    case multiplication = "*"
    case division = "/"
}

// Generate all 16 combinations of the 4 operations
func allOperations() -> [(Operation, Operation)] {
    var all = [(Operation, Operation)]()
    for op1 in Operation.allCases {
        for op2 in Operation.allCases {
            all.append((op1, op2))
        }
    }
    return all
}

// Return nil on divide by zero.
// Return nil when the result would be a negative number.
// Return nil when the result would be a fraction (not a whole number).
func performOperation(_ a: Int, _ b: Int, _ op: Operation) -> Int? {
    switch op {
    case .addition:        return a + b
    case .subtraction:     return (b > a) ? nil : a - b
    case .multiplication:  return a * b
    case .division:        return ((b == 0) || (a % b != 0)) ? nil : a / b
    }
}

// Perform (a op1 b) op2 c
// return (result, equation)
func performOp1First(a: Int, b: Int, c: Int, op1: Operation, op2: Operation) -> (Int?, String) {
    let str = "(\(a) \(op1.rawValue) \(b)) \(op2.rawValue) \(c)"
    
    if let r1 = performOperation(a, b, op1) {
        if let r2 = performOperation(r1, c, op2) {
            return (r2, str)
        }
    }
    return (nil, str)
}

// Perform a op1 (b op2 c)
// return (result, equation)
func performOp2First(a: Int, b: Int, c: Int, op1: Operation, op2: Operation) -> (Int?, String) {
    let str = "\(a) \(op1.rawValue) (\(b) \(op2.rawValue) \(c))"

    if let r1 = performOperation(b, c, op2) {
        if let r2 = performOperation(a, r1, op1) {
            return (r2, str)
        }
    }
    return (nil, str)
}

// Perform a op1 b op2 c - order doesn't matter for (+, +), (+, -), (*, *), and (*, /)
// return (result, equation)
func performNoParens(a: Int, b: Int, c: Int, op1: Operation, op2: Operation) -> (Int?, String) {
    let str = "\(a) \(op1.rawValue) \(b) \(op2.rawValue) \(c)"
    
    if let r1 = performOperation(a, b, op1) {
        if let r2 = performOperation(r1, c, op2) {
            return (r2, str)
        }
    }
    return (nil, str)
}

// Search all permutations of the numbers, operations, and operation order
func findBest(a: Int, b: Int, c: Int, target: Int) -> (diff: Int, equations: [String]) {
    let numbers = permuteNumbers(a, b, c)
    
    var best = Int.max
    var equations = [String]()
    
    for (a, b, c) in numbers {
        for (op1, op2) in allOperations() {
            // Parentheses are not needed if the operators are (+, +), (+, -), (*, *), (*, /)
            let noparens = [["+", "+"], ["+", "-"],["*", "*"], ["*", "/"]].contains([op1.rawValue, op2.rawValue])
            
            for f in (noparens ? [performNoParens] : [performOp1First, performOp2First]) {
                let (result, equation) = f(a, b, c, op1, op2)
                if let result = result {
                    let diff = abs(result - target)
                    if diff == best {
                        equations.append(equation)
                    } else if diff < best {
                        best = diff
                        equations = [equation]
                    }
                }
            }
        }
    }
    
    return (best, equations)
}

Examples:

print(findBest(a: 8, b: 6, c: 4, target: 10))

(diff: 0, equations: ["8 + 6 - 4", "6 + 8 - 4", "(6 - 4) + 8", "(8 - 4) + 6"])

print(findBest(a: 8, b: 6, c: 4, target: 12))

(diff: 0, equations: ["6 * 8 / 4", "8 * 6 / 4", "(8 / 4) * 6"])

print(findBest(a: 8, b: 6, c: 4, target: 4))

(diff: 0, equations: ["6 - (8 / 4)", "8 / (6 - 4)"])

print(findBest(a: 8, b: 6, c: 4, target: 5))

(diff: 1, equations: ["6 - (8 / 4)", "4 + 8 - 6", "(8 - 6) + 4", "8 - (6 - 4)", "8 / (6 - 4)", "8 + 4 - 6"])

print(findBest(a: 8, b: 6, c: 4, target: 7))

(diff: 1, equations: ["(8 - 6) + 4", "8 - (6 - 4)", "(8 - 6) * 4", "6 + (8 / 4)", "4 + 8 - 6", "4 * (8 - 6)", "8 + 4 - 6", "(8 / 4) + 6"])

Kotlin version

Here is a Kotlin version that was hand-translated from the Swift version. This is my first Kotlin program, so I'm sure I'm not doing everything in the most idiomatic way. I tested this program at the Online Kotlin Playground

import kotlin.math.abs

// Generate all 6 permuations of the 3 numbers.
// Use Set() to remove duplicates
fun permuteNumbers(a: Int, b: Int, c: Int): Set<List<Int>> {
    return setOf(
        listOf(a, b, c),
        listOf(a, c, b),
        listOf(b, a, c),
        listOf(b, c, a),
        listOf(c, a, b),
        listOf(c, b, a)
    )
}

enum class Operation(val string: String) { 
  ADDITION("+"), 
  SUBTRACTION("-") ,
  MULTIPLICATION("*"),
  DIVISION("/")
}

fun allOperations(): List<Pair<Operation, Operation>> {
    val result = mutableListOf<Pair<Operation, Operation>>()
    for (op1 in Operation.values()) {
        for (op2 in Operation.values()) {
            result.add(Pair(op1, op2))
        }
    }
    
    return result
}

fun performOperation(a: Int, b: Int, op: Operation): Int? {
    return when (op) {
        Operation.ADDITION       ->  (a + b)
        Operation.SUBTRACTION    ->  if (b > a) { null } else { a - b }
        Operation.MULTIPLICATION ->  a * b
        Operation.DIVISION       ->  if ((b == 0) || (a % b != 0)) { null} else { a / b }
    }
}

// Perform (a op1 b) op2 c
// return (result, equation)
fun performOp1First(a: Int, b: Int, c: Int, op1: Operation, op2: Operation): Pair<Int?, String> {
    val str = "($a ${op1.string} $b) ${op2.string} $c"
    
    performOperation(a, b, op1)?.also { r1 ->
        performOperation(r1, c, op2)?.also { r2 ->
            return Pair(r2, str)
        }
    }
    return Pair(null, str)
}

// Perform a op1 (b op2 c)
// return (result, equation)
fun performOp2First(a: Int, b: Int, c: Int, op1: Operation, op2: Operation): Pair<Int?, String> {
    val str = "$a ${op1.string} ($b ${op2.string} $c)"
    
    performOperation(b, c, op2)?.also { r1 ->
        performOperation(a, r1, op1)?.also { r2 ->
            return Pair(r2, str)
        }
    }
    return Pair(null, str)
}

// Perform a op1 b op2 c - order doesn't matter for (+, +), (+, -), (*, *), and (*, /)
// return (result, equation)
fun performNoParens(a: Int, b: Int, c: Int, op1: Operation, op2: Operation): Pair<Int?, String> {
    val str = "$a ${op1.string} $b ${op2.string} $c"
    
    performOperation(a, b, op1)?.also { r1 ->
        performOperation(r1, c, op2)?.also { r2 ->
            return Pair(r2, str)
        }
    }
    return Pair(null, str)
}

// Search all permutations of the numbers, operations, and operation order
fun findBest(a: Int, b: Int, c: Int, target: Int): Pair<Int, List<String>> {
    val numbers = permuteNumbers(a, b, c)
    
    var best = Int.MAX_VALUE
    var equations = mutableListOf<String>()
    
    for ((a1, b1, c1) in numbers) {
        for ((op1, op2) in allOperations()) {
            // Parentheses are not needed if the operators are (+, +), (+, -), (*, *), (*, /)
            val noparens = listOf(listOf("+", "+"), listOf("+", "-"), listOf("*", "*"), listOf("*", "/"))
                .contains(listOf(op1.string, op2.string))
            
            for (f in if (noparens) { listOf(::performNoParens) } else { listOf(::performOp1First, ::performOp2First) }) {
                val (result, equation) = f(a1, b1, c1, op1, op2)
                result?.also { result2 ->
                    val delta = abs(target - result2)
                    if (delta == best) {
                        equations.add(equation)
                    } else if (delta < best) {
                        best = delta
                        equations = mutableListOf(equation)
                    }
                }
            }
            
        }
    }
    
    return Pair(best, equations)
}

fun main() {
    println(findBest(4, 6, 8, 4))
}
user_16306180
Related