Sunday, October 15, 2006

Incremental flash backup tool

I recently decided that I would back up my documents to a high capacity flash disk. Thus I wrote a backup tool.
Features:
  • Dead simple. Something you'd write in an hour, so it won't mess you up by having volumes of code, weird interfaces, complicated man pages, or obscure back up formats.
  • The flash disk is a mirrored filesystem, so no special tools are required to read the backup.
  • The existing backed-up filesystem is updated if the backup command is re-issued.
  • Specified directories are recursively copied; hidden files are not copied. Thus one can flag large files that should not be backed up: make them hidden.
  • Eventually needs support for checksums, but I'm not too worried at the moment.
The program is public domain. Download and run it. Copy its example backup command line into a shell script. In my case, I use something similar to:

  % python backup.py D:\ D:\Documents D:\Code G:\Backup

(Source Code)

Sunday, August 06, 2006

Intelligent Minesweeper

A game of Minesweeper, with moves suggested by the entail module I posted earlier. The entail module contains a propositional logic inference algorithm: it lets one determine whether any given expression of binary variables follows logically from a set of assumptions:
    >>> s = AssumptionSet(['a => b => c <=> a'])
    >>> s.implies('a <=> b')
    True
    >>> s.assume('c')
    >>> s.implies('a')
    True
It is rather uncanny how complicated mathematical relationships can be derived ex nihilo using only the entail module. For the Minesweeper game, when the user chooses "Suggest Move," I add only the knowledge that the player possesses to an AssumptionSet, and then suggest a move if the logic algorithm can deduce that any given square is free of a mine. The result is a perfect deterministic minesweeper AI: if any given move on the board can be made safely, then the AI will suggest that square. If no move can be made safely, then no suggestion will be made. Note that this is also an experiment with using HTML widgets in lieu of using a widget toolkit such as wxPython, so bear with the strange appearance of the window.

(Screenshot) (EXE) (Source) (Module entail) (All public domain).

Friday, June 16, 2006

Real-time hair animation

I used the Verlet integration and relaxation method described by Thomas Jakobsen in "Advanced Character Physics" [1] coupled with the animation techniques suggested by Chang, Jin, and Yu in [2] to make a fast hair simulation. My resulting video [3] was captured in real-time. The program can actually be sped up significantly by placing bounding boxes around individual quads, vertices, and segments; however, I ran into bugs when I tried to do this, so I left that optimization out for now. The results are interesting because they indicate that in video games, hair can be animated in real-time with relative ease. The source code has been placed in the public domain.
(Video) (Writeup) (Source Code)

Saturday, June 10, 2006

Automatic Python imports with autoimp

I got sick of writing "import X" in Python. So, I created the public domain module autoimp, which imports all modules automatically:
>>> from autoimp import *
>>> os.stat('.')
>>> Image.open('test.bmp')
>>> pylab.plot([1,2],[3,4])
>>> scipy.linalg.eig([[1,2],[3,4]])
>>> ...
Thus one no longer needs to write "import X". It would take too long to load every module when one writes "from autoimp import *", so the imported modules are actually proxy objects which lazily load when they are first used.
(Module Website)

Thursday, May 18, 2006

Programming Language Productivity

Norvig [1] commented on two productivity studies by Prechelt [2] and Garret [3]. The results for the productivity of the languages isn't immediately apparent, so I extracted the relevant information as a "productivity summary" [4]. The results strongly indicate that programmers who solve a problem with fewer lines of code are more productive, irrespective of the language used. Thus languages which are more succinct could be said to be more productive.

For entertainment purposes, I solved the given problem in Python; it took me 1 hour 10 minutes, with 31 lines of code. I spent 10 minutes reading the problem, and 40 minutes fixing mistakes that I had made due to not reading the problem carefully enough. There is a lesson here...

(Productivity Summary) (My Solution)

Wednesday, May 10, 2006

Eight queens in Python

An elegant way to find all solutions to the 8-queens problem: generate all 8-castles solutions by a permutations() generator and filter the diagonals by checking that the set of diagonals represented has 8 elements. I implemented this algorithm in Python (17 lines) and C++ (66 lines).
(Python Code) (C++ Code)

Friday, April 28, 2006

Shedskin benchmarks

Shedskin [1] is an experimental Python to C++ compiler. I benchmarked it for some of the microbenchmarks in The Computer Language Shootout [2]. The results are interesting: for some benchmarks, the compiled Python code runs at nearly the speed of C.
(These benchmarks are out of date, so I removed the link).

Monday, January 23, 2006

rencode -- Reduced length encodings

A space-efficient Python serialization module based on bencode,
which can be used to decode strings from untrusted sources. Works well for complex, heterogeneous data structures with many small elements. The encodings take considerably less space than bencode, gherkin, and Recipe 415503 [1] for that use case, and this module is faster, too. (Source code), (Comparison).