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!

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 627 other followers

%d bloggers like this: