Latest Changes to CryptoQuip in Cocoa
I added a little twist to my Cocoa CryptoQuip solver - I made sure that the PuzzlePieces were unique, and then I sorted them in the Quip by the number of possible plaintext words that each had. Why? Well, the duplicates are just unnecessary work, and in my test quip, I had one. Just no need to do that. The sorting by the number of possible plaintext words is meant to reduce the number of iterations by "pinning" the most complete Legend as early as possible. If I have to cycle through 30 words first, and then 1 word, it's faster to pin the one word, and then search the 30. Not a lot faster, but as the searching grows, it makes a difference.
The way to guarantee uniqueness amongst the PuzzlePieces is to change the code for initialization of the Quip to look for duplicates first, and then only add the unique ones:
- (id) initWithCypherText:(NSString*)text where:(unichar)cypher equals:(unichar)plain usingDict:(NSArray*)dict { if (self = [self init]) { // save the important arguments as ivars [self setCypherText:text]; [self setStartingLegend:[Legend createLegendWhere:cypher equals:plain]]; // now let's parse the cyphertext into puzzle pieces PuzzlePiece* pp = nil; for (NSString* cw in [text componentsSeparatedByString:@" "]) { if ([cw length] > 0) { if ((pp = [PuzzlePiece createPuzzlePiece:cw]) != nil) { [self addToPuzzlePieces:pp]; } } } // if we have a dictionary of words, use them if (dict != nil) { for (NSString* pw in dict) { for (PuzzlePiece* pp in [self getPuzzlePieces]) { [pp checkPlaintextForPossibleMatch:pw]; } } } } return self; }
to:
- (id) initWithCypherText:(NSString*)text where:(unichar)cypher equals:(unichar)plain usingDict:(NSArray*)dict { if (self = [self init]) { // save the important arguments as ivars [self setCypherText:text]; [self setStartingLegend:[Legend createLegendWhere:cypher equals:plain]]; // now let's parse the cyphertext into puzzle pieces PuzzlePiece* pp = nil; for (NSString* cw in [text componentsSeparatedByString:@" "]) { if ([cw length] > 0) { if ((pp = [PuzzlePiece createPuzzlePiece:cw]) != nil) { if (![[self getPuzzlePieces] containsObject:pp]) { [self addToPuzzlePieces:pp]; } } } } // if we have a dictionary of words, use them if (dict != nil) { for (NSString* pw in dict) { for (PuzzlePiece* pp in [self getPuzzlePieces]) { [pp checkPlaintextForPossibleMatch:pw]; } } } } return self; }
which works wonderfully because we have already built the -isEqual: method for the PuzzlePiece:
/*! This method returns YES if the argument represents the same puzzle piece as this instance. That is not to say that they are identical, but that they have the same cyphertext, and same list of possible plain text words. */ - (BOOL) isEqual:(id)obj { BOOL equal = NO; if ([obj isKindOfClass:[self class]] && [[self getCypherWord] isEqual:[obj getCypherWord]] && [[self getPossibles] isEqualToArray:[obj getPossibles]]) { equal = YES; } return equal; }
Now to do the sorting we needed to add a little more code. The trick is to use the NSMutableArray's ability to sort it's content with the -sortUsingSelector: and then the key is to have the right selectors for the objects. I decided to make it pretty simple, and I implemented two versions of the -compare: method:
/*! This comparison method will compare the lengths of the cypherwords so that you can use this method to sort the puzzle pieces on the lengths of the words for some attack. */ - (NSComparisonResult) compareLength:(PuzzlePiece*)anOther { NSUInteger me = [[self getCypherWord] length]; NSUInteger him = [[anOther getCypherWord] length]; if (me < him) { return NSOrderedAscending; } else if (me > him) { return NSOrderedDescending; } else { return NSOrderedSame; } } /*! This comparison method will compare the number of possible plaintext matches for the argument and this instance to see who has more. This is useful in sorting the puzzle pieces on the number of possible matches in the attack. */ - (NSComparisonResult) comparePossibles:(PuzzlePiece*)anOther { NSUInteger me = [self countOfPossibles]; NSUInteger him = [anOther countOfPossibles]; if (me < him) { return NSOrderedAscending; } else if (me > him) { return NSOrderedDescending; } else { return NSOrderedSame; } }
With these, I'm able to easily sort the puzzle pieces by the number of their possible plaintext matches with:
// sort the puzzle pieces by the number of possible words they match [[self getPuzzlePieces] sortUsingSelector:@selector(comparePossibles:)];
With these changes, the time to solve my test case went from 0.21 sec to 0.18 sec. Not quite what I'd hoped, but I'm not done, either. I believe I'm on the right track, but I need to further limit the search space, and when that is done, I hope to be well under the 0.10 sec mark. Now that would be cool!