How to resolve the algorithm Roman numerals/Decode step by step in the JavaScript programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Roman numerals/Decode step by step in the JavaScript programming language
Table of Contents
Problem Statement
Create a function that takes a Roman numeral as its argument and returns its value as a numeric decimal integer. You don't need to validate the form of the Roman numeral. Modern Roman numerals are written by expressing each decimal digit of the number to be encoded separately, starting with the leftmost decimal digit and skipping any 0s (zeroes). 1990 is rendered as MCMXC (1000 = M, 900 = CM, 90 = XC) and 2008 is rendered as MMVIII (2000 = MM, 8 = VIII). The Roman numeral for 1666, MDCLXVI, uses each letter in descending order.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Roman numerals/Decode step by step in the JavaScript programming language
First Implementation (Declarative, Stateless)
This implementation uses a declarative and stateless approach:
- It declares a
Valuesarray of pairs, where each pair represents a Roman numeral and its corresponding numeric value. - The
parsefunction takes a Roman numeral string and iterates through theValuesarray, attempting to match the string with each pair. - For each match, the function adds the numeric value to the result and replaces the matched part of the string with a placeholder character (
UnmappedStr) to prevent further matching. - The function returns the final numeric value after looping through all the pairs in
Values.
Second Implementation (Functional, Recursion)
This implementation employs a functional and recursive approach:
- It defines a list of pairs with Roman numerals and their numeric values.
- The
romanValuefunction takes a Roman numeral string and recursively parses it. - It uses a
toArabicfunction to convert the string representation to a number, which is then added to the result of parsing the remaining string. - To handle complex Roman numeral combinations, the
chainfunction is used to map each pair to a new pair where the Roman numeral is removed and the remaining string is returned. - The
isPrefixOffunction checks if one list is a prefix of another. - The
dropfunction removes a specified number of elements from the beginning of a list.
Third Implementation (Purely Functional, Recursion)
This implementation follows a purely functional and recursive approach:
- It defines an object (
trans) mapping Roman numerals to numeric values. - The
romanValuefunction takes a Roman numeral string and recursively parses it. - It uses a comprehension to iterate through a list of Roman numeral glyphs and checks if the string starts with the glyph.
- If a match is found, the corresponding numeric value is added to the result and the remaining string is recursively parsed.
Fourth Implementation (Functional, Fold)
This implementation uses functional programming and demonstrates the use of folding:
- It defines an object (
dctTrans) mapping Roman numerals to numeric values. - The
romanValuefunction takes a Roman numeral string and parses it using a fold. - It iterates through the list of glyphs and adds the corresponding numeric values to the result, depending on whether the glyph is found in the string.
- The fold function accumulates the result by adding the current value to the previous result.
Source code in the javascript programming language
var Roman = {
Values: [['CM', 900], ['CD', 400], ['XC', 90], ['XL', 40], ['IV', 4],
['IX', 9], ['V', 5], ['X', 10], ['L', 50],
['C', 100], ['M', 1000], ['I', 1], ['D', 500]],
UnmappedStr : 'Q',
parse: function(str) {
var result = 0
for (var i=0; i<Roman.Values.length; ++i) {
var pair = Roman.Values[i]
var key = pair[0]
var value = pair[1]
var regex = RegExp(key)
while (str.match(regex)) {
result += value
str = str.replace(regex, Roman.UnmappedStr)
}
}
return result
}
}
var test_data = ['MCMXC', 'MDCLXVI', 'MMVIII']
for (var i=0; i<test_data.length; ++i) {
var test_datum = test_data[i]
print(test_datum + ": " + Roman.parse(test_datum))
}
(function (lstTest) {
var mapping = [["M", 1000], ["CM", 900], ["D", 500], ["CD", 400], ["C", 100], [
"XC", 90], ["L", 50], ["XL", 40], ["X", 10], ["IX", 9], ["V", 5], ["IV",
4], ["I", 1]];
// s -> n
function romanValue(s) {
// recursion over list of characters
// [c] -> n
function toArabic(lst) {
return lst.length ? function (xs) {
var lstParse = chain(mapping, function (lstPair) {
return isPrefixOf(
lstPair[0], xs
) ? [lstPair[1], drop(lstPair[0].length, xs)] : []
});
return lstParse[0] + toArabic(lstParse[1]);
}(lst) : 0
}
return toArabic(s.split(''));
}
// Monadic bind (chain) for lists
function chain(xs, f) {
return [].concat.apply([], xs.map(f));
}
// [a] -> [a] -> Bool
function isPrefixOf(lstFirst, lstSecond) {
return lstFirst.length ? (
lstSecond.length ?
lstFirst[0] === lstSecond[0] && isPrefixOf(
lstFirst.slice(1), lstSecond.slice(1)
) : false
) : true;
}
// Int -> [a] -> [a]
function drop(n, lst) {
return n <= 0 ? lst : (
lst.length ? drop(n - 1, lst.slice(1)) : []
);
}
return lstTest.map(romanValue);
})(['MCMXC', 'MDCLXVI', 'MMVIII']);
[1990, 1666, 2008]
(function (lstTest) {
function romanValue(s) {
return s.length ? function () {
var parse = [].concat.apply([], glyphs.map(function (g) {
return 0 === s.indexOf(g) ? [trans[g], s.substr(g.length)] : [];
}));
return parse[0] + romanValue(parse[1]);
}() : 0;
}
var trans = {
M: 1E3,
CM: 900,
D: 500,
CD: 400,
C: 100,
XC: 90,
L: 50,
XL: 40,
X: 10,
IX: 9,
V: 5,
IV: 4,
I: 1
},
glyphs = Object.keys(trans);
return lstTest.map(romanValue);
})(["MCMXC", "MDCLXVI", "MMVIII", "MMMM"]);
[1990, 1666, 2008]
(() => {
// romanValue :: String -> Int
const romanValue = s =>
s.length ? (() => {
const parse = [].concat(
...glyphs.map(g => 0 === s.indexOf(g) ? (
[dctTrans[g], s.substr(g.length)]
) : [])
);
return parse[0] + romanValue(parse[1]);
})() : 0;
// dctTrans :: {romanKey: Integer}
const dctTrans = {
M: 1E3,
CM: 900,
D: 500,
CD: 400,
C: 100,
XC: 90,
L: 50,
XL: 40,
X: 10,
IX: 9,
V: 5,
IV: 4,
I: 1
};
// glyphs :: [romanKey]
const glyphs = Object.keys(dctTrans);
// TEST -------------------------------------------------------------------
return ["MCMXC", "MDCLXVI", "MMVIII", "MMMM"].map(romanValue);
})();
[1990,1666,2008,4000]
(() => {
// -------------- ROMAN NUMERALS DECODED ---------------
// Folding from right to left,
// lower leftward characters are subtracted,
// others are added.
// fromRoman :: String -> Int
const fromRoman = s =>
foldr(l => ([r, n]) => [
l,
l >= r ? (
n + l
) : n - l
])([0, 0])(
[...s].map(charVal)
)[1];
// charVal :: Char -> Maybe Int
const charVal = k => {
const v = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000
} [k];
return v !== undefined ? v : 0;
};
// ----------------------- TEST ------------------------
const main = () => [
'MDCLXVI', 'MCMXC', 'MMVIII', 'MMXVI', 'MMXVII'
]
.map(fromRoman)
.join('\n');
// ----------------- GENERIC FUNCTIONS -----------------
// foldr :: (a -> b -> b) -> b -> [a] -> b
const foldr = f =>
// Note that that the Haskell signature of foldr
// differs from that of foldl - the positions of
// accumulator and current value are reversed.
a => xs => [...xs].reduceRight(
(a, x) => f(x)(a),
a
);
// MAIN ---
return main();
})();
You may also check:How to resolve the algorithm Sieve of Eratosthenes step by step in the F# programming language
You may also check:How to resolve the algorithm Penney's game step by step in the 11l programming language
You may also check:How to resolve the algorithm Rosetta Code/Fix code tags step by step in the Raku programming language
You may also check:How to resolve the algorithm Parallel brute force step by step in the C# programming language
You may also check:How to resolve the algorithm Substring step by step in the zkl programming language