Avenious - 1 year ago 36

Swift Question

Disclaimer: new to swift.

I have a simple dice game that needs to match the number shown on dice to the tiles(ints) remaining on the board. I am able to enumerate through the array for a direct match but, if the dice show a greater number than the tiles individually I need to check if those tiles(ints), in any combination, can also match the number on dice shown.

for loops, do-while, enumerations.....head is starting to explode. Example below shows a condensed version of where i think i'm going. any help would be great.

var array = [1,2,3,4]

func roundOver () {

`var ran = Int(arc4random_uniform(7) % 7 + 1)`

for (index,value)in enumerate(array) {

if value == ran {

println("match")

} else if value != ran {

do {..........huh?

Answer

If I understand your question correctly, you need to solve the "Subset sum problem":

Given a set

`S`

and a number`x`

, is there a subset of`S`

whose sum is equal to`x`

?

This problem can be efficiently solved with "dynamic programming", as described in
the Wikipedia article. For ** small sets**, a brute-force algorithm can be used which
simply tries all possible subsets. This can be recursively written as

```
func isSummableTo(array: [UInt], _ value: UInt) -> Bool {
if value == 0 {
// We have reached the exact sum
return true
} else if array.count == 0 {
// No elements left to try
return false
}
// Split into first element and remaining array:
var array1 = array
let first = array1.removeAtIndex(0)
// Try to build the sum without or with the first element:
return isSummableTo(array1, value) || (value >= first && isSummableTo(array1, value - first))
}
```

(Here I have assumed that you work only with non-negative integers.)

For example

```
isSummableTo([1, 3, 5, 10], 6) == true
```

because 1 + 5 = 6, and

```
isSummableTo([1, 3, 5, 10], 7) == false
```

because there is not subset of the numbers 1, 3, 5, 10 that sums up to 7.