Solving an interesting problem by using Swift concurrency

Using Swift
1

I wish to solve the following problem by using only the concurrency features of Swift.

Problem

Given N + 1 integer numbers, where N >= 1, determine if the first number (the target number) can be expressed as a combination of the remaining N numbers (the input numbers) by following some simple rules (given below).

Rules

The combination process must follow these two rules to combine the input numbers:

  1. Each number may be used at most once;
  2. Multiple numbers may be combined using the arithmetic operations of addition, subtraction, multiplication, and exact integer-division (integer division without remainder.)

For example, here are a few simple instances of the problem:

numbers: 7, 7 (N = 1)
answer: yes

numbers: 21, 32 (N = 1)
answer: no

numbers: 32, 20, 12 (N = 2)
answer: yes (32 = 12 + 20 or 32 = 20 + 12)

numbers: 1, 20, 12, 20, 100 (N = 4)
answer: yes (1 = 20 / 20)

numbers: 155, 0, 5, 75, 2, 25 (N = 5)
answer: yes (155 = 2 * 75 + 5 or 155 = 25 / 5 + 2 * 75)

Solving this problem obviously involves taking the k-permutations of the N input numbers, applying all possible arithmetic operations to each such permutation, and checking the result to see if it equals the target number.

I have already solved this problem (even created a free App for it a decade ago) by using Objective C++ and The Grand Central Dispatch.

But, now I am slightly lost in the sea of Swift concurrency. :worried:

Thank you in advance for any expert advice you provide.

2

Let's first solve the problem without using concurrency:

import Algorithms

func applySomeArithmeticOperations(inputNumers: [Int]) -> Int {
    guard inputNumers.count > 1 else {
        return inputNumers.first!
    }
    var numbers = inputNumers
    let first = numbers.removeFirst()
    let second = numbers.removeFirst()

    let operations: [(Int, Int) -> Int] = [(+), (-), (*)] // please provide the exact integer division yourself

    // Without the sleep the synchronous solution is faster
    Thread.sleep(forTimeInterval: 0.1)

    // probably incorrect solution, you weren't clear about applying some arithmetic operations
    return numbers.reduce(
        operations.randomElement()!(first, second),
        operations.randomElement()!
    )
}

func interestingProblem(_ target: Int, _ inputNumers: Int...) -> Bool {
    // taking the k-permutations of the N input numbers
    let permutations = inputNumers.uniquePermutations()
    var transformed: [Int] = []
    for permutation in permutations {
        transformed.append(
            // applying some arithmetic operations to each such permutation
            applySomeArithmeticOperations(inputNumers: permutation)
        )
    }
    // checking the result to see if it equals the target number
    return transformed.contains(where: { $0 == target })
}

I create the permutations, apply some arithmetic operation on them in a loop, and then check the result if it equals the target number, just like you said.

Let's convert that to use the concurency:

func applySomeArithmeticOperations(inputNumers: [Int]) -> Int {
... // same as above
}
func interestingProblem(_ target: Int, _ inputNumers: Int...) async -> Bool {
    // taking the k-permutations of the N input numbers
    let permutations = inputNumers.uniquePermutations()
    let result = await withTaskGroup(of: Int.self) { group in
        for permutation in permutations {
            group.addTask {
                // applying some arithmetic operations to each such permutation
                applySomeArithmeticOperations(inputNumers: permutation)
            }
        }
        // checking the result to see if it equals the target number
        return await group.contains(target)
    }
    return result
}

It's very similar to the previous one, but I am adding tasks to a TaskGroup instead of adding numbers to the var transformed. It uses concurrency, but you probably want parallelism. TaskGroup will probably be parallel, but if you don't trust it you can still use your favourite parallelism library to make sure

import Algorithms
import Foundation

func applySomeArithmeticOperations(inputNumers: [Int]) -> Int {
... // same as above
}

func applySomeArithmeticOperationsButThisTimeItsAsyncAndExecutesOnAGlobalQueue(inputNumers: [Int]) async -> Int {
    await withCheckedContinuation { continuation in
        DispatchQueue.global().async {
            let result = applySomeArithmeticOperations(inputNumers: inputNumers)
            continuation.resume(returning: result)
        }
    }
}
3

@cukr, thank you for the example code.

Sorry, I should have said all possible arithmetic operations. For example, given 3 input numbers u, v, w:

let result = u o v o w // o is an arithmetic operator

In the above expression, each operator 'o' independently takes on one of the values +, -, *, /.

4

I just put there whatever, because it wasn't related to concurrency.

Do you want my help with that part too?

5

Thank you. No, I think I can manage it now.

1 Like