Блог

Я разрабатываю игру в Xcode и мне нужно выяснить все возможные математические результаты 3 чисел. Игрок пытается использовать три числа, чтобы максимально приблизиться к целевому числу. Например, если целевым значением было 10, а вашими тремя числами были 8, 6 и 4, вы могли бы использовать 8 6 — 4. Если целевым числом было 12, вы могли бы использовать 8 * 6/4 и получить 12. В настоящее время я вручную просматриваю 142 возможные комбинации и сохраняю результаты в массиве:

 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);
  

Затем я проверяю массив на предмет ближайшего правильного ответа следующим образом:

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

Это работает, за исключением ошибки деления на ноль.

Я знаю, что есть способ получше, но я порылся в Интернете и пришел с пустыми руками. Есть идеи?

Это была забавная задача, которая позволила вам использовать возможности Swift по пользовательским перечислениям, опциям, наборам, функциям более высокого порядка ( map ) и возможность возвращать несколько значений из функции.

144 уравнения! Даже если бы у нас был код, было бы трудно подтвердить, что вы рассмотрели все. И деление на ноль — сложная ситуация, требующая особого внимания.

Вот мой взгляд на эту проблему. Целями моего решения являются:

1. Разбейте это на легко проверяемые шаги
2. Избегайте деления на ноль
3. Избегайте дробных вычислений
4. Избегайте отрицательных чисел
5. Отобразить уравнения в удобочитаемой форме
6. Найдите все уравнения, которые наиболее близки к целевому

 // 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)
}
  

Примеры:

 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

Вот версия Kotlin, которая была переведена вручную из версии Swift. Это моя первая программа Kotlin, поэтому я уверен, что я делаю все не самым идиоматичным способом. Я тестировал эту программу на онлайн игровой площадке Kotlin

 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))
}