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.
Friday, April 18, 2008
Scramble or hacking?
Some time ago, I was arguing with my colleagues about which required more intelligence: writing a program that could cheat at Scramble? Or winning at Scramble? Naturally, I took the stand that writing programs requires way more intelligence than playing some word-finding game. My friend, being a rather contentious guy, told me that I was biased because I am a programmer and that he respected the top scramble players because we couldn't do what they did, blah blah.
I said that all that scramble required was memory and basic pattern recognition coupled with the digital dexterity required to type words fast, while writing programs required a higher level of intelligence and the ability to understand what was required to solve that problem (i.e. problem abstraction). I told him that the skill set required to play scramble wasn't that much different from that required to play minesweeper, and that since I could hit timings of 80+ seconds on minesweeper, I could probably also play scramble well with practice. He didn't buy it, even though he's also a programmer. Well, I've written a program that could cheat at scramble. I've also been playing scramble and I've improved to the point where I can get to the top 10 positions.
To sidetrack a little bit, the main game in scramble has at least 300+ players playing on the same board at any one time, so it is really not that easy to own at the game.
However, I can actually prove my point with a simple observation. Let's take the intelligence quotient required to play well at scramble as X. So if you play well at scramble, all we can conclude is that you have at least an intelligence quotient of X. Now, let's posit that the intelligence quotient required to write a program that cheats at scramble is Y, as yet an unknown quantity. However, we observe that, since the program is able to attain better results than a human player (my program is able to get all the answers on the board within 1 second, while the average good human player plays a 3 minutes game and usually attains sub-perfect results, but let's forget the obvious disparity for now), the program itself has at least an intelligence quotient of X. If an entity with an intelligence quotient of Y is able to create an entity with an intelligence quotient of X, does it not logically follow that the creator is smarter than the creation?
I end this post with a challenge illustrating the above for those programmers who still disagree. You're probably smart enough to write a scramble solver. But are you smart enough to write a program that can write a scramble solver? (QED)
p.s. Note that I'm not saying that people who are good at scramble are less intelligent than me (though they probably are, heh heh). I'm just saying that of the two tasks, writing a scramble solver and solving scramble, writing a scramble solver requires higher intelligence.
p.p.s. If you come to me with a program that prints the source code for a scramble solver, I... would really not know what to say to you.
[Update] I spoke with the aforementioned colleague again and he pointed out a flaw in my previous reasoning, namely that it takes an entity with a higher level of intelligence to create an entity of a certain level of intelligence. Basically, if one believes, as I do, that humans will someday birth artificial intelligences greater than themselves, then one must believe that an inferior intelligence should be capable of creating a superior one. My bad.
I still think the second illustration is valid, i.e. the fact that one can write a scramble solver but cannot write a scramble solver writer implies that the former task is less complex and hence, requires less intelligence to accomplish.
The #1 purveyor of old, old, torrents. The only tracker site at which you can be almost absolutely assured of the availability of seeds. Fuck you, CRIA!
After struggling for 2 days to make some Javascript and CSS display code work on all versions of Internet Explorer ("overflow: hidden", anyone?), I had gotten increasingly frustrated. Today, in the office, after IE 8 refused to acknowledge what Javascript was trying to tell it*, I finally blurted out something that precipitated some merriment among the colleagues:
"Firefox is open-source! Go copy their code, for gods' sake!"
This goes out to all the engineers and programmers working on IE 8, who I know (hope?) are probably trying hard to address these issues.
In other news, I recently met with the ThinkingPHP.org guy, Felix Geisendörfer. If you're a PHP geek, you should know the name. Cool guy.
*IE 8 was listening to his Zune and whistling while Javascript spoke till she was blue in the face.
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. :)
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; }
/*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);
/*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;
Yesterday, my friend directed me to this YouTube video. I've heard the original before and wasn't much impressed with it, but this chick was something else. Her voice has a majestic* quality which was absent in the original singer's voice but essential for this song. You see, the title of this song is 女爵, which approximately means "Female Lord", though Marquis would probably be a closer literal translation. Surprisingly, she did not win the contest, which means either that the other contestants were from the angelic or demonic choir, or that the judges were a bunch of morons who have no taste whatsoever.
In case you were wondering, yes, I define people who have taste as people who like exactly what I like. Obviously.
Contrast this with the original.
*I actually meant 霸气, but I'm not sure how one translates that.
I've started using the Flock browswer and, being a geek and a man, I'm naturally curious about the vital question: How fast can it go before it breaks? So let's wait and see.
Anyway, here's some interesting stuff about Flock.
It's based on the Firefox code base. If you're not a geek, that means that it's a modified version of Firefox.
Related to point (2), the integration is pretty nifty. For example, if you integrate your Facebook account with Flock, you get a feed of all your "friends" in what they call a People Sidebar. This presumably makes you all feel really informed and up to date, because you're a bunch of lonely people. However, I digress.
If you integrate your Flickr and/or YouTube account with Flock, it can show you streams of media from those sites in your Media Bar. This helps to fill up that gaping emptiness you feel inside.
If you integrate any of your blogging accounts (even Xanga and LiveJournal), you can blog anytime by right-clicking in whatever site you happen to be visiting. Flock even adds the link to that site for you. This has a two-fold purpose.
It aids untalented and overly enthusiastic bloggers in filling up the internet with boring, ungrammatical posts about whatever inane thoughts or boring sites they happen to be entertaining or visiting at the moment.
It helps to lower the productivity of the aforementioned untalented but enthusiastic bloggers.
I am writing this post on Flock (screenshot below). :)
I posted the screenshots to Flickr using Flock. (screenshot below). :)
If you close the sidebar and the Flock toolbar, you're pretty much left with Firefox.
Verdict so far:
It's convenient, if you're like, still in school and have tons of time for social networking sites and blogging or if you're running a startup and thus have tons of time for social networking sites and blogging. Otherwise, it's mostly just eye-candy on good ol' Firefox. It's been fun so far, though.
For an otherwise intelligent lass, she seems to turn into a raving 'tard when she's with her boyfriend (like many other chicks). I am at a loss to explain this phenomenon. If you are reading this, DiDa, would you and your pilot bloke care to participate in a scientific investigation of this anomaly? *snigger*
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: