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

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 Enjoy the game!

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:

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

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 670 other followers

%d bloggers like this: