Fizzbuzz is a Jazz Standard

April 12, 2017

Jeff Atwood, of Coding Horror fame, wrote a blogpost called “Why Can’t Programmers.. Program?”, by a happy coincidence nearly exactly 10 years ago.

Central to the post is the assertion that candidates for development jobs should be initially screened on tasks that any remotely experienced programmer might (many would say should) consider low hanging fruit, the canonical example offered being “FizzBuzz.”

I think that the specification for the problem is pretty universally known at this point, mostly due to the linked post above, but it’s short and simple enough to allow a quick repeat here:

Print the numbers 1 to 100, replacing multiples of 3 with “Fizz”, multiples of 5 with “Buzz, and multiples of both 3 and 5 with “FizzBuzz.”

I’ve long been fascinated by this post, having read it very early on in learning to program myself, and coming away heartened about my chances of being “up to snuff” after solving fizzbuzz over beers one night while exploring the idea of a career change with a programmer friend.

At the time, I was incredulous that that was all it might take to prove a minimal competence. Jeff does a fine job extolling the efficacy of this level of screening and discussing both why it might be necessary and also why it totally shouldn’t be necessary. It’s worth a read if you haven’t seen that post before. I’m not entirely on board with the essentialism being implied, but there’s definitely not nothing to the main point.

I’m more interested, though, in the follow up. The very next day, Jeff published a post called FizzBuzz: the Programmer’s Stairway to Heaven.

Evidently writing about the FizzBuzz problem on a programming blog results in a nigh-irresistible urge to code up a solution. The comments here, on Digg, and on Reddit – nearly a thousand in total – are filled with hastily coded solutions to FizzBuzz. Developers are nothing if not compulsive problem solvers.

Indeed. There are so many solutions, in all manner of languages. They mostly look the same because of course they do- it is, after all, just Fizzbuzz, ffs, right? There is a spin off Discourse thread called FizzBuzz Solution Dumping Ground in which there are currently 262 posts. Some of them seem to bespeak of some pretty deep insecurities, some of them carry a light stink of what you might call ‘smug asshole’, even while kowtowing to the snipe hunt. The most recent post is from March 6, 2017. An incredible ten whole years of Fizzbuzz.

It is a little weird, really… why do so many people respond to the post as if it’s a challenge?

Improvisation and Levity

Jazz is an old form, now, or at least it is heading there. The Great American Songbook still has some room for additions, but rarely accepts them, and it is generally thought of as being canonical, and at this point, historical.

These capital-S Standards are standards because they are well known, having originally come from the pop music of the day. As jazz tunes, they serve as improvisational vehicles, providing the structure and outline inside of which an improvising musician can play extemporaneously. They remain standards in that capacity by serving as a common repertoire between jazz musicians, regardless of their differing backgrounds or generations or usually even jazz styles.

This type of lyric standard is just one type of jazz music, of course. We learn the melody, it’s easy, it’s hummable, it comes out kind of the same way each time. The melodies are poppy, memorable, and in many cases quite simple, in contrast to the often frenetic bebop standards, or modal tunes, or maybe latin big band, or fusion… the subgenre list could continue indefinitely.

But lyric standards like the ones in the Great American songbook provide a template for the whole endeavor, a sort of blueprint for how to improvise over any tune. They’re often used as pedagogical tools and as some of the first songs young musicians become acquainted with, while still remaining perennial set list favorites for musicians of the highest caliber.

A great improvisation will not just be riffs over the chord changes. The real goal is to move and flow with the implicit melodic outline, following the contours and implying the structure of the melody while playing inside of and around the harmony.

Here’s guitarist Gilad Hekselman demonstrating this concept in a workshop over the tune “It Could Happen to You” … listen to how he builds up a vocabulary that seems to belong just to this song over the course of a few choruses, each one getting a little bit further afield but maintaining the central cohesiveness of the overarching motive:

Listen to how he bobs and weaves around the structure of the song but is always hinting back at the melody, maintaining that thread, reinforcing that shape. It gets pretty out there, but it’s still the same song.

Sonny Rollins is an acknowledged master of this type of thematic improvisation. Here’s an excellent paper by Gunther Schuller discussing him in this context.

The ‘standard’ way to play standards is to play the melody first (the ‘head’) and then to improvise over the form of the song, possibly taking turns, and then to end the tune by playing the ‘head out’, recapitulating the melody a final time. But it doesn’t necessarily have to be that way. One of my favorite records is from Lee Konitz, recorded in 1961, called “Motion.” Lee is from a different school, a little more deconstructive. Even back then he was just launching right into the improvisation, as if to say “alright alright we all know this tune lets get on with it.”

He actually doesn’t even play the melody at all until the very very end- practically at the last second… starting at about 7:39, and even then it’s sparse- just one A section and a few flutters and that’s it.

I’ll permit that this is pretty inside baseball and winky. Not everyone listening knows the song, and certainly not everyone can hear the changes happening underneath the improvisation and place the song just by that. But it’s also really cool!

I photographed Lee Konitz in his apartment once for a magazine article. When we got there we asked him what he had been practicing that day. “All the things you are” he said. He’s been playing that old song for decades, and he’s still playing it.

Lee Konitz in his apartment

Fizzbuzz is not a hard problem. It’s an easy problem. You have to know what you’re doing to program Fizzbuzz in the same way you have to know what you’re doing to program anything… you need to know your tools and have a functional mental model of programming and understand some rudimentary control flow concepts. If Fizzbuzz as a task is testing anything at all, it’s really testing that, and that’s fine. Fizzbuzz is easy, sure, but it’s also not entirely dissimilar to workaday programming tickets I might see from time to time. “Filter out users who aren’t signed in and redirect them to the login page” maybe, or “catch these two exceptions for special treatment and disregard any others thrown,” or any number of other things. These types of tickets also aren’t necessarily difficult, but they’re certainly a part of my day to day life.

But I think there’s more to it than that.

Fizzbuzz is a melody; it’s a short and easy to remember little song. Much like a simple tune can become an ideal vehicle for improvisation and caprice precisely because it’s a simple tune, and not in spite of it, there is something about the structure and simplicity of fizzbuzz that gets you thinking… what if I did it like this? or that? or I wonder if I could do it using that other thing…

Have you seen FizzBuzz Enterprise Edition from Enterprise Quality Coding? It’s a hoot. There are 99 files in that repo, and they’re still receiving pull requests. And yeah, last time I checked at least, it ran.

The Recurse Center uses Fizzbuzz during its prelimenary application process both as a screening question and as an opportunity for displaying creativity, although they’ve changed the terms to ‘CracklePop’ to thwart would be plagiarizers.

I’ll admit, now, that despite my waxing on why so many people responded to that post with fizzbuzz solutions, I couldn’t resist it any better than they could.

The Great Programmer Song Book

Fizzbuzz isn’t alone in this song book, far from it. It belongs to a subclass of programming problems that have this some kind of, for lack of a better word, ‘poppiness’ to them. They may be but don’t have to be easy to complete, but they’re memorable for sure… easy to ‘hum.’

Another like this is the eight queens problem:

Place eight queens on an 8 by 8 chessboard so that no two queens threaten each other.

There are 92 and only 92 ways to do this. The problem could be “find one solution” or it could be “find all solutions” or it could be “find all solutions that are not rotations of any previously found solutions.” It could be generalized to be the “n-queens” problem…

Place n queens on an x by y chessboard so that no two queens threaten each other.

You could allow the chess board to be a non-rectangular shape, or it could be 3 dimensions, or it could be n dimensions. You could code golf it, you could try to get it to run as fast as possible, you could subject yourself to arbitrary constraints in the language you’re using just to see if you can do it. It’s naturally a recursive problem, but you could solve it iteratively.

There are tons of ways to play through this song, but the melody is always there.

Here’s a solution by David Dalrymple written directly in x86 Assembly that may very well run faster than any other solution ever.

Here’s one by Andree Monette that uses Python’s garbage collector as a computational stack and produces the correct value on exit of the program.

Wouldn’t you know it, here’s one by Aphyr posted not but a couple of days ago that… well I’ll let that one speak for itself.

There are so many ways to solve it, to ‘improvise’ around the ‘melody.’ Improvise might be a strange word to hear in this context, as it tends to imply performance, or at least making things up in the moment, on the spot. But really, that’s inconsequential. Improvisation and composition are not exactly the same thing, but they are inextricable, they have a lot in common with each other, they just happen on different time scales. What I’m trying to get at is the sense of play, the chasing down of an idea just for the fun of it, or for the shape of it, or for the challenge of it. Are these things necessary? No, of course not. Programming can be aesthetic, and it can be playful, and in a sense it can be improvisatory too. Just because something is a solved problem, and certainly fizzbuzz and 8-queens are solved problems, doesn’t mean it’s not worth spending time on them for creativity’s and learning’s sakes.

How about Conway’s Game of Life? Here’s a demonstration of an implementation of that in APL. I must have watched that video a dozen times and it still melts my brain.

The change counting problem from Structure and Interpretation of Computer Programs is a good candidate, as is the related n’th stair problem. There are a lot!

I don’t know exactly how to best describe the qualities that make a problem or puzzle or task feel like a ‘standard,’ and I suspect that they are different for different people with different backgrounds, too. Just like a fusion musician might have a different set of songs they know backwards and forwards, a graphics programmer might consider a ray tracer to be a standard… a language designer might consider a lisp interpreter to be one. I know that a lot of these tasks could be interview problems, too, but that’s also not a complete overlap.

I’m very interested to hear what people think about what exactly falls into this category!

Code as Craft / Coda

I came across a Longfellow verse today in a book I was leafing through…

In the elder days of art
Builders wrought with greatest care
Each minute and unseen part
For the Gods are everywhere.

The author quotes the verse and goes on:

The point of these lines is clear. In the old days, craftsmen did not cut corners. They worked carefully, and they took care with every aspect of their work. Every part of the product was considered, and each was designed and made to be exactly as it should be. These craftsmen did not relax their thoughtful self-discipline even with respect to features of their work which would ordinarily not be visible. Although no one would notice if those features were not quite right, the craftsmen would be bothered by their consciences.

I’ll leave you with my own versions of some old songs.

References

As I was writing this post I found myself linking to a ton of youtube videos of music. It got a little overwhelming, so I pared it down quite a bit. I’ve put them all in this playlist though, if you’re interested. Obviously this is pretty limited and not intended to be a survey of jazz history or styles or anything, but just to illustrate the concepts I was trying to get at.

Thanks to Lindsay Kuper, Jake Voytko, Eric Hirsh, and the other folks who helped me think through this post in draft form.