Wednesday, June 20, 2007

Roman Numeral Conversion in Factor

I whipped up some words to convert integers to Roman numerals. The word <PRIVATE changes the IN: vocabulary to roman.private to hide the implementation from the library user. Of course you can access these private words, like all words in Factor, with a USE:.

The algorithm is simple. Going from high to low, iterate the Roman numeral values and /mod (integer division with remainder) each with the input, outputting the divisor and replacing the input with the remainder. This algorithm treats 4s and 9s as digits, just as it treats single letters as digits (i, v, x, etc). Without the 4s and 9s, you end up getting longer answers that, while logical, are wrong, e.g. 9 is "ix", not "viv". (I found this bug in the first iteration while writing unit tests.)

The words we care about, >roman and >ROMAN, are placed IN: roman because of the PRIVATE> word, which drops back to the public vocabulary roman. The > in a word's name is a convention for words that do conversions; the parentheses around the word (>roman) mean it's an implementation word; you should never have a (>roman) without also having a >roman. Picking these names is done purely by convention--the only forbidden word names are numbers and words that start with a ", which parse as strings. Everything until whitespace is a word name.

The conversion from Roman numerals back to integers and roman+, roman*, etc are in roman.factor.

USING: arrays assocs kernel math math.vectors namespaces
quotations sequences sequences.private strings ;
IN: roman

<PRIVATE

: roman-digits ( -- seq )
{ "m" "cm" "d" "cd" "c" "xc" "l" "xl" "x" "ix" "v" "iv" "i" } ;

: roman-values ( -- seq )
{ 1000 900 500 400 100 90 50 40 10 9 5 4 1 } ;

TUPLE: roman-range-error n ;

: roman-range-check ( n -- )
dup 1 3999 between? [
drop
] [
<roman-range-error> throw
] if ;

: (>roman) ( n -- )
roman-values roman-digits [
>r /mod swap r> <repetition> concat %
] 2each drop ;

PRIVATE>

: >roman ( n -- str )
dup roman-range-check [
(>roman)
] "" make ;

: >ROMAN ( n -- str ) >roman >upper ;

2 comments:

Graham Fawcett said...

For the sake of learning, I coded up your algorithm in Haskell. I'm not a serious Haskell programmer, but I thought you might enjoy the comparison.

Conversions said...

Nice algorithm im just learning factor programming so this is all helpful.
Thanks