Compute every possible combination of numbers

Question

I have 9 tiles labeled 1-9 with corresponding values. Tile 1=1, tile 6=6, etc. A user can press down tiles that equal the sum of the die. When they press confirm move, those tales can not be used anymore.

I need to compute every possible combination of numbers to check whether or not the user can go again. Currently I am computing it like this, but I'm sure there has to be a better way. allTiles contains the tiles that are still available to be computed.

What would be the best way to check for all combinations?

- (void) getCombinations {

NSMutableArray *combinations = [[NSMutableArray alloc] init];

for (int i = 0; i < [allTiles count]; i++) {
    for (int j = i + 1; j < [allTiles count]; j++) {
        for (int k = i+2; k < [allTiles count]; k++) {
            TileView *first = [allTiles objectAtIndex:i];
            TileView *second = [allTiles objectAtIndex:j];
            TileView *third = [allTiles objectAtIndex:k];
            NSNumber *total = [NSNumber numberWithInt:first.getTileValue + second.getTileValue];
            NSNumber *total2 = [NSNumber numberWithInt:
                                first.getTileValue +
                                second.getTileValue +
                                third.getTileValue];
            [combinations addObject:[NSNumber numberWithInt:first.getTileValue]];
            [combinations addObject:[NSNumber numberWithInt:second.getTileValue]];
            [combinations addObject:[NSNumber numberWithInt:third.getTileValue]];
            [combinations addObject:total];
            [combinations addObject:total2];
        }
    }
}
if ([combinations containsObject:[NSNumber numberWithInt:[self diceTotal]]]) {
    NSLog(@"STILL COMBINATION AVAILABLE");
}
else {
    NSString *message = [NSString stringWithFormat:@"Your score: %i", player1Score];
    UIAlertView *alert = [[UIAlertView alloc]
                          initWithTitle:@"No more combinations left."
                          message: message
                          delegate:self
                          cancelButtonTitle:@"Go to player2"
                          otherButtonTitles: nil];
    [alert show];
    [alert release];
}
}

Here is a a screenshot of one of scenarios where my method doesn't work. enter image description here

@GabrielePetronella that's what I was basing my code off, however I figured there may be an easier way of computing possibilities other than adding more for loops. — joshft91, Apr 13 '13 at 17:55
So, just to be clear, the player can choose any number of tiles? E.g. in your example, the player can choose three tiles (1, 3, and 5) to reach the target number (9)? — rob mayoff, Apr 13 '13 at 18:21
Do you really need a list of all the combinations? Or do you just need to know whether any combinations exist? — rob mayoff, Apr 13 '13 at 18:29
Probably just know if they exist. I added the full method of how I check to see whether the game is over or not. It's still not fully functional and I'm having trouble figuring out what would be the best way to solve this problem. — joshft91, Apr 13 '13 at 18:33

rob mayoff · Accepted Answer · 2013-04-13T19:00:15.840

In your example, there are four tiles available to the player. Whether or not to include a tile is a binary choice (YES or NO), and there are 4 such choices in this example, so there are 2×2×2×2 = 2⁴ possible combinations of tiles. In general, there are 2ⁿ combinations where there are n tiles available.

The simplest way to check for a combination that sums to your target is simply to enumerate the integers from 0 through 2ⁿ. For each integer i, write i in binary and add up the tile values of the tiles corresponding to the 1's of the binary representation.

We'll cache the tile values in a local array to avoid sending the tileValue message over and over.

static int selectedNumbersSum(unsigned int selector, int const *numbers) {
    int sum = 0;
    for (int i = 0; selector != 0; i += 1, selector >>= 1) {
        if (selector & 1) {
            sum += numbers[i];
        }
    }
    return sum;
}

static BOOL tilesCanMakeTarget(NSArray *tiles, int target) {
    NSUInteger count = tiles.count;
    int numbers[count];
    for (int i = 0; i < count; ++i) {
        numbers[i] = [tiles[i] tileValue];
    }

    for (unsigned int step = 0, maxStep = 1 << count; step < maxStep; ++step) {
        if (selectedNumbersSum(step, numbers) == target)
            return YES;
    }
    return NO;
}

- (void)checkForEndOfPlayer1Turn {
    if (tilesCanMakeTarget(allTiles, self.diceTotal)) {
        NSLog(@"STILL COMBINATION AVAILABLE");
    } else {
        NSString *message = [NSString stringWithFormat:@"Your score: %i",
            player1Score];
        UIAlertView *alert = [[UIAlertView alloc]
            initWithTitle:@"No more combinations left."
            message:message delegate:self cancelButtonTitle:@"Go to player 2"
            otherButtonTitles:nil];
        [alert show];
        [alert release];
    }
}

Incidentally, we don't usually start our getter method names with get. Your getCombinations method should probably be called checkCombinations (or something like that) since it's not even a getter. And your getTileValue method should just be called tileValue.

I agree on the name, maybe even `-allCombinations`... but conventions do change... I have an Objective C book from the late 90's that suggests using `variable` and `variable:` for a getter and a setter... seems like properties have killed that convention pretty well. — Grady Player, Apr 13 '13 at 18:52
Thanks for the response. I'm a new Objective-C programmer so some of this stuff looks a little daunting to me. How does this fit in with what I currently have? — joshft91, Apr 13 '13 at 18:56
Key-Value Coding requires setters to start with `set` and getters to be unprefixed (except `BOOL` getters, which can have an `is` prefix). — rob mayoff, Apr 13 '13 at 18:56
[*Cocoa Core Competencies:* Accessor method](http://developer.apple.com/library/ios/#documentation/General/Conceptual/DevPedia-CocoaCore/AccessorMethod.html#//apple_ref/doc/uid/TP40008195-CH2-SW1) — rob mayoff, Apr 13 '13 at 19:01
Thank again for the reply. I"ll have a look at this in more detail when I have a chance. — joshft91, Apr 13 '13 at 19:03

Compute every possible combination of numbers

1 Answers1