Thinking Like a Programmer – Roman Numerals

We have a task to take a number and convert it into Roman numerals. That’s easy, right?  Lets work through the problem.

If you’re unfamiliar with Roman numerals, here is the Wikipedia link. It has information that we will use to write our function.

First Draft

How do we even begin to solve the problem? In the Wikipedia article the section on standard form gives a great idea. Lets work from the biggest numeral to the smallest. We should start and see if the number is greater than or equal to 1000, and work smaller. What if the number is 2000? Well then we should put it in a loop!

Here is the standard form combinations, sorted smallest to largest.

Now that we have this, we can use it as a lookup table. Lets write the loop to evaluate our number. The function will have just 1 input parameter, $number. We’ll use $number and modify it to determine how many more times to loop. If $number > 0, keep going.

Inside of the loop, we will want to go over the $numerals variable and if the index is greater than or equal to number we append the numeral string and minus the index from $number.

Second Draft

Awesome! And the code works, we get the expected results. That’s it right?

No.

It is true that the code works, but it can be better. How can we improve the code? Lets consider for a moment the Roman numeral for the number 3 which is III. What is I? It’s the Roman numeral for the number 1.

If we removed the numbers beginning with 2 or 3 (2, 3, 20, 30, 200, 300) from the lookup table it would be shorter. And the code would still function! How?

If there were no 2 or 3 but we pass in 3 to the function it would evaluate all the numbers and see that they are greater than 3, until it gets to 1. Then it would step inside the if statement append 'I' to the $return and reduce $number by 1. After that it would repeat that process 3 times before $number is reduced to 0. This works because in Roman numerals 3 is just 1 + 1 + 1.

We’ve made an improvement without changing the results! But there is more we can do.

What is the number 8? VIII, which is 5 + 3, or as we showed above, 5 + 1 + 1 + 1. Well, we already solved that case, so we can removed all the numbers that begin with 6, 7, and 8.

Our lookup table is now a lot shorter!

Final Code

There is still a problem though. When $number is 3 it iterates over ALL of the values of $numerals from 1000 then 900 then 500 et cetera until it gets to 1. Three times. It does that three times!

Consider this: if we have already gotten to 1 then we know that $number is less than the next greatest value 4. So why go over all of them again?

Lets not. If we remove the break statement we won’t go back to the beginning of the $numerals loop. We can now change the if statement into a while loop and get rid of the outer while loop.

Here is the final working code.

Epilog

This code does the same as what we started with, only it is better. It is more efficient in both size and looping.

Can this code be optimized even more? Yes, but it will begin to lose readability. There is a quote by Harold Ableson,

“Programs must be written for people to read, and only incidentally for machines to execute.”

Also consider the words by Martin Fowler et al

“Any fool can write code that a computer can understand. Good programmers write code that humans can understand.”