## Roman Numeral Puzzle

### February 3, 2012

This exercise gives us a fine excuse to show off the Standard Prelude, and we have a roman numeral converter from a previous exercise. Here is a function that checks if there are any duplicate characters in a string:

```(define (duplicate? str)   (let ((cs (sort charlist str))))     (not (equal? cs (unique char=? cs)))))```

Then it’s easy:

```> (length     (filter (compose not duplicate?)       (map number->roman         (range 1 10000)))) 316```

I absentmindedly chose 10000 as the limit, but a little bit of thought suggests that no number greater than MM = 2000 fits the criteria, and a little bit more thought suggests that MCM = 1900 is a tighter bound, and a little bit more thought suggests that MDCLXVI = 1666 is the largest roman numeral that has no repeated digits. I did a lot of extra work to no effect.

We used `range`, `filter`, `sort`, `unique`, and `compose` from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/YStV3byV. Enjoy the game!

Pages: 1 2

### 8 Responses to “Roman Numeral Puzzle”

1. Same basic idea, if not a little shorter in APL:

{~0∊nubsieve toRoman ⍵}{⍵ if ⍺⍺¨⍵}⍳1666

the {⍵ if ⍺⍺¨⍵} expression acts like the filter, and nubsieve is an analogue to ‘unique’ with a name by way of J.

2. Mike said
```from itertools import product

ks = ',M,MM,MMM'.split(',')
hs = ',C,CC,CCC,CD,D,DC,DCC,DCCC,CM'.split(',')
ts = ',X,XX,XXX,XL,L,LX,LXX,LXXX,XC'.split(',')
os = ',I,II,III,IV,V,VI,VII,VIII,IX'.split(',')

sum(len(s) == len(set(s)) for s in map(''.join, product(ks,hs,ts,os)))
```
3. ardnew said

haha boston patriots? they changed their name in the year MCMLXXI

4. Axio said

Isn’t the answer “the number of permutations of (non-empty) partitions of {i,v,x,l,c,d,m}”?

5. Axio said

Ah, no. At least because this brings up some invalid numbers…

6. Hi, late to the party, but at least my idea is original. Will provide details how I came across this solution. Plain C. Look below or here: http://codepad.org/D1Sesi4Q

```#include <stdio.h>
#define RN 7
#define BK 1
#define USE 2
#define recurse(x) { s[p]=(x); count += times * find(p + 1, s); }

typedef unsigned int uint;

uint find(uint p, uint* s)
{
uint count = 0;
if (p == RN) return 1;
uint times = 1;
recurse(USE);
recurse(0);
if (p > 0 && p % 2 == 0)
{
times = (uint)(s[p - 2] == USE && !s[p - 1]) + (uint)(s[p - 1] == USE);
if (times) recurse(BK);
}
return count;
}

int main(int argc, char** argv)
{
uint s[RN] = {0, 0, 0, 0, 0, 0, 0};
uint count = find(0, s);
printf("%d\n", count - 1);
return 0;
}

```
7. […] problem is stated in the following way: compute the number of Roman numerals where no letter appears twice. […]

8. Here’s my Scala solution, assuming an intToRoman from the previous exercise. Scala strings already have a method to eliminate duplicates in the standard library.

```val romans = 1 to 2000 map intToRoman
val distinct = romans filter ((x) => x.distinct.size == x.size)
println(distinct.size)
```