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!
Programming Praxis 
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.
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)))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
#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; }[…] 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.