4
\$\begingroup\$

I've submitted the following code for a job interview, and I wanna know if there is anything I can improve on it, or better ways to do the same thing.

const algarismsMap = {
    1 : {
        1 : 'I',
        4 : 'IV',
        5 : 'V',
        9 : 'IX'
    },
    1e1 : {
        1 : 'X',
        4 : 'XL',
        5 : 'L',
        9 : 'XC'
    },
    1e2 : {
        1 : 'C',
        4 : 'CD',
        5 : 'D',
        9 : 'CM'
    },
    1e3: {
        1 : "I\u0305",
        4 : 'I\u0305V\u0305',
        5 : 'V\u0305',
        9 : 'I\u0305X\u0305'
    },
    1e4: {
        1 : "X\u0305",
        4 : 'X\u0305L\u0305',
        5 : 'L\u0305',
        9 : 'X\u0305C\u0305'
    },
    1e5 : {
        1 : "C\u0305",
        4 : 'C\u0305D\u0305',
        5 : 'D\u0305',
        9 : 'C\u0305M\u0305'
    }
}

const divisors = Object.keys( algarismsMap ).reverse()

const romanizeNumber = module.exports = function( n ) {

    // not throwing an error because this can happen while recursing
    if ( n <= 0 ) {
        return ''
    }

    // welp, for numbers greater than 3999999 we break roman rules of not repeating the same algarism more than 3 times, 
    //   or we need to add more dashes, which is not really documented, at least I could not find some reliable source about it. 🤔
    if ( n >= 4e6 ) {
        throw new Error( 'The max supported number to be converted is 3999999' )
    }

    let romanizedNumber = ''

    // Some special cases for the M algarism.
    if ( n >= 1e3 && n <= 3999 ||  n >= 1e6 && n <= 3999999 ) {

        romanizedNumber += ( n >= 1e6 ? 'M\u0305' : 'M' ).repeat( n / (n >= 1e6 ? 1e6 : 1e3 ) )
        romanizedNumber += romanizeNumber( n % (n >= 1e6 ? 1e6 : 1e3 ) )

    } else {

        for ( let i = 0; i < divisors.length; i++ ) {

            const currDivisor = divisors[i]|0
            const currDivisorInfo = algarismsMap[currDivisor]

            const internalDivisors = Object.keys( currDivisorInfo ).reverse()

            // The number is not divisible by this one, keep going (we could just check if n < currDivisor duh)
            if ( n % currDivisor === n ) {
                continue
            }

            for ( let k = 0; k < internalDivisors.length; k++ ) {

                const currInternalDivisor = internalDivisors[k]|0
                const currInternalDivisorAlgarism = currDivisorInfo[currInternalDivisor]

                if ( n >= currInternalDivisor * currDivisor ) {

                    // the 1 check here is basically for the same motive than the 'M' check above.
                    romanizedNumber += currInternalDivisor === 1 ? currInternalDivisorAlgarism.repeat( n / currDivisor ) : currInternalDivisorAlgarism

                    romanizedNumber += romanizeNumber( n % (currInternalDivisor * currDivisor) )

                    return romanizedNumber
                }
            }
        }

    }

    return romanizedNumber
}

The \u0305 is the unicode for the combining overline character: https://en.wikipedia.org/wiki/Overline

\$\endgroup\$
  • 1
    \$\begingroup\$ Semicolons are missing all over the place -- a habit that is a great source of bugs especially when something is maintaining this code. I am not a JS guy, could you tell what is the ... = internalDivisors[k]|0 idiom? \$\endgroup\$ – Igor Soloydenko May 4 '17 at 16:13
  • 3
    \$\begingroup\$ Thanks for explaining the x|0 idiom! Good to know. As far as the semicolons go, it's your choice but many devs including me find it a gate to bugs hard to detect. In other words The only real pitfall when coding without semicolons which is mentioned in the post you shared, is a big deal, and the prepend next line with ; is a dirty hack. The “everybody else is doing it” phrase is a real argument, if everyone uses the semicolons, not using them becomes a risk when it comes to maintenance -- as a tech lead I would enforce the semicolons. \$\endgroup\$ – Igor Soloydenko May 4 '17 at 16:28
  • 1
    \$\begingroup\$ As I said, it's your call -- that's why I am not posing an answer, but a comment. I'm doing it only on personal projects is a common reasoning, but as soon as you delegate maintenance to someone else you may get cursed for that decision. \$\endgroup\$ – Igor Soloydenko May 4 '17 at 16:46
  • 1
    \$\begingroup\$ @IgorSoloydenko Thanks for supporting semi-colons in JS! :) Call me old-school, but I tend to insist on them too \$\endgroup\$ – Flambino May 4 '17 at 17:17
  • 3
    \$\begingroup\$ Haven't had time to really review this, so just two things that stand out: 1) The explanation for \u0305 should probably be in the code too, and 2) you're fond of the scientific number notation like 4e6 yet you also have to write 3999999 in the comment and error message – I'd define 3999999 as a MAX_INPUT constant or something, and stick to using decimals. To me it's just easier than doing the (admittedly simple) conversion in my head. You're already dealing with roman and decimal notation - I'd rather not add another on top of that. \$\endgroup\$ – Flambino May 4 '17 at 17:34
3
\$\begingroup\$
  • I would define a constant overline="\u0305" and then use interpolation further down: 4 : `C${overline}D#{overline}`,, it might even make sense to define overlineD and overlineC constants. An alternative might be to create an overline method and write something like 4: overline('CD') or even a tagged template literal (4: overline`CD`) if you want to impress.

  • Object.keys( algarismsMap ).reverse(): The order of keys in a hash is not guaranteed, it can vary depending on the implementation and if keys have been deleted, etc. If you need order you should use an array. Also rather than reversing just define it backwards.

  • Rather than if {...} else [lots of code] I find it better to use an early return if {...; return; } [lots of code]

  • One of the biggest thing to me is the lack of tests. I would expect to see something in an interview assignment, it doesn't have to use a framework, I would be fine with something like:

    function test(number, roman) {
      if (romanizeNumber(number) !== roman)
        console.error(`Failed! ${number} should be ${roman} but was ${romanizeNumber(number)}`);
    }
    test(10, 'X');
    test(11, 'XI');
    ...
    
\$\endgroup\$
  • \$\begingroup\$ About the lack of tests, the assignment platform were this was submitted had automated testing already (hackerrank.com). \$\endgroup\$ – JCM May 4 '17 at 20:58
3
\$\begingroup\$

Short review;

  • I think you mean https://en.wikipedia.org/wiki/Algorism, not algarism? I would use the correct name in that case, and personally I would even put a link to the wikipedia article for people (the vast majority I assume) who have never heard about Algorisms before

  • I would call Object.keys( algarismsMap ).sort().reverse(), making sure of the sort order

  • This statement annoys me tremendously as a reviewer:

    if ( n >= 1e3 && n <= 3999 || n >= 1e6 && n <= 3999999 )

    Either go for

    if ( n >= 1e3 && n < 4e3 || n >= 1e6 && n <= 4e6 )

    or

    if ( n >= 1000 && n < 4000 || n >= 1000000 && n <= 4000000 )

    mixing those 2 constant styles just makes my brain go 'wot?' To keep it simple, I would go with the first approach.

\$\endgroup\$
1
\$\begingroup\$

General style

  • As this is an interview submission, I recommend a conservative coding style including semicolons.
  • Mixing decimal and exponential notation for number literals is inconsistent.
  • Mixing "" and '' without need is somewhat irritating.
  • +string is more idiomatic and robust compared to the bitwise string|0 for integer string to number conversion.
  • for (let divisor of divisors) { ... } is more succint than for (let i = 0; i < divisors.length; i++) { let divisor = divisors[i]; ... }
  • Catching and handling corner cases such as if ( n % divisor === n ) continue; early at the beginning of the loop body improves readability somewhat.
  • I propose renaming
    • algarismsMap to algarisms - appending type information such as 'Array' or 'Map' rarely improves readability.
    • algarisms to symbols - algarism is exotic, symbol is a much more common term.
    • currDivisor to divisor - adding 'curr' and similar prefixes to loop iterators is noisy.
    • internalDivisor to digit - as it is more specific.

Error handling

This is inconsistent:

// not throwing an error because this can happen while recursing
if ( n <= 0 ) {
    return ''
}

if ( n >= 4e6 ) {
    throw new Error( 'The max supported number to be converted is 3999999' )
}

You throw an error when the input is too large, but not when it is too small. Also, instead of throwing an Error you could throw the more descriptive RangeError

Comments

While you include inline comments adressing implementation details, your interview submission is completely lacking in documentation style comments.

Regarding your inline comments:

// The number is not divisible by this one, keep going (we could just check if n < currDivisor duh)

Why don't you use n < currDivisor then?

// welp, for numbers greater than 3999999 we break roman rules of not repeating the same algarism more than 3 times,
// or we need to add more dashes, which is not really documented, at least I could not find some reliable source about it. 🤔 

Actually, you don't repeat symbols more than three times but throw an Error. This comment seems outdated. Also, using colloquial terms such as duh, welp and emoticons 🤔 in comments feels somewhat out of place in a professional setting (assuming you included them in your interview submission and not just for us reviewers).

// the 1 check here is basically for the same motive than the 'M' check above.

Since you never state the motive for the 'M' check, this comment is somewhat unhelpful.

Data structures

Your algarismsMap is a specialised, repetitive datastructure. It cannot be reused, as its structure seems to have explicitly been chosen to fit the needs of the romanizeNumber function.

However, you still need to perform key extraction and reversal

const internalDivisors = Object.keys( currDivisorInfo ).reverse()

as well as string to number conversion

const currInternalDivisor = currInternalDivisor|0

in order to extract the digits. This makes your code more complicated than necessary and less robust, as you rely on the unspecified Object.keys() enumeration order.

Also, you still need to hardcode some data within the romanizeNumber function:

romanizedNumber += ( n >= 1e6 ? 'M\u0305' : 'M' ).repeat( n / (n >= 1e6 ? 1e6 : 1e3 ) )

While you can't avoid handling these special cases somehow, you could still avoid redundant definition of roman symbols.

Design

Your monolithic, recursive romanizeNumber function is pretty complex and hard to read and understand. You can simplify your code by identifying sub-tasks and breaking it down into smaller, modular functions:

  • splitDigits(n) - split a number into digits. This replaces the modulo operations all over the place such as n % (currInternalDivisor * currDivisor) as well as the whole recursion.
  • romanizeDigit(digit, place) - convert a single digit. This basically replaces the inner loop over internalDivisors as well as the special vinculum handling.

We can also exploit the repetitive nature of digit conversion

1 - 10:     I II III IV V VI VII VIII IX X
10 - 100:   X XX XXX XL L LX LXX LXXX XC C
100 - 1000: C CC CCC CD D DC DCC DCCC DM M

and introduce a lookup table relating digits to symbols.

The broken-down, non-recursive, documented romanizeNumber could then be written as follows:

/**
 * Split positive integer n < 1e21 into digits.
 *
 * @param {number} n - positive integer < 1e21.
 * @return {number[]} digits starting with lowest position.
 */
function splitDigits(n) {
  return Array.from(String(n), Number);
}

/**
 * Symbols used by roman (vinculum) numerals in ascending order for non-vinculum or mixed-vinculum digits.
 */
const lower = ['I', 'V', 'X', 'L', 'C', 'D', 'M', 'V\u0305'];

/**
 * Symbols used by roman (vinculum) numerals in ascending order for entirely-vinculum digits.
 */
const upper = ['I\u0305', 'V\u0305', 'X\u0305', 'L\u0305', 'C\u0305', 'D\u0305', 'M\u0305'];

/**
 * Lookup map from decimal digits to roman symbol indices or offsets.
 * @example
 * lookup[4] // [0, 1] which corresponds to ['I', 'V']
 */
const lookup = [[], [0], [0, 0], [0, 0, 0], [0, 1], [1], [1, 0], [1, 0, 0], [1, 0, 0, 0], [0, 2], [2]];

/**
 * Convert decimal digit to roman numeral according to the digit's place value.
 * @example 
 * romanizeDigit(4, 1) // 'XL' since digit 4 at place 1 has place value 40
 *
 * @param {number} digit - digit from 0 - 9.
 * @param {number} place - place of digit.
 * @return {string} roman numeral with value digit × 10^place.
 */
function romanizeDigit(digit, place) {
  let vinculum = place > 3 || (place == 3 && (digit == 4 || digit == 9));
  if (vinculum) {
    return lookup[digit].map(i => upper[2 * (place - 3) + i]).join('');
  } else {
    return lookup[digit].map(i => lower[2 * place + i]).join('');
  }
}

/**
 * Convert positive integer to roman numeral.
 *
 * @param {number} n - integer in range [1, 3999999].
 * @return {string} roman numeral with value n.
 */
function romanizeNumber(n) {
  if (n < 1 || n > 3999999) throw RangeError('Only numbers between 1 and 3999999 supported');
  let digits = splitDigits(n);
  return digits.map((digit, i) => romanizeDigit(digit, digits.length - i - 1)).join('');
}
\$\endgroup\$

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.