# Optimal short-hand roman numeral generator

Goal:
Write a function that takes a number as input and returns a short-hand roman numeral for that number as output.

Roman Numeral Symbols:

Symbol  Value
I       1
V       5
X       10
L       50
C       100
D       500
M       1,000


For an example of what I mean when I say "short-hand roman numerals", let's consider finding a roman numeral to represent 1983, because that is the year I was born. One option is to do this the normal way (10 letters):

1983 = MCMLXXXIII = (1000 - 100 + 1000 + 50 + 30 + 3)

The other option is to do it the short-hand way (6 characters):

1983 = MXVIIM = (1000 - (10 + 10) + 1000 + 3)

Do you know what this means?!?!!?? If I was roman I could have saved 4 characters every single time I wrote my birth date! Woot Woot!!

However, before I get ahead of myself in excitement, I have a question to write, so I should probably define the short-hand roman numeral rules so we are all on the same page:

Short-Hand Roman Numeral Rules:

1. Always consider symbols from left to right until there are no more characters to consider.
2. If there are no higher-valued symbols to the right of the current symbol:
• Add the value of the current symbol to the running total of this roman numeral.
3. If there are higher-valued symbols to the right of the symbol you are considering:
• Locate the rightmost highest-valued symbol to the right of the current symbol
• Consider all the characters up to that symbol as one roman numeral
• Calculate the value of that roman numeral using these steps
• Subtract the value of that roman numeral from the running total of this roman numeral.
• Move to the next symbol after the group you just considered
4. Each roman numeral must have at least 1 symbol in it.
5. That's it! Anything following these rules will be accepted!

Examples:

IIIIV = (-(1+1+1+1)+5) = 1  //Don't ask me why you'd want to do this!

VVX = (-(5+5) + 10) = 0  //Who said you couldn't represent 0 with roman numerals?!!?

VVXM = (-(-(5+5) + 10) + 1000) = 1000  //Again...don't ask me why you'd want to do this!

MXIIXMI = (1000-(10-(1+1)+10)+1000+1) = 1983  //Ahhh...such a great year :)


Question Rules:

1. Make a function that takes a single number as input and returns a roman numeral for that number as output using the above rules. Calculate the codeGolfScore of this function.

example input: 2011
example possible output: MMXI
another possible output: MMVVIVV     //(2000 + 10 - 4 + 5)

2. Using your function from rule 1, generate the roman numerals between -1000 (that's right, NEGATIVE one-thousand) and 3000. Then sum up the character length of these roman numerals to get your totalCharacterCount. Here's some pseudocode to clarify:

totalCharacterCount = 0;
for(currentNumber = -1000; currentNumber <= 3000; currentNumber++){
totalCharacterCount += getRomanNumeral(currentNumber).length;
}

3. finalScore = codeGolfScore + totalCharacterCount

4. Lowest finalScore wins!

Note: As the totalCharacter count will be in the ten-thousands+, the character-length algorithm should be top priority. Code-golf scores are just the tie-breaker in case multiple users find the optimal algorithm or algorithms that are close to each other.

Good luck, and have fun at your MMXII celebrations tomorrow night!!!

• Great task! However, could you give an example of how a negative roman shorthand looks like? Does DDDDM stand for -1000? – pimvdb Dec 30 '11 at 19:00
• @pimvdb You got it! – Briguy37 Dec 30 '11 at 19:37
• A question regarding the special case zero: Is "" allowed for zero or do we have to use VVX or something equivalent? – Howard Dec 30 '11 at 19:46
• @Howard: Great question, I hadn't thought of that! I've added roman numeral rule 4 for which clarifies that case. – Briguy37 Dec 30 '11 at 20:00
• "Locate the rightmost highest-valued symbol to the right of the current symbol" -- which wins, rightmost or highest-valued? i.e., is IXV = -(-1 + 10) + 5 = -4 (rightmost wins), or IXV = -1 + 10 + 5 = 14 (highest-valued wins)? – Keith Randall Dec 30 '11 at 21:06

## C++, 345 characters of code, 25021 roman numeral digits = 25366

int N[]={1,5,10,50,100,500,1000};int V(int s,int L){if(!L)return 0;int K=0,B,m=s%7+1;for(int k=1,b=7;k<L;k++,b*=7){if(s/b%7>=m){K=k;B=b;m=s/b%7;}}return K?V(s/B,L-K)-V(s%B,K):N[s%7]+V(s/7,L-1);}char r[99];char*f(int n){for(int L=1,B=7,i,j;1;L++,B*=7){for(i=0;i<B;i++){if(V(i,L)==n){for(j=0;j<L;j++){r[j]="IVXLCDM"[i%7];i/=7;}r[L]=0;return r;}}}}


deobfuscated a bit, with a driver:

int N[]={1,5,10,50,100,500,1000};
int V(int s,int L){
if(!L)return 0;
int K=0,B,m=s%7+1;
for (int k=1,b=7;k<L;k++,b*=7) {
if(s/b%7>=m){K=k;B=b;m=s/b%7;}
}
return K ? V(s/B,L-K)-V(s%B,K) : N[s%7]+V(s/7,L-1);
}
char r[99];
char *f(int n){
for(int L=1,B=7;1;L++,B*=7) {
for(int i=0;i<B;i++) {
if(V(i,L)==n){
for(int j=0;j<L;j++) {
r[j]="IVXLCDM"[i%7];i/=7;
}
r[L]=0;
return r;
}
}
}
}
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
printf("%s\n", f(atoi(argv[1])));
}


V computes the numerical value of a given roman numeral string s of length L. Strings are encoded base 7 (first digit is s%7, second digit is s/7%7, ...). Each digit is encoded with I=0, V=1, ..., M=6. f does a brute-force enumeration of possible roman numeral strings to find one that V evaluates to n.

The total number of roman numeral digits is optimal. The longest roman numeral needed for [-1000,3000] is 11 digits (e.g. -827=CMDDMLXXIII), which takes about 5 minutes on my machine.

• Wait a moment, that doesn't behave the way specified. Your program gives e.g. LMCLXXIII as the answer to -777. I'd read that as -50+1000-100+50+10+10+3 = 923 ≠ -777, only with "rightmost higher -valued" instead of "highest" does it give -777. But that was just what you asked for in the comments! – ceased to turn counterclockwis Jan 1 '12 at 2:10
• @leftaroundabout: of course you are right. I'll fix it, but no time right now... – Keith Randall Jan 1 '12 at 4:19
• @leftaroundabout: ok, all fixed. – Keith Randall Jan 1 '12 at 18:32
• All right. It's not optimal now, though (e.g. gives VVVXI for -4 when IXVX is actually shorter, as I just noticed) – but that's perfectly legal. – ceased to turn counterclockwis Jan 3 '12 at 13:24
• @leftaroundabout: ok, fixed again. Hopefully it is correct this time... – Keith Randall Jan 3 '12 at 18:58

## Haskell, 25637 (= 268 + 25369) 26045 (= 222+25823)

r 0="VVX"
r n=s(zip[1000,500,100,50,10,5]"MDCLXV")n ξ
ξ='ξ'
s[]q f
|q<0=s[](5-q)f++"V"
|q<1=""
|r<-q-1='I':s[]r f
s ω@((v,a):l)q f
|q>=v,f/=a=a:s ω(q-v)ξ
|f==a,γ<-'I':a:s l(q-v+1)ξ,η γ<η(s l q ξ)=γ
|f==ξ,γ<-s ω(v-q)a++[a],η γ<η(s l q ξ)=γ
|True=s l q ξ
η=length


to be used as e.g.

GHCi> r 7
"VII"
GHCi> r 39
"XIL"
GHCi> r (-39)
"ICXLC"        --  "LLXILC" in my original version
GHCi> r 1983
"MXVIIM"
GHCi> r 259876
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMCXXIVM"


You can evaluate the length sum with the straightforward

GHCi> sum . map(length.r) \$ [-1000..3000]
25369


Which takes something in the order of a minute.

## Ruby, 25987 (= 164 + 25823)

h=->i,d,v,k{i==0?'':i<v ?(a=h[v-i,x=d[1..-1],v/k,k^7]+d[0];i<0?a:(b=h[i,x,v/k,k^7];a.size<b.size ? a :b)):d[0]+h[i-v,d,v,k]}
r=->i{i==0?'DDM':h[i,'MDCLXVI',1000,2]}


You can call r directly to get the results. The sum over the specified range yields

> (-1000..3000).map{|i|r[i].size}.reduce &:+
25823


which is the optimal sum as with the other solutions.

# C# 23537 (639 characters of code + 22898 characters of output)

class M
{
public static string R(int n, int? s = new int?())
{
var r = "";
var D = new Dictionary<int, string> {{ 1000, "M"}, { 900, "CM"},{ 800, "CCM"},{ 500, "D"}, { 400, "CD"},{ 300, "CCD"},{100, "C"}, {90, "XC"},{80, "XXC"},{50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"}, {8, "IIX"}, {5, "V"}, {4, "IV"},{1, "I"}};
if (n == 0) return "VVX";
if (n == -1) return "IIIIIIV";
if (n < 0) return N(n * -1);

foreach(int k in D.Keys)
{
if (s.HasValue && k > s) continue;

while(k <= n)
{
n -= k;
r += D[k];
}
}

return r;
}

public static string N(int n)
{
var D = new Dictionary<int, string> {{1, "I"}, {5, "V"}, {10, "X"}, {50, "L"}, {100, "C"}, { 500, "D"}, {1000, "M"}};

int i = D.Keys.First(v => v >= n), m = D.Keys.Where(v => v < i).Max();

return R(n + i, m) + D[i];
}
}


To Calculate:

Enumerable.Range(-1000, 3000).Sum(i => M.R(i).Length);

• And what's your score? – user unknown Apr 19 '12 at 12:38