Rites of Passage

Every community has some kind of rite of passage. Christians have the baptism, jews have the bar mitzva, Valley Girls have the debutante ball. Programmers also have their rites of passage, the most common being hello world. At the brazilian universities in the nineties, one very common rite was the roman numbers.

At the time, both USP and UFMG asked the students, as a first exercise, to write a program to convert integers to the equivalent roman number. It seems a simple task, and it really is, even though it's only the first task of a series of increasingly difficult tasks (in my year, the following exercises asked for the forces in a lattice, and for a 3d wireframe renderer).

On the other hand, the simpler the task, the most creative you can get to solve it. It's said that one student submitted this solution:

scanf("%d", &n);
if (n==1) printf("I");
if (n==2) printf("II");
...
if (n==3999) printf("MMMCMXCIX");

I thought this approach was quite nice: of course the teacther can't complaint, since it does solve the problem. But even though this approach was fun, it was not optimal. In fact, it's only O(n).

So how could we write a solution that's both funny and optimal? We could create an array of strings initialized with the values, this way we could have O(1). This would not be funny, however. It would be better if we could create the array at compile time using some kind of metaprogramming, like the template metaprogramming in C++.

Even then, template metaprogramming is not as obscure as it used to be, lots of people know how it works. What few people know is that you can do metaprogramming using only features available on the C language. My solution uses a spell known only by the priests of the ioccc, the preprocessor metaprogramming:

Roman numbers using preprocessor metaprogramming

The C preprocessor is not turing-complete as the C++ templates, but it is enough to write simpler programs. My solution uses a finite automaton, where the state transition is done by an #include of itself, and the states are encoded bit by bit, using BCD.

Please try to run the code yourself, but I do warn you that it may take a while to compile. To look at the generated code, use the flag -E of gcc.

I had another idea for a clever metaprogramming usage, but that's a story for another post :)