A few of the guys in my team have a fairly regular ritual of going to the espresso bar on the first floor to swap anecdotes and design/programming problems over coffee (or any similarly delicious beverage). At today\’s session, a co-worker and friend of mine raised an interesting programming problem that had been posed to him by another person, and I thought it was interesting enough to reproduce here. Give it a shot if you feel so inclined 🙂

The goal is to write a function in C that, given a null-terminated string, prints it in reverse (You don\’t have to return the reversed string – just print it). However, there are a few restrictions:

  1. You can\’t create any local variables (apart from function arguments)
  2. The only library function you can use is printf()
  3. You can\’t use any other language constructs (no if…else, no loops of any kind, no goto, etc)
  4. Any subroutines you create must also abide by rules 1, 2 and 3

This is apparently entirely possible. My C is rusty at best, but I\’ll be giving it a shot on my newly-formatted Linux laptop (which I have christened \’Potato\’ for some bizarre reason).

A hint that may or may not be useful: think about what printf() returns.

On a side note, my friend\’s suggested solution was pretty hilarious; he suggested using a format-string exploit in printf() to point the instruction pointer at an arbitrary location in memory, which he would have filled up at an earlier point with assembly instructions (again using printf()). The assembly code then prints the string in reverse with no regard to the rules (since it isn\’t technically C). He hadn\’t gotten it to work, but I\’m pretty sure that it would, given enough time.

Said friend is leaving Amazon to work for Microsoft in a few weeks, by the way, which makes me wonder what sort of software he might write there.

On an even more hilarious note, as a result of the above \’solution\’, the discussion quickly turned into one about whether or not C\’s printf() function is in fact Turing-complete.

EDIT 2008/05/21, 2045 PDT: Solved it! Although the basic idea for the solution came frome one of my teammates…

Leave a Reply

Your email address will not be published. Required fields are marked *