Bus numbers

If route numbers are restricted to strictly, say, decreasing digit strings, does it make mechanically variable signs easier to make?

Trojan RFID card

Could one create a trojan RFID card, like the MBTA's CharlieCard, which surreptitiously reads all the other RFID cards in your wallet, the reports back what it has collected the next time the trojan card is used? It might also then receive further instructions to actively perform more evil deeds on its victim cards the when it is placed back into the wallet.

Haskell compiler front-end

How can I create a tree that I can traverse to a node's parent as well as children? Do I really want to? Can I create a symbol table that points back into the parse tree to where the symbol is defined, at the same time have the parse tree point into the symbol table on each symbol's use? Is that the right way?

Larger chessboard

The chess board can be extended to arbitrary size straightforwardly. Ranks can be added in the middle. What happens if ranks are subtracted? How goes 4x8 chess? Files may be added beyond the rooks. However to preserve the corner feel of the a and h files, a thin barrier, two ranks tall, is erected beyond the rook and rook pawn. Only the knight may move through the barrier, thus extricating the rook still requires effort. There is a new opening move Ni2 and its mirror. The barrier is two ranks tall instead of one to prevent an additional diagonal attack on a1.

However, there are good reasons for not altering the size of the chess board. The regular size is balanced between large enough to allow for locality and applying lessons learned from similar positions from previous games, and small enough that any move can have effects across the board. Incidentally, these allow the construction of cool chess problems.

Compressing the Human Genome

Compressing the human genome is a worthy task because compressing better means a deeper understanding of the patterns and structure of the genome. Here are some results with popular open-source text compressors.

genome.tar 3124449280 bytes

gzip 1.3.5
real 12m35.780s
user 11m35.300s
sys 0m8.410s
genome.tar.gz 861173407 bytes

pbzip2 0.9.6, with 4 processors
real 5m3.966s
user 18m16.750s
sys 0m35.780s
Output Size: 793150501 bytes

With multiple processors, pbzip2 is faster than single-processor gzip.

7za a -m0=LZMA:d28 -mx=9 genome genome.tar
7-Zip (A) 4.44 beta Copyright (c) 1999-2007 Igor Pavlov 2007-01-20
p7zip Version 4.44 (locale=C,Utf16=off,HugeFiles=on,2 CPUs)
real 245m55.993s
user 347m56.284s
sys 1m28.416s
(Note: used 2.7 GB memory, also timing done on different machine than gzip and pbzip2, so useful only as an order of magnitude comparison)
683829237 bytes

with the option LZMA:d27 the output is 4MB larger, ie 687816321 bytes, It uses 1.3 GB memory. real 229m55.132s, user 316m36.679s, sys 0m26.043s

With 7-zip it fits on to one CD!

Dependency checking

Suppose you have a list of dependencies like for "make". Give N orderings that try to test as well as possible whether those dependencies are sufficient, where N is limited to something smaller than exhaustive search of permutations that satisfy the given dependencies.

Deletions in error-correcting codes

Deletions are a messy problem for error-correcting codes. One standard way of dealing with them is with synchronization strings. We can do better. The key is to use a short block size ECC as the first layer, short enough that we expect at most one deletion within it. Instead of scanning a sliding window for the synchronization string, we search for for a block which decodes mostly OK, possibly doing a side search for one deletion, as an erasure, or insertion within it. Each data block needs a its block number, perhaps modulo a number larger than the longest expected deletion. Another interleaved ECC layer corrects errors and erasures after deletions and insertions have been taken care of.

I wonder how DNA deals?