Roman Numeral Puzzle
February 3, 2012
The Super Bowl is the championship game of the American league of professional football teams — and an annual cultural event. The first Super Bowl, won by the Green Bay Packers under head coach Vince Lombardi, was in 1967, and wasn’t even called “Super Bowl” at the time; the name didn’t attach to the game until Super Bowl III, when Joe Namath of the New York Jets guaranteed a victory. Roman numerals have been used to designate the Super Bowl ever since. The game this year, between the Boston Patriots and New York Giants, is Super Bowl XLVI; you can solve today’s exercise while you watch the game on Sunday evening.
John D. Cook turned the wacky roman numerals of the Super Bowl into an exercise at his blog; he was inspired by an advertisement for Super Bowl XLVI on a pizza box. Cook asked his readers to compute how many numbers can be expressed as roman numerals without duplicating any of the symbols I, V, X, L, C, D or M.
Your task is to compute the number of roman numerals that have no duplicate characters. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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.