16
Write an algorithm to interpret a sequence of letters as a Roman numeral. (see roman numeral rules below)
Each distinct letter has a matching Arabic decimal value, no maximum. But you don't have the key beforehand, so {A=10, I=1, X=5, ... Z=1000000}
is decided by your interpretation.
Challenge
- Read input via
STDIN
or equivalent and write output viaSTDOUT
or equivalent - Valid inputs are combinations of uppercase and lowercase letters i.e. matching
\[a-zA-Z]+\
- Input should be validated to see if the letter sequence can be interpreted as valid Roman numeral
- If the input passes validation, valid output should be the lowest Arabic decimal interpretation and the key used i.e.
Aa
is interpreted as4 {a=5, A=1}
not6 {A=5, a=1}
or9 {a=10, a=1}
Roman Numeral Rules
Only letters representing powers of ten can be repeated, maximum of three times successively and four times in total e.g.
II
III
XXXIX
If one or more letters are placed after another letter of greater value, add that amount
AAaa => 22 {A=10, a=1} (20 + 2 = 22) bbAAaa => 222 {b=100, A=10, a=1} (200 + 20 + 2 = 222)
If a letter is placed before another letter of greater value, subtract that amount
Aa => 4 {a=5, A=1} (5 – 1 = 4) AaA => 19 {A=10, a=1} (10 + 10 – 1 = 19) BbBaA => 194 {B=100, b=10, A=5, a=1} (100 + 100 - 10 + 5 - 1 = 194)
Several rules apply for subtracting amounts from Roman numerals:
- Only subtract powers of ten i.e.
1, 10, 100...
not5, 50, 500...
- No double subtraction therefore
18
is written asXVIII
notIIXX (10 + 10 - 1 - 1)
- Do not subtract a number from one that is more than ten times greater.
You can subtract1
from5
or10
but not from50, 100, 500...
- Only subtract powers of ten i.e.
Example
Input:
Aa
BAa
CCCXLVII
MMMCDVII
ABADDF
XVVX
FAASGSH
DXCCDA
AaBbcDEf
Output:
4 {a=5, A=1}
14 {B=10, a=5, A=1}
347 {C=100, L=50, X=10, V=5, I=1}
347 {M=100, D=50, C=10, V=5, I=1}
1921 {A=1000, B=100, D=10, F=1}
'XVVX' failed Roman numeral test
7191 {F=5000, A=1000, S=100, G=10, H=1}
'DXCCDA' failed Roman numeral test
4444 {a=5000, A=1000, b=500, B=100, D=50, c=10, f=5, E=1}
3
@IamOgbz this has turned into a great question but attracted a lot of questions in comments along the way. Now that you have enough reputation, I recommend the sandbox. I find it very useful for getting questions just right before posting.
– trichoplax – 2015-10-15T11:25:43.217Wouldn't CCCLXVII be interpreted as CCCXLVII, giving 347? – Skyler – 2015-10-15T19:52:24.897
@Skyler you're absolutely right, will update now! thanks. – iamogbz – 2015-10-15T20:39:04.133
I don't see any restriction on what values the individual letters can have (and indeed you mention 20, which is not the value of a standard Roman numeral). Do you mean to say that any positive integer can be represented by a Roman numeral? In that case,
Aa
has a value of 1 (A=1, a=2). – msh210 – 2015-10-26T15:48:04.843@msh210 as the letters can only be interpreted as Roman Numerals, it follows that individual letter values can only be powers of 10 or 5 times powers of 10. 20 was only mentioned in relation to combining two roman numerals (and to stress that IXX = 19 is not a valid subtraction). Hope that clears it up for you. – iamogbz – 2015-10-27T04:33:54.823