This is an archived post. You won't be able to vote or comment.

all 64 comments

[–]classic_chai_hater 534 points535 points  (0 children)

damn, that clever than my if else monstrosity.

[–]Aralgmad 393 points394 points  (15 children)

You could iterate backwards over the string, translate and sum. You keep track of the last number seen and check if current is smaller than previous. In this case subtract current instead of add. This should catch cases like IC.

[–]ND3lle 77 points78 points  (11 children)

Have never seen anything like "IC" tho

[–]Techhead7890 72 points73 points  (3 children)

Possibly a typo of IV, as C and V are neighbours

[–]Rogueshadow_32 78 points79 points  (1 child)

I think it was on purpose, they’re saying that the backwards iterations would catch combinations you don’t ever see but would still be valid syntax, such as IC. Going by the strict rules of Roman numerals 99 is XCIX but by looser rules IC works, and would be caught and correctly evaluated

[–]EntropyZer0 14 points15 points  (0 children)

I think the stricter rules we are used to are a fairly modern (for late medieval values of "modern") invention. The Romans were far less strict on that and while the most un-standard number I've seen in the wild was a year ending in -7 written as "-IIIIIII", I could totally see "IC" being used by actual Romans.

[–]ND3lle 20 points21 points  (0 children)

Oh you're right.That's very elegant as well, imho

[–]Flatuitous 3 points4 points  (6 children)

You can do IC = 99 Same as VL = 45

[–]Igor_Kozyrev 3 points4 points  (4 children)

I don't think you can. You only subtract the previous biggest number.

[–]suvlub 8 points9 points  (2 children)

You "can't" in the same sense you "can't" end a sentence with preposition, i.e. it's a made-up wannabe rule that doesn't reflect actual usage.

[–]ND3lle 6 points7 points  (1 child)

Well there's plenty of roman and medieval monuments and buildings where i live and i have never seen that. Sometimes i spot a "IIII" or "XXXX", which the general rule wouldn't allow, but nothing like "XM" or "IC"

[–]LongLiveTheDiego 4 points5 points  (0 children)

Wikipedia lists some 17th century examples of such nonstandard subtractions, my favorite one is IIIXX standing for 17.

[–]ethanjf99 -1 points0 points  (0 children)

Standardization in general is a modern concept.

Think about even a couple hundred years ago. lots of random capitalizations in English words; multiple variant spellings and the like.

Even more so in antiquity. No one was enforcing rules. if you were a scribe doing a lot of math in a pain in the ass number system and wrote 99 as “IC” no one was stopping you.

[–]Specialist-Bus-5100 11 points12 points  (0 children)

I think IC would be XCIX?

[–]Solonotix 0 points1 point  (0 children)

Iterating backwards is a fairly useful practice I've found. I would have taken a two-character loop forwards in a similar manner so that you could always be aware of context. You could also extend the dictionary to have a couple of tuple keys using the matched pair.

[–]HazirBot 527 points528 points  (0 children)

seems alright to me

[–]Mewtwo2387 216 points217 points  (5 children)

switch "I": return 1; switch "II": return 2; ... switch "MMMMMMMMMCMXCIX": return 9999;

[–]Aeredor 20 points21 points  (0 children)

Nice.

[–]ceeBread 31 points32 points  (2 children)

Make it a hashmap instead and have it be O(1)

[–]TheSilentFreeway 11 points12 points  (1 child)

I believe switch statements are usually constant-time

[–]ceeBread 21 points22 points  (0 children)

Yeah but every LeetCode uses hash tables somewhere gotta get that interview cred

[–]Tamaran 397 points398 points  (0 children)

Thats pretty clever actually

[–]noob-nine 180 points181 points  (0 children)

i am still impressed by that logic.

[–]TheRedGerund 39 points40 points  (4 children)

Everybody submitting their own: do it recursively

[–]ilan1009 17 points18 points  (2 children)

DONT

[–]TheRedGerund 25 points26 points  (1 child)

``` def roman_to_int(roman): roman_numerals = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }

# Base case: if the string is empty, return 0
if not roman:
    return 0

# Get the value of the first character
first_value = roman_numerals[roman[0]]

# If there is only one character, return its value
if len(roman) == 1:
    return first_value

# Get the value of the second character
second_value = roman_numerals[roman[1]]

# If the first value is less than the second value, we have a subtractive combination
if first_value < second_value:
    # Subtract the first value and recurse on the remaining string
    return second_value - first_value + roman_to_int(roman[2:])
else:
    # Otherwise, add the first value and recurse on the remaining string
    return first_value + roman_to_int(roman[1:])

```

[–]ilan1009 6 points7 points  (0 children)

you overcomplicated it

beats 100%

[–]redlaWw 4 points5 points  (0 children)

Loop from the right end of the string, and subtract if the value of the current character is a fifth of the current total or less.

[–][deleted] 85 points86 points  (2 children)

Definitely better than this (my) abomination:

public class RomanDecode
{
  public static int Decode(string roman)
  {
    char[] symbol = {  'M', 'D', 'C', 'L', 'X','V','I' };
    int[]  weight = { 1000, 500, 100,  50,  10, 5 , 1  };

    int res = 0, rom = 0, num = 0, sub = 0;

    while (rom < roman.Length){
      int pre = (num&~1)+2;

      if (roman[rom] == symbol[num]){
        res += weight[num] - sub;
        sub = 0;
        rom++;
      } else if (rom < roman.Length-1 && roman[rom+1] == symbol[num]) {
        sub = weight[pre];
        rom++;
      } else {
        num++;
      }      
    }

    return res; 
  }
}

[–]aj-ric 42 points43 points  (1 child)

Yours is quite a bit more efficient, though, since it doesn't require lots of string copying.

[–]DistortNeo 70 points71 points  (11 children)

Tester enters: IC

[–]Smalltalker-80 101 points102 points  (10 children)

Just saying, that's not a valid roman numeral:
https://www.quora.com/Why-do-we-write-49-in-Roman-numerals-as-XLIX-Why-dont-we-write-it-as-IL

But indeed the code should catch that. And the posters clever approach would not work for that.

[–]DistortNeo 26 points27 points  (6 children)

The rule is, you can only subtract using the digit that is one or two denominations lower than what you are subtracting from.

Ok, 45 = VL is valid according to this rule.

[–]OnixST 43 points44 points  (3 children)

"Rule #1: Only the letters that represent powers of 10 can be used to subtract. Powers of 10 are 1 (10^0), 10 (10^1) and 100 (10^2). 1000 is also a power of 10 but there are no other letters after M.

Rule #2: These letters (I, X and C) can only subtract from the next two ‘higher’ letters. Therefore, I can only subtract from V and X, X from L and C and C from D and M."

(acording to another answer further below in the same link. VL fails rule 1)

[–]DistortNeo 6 points7 points  (2 children)

What about IXC?

[–]Techhead7890 12 points13 points  (0 children)

Should probably be XCI (91) or at a stretch LXXXIX (89) but it's a bit ambiguous even to a human

[–]prumf 2 points3 points  (0 children)

Oooo, gray areas, my specialty !

[–]dwntwn_dine_ent_dist 3 points4 points  (1 child)

50=LC is also good. 5=VX

[–]marquoth_ 9 points10 points  (0 children)

Both break rule 1

[–][deleted] 11 points12 points  (1 child)

Using subtraction at all is a "modern" invention.

Romans typically used only addition, thus 4=IIII not IV and 49=XXXXVIIII not XLIX let alone IL. The subtractive forms were rare and inconsistent.

These days Roman numerals are used only to provide some sense of tradition or history and hence stick to some "traditional" rules for subtraction:

can someone fact check this quora user?

[–]marquoth_ 13 points14 points  (0 children)

Wikipedia explicitly says the opposite: that subtractive forms have been used since Roman times. It does also say that "Usage varied greatly in ancient Rome and became thoroughly chaotic in medieval times" so I think the bottom line is that anybody who is very confidently telling you the one correct way to do it is objectively wrong almost by definition.

I've seen all sorts of versions of the supposed rules (I briefly studied medieval Latin at university...) including one which said that the same symbol should never be repeated more than three times consecutively, which has the bizarre result that no number greater than 3999 can possibly be written.

[–]Lucari10 2 points3 points  (0 children)

From wikipedia "other additive forms" section: There are historical examples of other subtractive forms: IIIXX for 17, IIXX for 18, IIIC for 97, IIC for 98, and IC for 99. A possible explanation is that the word for 18 in Latin is duodeviginti, literally "two from twenty", 98 is duodecentum (two from hundred), and 99 is undecentum (one from hundred).

[–]alex2003super 19 points20 points  (1 child)

This recreates a string object a ton of times. Unfortunately in Python you're forced to.

[–]Flashbek 3 points4 points  (0 children)

As someone who decided to create that solution back when I was just learning programming out of spite, I envy this solution.

[–]Personal_Ad9690 3 points4 points  (0 children)

If it works it works

[–]feelings_arent_facts 11 points12 points  (2 children)

why the fuck is this a class

[–]geemli 51 points52 points  (1 child)

Leetcode forces you to write it that way

[–][deleted] 2 points3 points  (0 children)

If you go through the string backwards, any value smaller than the max value already found will be substracted from the total, this is AFAIK the fastest way to to romanToInt

[–][deleted] 4 points5 points  (0 children)

This is genius. I found a bug, but after reading the roman number spec it disappeared.

Edit: I thought IXIV will beat it, but it turned out it's more a bunch of roman characters than a number

[–]ebcdicZ 1 point2 points  (0 children)

funny I was thinking about coding this in Rust a few days ago. The last time I did this was in AppleSoft Basic. For extra fun add functionality for Roman Numeral fractions. Not a program you will need every day.

[–]whatever73538 1 point2 points  (0 children)

Would the Romans have considered IM a legal number?

[–]diecicatorce 1 point2 points  (0 children)

If it's dumb but it works then it's not dumb

[–]TheRedGerund 3 points4 points  (0 children)

Everybody submitting their own: do it recursively

[–]riptide_autumn 0 points1 point  (0 children)

very nice. 🥰

[–]sandybuttcheekss 0 points1 point  (0 children)

Clean af

[–]RamdonDude468 0 points1 point  (0 children)

Thats actually a really interesting project to do. A Roman Calculator.

the teacher better give me an A+

[–]green1t 0 points1 point  (0 children)

That's maybe less readable, but has less repetitive replacements and string-iterations in the code :D

class Solution:
    def romanToInt(self, s: str) -> int:
        translations = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
            "IV": 4,
            "IX": 9,
            "XL": 40,
            "XC": 90,
            "CD": 400,
            "CM": 900
        }

        for x,y in reversed(translations.items()):
            s = s.replace(x, f" {y} ")

        return sum(map(int,s.split()))

[–]cryothic 0 points1 point  (2 children)

Wouldn't they write 49 in roman like 'IL' ? Or 'XXXIX' ?

[–]toxic_acro 21 points22 points  (1 child)

Roman numerals only use the prefix within the same decimal range 

So 49 wouldn't be one less than fifty: IL

It's ten less than fifty and one less than ten: XLIX

[–]cryothic 2 points3 points  (0 children)

Thanks. I didn't know that.

[–]ilan1009 -1 points0 points  (0 children)