11
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

@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.

\$\endgroup\$
  • \$\begingroup\$ Nice catch, 2, 3 and 4 are indeed broken. How did I not catch that... \$\endgroup\$ – Mast Jan 26 '16 at 10:25
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Good review, and I totally agree the improvements. Nevertheless the initial loop needs break; (or will generate a lot of unexpected romans). BTW the for() loop may be replaced by while (num > 0), so avoids declaring var i. I already included those changes in my proposed edit in your answer. \$\endgroup\$ – cFreed Jan 23 '16 at 10:24
  • \$\begingroup\$ How about reordering the loops - remove the outer for/while and change the if to while? The idea is to check roman letters from the highest value to lowest and add as many of the same latter as possible before going to lower value. \$\endgroup\$ – user52292 Jan 23 '16 at 11:27
  • 1
    \$\begingroup\$ Agree that the for loop should be while loop. Why use modulus when >= would suffice? If you include all possibilities, i.e. >=900 is CM, >= 400 is CD, then you won't need regex at all. \$\endgroup\$ – dbasnett Jan 23 '16 at 12:56
  • \$\begingroup\$ @dbasnett Replacing the % with >= gives an infinite loop. \$\endgroup\$ – SirPython Jan 23 '16 at 18:58
  • 1
    \$\begingroup\$ @cFreed A for always has a clear start and end. A while depends on the rest of the code and is therefore more error-prone. \$\endgroup\$ – Mast Jan 24 '16 at 22:33
2
\$\begingroup\$

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. 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. */

public class RomanYear
{
    private String era;                                                                 // Era initials, e.g. "BC" or "AD"
    private int year;                                                                       // Arabic year alone, e.g. 1916

    public RomanYear(String stringYear)
    {
        era = stringYear.substring(stringYear.length() - 2);
        year = Integer.parseInt(stringYear.substring(0,stringYear.length() - 3));
    }

    public String getRomanYear()
    {   
        if ( year == 0)                                                         // Special case of 0 AD or 0 BC ...
            return "No year 0 BC or 0 AD ! After 1 BC comes 1 AD.";

        if (year / 1000 > 9)                                                            // Date range check ...
            return "Input year " + year + " " + era + " is out of range for this program.";
        StringBuilder romanYear = new StringBuilder("");                                                                // Initialise output string                             

                                                                                            // Numerals for ...
        String[][] numerals = { 

                                { "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

                                                    };                                              

        int period = 10000,
            remYear = year,
            numPeriods,                                                                                                         
            decExp = 3;
        for (decExp = 3; decExp > -1; decExp--)                             // Generate period substrings ...
        {
            period /= 10;
            numPeriods = remYear / period;
            switch(numPeriods)                                                                  
            {
                case 0: break;
                case 1 : romanYear.append(numerals[decExp][0]); break;
                case 2 : romanYear.append(numerals[decExp][1]); break;
                case 3 : romanYear.append(numerals[decExp][2]); break;
                case 4 : romanYear.append(numerals[decExp][3]); break;
                case 5 : romanYear.append(numerals[decExp][4]); break;
                case 6 : romanYear.append(numerals[decExp][5]); break;
                case 7 : romanYear.append(numerals[decExp][6]); break;
                case 8 : romanYear.append(numerals[decExp][7]); break;
                case 9 : romanYear.append(numerals[decExp][8]); break;
                default: break;
            }
            remYear = (remYear - numPeriods * period);
        }
        return romanYear.toString() + " " + era;
    }

    public static void main(String[] args)
    {
        String[] yearStrings = { "0 BC", "0 AD", "9 BC", "99 AD", "432 AD", "999 AD", "1001 AD", "1492 AD", 
                                 "1690 AD", "1789 AD", "1899 AD", "1900 AD", "2018 AD", "4018 AD", "5092 AD", 
                                 "8999 AD", "9999 AD", "11700 AD" };

        for (int i = 0; i < yearStrings.length; i++)
        {
            RomanYear romanYear = new RomanYear(yearStrings[i]);
            System.out.printf("%-20s %-20s\n", yearStrings[i], romanYear.getRomanYear());
        }

    }


}

OUTPUT
======

0 BC            No year 0 BC or 0 AD ! After 1 BC comes 1 AD.
0 AD            No year 0 BC or 0 AD ! After 1 BC comes 1 AD.
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        Input year 11700 AD is out of range for this program.

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.

\$\endgroup\$
  • \$\begingroup\$ It looks like you indenting is off. \$\endgroup\$ – Stephen Rauch Oct 29 '18 at 23:06
  • 2
    \$\begingroup\$ Yes. What you see in edit mode isn't often what it's going to look like after, especially after the recent narrowing of the code viewport. Thanks, SR. \$\endgroup\$ – Trunk Oct 30 '18 at 11:05
  • \$\begingroup\$ A great thing about TDD is that you can write a bunch of tests at once if you see that the implementation will be easy - and if you're wrong, you can back off and return to implementing one at a time. Remember though, that the most important step in TDD is the refactoring, rather than merely passing tests. \$\endgroup\$ – Toby Speight Oct 30 '18 at 16:25
  • \$\begingroup\$ As a matter of interest, are TDD tests passed by dedicated testers before, or after, code writing ? \$\endgroup\$ – Trunk Oct 30 '18 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.