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).

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)

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)

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)

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)

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).

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).

Allegro Quick Reference in Japanese

The Allegro Quick Reference guide that I wrote in 2002 [1] has been translated into Japanese [2] by Ohsawa Hirotaka. Cool.

Search the Web in Python

Query 6 search engines in Python. (Module website).

MPI matrix multiplication and inversion

MPI matrix multiplication and inversion routines, written for a physics class that I took last year. The code is modular, and more flexible than the matrix multiplication codes I found on the Web (I couldn't find any simple MPI matrix inversion routines on the Web). The PDF document is public domain. (Algorithms and Code).

See also: ScaLAPACK.

Moore's law

For the past 5 years, CPU speeds have been increasing roughly linearly. That's right, for processor speeds, Moore's law does not currently apply.

FFT polynomial multiplication

It's easier than you might think:

>>> def fft_mul(C1, C2):
...   d = len(C1)+len(C2)-1
...   c1 = FFT.fft(list(C1) + [0] * (d-len(C1)))
...   c2 = FFT.fft(list(C2) + [0] * (d-len(C2)))
...   return list(FFT.inverse_fft(c1*c2)[:d].real)
...
>>> fft_mul([1,2,3],[4,5]) # (1+2*x+3*x**2)*(4+5*x)
[4.0, 13.0, 22.0, 15.0]

Takes O(n logn) time. The idea is to right pad each polynomial with enough zeros so that the cyclic convolution becomes a noncyclic convolution. For more speed, pad c1 and c2 so each has power-of-2 length. (Source Code).

I posted the algorithm [1] on Wikipedia (alternate link: [2]).

Trigonometry proved

Common trigonometric identities, proved in one page.

pysam -- Python I2P SAM library

A Python I2P SAM library, emulates the Python socket module. I haven't updated it in a while, but it works. (Main Page).

Hogwarts Security

Wow. I thought I'd seen it all. Then I find the world's most famous cryptographer talking about security in the sixth Harry Potter book. Yes, I'm talking about Bruce Schneier, author of Applied Cryptography. That made me smile. The guy is also a judge for a proposed Tor GUI. Which makes me wonder: is he now interested in anonymous networks?

Propositional logic in Python

Propositional logic inference via compressed truth tables. Module entail is presumably slower than your industrial-grade C inference algorithm, but logical statements are given as Python expressions, and entailment can be checked at the interactive prompt. This makes the module easy to use, and fun. (Source Code).

Ventiloquate

Hyperventilate + loquacious = ventiloquate, to freak out and speak too much, too fast, and use way more breath than is actually needed to explain the idea. I assumed that this word existed, but I guess it actually doesn't.

Basic factorization algorithms

A paper which gives pseudocode and the reasoning behind some basic factorization algorithms: Fermat factorization, Pollard rho, Pollard p-1, and Brent's method. Public domain. (PDF document).

Memoization with cache clear on return of last function call

Memoization is nice, but in dynamic programming, it can eat up ever-increasing amounts of memory as your memoized function is called with various arguments. A simple solution is to clear the cache when the last function call returns. (Python Recipe).

mw2html -- Export Mediawiki to static, traditional website

mw2html is a Python program which exports a Mediawiki site to a traditional-looking HTML site. No indices are generated, and Wikipedia sidebars and extra formatting are removed to give a simple, streamlined site (you can substitute in your own sidebars if you wish). The outputted HTML source code is Monobook-specific and rather verbose at the moment. But the sites thus exported don't look bad. (Source code).