Algorithms fascinate me again and again. They seem to be very hard to understand, but once you have practiced enough, you will recognize common patterns. Once you reach the state where you see a problem and can imagine a solution, it seems like that you just adjust the previous algorithm used. Saying this, I am trying to say that it is important to practice and that there is no place for self-doubt 😊
Saying this, I want to talk in this post about roman numerals. The Romans used a different (and in my opinion very difficult) way to represent numbers than we do today. Even after the decline of the Roman Empire, the system remained for a long time (and still remains – even if we use Arabic numerals today). But let’s recall how Roman numerals are structured:
| Decimal | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |
| Roman | I | V | X | L | C | D | M |
As you can see, there is a limited set of symbols that represent a limited set of numbers. Other numbers, such as 2 or 9, are represented by a simple chain of (multiple) symbols. For example, the numbers 1-10 look like:
| Decimal | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Roman | I | II | III | IV | V | VI | VII | VIII | IX | X |
The Special Cases
There are two special cases in the example above: Number 4 and 9. Where for every other chain, the numbers are simply added up (for example, number 8 is represented as 5+1+1+1), for 4 and 9, however, we subtract the first value from the second. For instance, the Roman numeral 4 is represented as 5-1 and 9 as 10-1.
It seems that the biggest challenge here is to know when to add and when to subtract. We need to find a pattern to chain the right numerals in the right order.
Converting Roman Numerals
The following code seems to be very simple. But it is important to understand what exactly happens:
1 2 3 4 5 6 7 8 9 10 | def to_roman(number: int) -> str: result = "" map = {"M": 1000, "CM": 900, "D": 500, "CD": 400, "C": 100, "XC": 90, "L": 50, "XL": 40, "X": 10, "IX": 9, "V": 5, "IV": 4, "I": 1} for key in map: value = map[key] while value <= number: result += key number -= value return result |
When I was working on this problem, I tried to find a pattern differentiates between when to add and subtract (just as stated in the introduction). But sometimes, it is easier than that. It would be an ugly if-else construct if we try to check whether the number is a 4/9 (or 40/90, or 400/900, etc). But there is a better way.
First, we define a map of roman numerals and their decimal counter parts. In addition to the base numerals, we also add 4, 9, 40,90, 400 and 900 to the map. This makes the algorithm much easier, as we do not need to differ between addition and subtraction.
Then, we iterate over the map. Whenever we find a value (the decimal counter part of the current roman numeral), we add this to our result and subtract it’s value from the number. If the value is greater than our number, it does not fit in the result and we need to look for the next one. If the value is smaller, the while loop runs until number gets less than the current value 1.
As you can see, the all magic is to define the right data structure (a map, in this case) and have the right understanding for chaining the values to the resulting string.
Please keep in mind that there are other/better solutions than this. If you have suggestions on how to improve, please let me know in the comments.
PS: Yes, I used Python. No PHP 🙂