Comment on

 Need Help??

After my recent "discovery" of the PGA-TRAM algorithm, I couldn't resist coding it up in a variety of languages. I'm doing this as a rosetta code node because I find it fun; hopefully, it'll provide some interesting insights into a variety of programming languages. Please note that this meditation is not about golf, but about implementing an arbitrary, specific algorithm in the most "natural" way in a variety of languages.

Here's the spec:

Write a function, roman_to_dec, to convert a "modern" Roman Numeral to its decimal equivalent. The function takes a single string argument and returns an integer. The string argument may be assumed to always contain a valid Roman Numeral in the range 1-3999. Error handling is not required. For example, roman_to_dec("XLII") should return 42.

Perl

Let's get started with a Perl version:

```use strict;
use warnings;
use List::Util qw(reduce);

{
my %rtoa = ( M=>1000, D=>500, C=>100, L=>50, X=>10, V=>5, I=>1 );
sub roman_to_dec {
reduce { \$a+\$b-\$a%\$b*2 } map { \$rtoa{\$_} } split//, uc(shift)
}
}

my @testdata = ( "XLII", "LXIX", "mi" );
for my \$r (@testdata) {
print "\$r: ", roman_to_dec(\$r), "\n";
}

Running this program produces:

```XLII: 42
LXIX: 69
mi: 1001

To me, this is the most natural way to express the PGA-TRAM algorithm in Perl. It uses a variety of common Perl idioms:

• A hash (rtoa) for the lookup table.
• Lexical scope to "data hide" the rtoa hash.
• A Perlish functional "pipeline": uc -> split -> map -> reduce.
Please feel free to disagree with my assessment and respond with your own preferred Perl solution.

For those folks unfamiliar or uncomfortable with reduce, note that it can be eliminated like this:

```  sub roman_to_dec {
my \$t = 0;
for my \$n ( map { \$rtoa{\$_} } split//, uc(shift) ) {
\$t += \$n-\$t%\$n*2;
}
return \$t;
}
Though I don't mind that at all, I do prefer the reduce version.

Python

As you might expect, my "most natural" Python solution looks very similar to the Perl one above:

```def roman_to_dec(r, __rtoa = dict(M=1000, D=500, C=100, L=50, X=10, V=
+5, I=1) ):
return reduce( lambda t,n: t+n-t%n*2, (__rtoa[c] for c in r.upper())
+ )

testdata = [ "XLII", "LXIX", "mi" ]
for r in testdata:
print r, ":", roman_to_dec(r)
That this solution is essentially identical to the Perl one shows how similar these two languages are. Indeed, I'm fond of claiming that Perl, Python and Ruby are "essentially equivalent". :) Since Python lacks Perl's simple lexical scoping mechanism, I chose to "data hide" the rtoa hash by making it a default function argument. Note that Python default function arguments are initialized once only. Though I could have employed the Python map function (with a lambda), I chose instead to use a lazily evaluated Python generator list comprehension, (__rtoa[c] for c in r.upper()), because that seemed more "naturally Pythonic" to me.

Here's my Haskell solution, using GHC:

```{-# OPTIONS_GHC -fglasgow-exts -Wall #-}

import Data.Char (toUpper)
import Data.List (concat, intersperse)

rtoa :: Char -> Int
rtoa 'M' = 1000
rtoa 'D' =  500
rtoa 'C' =  100
rtoa 'L' =   50
rtoa 'X' =   10
rtoa 'V' =    5
rtoa 'I' =    1
rtoa r   = error \$ "Invalid rtoa char:" ++ show r

urtoa :: Char -> Int
urtoa = rtoa . toUpper

roman_to_dec :: String -> Int
roman_to_dec = foldl1 (\t n -> t+n-t`mod`n*2) . map urtoa

myshow :: (String -> Int) -> String -> String
myshow fn val = val ++ ": " ++ (show (fn val))

testdata :: [String]
testdata = [ "XLII", "LXIX", "mi" ]

main :: IO ()
main = do
putStrLn \$ (concat \$ intersperse "\n" (map (\c -> (myshow roman_to_d
+ec c)) testdata))
Instead of using a rtoa hash, natural in Perl and Python, a rtoa function using simple pattern matching seemed the most Haskelly way of expressing this algorithm.

C++

Finally, my ANSI C++ solution:

```#include <cctype>
#include <iostream>
#include <string>
#include <vector>
#include <numeric>

using namespace std;

const int romtab[] = {
0,0,0,0,0,0, 0,   0,  0,0,  // 00-09
0,0,0,0,0,0, 0,   0,  0,0,  // 10-19
0,0,0,0,0,0, 0,   0,  0,0,  // 20-29
0,0,0,0,0,0, 0,   0,  0,0,  // 30-39
0,0,0,0,0,0, 0,   0,  0,0,  // 40-49
0,0,0,0,0,0, 0,   0,  0,0,  // 50-59
0,0,0,0,0,0, 0, 100,500,0,  // 60-69 (C:67,D:68)
0,0,0,1,0,0,50,1000,  0,0,  // 70-79 (I:73,L:76,M:77)
0,0,0,0,0,0, 5,   0, 10,0   // 80-89 (V:86,X:88)
};

inline int rtoa(int c)
{
return romtab[c];
}

inline int accfn(int t, char c)
{
return t+rtoa(toupper(c))-t%rtoa(toupper(c))*2;
}

int roman_to_dec(const string& s)
{
return accumulate(s.begin(), s.end(), 0, accfn);
}

int main(int argc, char* argv[])
{
vector<string> testdata;
testdata.push_back("XLII");
testdata.push_back("LXIX");
testdata.push_back("mi");
for (vector<string>::const_iterator iter  = testdata.begin();
iter != testdata.end();
++iter) {
cout << *iter << ": " << roman_to_dec(*iter) << '\n';
}
return 0;
}
The Perl reduce function is called "accumulate" in ANSI C++. Implementing the lookup with the admittedly long-winded romtab[] table felt like natural C++ to me because it seeks high performance. Indeed, if you peek inside <ctype.h> you will likely see toupper() implemented in a similar vein. This makes the rtoa(toupper(c)) above ridiculously fast, costing only two (constant) array lookups, not requiring even a single C function call! Also of note in this solution is that I didn't bother with map, instead simply applying the ultra fast rtoa(toupper(c)) combo twice in the accumulator function.

Update: As indicated below, we can eliminate the call toupper(), while eliminating any memory faults on invalid input, by adjusting romtab as shown below:

```// Note: there are less than 256 initializers in this table;
// the uninitialized ones are guaranteed by ANSI C to be
// initialized to zero.
const int romtab[256] = {
0,0,0,0,0,0,   0,   0,   0,   0,  //  00- 09
0,0,0,0,0,0,   0,   0,   0,   0,  //  10- 19
0,0,0,0,0,0,   0,   0,   0,   0,  //  20- 29
0,0,0,0,0,0,   0,   0,   0,   0,  //  30- 39
0,0,0,0,0,0,   0,   0,   0,   0,  //  40- 49
0,0,0,0,0,0,   0,   0,   0,   0,  //  50- 59
0,0,0,0,0,0,   0, 100, 500,   0,  //  60- 69
0,0,0,1,0,0,  50,1000,   0,   0,  //  70- 79
0,0,0,0,0,0,   5,   0,  10,   0,  //  80- 89
0,0,0,0,0,0,   0,   0,   0, 100,  //  90- 99
500,0,0,0,0,1,   0,   0,  50,1000,  // 100-109
0,0,0,0,0,0,   0,   0,   5,   0,  // 110-119
10,0,0,0,0,0,   0,   0,   0,   0   // 120-129
};

// Return the arabic number for a roman letter c.
// Return zero if the roman letter c is invalid.
inline int urtoa(int c)
{
return romtab[c];
}

inline int accfn(int t, char c)
{
return t+urtoa(c)-t%urtoa(c)*2;
}

I'd love to see some sample implementations in other languages, especially Perl 6. So please feel free to respond away. :)

Other Rosetta Code Nodes

In reply to Rosetta PGA-TRAM by eyepopslikeamosquito

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the monks are chillaxin'...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (10)
As of 2018-05-22 08:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (163 votes). Check out past polls.

Notices?