Recent News
Added Sworderation
I've added a game I worked on in 2004 -- Sworderation -- to the games section. I just played through it again, and it's still fun. I hope you think so too.
ICFP 2010
This year, I took part in the ICFP Programming Contest as part of the team "cbv" (Cult of the Bound Variable). It was my first experience with a long-form programming contest, and I had a good time -- probably because the whole team was so fun to work with.
The rest of this post will make very little sense unless you read through the task description for the contest. Briefly, the contest involved creating systems of linear inequalities on matrix products (called "cars"), and matrices that satisfied these systems of inequalities (called "fuel"). Both cars and fuels needed to be encoded in trinary (base-three) strings, with the fuels further encoded as a network of 2-in 2-out trinary logic gates.
Over the course of the contest I wrote a few solvers (simple randomized search and exhaustive enumeration) that could generally succeed on 2x2's and the occasional 3x3 solution, as well as an ILP-based solver that could find almost all 1x1 solutions in a few seconds. These weren't the heaviest solvers we deployed, but they did manage to mop up probably 60-65 percent of the cars submitted to the contest.
However, probably the most useful thing I did during the contest was to write our second fuel-encoding program. It was about 3am Saturday; I had just gotten home and was taking a quick shower before bed, thinking about the contest. At this time, we already had a perfectly serviceable encoder which, unfortunately, required something between seven and fifteen gates for each trit. The large number of gates was a result of our encoding strategy relying on lots of constant generators.
What I realized in the shower was that, with the proper back-edges, the only values you care about are those your gates produce on the first tick. And -- better yet -- on the first tick you get as many zeroes as you want (back-edges from other gates) for free. I decided this would probably be my last real contribution to the team, so I set to work, finishing up around 10am (and -- as expected -- destroying myself for the remainder of the competition). In a fit of not-quite-movie-referencing, I called the final product gates motel.
Overview
Gates motel encodes a string of n trits using between 6 + n and 7 + 2n gates. Six of these gates are a zeroer (whatever in, zeroes out) to force a known input stream. Figuring out the server's input beyond the first 17 trits (X::X is a handy factory, by the way) would have allowed these six gates to be removed. The runtime of the encoder is O(n2), though an O(n) seems doable if one is clever.
You can download the source here. I describe the gist of the algorithm below.
The Problem
The goal of a fuel encoding program is to take a given string of trinary numbers and create a network of 2-in, 2-out logic gates to encode the string. This is complicated by three tricky things. The first tricky thing is that the only type of gate allowed is one that takes numbers x and y and outputs x - y and xy-1. Here's a picture of one of these fellows:
Input and output are handled through a special 0-in 1-out "input from world" gate and a special 1-in 0-out "output to world" gate. The second tricky thing is that no fan-out is allowed (that is: each input connects to exactly one output and each output connects to exactly one input). The third tricky thing is that the values appearing on the input gate each tick are unknown.
Gates are executed in a fixed order you get to choose (in my pictures this will always be top-to-bottom). When a gate is executed, it recomputes its output values from its input values. The outputs of all gates are initialized to zero at the beginning of execution.
As an example, this circuit, due to jcreed, takes as input an arbitrary string and produces a string of zeros:
The Algorithm
Gates motel builds an encoding circuit top-to-bottom, chunk-by-chunk. Before I get into how the details, let me introduce you to six special groups of gates:
The Z group is the aforementioned zeroer. One will be used in every circuit.
The remaining groups will be selected based on the input string. Each group has two inputs and two outputs. The left output is the "control" output. Each block is designed so that on the first tick the control output will take a specific value. The right output is the "junk" output. It takes an arbitrary value. The left input is the "junk" input. It will take a known value from the portion of the circuit above this group. The right input is the "control" input. Each group is designed such that by setting the control input to 0,1, or 2 the control output will assume 0,1, and 2 (in some permutation, which may change per-tick).
Additionally, given a certain "junk" input and a "control" input of zero, it is possible to get 0, 1, or 2 on the "control" output by choosing groups as follows:
| Control output | ||||
| 0 | 1 | 2 | ||
| Junk input | 0 | E | 1 | 2 |
| 1 | 0 | E | N | |
| 2 | 0 | N | E | |
Gates motel encodes a string of trits by building a chain of these groups, one group per trit. For instance, this chain happens to encode the string 0220:
What if we wanted to encode 02201? Notice that because of the "control output is dependent on control input" property, supplying input x to the last group after tick 1 selects the output of the first group after tick 5:
Of course, the sign of x and the offset d are not known -- but we can simply simulate the circuit thrice to discover them. In this case, an input of 1 is required.
Also by simulation, we can determine that when running the first tick the right output of the current last group will be 2. So we need to add a group that will take a 2 on its junk input and a zero on its control input and produce a 1 on its control output. It turns out that N is such a group:
So this is an encoding of 02201.
The Groups
What are these magical groups? Here they are:
Notice that there is one special case to handle here: when the final group is a 0, an extra gate needs to be wired in between the junk output and the control input to ensure that it actually gets a zero on the first tick.
(Note: figures in this page available in a monolithic svg file if you are interested.)
wmiirc and Disks
(From the not-useful-unless-you-use-Linux-like-I-do department.)
So, I've been using wmii as the window manager on my laptop. Other than changing its default meta key to be the winkey (I should really do something about that branding), setting it to launch uxterms, configuring it to show CPU and battery info, and setting up pidgin to change a tag color on new messages, I haven't had to change its default settings at all.
That may seem like a lot, but in the world of "nonstandard" window managers, well, it isn't. Programmers (the probable main consumers of -- and face-slappingly-obviously main producers of -- such WMs) are picky people. Indeed, the fact that I didn't have to edit the source code to do any of this is right civilized! (Unlike switching the meta key in, say, Fluxbox.)
However, I did manage to do something stupid when performing that second-to-last tweak.
First some background:
wmii has a status line at the bottom of the screen.
In the wmiirc script there is a function -- status() -- whose output is pasted into the lower right at some frequency.
To display battery information you simply create a program (likely a shell script) to echo the information you'd like displayed and have status() call it.
I learned as much from this forum post, which also includes a handy script to produce exactly the sort of info I wanted to display.
Thus, I adapted this script to my needs and it has been quietly working ever since.
But my hard drive has been being accessed every five seconds (even when the computer is apparently idle) ever since I set that script up. Turns out that here-documents in bash create temp files. Creating temp files is disk activity. Disk activity makes kjournald decide to write a journal every five seconds. Which is probably not good for the disk, definitely not good for battery life, and quite annoying. Here's my version with that problem fixed.
By the way, should you find yourself in a similar pickle, echo '1' > /proc/sys/vm/block_dump.
It will produce kernel messages (viewable by dmesg -- you probably want to turn off your system logger while doing this) which will let you know who is causing blocks to need writeback.
SIGGRAPH Panic
(Reported far after the deadline.)
SIGGRAPH is crazy. What do you do when you need more space to edit your video? Well, to be fair, I had those backed up on another computer. Still, it was the most convenient spare 10+ gig.
And kdenlive is quite buggy (not old days cinelerra bad, but...). I've resisted up to now, but I may have to write my own nonlinear video editor. Or maybe try blender's built-in editor. The key is to write up a library that can load and seek video files in a frame-accurate way, with minimal pre-processing and memory overhead.
Dead-Bugging a QFP32
This morning I spent a few hours soldering a QT1103. Now, the QT1103 comes in a QFP32 form factor -- a form factor which was almost certainly never meant to be soldered by hand, and, just as certainly, never meant to be soldered without a nice little footprint of tinned smd pads. But you can connect to them, so I had read, by flipping 'em on their back and soldering small wires to each pin, the result of which you see above. While this may look like a terrible job (a) there aren't any bridges and (b) this is really really small -- these wires are individual strands of a stranded copper wire.
Of course, I have yet to see if the device will actually work after I went to all this trouble (I could have cooked it, after all). But whatever the outcome, it was certainly the most fiddly soldering job I've ever done. I begin to see why people pay $20-$40 to have a PCB made.
SIGGRAPH Day 5
Well, that's it. The end.
I gave my talk today, and people seemed to appreciate it (and the presentation software). It would be cool if someone else started using my presentation style, but I doubt it will happen. On the plus side, this was a fully morally-correct presentation: linux and my own presentation software -- no non-free taints.
I also got my final sticker sheets: TCHOW in color + some 'redacted' stickers to place over my laptop's hard-to-remove branding. All told I have enough stickers to even give a few away or stick them on stuff.
SIGGRAPH Day 4
Today was exciting. I made stickers (again), and talked with Mat Shlian, who does cut and folded paper sculpture. The thing pictured below impressed me because it has a nice springiness.
I chatted with some interesting folks during the poster session; not so much about the poster and more about life in general. Most interesting was the conversation with a film restorer about how noise is removed and then re-added for old films.
I went to the reception and hung out with various people; found out that some other folks are also considering research much like mine (but I think it will be okay).
I did a talk dry run in here somewhere too. Should be interesting to see how it goes tomorrow.
SIGGRAPH Day 3
Not much happening that I was interested in today. Saw Ton Rosendaal and others talk; resisted the urge to get a photo with him. Picked up my stickers from Studio; I shall definitely do more! Digital Domain's pre-vis for Speed Racer used the Top Gear intro music.
I went to the Computer Animation Festival. There was a long run of films from a French school (supinfocom, if I recall), all of which had a lazy animation style that offended my eyes. It was very much like being slowly crushed by rocks. The other films were good though.
SIGGRAPH Day 2
Sat in sessions in the morning, talked with people about my poster (and about gradient paint) in the afternoon. Brian Curless apparently has something coming out at ECCV worth checking out. Gradient Paint seems to impress and confuse people (though different people are confused by different parts).
In the art gallery, I came across a cleverly cut sheet of steel:
Then came TCHOW logo-stuff.
Thanks to emerging technology (and the guts of an old printer), one can enjoy a TCHOW-branded cup of coffee, as pictured above -- though, unfortunately, they weren't actually allowing people to drink the coffee. So one could look at it, at least.
That's a lenticular print of the tchow logo (that is, a flat image with a lens sheet over it allowing for different views per-eye). Sort of very much like a zig-zag-folded piece of paper really. Upshot being that, in person, it's 3d. Which is nifty!
Finally, I made some TCHOW stickers, but those haven't printed yet.