Skip to content

Instantly share code, notes, and snippets.

@joelparsons
Last active December 17, 2015 20:19
Show Gist options
  • Save joelparsons/5666671 to your computer and use it in GitHub Desktop.
Save joelparsons/5666671 to your computer and use it in GitHub Desktop.
Graph search algorithm implementation of searching for words on a boggle board in objective-c
#import <Foundation/Foundation.h>
@interface Node : NSObject
@property (nonatomic, strong) NSString * letter;
@property (nonatomic, strong) NSMutableSet * adjacentNodes;
@end
@implementation Node
-(NSMutableSet *)adjacentNodes{
if(_adjacentNodes){
return _adjacentNodes;
}
_adjacentNodes = [[NSMutableSet alloc] init];
return _adjacentNodes;
}
@end
@interface Graph : NSObject
@property (nonatomic, strong) NSSet * nodes;
@property (nonatomic, strong) NSDictionary * lookupDictionary;
+(instancetype)graphForBoggleBoard:(NSArray *)board;
-(BOOL)searchForWord:(NSString *)word;
@end
@implementation Graph
+(instancetype)graphForBoggleBoard:(NSArray *)board{
NSMutableSet * nodes = [[NSMutableSet alloc] init];
NSMutableDictionary * dictionary = [NSMutableDictionary dictionary];
NSMutableArray * nodeBoard = [[NSMutableArray alloc] initWithCapacity:board.count];
for (NSArray * row in board){
NSMutableArray * nodeRow = [[NSMutableArray alloc] initWithCapacity:row.count];
for (NSString * letter in row){
Node * node = [[Node alloc] init];
node.letter = letter;
[nodeRow addObject:node];
[nodes addObject:node];
if (dictionary[node.letter]){
[dictionary[node.letter] addObject:node];
}else{
dictionary[node.letter] = @[node].mutableCopy;
}
}
[nodeBoard addObject:nodeRow];
}
NSArray * previousRow = nil;
for (NSInteger row = 0; row < nodeBoard.count; row++){
NSArray * nodeRow = nodeBoard[row];
for (NSInteger col = 0; col < nodeRow.count; col ++){
Node * currentNode = nodeBoard[row][col];
for (int i = col - 1; i <= col + 1; i++){
if (i < 0 || i >= nodeRow.count)
continue;
Node * node = previousRow[i];
if (node){
[currentNode.adjacentNodes addObject:node];
[node.adjacentNodes addObject:currentNode];
}
}
if (col > 0){
Node * node = nodeBoard[row][col - 1];
[currentNode.adjacentNodes addObject:node];
[node.adjacentNodes addObject:currentNode];
}
}
previousRow = nodeRow;
}
Graph * graph = [[Graph alloc] init];
graph.lookupDictionary = dictionary;
graph.nodes = nodes;
return graph;
}
BOOL depthFirstSearch(Node * node, NSString * word, NSInteger depth, NSMutableSet * visitedNodes){
unichar nodeLetter = [node.letter characterAtIndex:0];
unichar wordLetter = [word characterAtIndex:depth];
[visitedNodes addObject:node];
if (nodeLetter == wordLetter){
if (depth < word.length - 1) {
for (Node * adjacentNode in node.adjacentNodes){
if ([visitedNodes containsObject:adjacentNode]) continue;
BOOL found = depthFirstSearch(adjacentNode, word, depth + 1, visitedNodes);
if (found) return found;
}
}
else return YES;
}
[visitedNodes removeObject:node];
return NO;
}
-(BOOL)searchForWord:(NSString *)word{
NSString * firstLetter = [NSString stringWithFormat:@"%c",[word characterAtIndex:0]];
NSSet * firstNodes = self.lookupDictionary[firstLetter];
for (Node * node in firstNodes){
NSMutableSet * visitedNodes = [[NSMutableSet alloc] initWithCapacity:word.length];
BOOL found = depthFirstSearch(node, word, 0, visitedNodes);
if (found) return found;
}
return NO;
}
@end
int main(int argc, char *argv[]) {
@autoreleasepool {
NSArray * boggleBoard = @[
@[@"a", @"b", @"c"],
@[@"d", @"d", @"h"],
@[@"e", @"i", @"u"]
];
Graph * graph = [Graph graphForBoggleBoard:boggleBoard];
NSLog (@"Word %@", [graph searchForWord:@"chuddd"] ? @"exists" : @"doesnt exist");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment