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!

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
8 Comments »

8 Responses to “Roman Numeral Puzzle”

  1. Randy A MacDonald said
    February 3, 2012 at 1:35 PM

    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
    February 4, 2012 at 1:33 AM 
    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
    February 6, 2012 at 8:57 PM

    haha boston patriots? they changed their name in the year MCMLXXI

  4. Axio said
    February 7, 2012 at 11:08 AM

    Isn’t the answer “the number of permutations of (non-empty) partitions of {i,v,x,l,c,d,m}”?

  5. Axio said
    February 7, 2012 at 11:22 AM

    Ah, no. At least because this brings up some invalid numbers…

  6. Tomasz Kwiatkowski said
    February 7, 2012 at 3:22 PM

    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. Roman numerals without repetitions « From C/C++ to Python said
    February 7, 2012 at 11:01 PM

    […] problem is stated in the following way: compute the number of Roman numerals where no letter appears twice. […]

  8. Karl Bielefeldt said
    June 6, 2014 at 5:31 AM

    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 comment