Category Archives: Programming

Second Order FizzBuzz

The FizzBuzz problem requires the construction of a well-known list of interleaved numbers and nonsense words. The list has been studied extensively, and recent work at CERN has constrained its utility to less than 10-16 of a mosquito’s left nut. In modern times, the task of its production is typically relegated to computer programs. It is an open question why some institutions continue to use FizzBuzz as a test of programming ability, given universal knowledge of the test and the wide availability of solutions on Google and StackOverflow.

Programs that solve FizzBuzz are typically constructed by hand in an ad-hoc manner, often by inexperienced computer scientists, and entail a hazard of boredom-induced mortality. Below is presented an algorithmic solution to the second-order problem of generating such programs. In general, we define a class of nth-order FizzBuzz problems which require the production of a program which solves the (n-1)th-order FizzBuzz problem.

We use a variation on the stacksort algorithm due to Munroe (2013) and first implemented by Koberger (2013), which mimics a technique commonly employed in the wild. Here, the Continue reading →

How a Kalman filter works, in pictures

I have to tell you about the Kalman filter, because what it does is pretty damn amazing.

Surprisingly few software engineers and scientists seem to know about it, and that makes me sad because it is such a general and powerful tool for combining information in the presence of uncertainty. At times its ability to extract accurate information seems almost magical— and if it sounds like I’m talking this up too much, then take a look at this previously posted video where I demonstrate a Kalman filter figuring out the orientation of a free-floating body by looking at its velocity. Totally neat!

What is it?

You can use a Kalman filter in any place where you have uncertain information about some dynamic system, and you can make an educated guess about what the system is going to do next. Even if messy reality comes along and interferes with the clean motion you guessed about, the Kalman filter will often do a very good job of figuring out what actually happened. And it can take advantage of correlations between crazy phenomena that you maybe wouldn’t have thought to exploit!

Kalman filters are ideal for systems which are continuously changing. They have the Continue reading →

I spent about 15 minutes staring at this

What’s wrong with this code:

959  // we don't have a lot of entropy to work with here :\
960  RtPoint2 random_pt( deterministic_float( node->center_luminance, rnd1, (uint32_t)(1280498143 * rnd0) ),
961                      deterministic_float( data_pt->p,             rnd1, (uint32_t)(3584308421 * rnd0) ) );

The compiler error:

foo.cpp:961:100: error: expected ';' before ')' token

Where’s the mismatching paren?

Answer (highlight to view): The “:\” smiley face extends its comment to the next line. My syntax highlighter didn’t pick this up.

There’s probably an underhanded c competition entry in here.

EDIT: It’s occurred to me that, based on the compiler error message, the compiler would have preferred I make a winky smiley face instead.