#swift #kotlin #combinations #permutation
#swift #kotlin #комбинации #перестановку
Вопрос:
Я разрабатываю игру в 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]
Это работает, за исключением ошибки деления на ноль.
Я знаю, что есть способ получше, но я порылся в Интернете и пришел с пустыми руками. Есть идеи?
Комментарии:
1. Вас волнует, какая формула дает наиболее близкий результат, или вам просто нужно знать число? Что вы хотите сделать, если существует более одного значения, которое одинаково близко?
Ответ №1:
Это была забавная задача, которая позволила вам использовать возможности Swift по пользовательским перечислениям, опциям, наборам, функциям более высокого порядка ( map
) и возможность возвращать несколько значений из функции.
144 уравнения! Даже если бы у нас был код, было бы трудно подтвердить, что вы рассмотрели все. И деление на ноль — сложная ситуация, требующая особого внимания.
Вот мой взгляд на эту проблему. Целями моего решения являются:
- Разбейте это на легко проверяемые шаги
- Избегайте деления на ноль
- Избегайте дробных вычислений
- Избегайте отрицательных чисел
- Отобразить уравнения в удобочитаемой форме
- Найдите все уравнения, которые наиболее близки к целевому
// 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))
}
Комментарии:
1. Это потрясающе! Большое спасибо. Однако есть одна проблема, которую я должен был объяснить в описании игры. Я только хочу показать уравнения, которые приводят к целому числу. Например: print(findBest(a: 8, b: 6, c: 4, target: 5)) лучшим решением было бы 8 — 6 4 . Разница будет равна единице. Решения, которые приводят к десятичным числам, были бы слишком сложными. Есть ли способ изменить это, чтобы находить решения, приводящие только к номерам отверстий?
2. Я могу предположить, что входные числа также являются целыми числами? Также будет ли в порядке уравнение типа 8 * (1/2), поскольку ответ равен целым 4, даже если во время вычисления есть 0,5?
3. Да, все входные числа являются целыми числами от 1 до 40. 8 * (1/2) было бы неправильно, потому что 1/2 не дает целого числа. Мы пытаемся использовать только уравнения, в которых числа непосредственно делятся друг на друга. Эта игра предназначена для детей младшего школьного возраста. Еще раз спасибо!
4. Я думаю, что это может быть достигнуто путем возврата nil для делений, которые не возвращают целые числа. То есть мы будем рассматривать эти дробные деления как деление на ноль и отвергнем эти ответы. Кроме того, я думаю, что мы можем использовать только целочисленную математику.
5. Как насчет того, чтобы избежать отрицательных чисел? Следует ли
8 (4 - 6)
отвергать и(8 4) - 6
отдавать предпочтение?