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.

About these ads

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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 636 other followers

%d bloggers like this: