Number to Roman numerals

Question

I've been working on numerals conversion lately. Now the JavaScript course I'm following asked me to do something similar for Roman numerals.

To keep things fresh and given the amount of test-cases provided I decided to write this one Test-Driven Development style. That is, for as much as I understand it.

First I check whether it's dividable by a full numeral (M, C, etc.). After that I have to reverse the string because the numerals were added in reverse order. The next step is to translate all combinations into their correct form using regex and a translation map. The functions were written in that order and fixing the problem the last part caused.

So far it looks very messy. Is this how one is supposed to solve problems TDD style? There is definitely a lot of code duplication going on, could this be fixed with another map?

Challenge

Convert the given number into a Roman numeral.

All Roman numerals answers should be provided in upper-case.

Test cases

convert(5) // "V".
convert(9) // "IX".
convert(12) // "XII".
convert(16) // "XVI".
convert(29) // "XXIX".
convert(44) // "XLIV".
convert(45) // "XLV"
convert(68) // "LXVIII"
convert(83) // "LXXXIII"
convert(97) // "XCVII"
convert(99) // "XCIX"
convert(500) // "D"
convert(501) // "DI"
convert(649) // "DCXLIX"
convert(798) // "DCCXCVIII"
convert(891) // "DCCCXCI"
convert(1000) // "M"
convert(1004) // "MIV"
convert(1006) // "MVI"
convert(1023) // "MXXIII"
convert(2014) // "MMXIV"
convert(3999) // "MMMCMXCIX"

Code

function convert(num) {
  roman = "";
  for (var i = 0; i < num; i++) {
    //MDCLXVI
    if (!(num % 1000)) { roman += "M"; num -= 1000; }
    else if (!(num % 500)) { roman += "D"; num -= 500; }
    else if (!(num % 100)) { roman += "C"; num -= 100; }
    else if (!(num % 50)) { roman += "L"; num -= 50; }
    else if (!(num % 10)) { roman += "X"; num -= 10; }
    else if (!(num % 5)) { roman += "V"; num -= 5; }
    else if (!(num % 1)){ roman += "I"; num -= 1; }
  }
  roman = roman.split('').reverse().join('');
  var translationMap = {
    DCCCC : 'CM',
    CCCC : 'CD',
    LXXXX : 'XC',
    XXXX : 'XL',
    VIIII : 'IX',
    IIII : 'IV',
  };
  for (var i in translationMap) {
    roman = roman.replace(new RegExp(i,'g'), translationMap[i]);
  }
  return roman;
}

convert(3999);

Run it at repl.it

Answer 1

@SirPython has already given us some great steps to improve this implementation but I'd like to focus on the process of getting there as well since that seems to be part of the question.

Is this how one is supposed to solve problems TDD style?

I think it's interesting that you suggest TDD shapes your solution. I find that a test driven approach changes my interfaces but has much less impact on what the final implementation of a function looks like. Whatever process you use, if you end up with "very messy" code then I think something needs to change. Code is written for humans to read and messy code will cause you grief in the future.

I'm not sure what your workflow looked like to arrive at this solution but here's what I would expect:

1. Write a test describing what the unit you are testing should do.
2. See the test fail.
3. Write code to pass the test.
4. See the test pass.
5. Consider if a refactor could improve your implementation and if so apply it.
6. See that all the tests still pass, giving you confidence that your refactor was a safe change.

You have a bunch of test cases but running through and verifying them manually seems tedious. Let's start by making that easy. There are a bunch of testing libraries you might use but we can practice TDD with something simple:

function runTests(tests) {
    var failureCount = 0
    var testsCount = tests.length
    var testTimerName = 'tests completed in'
    console.time(testTimerName)
    for (var t = 0; t < testsCount; t++) {
        var test = tests[t]
        var input = test['input']
        var expectation = test['expected']
        var output = convert(input)
        if (output != expectation) {
            console.log('Failure: expected convert(' + input + ') to equal \'' + expectation + '\' but got \'' + output + '\'')
            failureCount += 1
        }
    }
    console.log(testsCount - failureCount + '/' + testsCount + ' tests passed.')
    console.timeEnd(testTimerName)
}

var tests = [
    {'input': 5, 'expected': 'V'},
    ]
runTests(tests)

When run we get:

ReferenceError: convert is not defined

We need to at least implement a convert function:

function convert(num) {
    return ''
}

---

>
Failure: expected convert(5) to equal 'V' but got ''
0/1 tests passed.
tests completed in: 1ms

A test failed. That's good, we know we'll see failures when they happen. Let's make the test pass.

---

function convert(num) {
    return 'V'
}

---

>
1/1 tests passed.
tests completed in: 1ms

Now we have a quick way to run our tests every time we make a change and see which, if any, failed. That should allow us to make changes to convert fearlessly, confident that we will know if we're improving the implementation or if we break behaviors which used to work.

From here we could add one test case at a time, update convert to make the new test pass, clean up our work, and then repeat. Sometimes that sort of incremental approach works great. Alternately we might write a bunch of tests, all of which will fail for now, and then work on getting more and more of them to pass. Since we already have some idea what our implementation might look like let's take that second approach.

var tests = [
    {'input': 1, 'expected': 'I'},
    {'input': 2, 'expected': 'II'},
    {'input': 3, 'expected': 'III'},
    {'input': 4, 'expected': 'IV'},
    {'input': 5, 'expected': 'V'},
    {'input': 9, 'expected': 'IX'},
    {'input': 12, 'expected': 'XII'},
    {'input': 16, 'expected': 'XVI'},
    {'input': 29, 'expected': 'XXIX'},
    {'input': 44, 'expected': 'XLIV'},
    {'input': 45, 'expected': 'XLV'},
    {'input': 68, 'expected': 'LXVIII'},
    {'input': 83, 'expected': 'LXXXIII'},
    {'input': 97, 'expected': 'XCVII'},
    {'input': 99, 'expected': 'XCIX'},
    {'input': 500, 'expected': 'D'},
    {'input': 501, 'expected': 'DI'},
    {'input': 649, 'expected': 'DCXLIX'},
    {'input': 798, 'expected': 'DCCXCVIII'},
    {'input': 891, 'expected': 'DCCCXCI'},
    {'input': 1000, 'expected': 'M'},
    {'input': 1004, 'expected': 'MIV'},
    {'input': 1006, 'expected': 'MVI'},
    {'input': 1023, 'expected': 'MXXIII'},
    {'input': 2014, 'expected': 'MMXIV'},
    {'input': 3999, 'expected': 'MMMCMXCIX'},
    ]
runTests(tests)

---

>
Failure: expected convert(2) to equal 'II' but got 'I'
Failure: expected convert(3) to equal 'III' but got 'II'
Failure: expected convert(4) to equal 'IV' but got 'II'
23/26 tests passed.
tests completed in: 3ms

Interesting, looks like there are at least a few cases this implementation does not handle correctly yet. We can fix these and running our tests as we go will make sure we don't break other test cases (like 'IX') as we make changes.

In addition to helping us implement new behavior these tests are also useful for the final and essential "refactor" step in a TDD "red-green-refactor" workflow. Now that we have test verifying that this function behaves as we expect we can step back and consider how the implementation can be improved with confidence that we haven't changed its behavior, as long as our tests still pass. If we apply the changes @SirPython suggested we will hopefully see that our tests still pass and perhaps even run in less time.

Taking time for this final refactor step is, I think, essential for making sure incrementally developed behaviors do not end up as the sort of messy but probably valid implementation @Mast wanted to avoid.

Answer 2

Roman letter to value map

if (!(num % 1000)) { roman += "M"; num -= 1000; }
else if (!(num % 500)) { roman += "D"; num -= 500; }
else if (!(num % 100)) { roman += "C"; num -= 100; }
else if (!(num % 50)) { roman += "L"; num -= 50; }
else if (!(num % 10)) { roman += "X"; num -= 10; }
else if (!(num % 5)) { roman += "V"; num -= 5; }
else if (!(num % 1)){ roman += "I"; num -= 1; }

You should be using a map here to store the roman numeral values and their corresponding characters:

var romanCharacterMap = {
    "M": 1000,
    "D": 500,
    ...
}

With this, you can easily add on more letters if you ever felt like expanding it. Now, here is what your code would look like there:

while (num > 0) {
    for(var romanCharacter in romanCharacterMap) {
        var value = romanCharacterMap[romanCharacter];
        if(!(num % value)) {
            roman += romanCharacter;
            num -= value;
            break;
        }
    }
}

Then, to OOP this code up, you could move this function and the new map to an object to keep things together:

var RomanNumberalConverter = {
    ...
}

Then, the map won't be created every time the function is called; it will be created and referenced once.

---

Moar regexes... moar!

In this loop:

  for (var i in translationMap) {
    roman = roman.replace(new RegExp(i,'g'), translationMap[i]);
  }

Every iteration, you are creating a regex for every entry in the map. However, every time this function is called, the same regexes are created because that map is the same every time.

To speed things up, try creating the regex once and keeping it in the map that is also in this RomanNumberConverter object:

translationMap: {
    DCCCC: {
        replace: "CM",
        regex: /DCCCC/g
    },
    ...
}

Your code will now be faster because a new series of regexes doesn't have to be created every function call.

Answer 3

If TDD means writing code to pass tests of increasing complexity, then I think that this process will perforce be inefficient use of coder time. This is because code for the next test will always have to be redesigned to embrace harder test cases. To me, TDD just meant having a good list of tests written before any code was written. The code first written would therefore be an attempt to pass ALL tests for each separate block of the code, e.g. input validation code block or the year conversion code block. In the above situation, I'd also put in a test for year 0 AD just in case execution arrived at it after a subtraction. Likewise with years before 9999 BC or after 9999 AD as these are good nominal boundaries for most applications.

I'm not convinced that the loop algorithm above is faster than, let's say, an algo that set millenia, centuries, decades and digits to the year using 4 successive switch statements and hard-coded conversion strings.

package romanYears;

    /** A small class to allow generation & manipulation of years in Roman numeral format. 
 *  This program covers all years from 9999 BC to 9999 AD inclusive.
 *  Input year strings MUST CONFORM to the format: YYYY BC or YYYY AD, where YYYY is a 
 *  positive integer between 1 and 9999 inclusive. 
 *  Only ONE space is allowed before the era string, "BC" or "AD".
 */

public class Numerals
{
    private static String era;                                                                                              // Era initials, e.g. "BC" or "AD"
    private static int year;                                                                                                // Arabic year alone, e.g. 1916
    private static String yearSt;                                                                                           // Input year string with era and space removed

    final static String[][] numerals = {                                                                                    // NUMERALS FOR ARABIC TO ROMAN CONVERSION ...

                                {"I",                                                                                       // ... XXX1
                                 "II",                                                                                      // ... XXX2
                                 "III",                                                                                     // ... XXX3
                                 "IV",                                                                                      // ... XXX4
                                 "V",                                                                                       // ... XXX5
                                 "VI",                                                                                      // ... XXX6
                                 "VII",                                                                                     // ... XXX7
                                 "VIII",                                                                                    // ... XXX8
                                 "IX" },                                                                                    // ... XXX9

                                { "X",                                                                                      // ... XX1X
                                  "XX",                                                                                     // ... XX2X
                                  "XXX",                                                                                    // ... XX3X
                                  "XL",                                                                                     // ... XX4X
                                  "L",                                                                                      // ... XX5X
                                  "LX",                                                                                     // ... XX6X
                                  "LXX",                                                                                    // ... XX7X
                                  "LXXX",                                                                                   // ... XX8X
                                  "XC" },                                                                                   // ... XX9X

                                { "C",                                                                                      // ... X1XX
                                 "CC",                                                                                      // ... X2XX
                                 "CCC",                                                                                     // ... X3XX
                                 "CD",                                                                                      // ... X4XX
                                 "D",                                                                                       // ... X5XX
                                 "DC",                                                                                      // ... X6XX
                                 "DCC",                                                                                     // ... X7XX
                                 "DCCC",                                                                                    // ... X8XX
                                 "CM" },                                                                                    // ... X9XX

                                { "M",                                                                                      // ... 1XXX
                                  "MM",                                                                                     // ... 2XXX
                                  "MMM",                                                                                    // ... 3XXX
                                  "MV" + "\u0305",                                                                          // ... 4XXX
                                  "V" + "\u0305",                                                                           // ... 5XXX
                                  "V" + "\u0305" + "M",                                                                     // ... 6XXX
                                  "V" + "\u0305" + "MM",                                                                    // ... 7XXX
                                  "V" + "\u0305" + "MMM",                                                                   // ... 8XXX
                                  "MX" + "\u0305" }                                                                         // ... 9XXX
                                };


    public Numerals(String stringYear)                                                                                      // Full Arabic year as a string, e.g. 1916 AD
    {
        if (stringYear.equals(""))
        {
            throw new IllegalArgumentException("Invalid input !", new Throwable("Empty string"));
        }
        if (stringYear.length() < 4)
        {
            throw new IllegalArgumentException("Invalid input !", new Throwable("String too short"));
        }
        era = stringYear.substring(stringYear.length() - 2);
        if (!era.equals("BC") && !era.equals("AD"))                                                                         // Invalid era string, i.e not BC or AD
        {
            throw new IllegalArgumentException("Invalid input !", new Throwable("Era string wrong"));
        }
        yearSt = stringYear.substring(0, stringYear.length() - 3);
        if (!yearSt.equals(yearSt.trim()))
            throw new IllegalArgumentException("Invalid input !", new Throwable("More than 1 space before era"));
        try
        {
            year = Integer.parseInt(yearSt);
        }
        catch (Exception e)
        {
            throw new IllegalArgumentException("Invalid input !", new Throwable("Year in wrong format"));
        }
        if (year < 0) throw new IllegalArgumentException("Invalid input !", new Throwable("Negative year"));
        if (year == 0) throw new IllegalArgumentException("Invalid input !", new Throwable("No year 0 BC or 0 AD"));
        if (year/1000 > 9) throw new IllegalArgumentException("Invalid input !", new Throwable("Year out of range"));
    }

    public String getEra()
    {
        return era;
    }     

    public int getYear()
    {
        return year;
    }

    public static void main(String[] args)
    {
        Numerals numerals;
        String rYear,
               margin = "      ";                                                                                           // Column margin when printing output
        String[] testYears = {                                                                                              // Invalid input formats ...

                "",                                                                                                         // Blank input
                "?",                                                                                                        // Input char invalid & too short
                "9BC",                                                                                                      // No space between year and era & too short
                "0 BC",                                                                                                     // Invalid year
                "0 AD",                                                                                                     // Invalid year
                "1 AB",                                                                                                     // Invalid era string
                "1 A.D.",                                                                                                   // Era has periods
                "AD 12",                                                                                                    // Era before year
                "1 ad",                                                                                                     // Era lower case
                "? BC",                                                                                                     // Year has invalid char
                "-157 BC",                                                                                                  // Negative year
                "33.3 BC",                                                                                                  // Non-integer year
                "10  BC",                                                                                                   // Double spacing before era
                "9 BC",                                                                                                     // Low BC year & IX test
                "99 AD",                                                                                                    // Low AD year & XCIX vs IC test
                "432 AD",                                                                                                   // CD test
                "999 AD",                                                                                                   // CM test & XCIX test
                "1001 AD",                                                                                                  // MI test
                "1492 AD",                                                                                                  // MCD test
                "1690 AD",                                                                                                  // MDC test
                "1789 AD",                                                                                                  // Bastille test !
                "1899 AD",                                                                                                  // Just before MCM test
                "1900 AD",                                                                                                  // MCM test
                "2018 AD",                                                                                                  // This year test
                "4018 AD",                                                                                                  // MV-prime test
                "5092 AD",                                                                                                  // V-prime test
                "8999 AD",                                                                                                  // Just before MX-prime test
                "9999 AD",                                                                                                  // Just before X-prime test
                "11700 AD"                                                                                                  // Out of allowed range input
        };

        for (String testYear : testYears)
        {
            try
            {
                numerals = new Numerals(testYear);                                                                          // Check validity of each year string
            }
            catch (Exception iae)
            {
                System.out.printf("\n%8s%4s%-60s", testYear, margin, iae.getMessage()                                       // Invalid => Output error message
                        + " Cause: " + iae.getCause().getMessage());
                continue;                                                                                                   // ... and break out of value loop
            }
            try                                                                                                             // Valid year string ...
            {
                year = numerals.getYear();                                                                                  // ... set year parameter ...
                rYear = numerals.convertToRomanYear();                                                                      // ... and try conversion to Roman
            }
            catch (Exception iae)                                                                                           // Can't convert to Roman ...                                                                                       
            {
                System.out.printf("\n%8s%4s%-60s", testYear, margin, iae.getMessage() 
                        + " Cause: " + iae.getCause().getMessage());                                                        // ... Output error
                continue;                                                                                                   // ... and break value loop
            }
                                                                                                                            // Successful conversion to Roman 
            System.out.printf("\n%8s%4s%-60s", testYear, margin, rYear);                                                    // => Output Roman conversion
        }

    }



    /** Converts a year in Arabic numerals to its Roman year equivalent string.
     *  @return A String holding the converted year.
     * */
    public String convertToRomanYear()
    {
        StringBuilder romanYear = new StringBuilder();                                                                      // Initialise output string
        int period = 1000, 
            numPeriods;                                                                                                     // Period, e.g. 1000, 100, 10

        for (int decExp = 3; decExp > -1; decExp--)                                                                         // Generate period substrings
        {
            numPeriods = year / period;
            romanYear.append(switch(numPeriods)
            {
                case 0 -> "";
                case 1, 2, 3, 4, 5, 6, 7, 8, 9 -> numerals[decExp][numPeriods - 1];                                             // New switch statement (Java 14)
                default ->  throw new IllegalArgumentException("Invalid input !", new Throwable("number of periods"));
            });
        }
            year -= numPeriods * period;                                                                                    // Remove converted digit from year
            period /= 10;
        }
        return romanYear.toString() + " " + era;                                                                            // Conversion to output String
    }
}

  OUTPUT
  ======
              Invalid input ! Cause: Empty string                         
       ?      Invalid input ! Cause: String too short                     
     9BC      Invalid input ! Cause: String too short                     
    0 BC      Invalid input ! Cause: No year 0 BC or 0 AD                 
    0 AD      Invalid input ! Cause: No year 0 BC or 0 AD                 
    1 AB      Invalid input ! Cause: Era string wrong                     
  1 A.D.      Invalid input ! Cause: Era string wrong                     
   AD 12      Invalid input ! Cause: Era string wrong                     
    1 ad      Invalid input ! Cause: Era string wrong                     
    ? BC      Invalid input ! Cause: Year in wrong format                 
 -157 BC      Invalid input ! Cause: Negative year                        
 33.3 BC      Invalid input ! Cause: Year in wrong format                 
  10  BC      Invalid input ! Cause: More than 1 space before era         
    9 BC      IX BC                                                       
   99 AD      XCIX AD                                                     
  432 AD      CDXXXII AD                                                  
  999 AD      CMXCIX AD                                                   
 1001 AD      MI AD                                                       
 1492 AD      MCDXCII AD                                                  
 1690 AD      MDCXC AD                                                    
 1789 AD      MDCCLXXXIX AD                                               
 1899 AD      MDCCCXCIX AD                                                
 1900 AD      MCM AD                                                      
 2018 AD      MMXVIII AD                                                  
 4018 AD      MV̅XVIII AD                                                 
 5092 AD      V̅XCII AD                                                   
 8999 AD      V̅MMMCMXCIX AD                                              
 9999 AD      MX̅CMXCIX AD                                                
11700 AD      Invalid input ! Cause: Year out of range  

Of course, this is a simple enough piece of coding. With more complex situations it may well be that writing code to pass successively harder tests may make for a shorter development cycle time. But I think that a lot depends on the way the coder approaches the task. More logical types may find TDD is faster, more conceptual people might find an all-in-one approach easier and quicker.