How to randomize letters correctly from an NSStrin

Question

I am creating a word scrambler and I am having issues randomizing the letters. When the letters get randomized, it doesn't make sense.

For example, the word PARK shows as AAPA. So, as you can tell it won't make sense for the user when it is time to unscramble.

Just so you know, I am using a .plist file to hold the words.

This is the code I am using to randomize the letters:

    _words = [NSMutableArray arrayWithCapacity:scramblelength];

    for (int i=0;i<scramblelength;i++) { 

    NSString *letter = [scramble substringWithRange:[scramble rangeOfComposedCharacterSequenceAtIndex:arc4random()%[scramble length]]];

Then, I am creating UIImageViews to display the scrambled words:

    if (![letter isEqualToString:@""]) {
        GameView *boxes = [[GameView alloc] initWithLetter:letter andSideLength:boxSide];
        boxes.center = CGPointMake(xOffset + i*(boxSide + kTileMargin), kScreenHeight/4*3);

        [self.scrambleView addSubview:boxes];
        [_words addObject:boxes];

What am I doing wrong here? I would like for the letters in the scrambled words to make sense.

Please help, I am stuck on this one!

Thanks!

Answer 1

When you are getting a random letter, you need to do something to remove that letter from your NSMutableArray (ie the word's letters when in order). So as you iterate through the word, each time there are fewer characters remaining. Right now, from your limited code block (the first one), it appears you might not be doing that. You want something like "[_words removeObjectAtIndex:letterIndex]" and you would also want to iterate from number of letters down to zero as you remove items from the array also: for (int i=[_words count]; i > [_words count]; i--) because you need to go from 4 letters down to 0 letters left.

Answer 2

So, I'm sure there are more efficient ways to do this, but I go by the rule of not optimizing until you need to. With that in mind, this code appears to work correctly:

- (NSString *)scrambleWord:(NSString *)word {
    NSMutableArray *letterArray     = [self letterArrayFromWord:word];
    NSMutableString *returnValue    = [[NSMutableString alloc] init];
    do {
        int randomIndex = arc4random() % letterArray.count;
        [returnValue appendString:letterArray[randomIndex]];
        [letterArray removeObjectAtIndex:randomIndex];
        if (letterArray.count == 1) {
            [returnValue appendString:letterArray[0]];
            break;
        }
    } while (YES);
    if ([[returnValue copy] isEqualToString:word]) {
        return [self scrambleWord:word];

    } else {
        return [returnValue copy];

    }
}
- (NSMutableArray *)letterArrayFromWord:(NSString *)word {
    NSMutableArray *array = [NSMutableArray array];
    for (int i = 0; i < word.length; i = i + 1) {
        [array addObject:[NSString stringWithFormat:@"%C", [word characterAtIndex:i]]];
    }
    return array;
}

Answer 3

As long as your string length will fit in 32 bits, this should be fine. If not, I would replace arc4random_uniform with a uniform random number generator in C++ and compile this as an Objective-C++ module.

The code simply iterates through the string, and swaps each composed character sequence with some random composed character sequence from the same string.

Sorry, that's what happens when you are arrogant and just type out code. Let me know if you have trouble with this one...

For much larger strings, there is a more efficient way, but this seems to do the trick.

NSMutableString category...

@interface NSMutableString (Scramble)
- (void)scramble;
@end

@implementation NSMutableString (Scramble)
static void
swapRanges(NSMutableString *string, NSRange iRange, NSRange jRange)
{
    // Need to replace the "trailing" component first
    if (NSEqualRanges(iRange, jRange)) return;
    if (iRange.location > jRange.location) {
        NSRange tmpRange = iRange;
        iRange = jRange;
        jRange = tmpRange;
    }
    NSString *iString = [self substringWithRange:iRange];
    NSString *jString = [self substringWithRange:jRange];
    [string replaceCharactersInRange:jRange withString:iString];
    [string replaceCharactersInRange:iRange withString:jString];
}

- (void)scramble
{
    for (NSUInteger i = 0; i < self.length; ++i) {
        NSRange iRange = [self rangeOfComposedCharacterSequenceAtIndex:i];
        NSUInteger j = arc4random_uniform(self.length);
        NSRange jRange = [self rangeOfComposedCharacterSequenceAtIndex:j];
        swapRanges(self, iRange, jRange);
    }
}
@end

NSString category...

@interface NSString (Scramble)
- (NSString*)scrambledString;
@end
@implementation NSString (Scramble)
- (NSString *)scrambledString
{
    NSMutableString *result = [self mutableCopy];
    [result scramble];
    return [result copy];
}
@end

Sample use...

[someMutableString scramble];

NSString *mixedUp = [someString scrambledString];

Or, if you are comfortable with C++, convert to a std::wstring, call std::random_shuffle, then convert that to a NSString. Lots less bugs when using proven, well tested code.