10/05/07
Roman numbers
Before I get started, since it’s my first time posting a solution, it goes without saying that there are more than one way to solve a problem. So the last thing I want is a bigot smugly insisting that his solution is the correct one. Nevertheless, I’ll gladly accept criticisms, holes, and alternative solutions when they’re pointed out. Oh and when when ever I use superlatives, add “probably the” before the said superlative. So when I say “best” I mean “probably the best", when I say “easiest” I mean “probably the easiest” etc.
Converting and checking Roman numbers is a classic computing problem. For this problem, I’ll use an ACM problem in the 2006 Asia Regionals held in the Philippines: Nuevo-Romano it involves both converting from Decimal to Roman, the other way around, and checking for validity of roman numbers.
Follow up:
Basically, the problems requires you to add two roman numbers and return the result in the form of “Roman=decimal". Knowing this I quickly outlined the solution (note: the code’s in C++):
C++:
| string input; | |
| while ( cin >> input ) { | |
| for ( unsigned int i = 0; i < input.size(); ++i ) | |
| input[i] = toupper( input[i] ); | |
| string::size_type pos = input.find( ‘+’ ); | |
| string right = input.substr( 0, pos ), left = input.substr( pos + 1 ); | |
| if ( !isRoman( right ) || !isRoman( left ) ) { | |
| cout << "INVALID\n"; | |
| continue; | |
| } | |
| unsigned int sum = toDecimal( right ) + toDecimal( left ); | |
| cout << toRoman( sum ) << "=" << sum << endl; | |
| } |
So basically, I need to implement the following functions: isRoman( string roman ), toDecimal( string roman ) and toRoman( unsigned int decimal )
Now, actually, I only need to implement one functions, that is toRoman( unsigned int decimal ). Why? Remember that the range of roman numbers are from 1 - 3999, only 3998 combinations. So it’s possible to generate ALL combinations within a reasonable amount of time. We use isRoman to generate a map of all possible roman numbers and their decimal eqivalents. This way, we check for valid romans by checking if that combinations exists in the map and we convert it decimal by using the map.
So, before everything else, we need to pregenerate all possible combinations. There are two ways to do this: Do it in the program itself or do it in the separate program which prints all possible combinations in array format and copy-paste it to the main program afterwards. I tried doing the latter but the source code size constraint (32kb) is not enough to hold all possible combinations (total of 35kb) so I went for the former method:
C++:
| //global variable | |
| map<string, unsigned int> g_romans; | |
| //somewhere right after int main() | |
| for ( unsigned int i = 1; i < 4000; ++i ) | |
| g_romans[toRoman( i )] = i; |
And implementing toDecimal and isRoman would be trivial:
C++:
| bool isRoman( string roman ) { | |
| return g_romans.count( roman ) > 0 ? true : false; | |
| } | |
| unsigned int toDecimal( string roman ) { | |
| return g_romans[roman]; | |
| } |
You could also implement toDecimal “manually” be scanning the string from left to right and adding the appropriate values, but when you have time constraint, just using the map would save you a lot of time coding.
What about the toRoman? Well, I did mine in a deductive manner: start out with the number, if it’s greater than or equal to 1000, keep subtracting from it while adding “M” to the string until it’s less than 1000, afterwards, check if it’s greater than or equal to 900. IF yes add “CM” and subtract 900 from the number, if no, check if it’s greater than or equal to 500, if yes, add “D” and subtract 500 from the number, of no, check if it’s greater than or equal to 400, if yes, add “CD” and subtract 400 from the number. Finally while the number is greater than or equal to 100, add “C” and subtract 100 from the number. Repeat for “X” and “I". Here’s the code:
C++:
| string toRoman( unsigned int decimal ) { | |
| string ret; | |
| | |
| while ( decimal >= 1000 ) { | |
| ret += ‘M’; | |
| decimal -= 1000; | |
| } | |
| if ( decimal >= 900 ) { | |
| ret += "CM"; | |
| decimal -= 900; | |
| } else { | |
| if ( decimal >= 500 ) { | |
| ret += ‘D’; | |
| decimal -= 500; | |
| } else if ( decimal >= 400 ) { | |
| ret += "CD"; | |
| decimal -= 400; | |
| } | |
| while ( decimal >= 100 ) { | |
| ret += ‘C’; | |
| decimal -= 100; | |
| } | |
| } | |
| if ( decimal >= 90 ) { | |
| ret += "XC"; | |
| decimal -= 90; | |
| } else { | |
| if ( decimal >= 50 ) { | |
| ret += ‘L’; | |
| decimal -= 50; | |
| } else if ( decimal >= 40 ) { | |
| ret += "XL"; | |
| decimal -= 40; | |
| } | |
| while ( decimal >= 10 ) { | |
| ret += ‘X’; | |
| decimal -= 10; | |
| } | |
| } | |
| if ( decimal >= 9 ) { | |
| ret += "IX"; | |
| decimal -= 9; | |
| } else { | |
| if ( decimal >= 5 ) { | |
| ret += ‘V’; | |
| decimal -= 5; | |
| } else if ( decimal >= 4 ) { | |
| ret += "IV"; | |
| decimal -= 4; | |
| } | |
| while ( decimal >= 1 ) { | |
| ret += ‘I’; | |
| decimal -= 1; | |
| } | |
| } | |
| return ret; | |
| } |
Of course, we’re not done yet. We’re still missing parsing the “O” value but I would leave the implementation of that since it’s trivial (or is it?). The hint in doing the “O” is the fact the we separated parts of the algorithm into subroutines (another hint: recursion).
As a side note, the performance of searching against the map is good. There are 3998 combinations and the implementation of the std::map class in C++ is a red-black tree, meaning the complexity for insertion, deletion and searching is approximately O(log2n) and 212 = 4096 so there’s a maximum of 12 comparison operation when checking and converting the roman number. For Java programmers, you could use the Hashtable which uses hashes instead of red-black trees.
Trackback address for this post
Trackback URL (right click and copy shortcut/link location)
No feedback yet
Comment feed for this postLeave a comment
