Tuesday, November 13, 2007

Tetris Overflow - On Camera

As explained in an earlier post, in the Tetris game from WEP, the score overflows. I was able to repeat this a few times and it happened each time. Now, I've got it on camera (needed a lot of takes, so I have even more practice now).

Video

Look at the score.

Monday, November 12, 2007

201%

(If you don't get it, it's a reference to a song).

Saturday, November 10, 2007

Directory

Last year, I wrote a DHTML app (in 30 minutes) for searching the directory of my college.
I parsed all of the data and wrote a Python script to turn it into a JavaScript array. With all of the student data in one JavaScript file, looking up information is extremely quick because everything is on the client and there is no server round-trip. So, I didn't even make a "Search" button - the results are returned as you type.
You can search by dorm and by floor, and send e-mails.
This year, fellow students built upon this idea and created a Directory with even more features.

Saturday, November 3, 2007

Pyget

I wrote a small program in Python for downloading files. (It is basically an interface for urllib, which does the real work). You can also use it from the command line with wget-like syntax.

It has some convenient features. If you have copied a url in the clipboard, it is automatically placed in the field, saving you a step. In the "Add..." dialog, you can specify a sequence of urls with the syntax "http://test.com/file_[0-4].zip", which expands into "http://test.com/file_0.zip", "http://test.com/file_1.zip", and so on. The most useful feature is downloading links from an html page:

Here's the code. You'll need a recent version Python and the wxPython GUI toolkit.

Friday, November 2, 2007

Quoteboard

I wrote an online quoteboard from scratch. Using only my own code makes it lightweight, and I like being able to customize every detail.
After 30 minutes planning and around 30 minutes of quick PHP/Mysql coding, I had a functional version of the site: Each quote also has a page where you can discuss it. Using xmlhttprequest, I added AJAX voting buttons that don't require a page refresh!
Today, I added some styling, which took a while, but looks nicer:

Thursday, November 1, 2007

Nondeterministic Finite Automata

For an open-ended project in my Computer Science course, I wrote a program which will take any regular expression as an input and generate a NFA for recognizing that language. It can display this NFA graphically as well as generate Prolog code for simulating it and using it to match strings. (So, if you have Prolog, you could use this as an implementation of regular expressions.)

I generate dot format files and call GraphViz to draw the graph. I use the symbol ',' to mean concatenation and enter 'a,a,b,b' instead of the traditional regexp 'aabb'. In the graphs, '.' refers to a null transition. Here are some sample inputs and outputs:

a*,b|c (a|b)* (a|b),(a|b) (Note that my handling of * is slightly incorrect because the expression must be present at least once.) Disjunction uses the '|' symbol, for example 'a|b' means a or b. Unlimited levels of nested parenthesis are supported, thanks to recursion.

I process the expression recursively by at each point dividing the input string into two parts, if possible. The string '(a|b),b' is split into (a|b) and b with the operation ',' , and the first part is then split into a and b with the operation |. If the expression is a or a*, then it will return, and work its way down. To my knowledge all complicated expressions are recognized successfully.

The Python program then will output Prolog code that can be consulted. Once consulted, the predicate parse can be used with a list to see if the string is recognized by the language.

Prolog code generated for (a|b),(a|b)
parse(L) :- start(S), 
    trans(S,L).

trans(X,[A|B]) :-
      delta(X,A,Y),
      write(X),
      write('  '),
      write([A|B]),
      nl,
      trans(Y,B).
      
trans(X,[A|B]) :-
      nulltrans(X,Y),
      trans(Y,[A|B]).
      
trans(X,[]):-
    nulltrans(X,Y),
    trans(Y,[]).
      
trans(X,[]) :- 
      final(X),
      write(X),
      write('  '),
      write([]), nl.

delta(0,a,1).
delta(0,b,2).
delta(3,a,4).
delta(3,b,5).
nulltrans(1,3).
nulltrans(2,3).
nulltrans(4,6).
nulltrans(5,6).
nulltrans(99,99).
start(0).
final(6).

Sample output of this Prolog code recognizing (a|b),(a|b):
| ?- parse([a,b]).
0  [a,b]
3  [b]
6  []

true ?

yes
| ?- parse([b,a]).
0  [b,a]
3  [a]
6  []

true ? 

(15 ms) yes
| ?- parse([b,a,b]).
0  [b,a,b]
3  [a,b]

no
| ?- parse([b]).
0  [b]