## 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

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.

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

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

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

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

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

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.