Thunk

Here’s another problem dealing with roman numbers. The problem is basically, given a string, find the largest roman number you can extract from it. One important thing to note in this problem is that unlike “normal” roman numbers, where “M” can only appear three(3) times max, the “M” here can be as many as possible.

The first step would be filtering out the unnecessary non-roman characters. If we’re planning to scan the string as lot of times, we might as well remove the non-roman characters first. Else, if we’re just going to scan it once, we might as well just scan it and not bother removing the non-roman characters first. Nevertheless this is just a trivial decision so the samples following this will only contain roman numbers for clarity.

Since the problem is asking for the largest roman number (in decimal) in a string, we should follow the “greedy” process of getting the numbers. We scan the string from left to right, looking for roman characters in descending order (From M to I) without backtracking (since we read from left to right at least for English right?). So, for example, if we have CMMV, we’ll scan for M first, getting the first two M’s, and ignoring the C (though CM is valid, it’s not the most you can get out of it). Then we should get the value next to M which is C, but since the only C is before the M’s (remember, we can’t go back), we’ll have to move on and get V. So all in all, we end up with MMV = 2005 (as opposed if you get CM, you’ll have to skip the second M and end up with CMV = 905 which is less).

Read more »

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.

Read more »