<$BlogRSDURL$>
I rock, you suck
Donate to my Beer Fund


If you enjoyed/hated my blog/have money to burn/are crazy, why not give me your money?
All you have to do is click on the button above.
No? Well, go on to the posts below, then, you prick.


Thursday, March 27, 2008
 
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;
}
Blogged with the Flock Browser

Labels: , , , , ,

 
Comments:
Post a Comment
Back

Links to this post:

Create a Link

Laughing at the cosmic gag reel since March '04!

Links
L.E.W.D (click to know more):


Fred And Phil

Fiction

Hot Babe Blogs:

Other Blogs (that are not quite as good as mine):


Unforgettables:

Recent Posts:

ARCHIVES

To Those Who Wish To Link Me:

Due to the fact that my ego is a humongous, bloated monstrousity, it is not highly unlikely that I wouldn't say no to your linking my blog, so there is no need to ask me.


Winners of Adrian Coolness Points:

The Feisty Bitch: For reasons best known to ourselves. (1)
The Feisty Bitch: For getting featured on the Sunday Times (2)
Adri: For being geeky enough to write recursive prose. (1)
Sheena: For really, really liking my blog. (1)
Sheena: For the use of her finger. (2)
Sheena: For getting on the Straits Times. (3)
Ivan: For referring to me as one of "Singapore's leading bloggers". (1)
Ivan: For coming up with the PubicLicezilla idea. (2)
The Big Fuck: For being such a big fuck. (1)
The Big Fuck: For making the miniature Badge of Lewdness. (2)
Anonymous fan: For making a cool finger. (1)
Celly: For appreciating the genius behind the Pagan Bible here. (1)
Icebreeze: For being wise enough to flatter me. (1)
Barffie: For furthering the LEWD cause by appearing in the papers. (1)
Blinkymummy: For furthering the LEWD cause by appearing in TWO papers within the space of two days, fuckin' A! (2)
Jess: For being observant enough to spot the similarity between Lewdites and Luddites. You rock, babe. (1)
Jiameei: For being my champion against anonymous hecklers. (1)


Powered by Blogger

Ablewise.com Free Classifieds - The Online Classifieds Solutions (TM)




free dating sites

Get custom programming done at GetACoder.com!