What's it all about, Alfie?

This morning I took a little time to bring the pattern matching code from the Clojure and Swift codebases of the Quip solver to the ObjC version because I noticed the other day that the ideas of the pattern matching were added after the ObjC version was working, and I hadn't back-filled them to the older code. I know it won't make a difference in the execution time, as this is all done before the attack is started, but the old code really was a mess, and the new code had to be cleaner.

The original code had the following method on the CypherWord:

- (BOOL) matchesPattern:(NSString*)plaintext
{
    BOOL  match = YES;
 
    // make sure that we have something to work with
    if (match && (([self getCypherText] == nil) || (plaintext == nil))) {
        match = NO;
    }
 
    // check the lengths - gotta be the same here for sure
    if (match && ([[self getCypherText] length] != [plaintext length])) {
        match = NO;
    }
 
    /*
     * Assume that each pair of characters is a new map, and then test that
     * mapping against all other cyphertext/plaintext pairs that SHOULD match
     * in the word. If we get a miss on any one of them, then we need to fail.
     */
    if (match) {
        unichar    cypher, plain, c, p;
        NSUInteger len = [plaintext length];
        for (NSUInteger i = 0; (i < len) && match; ++i) {
            // get the next possible pair in the two words
            cypher = [[self getCypherText] characterAtIndex:i];
            plain = [plaintext characterAtIndex:i];
            // check all the remaining character pairs
            for (NSUInteger j = (i+1); (j < len) && match; ++j) {
                c = [[self getCypherText] characterAtIndex:j];
                p = [plaintext characterAtIndex:j];
                if (((cypher == c) && (plain != p)) ||
                    ((cypher != c) && (plain == p))){
                    match = NO;
                    break;
                }
            }
        }
    }
 
    return match;
}

And it worked because it checked each pair of characters in the plaintext and cypher text, and looked for mismatches... but it wasn't very clean, and the same scanning had to be done on the same word over and over. So it wasn't all that efficient.

Then I added a class method to CypherWord to generate the pattern:

+ (NSString*) createPatternText:(NSString*)text
{
    const char *src = [[text lowercaseString] UTF8String];
    NSUInteger  len = [text length];
    const char *ascii = "abcdefghijklmnopqrstuvwxyz";
    char        pattern[255];
    for (NSUInteger i = 0; i < len; ++i) {
        pattern[i] = ascii[strchr(src, src[i]) - src];
    }
    pattern[len] = '\0';
    return [NSString stringWithUTF8String:pattern];
}

In the setter we then added:

- (void) setCypherText:(NSString*)text
{
    _cyphertext = text;
    _cypherSize = [text length];
    _cypherPattern = [CypherWord createPatternText:text];
}

So that setting the CypherText set the length and the pattern as well. Not bad at all, and the overhead is minimal for the puzzles we're dealing with.

At this point, we can then re-write the -matchesPattern: to be:

- (BOOL) matchesPattern:(NSString*)plaintext
{
    return ([self getCypherText] != nil) && (plaintext != nil) &&
           ([self length] == [plaintext length]) &&
           [[self getCypherPattern] isEqualToString:[CypherWord
             createPatternText:plaintext]];
}

and leverage the fact that we have instance variables for the length and pattern, and still use all the short-circuit techniques to make sure that we don't make a bad call, or sloppy comparison.

Nothing amazing, but it's nice to get this version up to the same design as the others.

This entry was posted on Tuesday, April 2nd, 2019 at 11:20 am and is filed under Cocoa Coding. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.