08 Sep 2009
This weekend I wrote a Javascript clone of the old Atari “Breakout” game.
Thanks to the “Canvas” tag it was very easy to write, but I did run into a few
problems:
-
Javascript math is always floating point, so I had to use the “Math.floor”
function to convert the results of a division to an integer. This was in the
brick collision detection logic, where I am converting the ball’s (x,y)
coordinates to the bricks that the ball might be hitting.
-
I was evaluating document.getElementById too early in the document lifecycle,
before the corresponding elements existed. This took me a long time to
diagnose – I ended up just moving the getElementById calls to their run-time
use, rather than trying to cache the results.
Jack’s Brick Break Breakout clone
04 Sep 2009
Well, 8 hours using wmii was enough for me. Too many apps didn’t quite work
right. So I’m back to plain-old-boring-but-familiar Gnome.
03 Sep 2009
In no particular order, here’s what I’ve been studying lately:
- Javascript. I’ve avoided this language over the years because of its low speed and shoddy reputation. But the language implementations seem to be getting faster and the available libraries seem to be getting more interesting. I’ve just watched all of Doug Crockford’s YUI lectures on JavaScript, and I’m thinking about trying to use the language in some toy projects.
- git gui - this git command, available in recent builds of git, make Git changes pretty easy to author.
- The Undercover Economist - this is a great book about economic theory. It’s pretty easy to read while shaving, or waiting for compiles. Lots of good anecdotes and tools for modeling the behavior of consumers and firms. I took 3 economics classes in college, and they didn’t teach me as much practical information as I’ve learned from reading this book.
- Hacker News - this link voting site has replaced alterslash and reddit programming as my daily comp-sci news site. I like the emphasis on start-up news.
- wmii - yet another tiling window manager. I tried a bunch of tiling window managers, and this one seemed to “click” with me. I found that I could customize it easily, and it mostly “just worked” the way I wanted it to. We’ll see if I stick with it or go back to Gnome. [Follow-up. I went back to Gnome (and then to OSX). Oh well.]
- Chrome - now that the Linux and OSX versions have Flash support, Chrome has become my default web browser. I like its clean UI.
03 Sep 2009
After a month of using the Dual XHD7714,
during which my family and I took a 4000 mile road trip, I have
to say it’s a pretty nice system. We used it almost exclusively as an MP3
player, rather than an HD Radio or a CD player. I loaded 800 songs from our
home music collection onto an 8GB memory stick. It was great introducing my
kids to some new music. By the end of the trip their favorite songs were
Shock the Monkey and The Magical Mr. Mistoffelees.
Some problems specific to the Dual XHD7714:
Bluetooth issues:
- Bluetooth headset mode only syncs with one phone at a time. This seems to be a common limitation of low-end bluetooth car stereos, but it’s quite frustrating for two-driver families like mine.
- Bluetooth audio streaming mode doesn’t sound very good on this radio. However, I didn’t experiment with this very much, so it may have been source-material related.
USB MP3 player issues:
- It takes about 5 seconds per GB to index USB stick music each time it starts up.
- It only recognizes US-ASCII characters. If any non-ASCII characters are present in the album or song name the entire name is replaced with the string “Not supported”. We had a lot of Chinese-language tracks that displayed that way, making them very difficult to navigate.
- It can’t fast-forward or rewind through MP3s.
- When you turn on the radio, it does remember where in the current MP3 it is playing, but it takes a long time to resume playing an MP3 in the middle. So it’s awkward listening to long podcasts.
Still, even with all these flaws, I’m quite happy with the radio. We really
enjoyed being able to conveniently listen to so many different songs during
our trip.
23 Jul 2009
I’ve just had a chance to use a Nehalem HP Z600 workstation with 2 Xeon E5520
CPUs. The machine has 8 cores, 16 hardware threads, and an absurd 12 GB of
RAM.
It’s very fast. It’s about 2.5 times as fast (when building the Android
sources) as the previously fastest machine I’d used, which was an HP xw6600
with a single Xeon E5420 CPU.
The machine’s relatively small, no larger than an ordinary ATX tower. One way
that HP kept the case small is by making the motherboard an odd shape: it is
“C” shaped, with a cutout that leaves room for the DVD drive.
18 Jul 2009
The other day my wife said to me, “Jack, we’re going on a road trip soon. Is
there any way we could hook up our MP3 player to the car stereo, so that the
kids could listen to their favorite songs during the trip?”
Twenty hours of
web research and $250 later we’ve got a new car stereo. It’s a
Dual XHD7714 from
Crutchfield. I’m getting it installed by Best
Buy tomorrow. Let’s hope their AV installers do a good job!
First, why did I
get a new stereo at all? Well, all I wanted to do was hook up an MP3 player.
But there was no easy way to do that. My 2005 minivan came with a factory
installed stereo that didn’t have an auxiliary input. There are cheap FM
transmitter systems that work with any radio, but they look clunky and the
sound quality is supposed to be poor. A lot of web searching turned up some
aftermarket accessories that allow hooking up either an audio input jack ($75
- $50 installation = $125) or an MP3 player and/or iPod ($125 + $50 = $175.)
But the for just a little more money I was able to get a a whole new radio
with lot of additional features.
Why this particular model? It was well
reviewed and relatively inexpensive. The features I was interested in were:
- MP3 player / USB memory stick player.
- Hands-free bluetooth calling with a built-in microphone.
- Streaming audio from a bluetooth phone.
- Charging USB devices.
- HD radio.
- Good fast text UI for navigating a MP3 player.
- Play MP3s stored on CDs.
- Wireless remote control for “back seat DJs”
General thoughts on the car stereo market
- Crutchfield is a good place to research and buy car stereos. For research purposes they have a wide selection, and they have very good information, especially in the form of user reviews. For buying they offer free shipping and more importantly a free installation and wiring kit. They also seem to offer very good telephone help for do-it-yourself installers.
- The add-on car stereo market is in long-term decline. I think that in the next few years the car stereo will become little more than a mobile phone docking station. People will keep their music collection on their phone, or stream it from the internet.
- Car stereo makers are not going down without a fight. They are experimenting with iPhone-inspired full-screen touch-screen UIs and built-in internet radios. While very creative, I don’t think people will buy them. They will just use their phones instead.
- Many people want to connect their iPods to their car stereo. In the short term Apple is making this difficult by changing their communication protocols with every generation of iPod. In the long term iPods are going to be replaced by iPhones, which will probably be forced to support bluetooth stereo streaming.
07 Jul 2009
I frequently switch between Mac and Linux, and it’s been troublesome to
remember to type Command-whatever on the Mac, but Control-whatever on Linux.
(For copy-and paste, for example.)
I did a quick web search and found out that it’s easy to
make Ubuntu Linux recognize the Command keys as an extra set of control keys:
Choose menu: System : Preferences : Keyboard
Select the Layouts tab
Choose "Layout Options"
Open the "Alt / Win Key Behaviour" tab
Check the "Control is mapped to the Win-keys" checkbox.
28 Jun 2009
I just threw in the towel on the
ICFP 2009 Programming Contest.
The problem this year was a set of 4 sub-
problems related to orbital mechanics, plus a virtual machine spec. The
virtual machine was used to enable the problems to be specified exactly,
without worrying about differences in the order of math operations.
Implementing the virtual machine was easy and fun. Unfortunately, actually
solving the final sub-problem required learning too much math and physics. I
was able to solve problems 1 and 2, and make an entry for the lightning round.
And I brute-forced a solution for problem 3. But now, 56 hours into the
contest, I am giving up on problem 4.
I can see the general outline of how to
solve it, but it would take sharper tools than I have now. For example, I’d
like a way of solving Lambert’s equations, but I’m having trouble deriving the
code on my own, and the best example I’ve found while searching the web is a
30-year-old NASA Space Shuttle Fortran program.
Also, I’m pretty tired, and this is affecting my
judgment. I don’t think it’s worth going on at this point.
Some fun things I did during the contest:
- Learned Orbital Mechanics, the study of how bodies move in space.
- Learned what a Hohmann Transfer Orbit is and why to use it.
- Learned what Lambert’s Theorem is, and how to apply it to missile guidance.
- Wrote a Python program that did efficient calculations by generating a C program, compiling it, and then running it and talking to it via a pipe.
- Read a ton of Wikipedia articles, Google Books books and old NASA tech reports on orbit planning and course corrections.
- Learned how old-school Q-system guided missiles work. Very clever use of ground-based computers to compute coefficient matrices that were fed into simple on-board analog computers for the duration of the flight.
Highlights of the contest:
- Hanging out on IRC with 20 other contestants, trying to get the simulator to work.
- Getting problems 1 and 2 to work.
- Giving up on problem 3, then thinking of a brute-force way of solving it while in the parking lot, about to drive home. (Too bad I wasn’t further inspired to solve problem 4.)
- Seeing the pretty pictures of the satellite orbits for problem 4.
Low-lights of the contest:
- Wasting an hour or so due to bugs in the specification
- Wasting an hour writing a Tkinter alternative to turtle graphics, then not being able to get a Tkinter window to show up, then realizing that Tkinter graphics are so limited that there’s no feature benefit over using the already-working turtle graphics.
- The buggy scoring in problem 1 encourages people to program-to-the-scorer rather than solve the stated problem. I could probably increase my position in the standings by 10 places by hacking an “optimal” solution to problem 1 that uses all of the available fuel. But it seems like a waste of time.
- Having to give up on problem 4.
My advice to (future) contest organizers:
- Consider avoiding problems that require deep domain expertise. There’s only so much orbital mechanics and numerical methods one can learn in 72 hours.
- Do whatever it takes to ensure that your VM machine spec is correct. In this case, just asking someone to spend a couple of hours implementing the spec would have exposed the show-stopping problems that everyone encountered.
Advice to myself for future contests:
- Pace yourself on day two, to avoid burning out on day 3.
- Be sure you understand the scoring system. For example problem 4 had partial credit, so a solution for problem 3 might have worked on problem 4.
- Scheduling work and family life to enable a free weekend for the contest worked out very well.
- Do more planning, and keep an eye on how the work is progressing, to avoid spending too much time on unnecessary work. “What’s the simplest thing that could possibly work”, and “you aint going to need it” are both good mottoes for this kind of contest.
- Take a little time to refactor the code as you go along, to avoid slowing down due to barnacles. (Example, passing the problem number all over the place because it was one of the inputs to the simulation, rather than special-casing it and setting it once in the VM.)
Analysis of programming languages I used in the contest
I used Python and C. I
actually completed the lightning round in pure Python.
Benefits of Python
- Rapid development due to no compilation time, clean sparse syntax, well designed libraries, plenty of documentation and help available on-line.
- Turtle graphics made it dead simple to display satellite orbits
- The “struct” package made it dead simple to import and export binary data.
- The “subprocess” package made it easy to start and control other programs.
- Python 3.1’s exact printout of floating point values made it easier to tell what the math was doing. (Other projects ran into problems with almost-zero values printing as zero.)
Drawbacks of Python
- Slow. I had to switch the simulation to C to have it run fast enough for problems 3 and 4
- Global Interpreter Lock (GIL) - meant I couldn’t use multiple calculation threads written in Python in one process. (And my machine’s got 8 hardware threads. :-) )
- Lack of static type checking is frustrating when program run times are long: I had a half-hour period wasted debugging simple errors that only occurred after 2 minutes of simulation run-time that a static type checker would have caught immediately. To be fair, I could also have caught them with unit testing.
Benefits of C
- Very simple to write code.
- Runs really fast. :-)
Why My VM’s Cool
I wanted to explain how my VM implementation worked, because
I think it probably ran faster than most other VMs.
I wrote a Python-based VM
as a reference. Then I wrote a VM generator that would read a VM spec and
generate hard-coded C to implement that specific spec. I used a “comparer” VM
to compare the output of the two VMs to make sure that there were no bugs in
the generated C version.
The hard-coded C VM was really hard coded to each
problem. All the VM instruction interpretation overhead was removed. In
addition, because the VM didn’t have any indirection, the “mem” array was
replaced by hundreds of individual local variables. This allowed the C
compiler to do a very good job of optimizing the code, because it could easily
tell there was no aliasing.
I included a simple interactive shell in each
generated hard-coded C program. The console let you set inputs, run “n”
simulation steps, and read the outputs. This made it easy for me to control
the simulation from Python. It also made it easy to hand-test the C
simulation.
One feature I meant to add, but ran out of time/energy for, was to
save and restore the state of the simulation. This would have been very
helpful in solving problem 4.
How I solved the problems
Problem 1: Wrote
Python VM. Implemented Hohmann transfers as described in a Wikipedia
article.
Problem 2:
Calculated the correct time to start the Hohmann transfer analytically. (I
read about how to do this in a textbook I found through Google books.) Added
simple brute-force docking code to match orbits exactly. No fancy “S” curves
for me. (And wasted about an hour wondering why I didn’t score, because early
versions of the contest problem spec didn’t say you had to turn off your
engine for 900 seconds. I finally figured this out by disassembling the VM to
see why the score wasn’t being set properly.)
Problem 3: Used my fast VM to
compute a table of where the satellites would be over time, then wrote a set
of nested for loops that tried various Hohmann transfers at various times
looking for a solution. The precomputed tables meant I could just look up
where the target satellite would be for any time in the future, rather than
having to do complex elliptical math.
Problem 4: Only got as far as simulating
and visualizing this one (boy the orbits are pretty!) Too tired to continue. I
was planning on using a variation of the brute-force approach that solved
problem 3, with save-and-restore of the simulator state, because I would have
to recompute the table of locations for my rocket each time its orbit changed.
Conclusions
Upon reflection, I think that this particular contest, especially
problems 3 and 4, is best suited to a C/C++ solution. This is due to the heavy
reliance on numerical methods to calculate the optimal trajectories.
I liked
that there were multiple versions of each problem. It made it easier to tell
if we were making progress, and also allowed whole-program-level
parallelization to make use of muticore machines to solve the problems in
parallel.
While I expect the ultimate contest winners will code in a mutable-
state static-type-checked compiled language like C/C++, I predict Haskell will
do fairly well in the contest, due to its speed and the ease with which it
handles math. However, the winners will probably have a good grasp of orbital
mechanics, and it seems that someone who knows the math is more likely to be
using C-like-languages.
Well that’s it, now I’m looking forward to next year!
P.S. Here’s a Wiki with other team writeups:
FUN Team ICFP 2009 Writeup / Wiki
15 Jun 2009
This weekend I wrote a JavaScript version of my old Atari 800 game Dandy.
Check it out: Web Dandy
It was my first JavaScript application. It was about as easy as writing the
Python version. I have only tested it in two browsers so far (Firefox 3.0 and
Chrome), and only on one platform, OSX. I have already run into differences
between the two browsers: Firefox 3.0 for OSX seems to double-post keydown
events.
No sound or multiplayer yet. Oh, and I use the CANVAS tag, so I think older
browsers (like IE 7) won’t work.