Hacking Scramble in C
Recently, I've been playing this game on facebook called Scramble. It's basically an online version of Boggle. I noticed that there were a group of players who consistently had way, way higher scores than the rest of the players. Naturally, there were accusations of cheating, but how would you determine whether someone was cheating?

Well, the easiest way in this case was to also attempt cheating and see what the limits of it are. So I googled around for a cheat and found this solution implemented in Ruby. I ran it and thought it was rather slow, so I decided to implement my own cheat in the fastest language of them all.

C! I've had precious little opportunity to hack in C since graduating anyway, so I thought this would be a good opportunity to get in some practice. So anyway, it runs quite a bit faster than the Ruby solution (less than 1 second for a dictionary with 151000~ words), but it doesn't calculate the total score and it doesn't output stuff like "found word:". On the plus side, though, you don't need to run it everytime the board refreshes and thus suffer the overhead of loading the dictionary everytime.

Of course, it was relatively easy to win using the program against non-cheaters, but like that Ruby hacker said, it takes all the fun out of the game. Anyway, my verdict is that the players I was talking about were definitely cheating. Some of them could almost keep up with me despite the fact that I did not even have to look for the words on the board. No way there are more than one in a million people capable of beating a computer for speed at finding words on the board.

I don't grok Ruby, so I can't really tell why there's a difference in speed, but my guess would be that it's because Boggler.rb solves the board by doing a board traversal while scramblecheat.c tries to match words to the board.

One last point before the code itself. I did not provide for the "Qu" tile, but since this is a proof of concept, I don't care to provide an edge case for it. Interested parties can solve that for themselves. The code was compiled on Linux using gcc-4.1.2 and no, I'm not providing binaries. Oh, and you can do whatever you like with the code, including stripping it for spare parts and selling it. :)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BS 4
#define MAXLEN 8

void resetuse(int usearray[BS][BS]);
void startboard(char boardin[(BS*BS)+2], char board[BS][BS]);
int findword(char *word, char board[BS][BS], int usearray[BS][BS], int wlen);
int findrest(char *word, char board[BS][BS], int usearray[BS][BS], int wlen, int pos, int x, int y);

int main(int argv, char *argc[]){
	int c,lines=0,maxchars=0,currentlen=0,wlen;
	int i,j,k,l;
	char **dictionary;
	char board[BS][BS];
	char boardin[(BS*BS)+2];
	int bcount=0,getout=0;
	int sa=(int)'a';
	int sz=(int)'z';
	int usearray[BS][BS];
	FILE *fp=NULL;
	if(argv!=2){
		printf("Usage: scramblecheat <dictionary filename>\n");
		return 0;
	}

	if(!(fp=fopen(argc[1],"r"))){
		printf("Could not open %s.\n",argc[1]);
		return 0;
	}

	printf("Finding maximum word length and number of words...");
	/*find the number of lines and maximum string length*/
	while((c=fgetc(fp))!=EOF){
		if((unsigned char)c=='\n'){
			lines++;
			currentlen=0;
			continue;
		}
		currentlen++;
		if(currentlen>maxchars)
			maxchars=currentlen;
	}
	maxchars+=2;

	printf("Done.\n");
	printf("Maximum word length = %i\nNumber of words = %i\n",maxchars-2,lines);
	rewind(fp);

	/*preparing dictionary*/
	printf("Preparing dictionary...");
	if(!(dictionary=(char **)malloc((size_t)(lines*sizeof(char *))))){
		printf("\nFailed to allocate memory for dictionary. Exiting.\n");
		return 0;
	}
	for(i=0;i<lines;i++){
		if(!(dictionary[i]=(char *)malloc((size_t)(maxchars*sizeof(char))))){
			for(j=i-1;j>=0;j--)
				free(dictionary[j]);
			free(dictionary);
			printf("\nFailed to allocate memory for dictionary words. Exiting program.\n");
			fclose(fp);
			return 0;
		}
		if(!fgets(dictionary[i],maxchars,fp)){
			for(j=i;j>=0;j--)
				free(dictionary[j]);
			free(dictionary);
			printf("\nFailed to form dictionary at line %i. Exiting program.\n",i+1);
			fclose(fp);
			return 0;
		}
		/*get rid of newline*/
		for(j=0;j<maxchars-1;j++){
			if(j==maxchars-2)
				dictionary[i][j]='\0';
			if(dictionary[i][j]=='\0')
				break;
			if(dictionary[i][j]=='\n'){
				dictionary[i][j]='\0';
				break;
			}
		}
	}
	fclose(fp);
	printf("Done.\n");

	/*get board*/
	while(1){
		printf("Enter board letters in small caps in the order left to right followed by top to bottom or enter an empty board to quit: ");
		fgets(boardin,(BS*BS)+2,stdin);
		/*get rid of newline, make sure length of string is correct*/
		for(i=0;i<(BS*BS)+2;i++){
			if(i==(BS*BS)+1)
				boardin[i]='\0';
			if(boardin[i]=='\0')
				break;
			if(boardin[i]=='\n'){
				boardin[i]='\0';
				break;
			}
		}
		if((int)strlen(boardin)==0){
			printf("Thanks for using the scramble cheat, you disgusting creature.\n");
			break;
		}
		else if((int)strlen(boardin)!=BS*BS){
			printf("Wrong board size! Please try again! Cheat with intelligence!\n");
			continue;
		}

		for(i=0;i<BS;i++){
			for(j=0;j<BS;j++){
				/*check for invalid chars*/
				if(!((int)boardin[bcount]>=sa && (int)boardin[bcount]<=sz)){
					printf("Invalid characters in board! Try again! Cheat with intelligence!\n");
					getout=1;
					bcount=0;
					break;
				}
				board[i][j]=boardin[bcount];
				bcount++;
			}
			if(getout){
				break;
			}
		}
		bcount=0;
		if(getout){
			getout=0;
			for(i=0;i<BS;i++)
				for(j=0;j<BS;j++)
					board[i][j]='0';
		}

		/*generate words*/
		/*for each word in dictionary, try to find it in the board*/
		for(i=0;i<lines;i++){
			resetuse(usearray);
			wlen = strlen(dictionary[i]);
			if(wlen>MAXLEN)
				continue;
			if(findword(dictionary[i],board,usearray,wlen))
				printf("%s\n",dictionary[i]);
		}

	}

	/*cleaning up. always clean up after a good job*/
	for(i=0;i<lines;i++)
		free(dictionary[i]);
	free(dictionary);


	return 0;
}

/* reset usearray */
void resetuse(int usearray[BS][BS]){
	int i,j;
	for(i=0;i<BS;i++)
		for(j=0;j<BS;j++)
			usearray[i][j]=0;
}

/*tries to find specified word on board*/
int findword(char *word, char board[BS][BS], int usearray[BS][BS], int wlen){
	int i,j,found=0;

	for(i=0;i<BS;i++){
		for(j=0;j<BS;j++){
			if(board[i][j]==word[0]){
				usearray[i][j]=1;
				if((found=findrest(word,board,usearray,wlen,1,i,j)))
					return found;
				usearray[i][j]=0;
			}
		}
	}
	return found;
}

/*tries to find the rest of the word*/
int findrest(char *word, char board[BS][BS], int usearray[BS][BS], int wlen, int pos, int x, int y){
	int found=0;
	/*word found*/
	if(pos==wlen)
		return 1;
	
	/*try x-1,y-1*/
	if(x-1>=0 && y-1>=0){
		if(!usearray[x-1][y-1] && board[x-1][y-1]==word[pos]){
			usearray[x-1][y-1]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x-1,y-1)))
				return found;
			usearray[x-1][y-1]=0;
		}
	}
	/*try x,y-1*/
	if(y-1>=0){
		if(!usearray[x][y-1] && board[x][y-1]==word[pos]){
			usearray[x][y-1]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x,y-1)))
				return found;
			usearray[x][y-1]=0;
		}
	}
	/*try x+1,y-1*/
	if(x+1<BS && y-1>=0){
		if(!usearray[x+1][y-1] && board[x+1][y-1]==word[pos]){
			usearray[x+1][y-1]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x+1,y-1)))
				return found;
			usearray[x+1][y-1]=0;
		}
	}
	/*try x-1,y*/
	if(x-1>=0){
		if(!usearray[x-1][y] && board[x-1][y]==word[pos]){
			usearray[x-1][y]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x-1,y)))
				return found;
			usearray[x-1][y]=0;
		}
	}
	/*try x+1,y*/
	if(x+1<BS){
		if(!usearray[x+1][y] && board[x+1][y]==word[pos]){
			usearray[x+1][y]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x+1,y)))
				return found;
			usearray[x+1][y]=0;
		}
	}
	/*try x-1,y+1*/
	if(x-1>=0 && y+1<BS){
		if(!usearray[x-1][y+1] && board[x-1][y+1]==word[pos]){
			usearray[x-1][y+1]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x-1,y+1)))
				return found;
			usearray[x-1][y+1]=0;
		}
	}
	/*try x,y+1*/
	if(y+1<BS){
		if(!usearray[x][y+1] && board[x][y+1]==word[pos]){
			usearray[x][y+1]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x,y+1)))
				return found;
			usearray[x][y+1]=0;
		}
	}
	/*try x+1,y+1*/
	if(x+1<BS && y+1<BS){
		if(!usearray[x+1][y+1] && board[x+1][y+1]==word[pos]){
			usearray[x+1][y+1]=1;
			if((found=findrest(word,board,usearray,wlen,pos+1,x+1,y+1)))
				return found;
			usearray[x+1][y+1]=0;
		}
	}
	return found;
}

Labels: C, cheat, facebook, geek, hacking, scramble

  ¶
Permalink

If you don't like what I say, why not subscribe me for some porn?