Beefy Boxes and Bandwidth Generously Provided by pair Networks vroom
Problems? Is your data what you think it is?

Comment on

( #3333=superdoc: print w/ replies, xml ) 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.


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 very Perly 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.


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.


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.

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

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!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • 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
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others perusing the Monastery: (23)
    As of 2014-04-17 16:01 GMT
    Find Nodes?
      Voting Booth?

      April first is:

      Results (453 votes), past polls