Enigmatic Code

Programming Enigma Puzzles

Enigma 1533: Roman grid

From New Scientist #2696, 21st February 2009 [link]

Put one of the letters C, L, X, V, I into each cell of a 5 × 5 grid so that each row and each column is a valid five-letter Roman numeral less than 300. No numeral may appear more than once; the five horizontal numerals should be in descending numerical order from top to bottom, and the five vertical numerals in descending numerical order from left to right.

What is the sum of your 10 Roman numerals (expressed in ordinary Arabic numerals)?

[enigma1533]

Advertisements

5 responses to “Enigma 1533: Roman grid

  1. Jim Randell 2 July 2012 at 9:26 am

    Here’s my original brute-force Perl program. It uses the Text::Roman module to deal with Roman Numerals. It runs in 2m25s.

    use strict;
    
    use Text::Roman qw/roman2int int2roman/;
    
    use Enigma qw/distinct/;
    
    # find 5 digit roman numerals < 300
    my %ROMANS = ();
    for (1..299) {
      my $roman = int2roman($_);
      next unless length($roman) == 5;
      $ROMANS{$roman} = $_;
    }
    
    # now we need to pick 5 of them (in descending order)
    my ($R1, $R2, $R3, $R4, $R5, $C1, $C2, $C3, $C4, $C5, $C6, @X, $SUM);
    for $R1 (keys %ROMANS) {
      for $R2 (keys %ROMANS) {
        next unless $ROMANS{$R1} > $ROMANS{$R2};
        for $R3 (keys %ROMANS) {
          next unless $ROMANS{$R2} > $ROMANS{$R3};
          for $R4 (keys %ROMANS) {
            next unless $ROMANS{$R3} > $ROMANS{$R4};
            for $R5 (keys %ROMANS) {
              next unless $ROMANS{$R4} > $ROMANS{$R5};
    
              @X = split '', "$R1$R2$R3$R4$R5";
              $C1 = "$X[0]$X[5]$X[10]$X[15]$X[20]";
              next unless $ROMANS{$C1};
              next unless distinct($ROMANS{$C1}, $ROMANS{$R1}, $ROMANS{$R2}, $ROMANS{$R3}, $ROMANS{$R4}, $ROMANS{$R5});
              $C2 = "$X[1]$X[6]$X[11]$X[16]$X[21]";
              next unless $ROMANS{$C2};
              next unless distinct($ROMANS{$C2}, $ROMANS{$R1}, $ROMANS{$R2}, $ROMANS{$R3}, $ROMANS{$R4}, $ROMANS{$R5});
              next unless $ROMANS{$C1} > $ROMANS{$C2};
              $C3 = "$X[2]$X[7]$X[12]$X[17]$X[22]";
              next unless $ROMANS{$C3};
              next unless distinct($ROMANS{$C3}, $ROMANS{$R1}, $ROMANS{$R2}, $ROMANS{$R3}, $ROMANS{$R4}, $ROMANS{$R5});
              next unless $ROMANS{$C2} > $ROMANS{$C3};
              $C4 = "$X[3]$X[8]$X[13]$X[18]$X[23]";
              next unless $ROMANS{$C4};
              next unless distinct($ROMANS{$C4}, $ROMANS{$R1}, $ROMANS{$R2}, $ROMANS{$R3}, $ROMANS{$R4}, $ROMANS{$R5});
              next unless $ROMANS{$C3} > $ROMANS{$C4};
              $C5 = "$X[4]$X[9]$X[14]$X[19]$X[24]";
              next unless $ROMANS{$C5};
              next unless distinct($ROMANS{$C5}, $ROMANS{$R1}, $ROMANS{$R2}, $ROMANS{$R3}, $ROMANS{$R4}, $ROMANS{$R5});
              next unless $ROMANS{$C4} > $ROMANS{$C5};
    
              $SUM = $ROMANS{$R1} + $ROMANS{$R2} + $ROMANS{$R3} + $ROMANS{$R4} + $ROMANS{$R5} +
                     $ROMANS{$C1} + $ROMANS{$C2} + $ROMANS{$C3} + $ROMANS{$C4} + $ROMANS{$C5};
    
              print "$R1\n$R2\n$R3\n$R4\n$R5\n[($ROMANS{$R1} + $ROMANS{$R2} + $ROMANS{$R3} + $ROMANS{$R4} + $ROMANS{$R5}) + ($ROMANS{$C1} + $ROMANS{$C2} + $ROMANS{$C3} + $ROMANS{$C4} + $ROMANS{$C5}) = $SUM]\n";
            }
          }
        }
      }
    }
    

    Solution: The sum of the Roman Numerals is 1072.

    • Jim Randell 2 July 2012 at 9:34 am

      Here is a neater version in Python that uses recursion. It runs in 20.8s (or 5.4s under PyPy).

      I added the int2roman() and roman2int() functions that deal with Roman Numerals to my enigma.py library.

      from enigma import irange, int2roman, roman2int, concat, printf
      
      # make a list (in descending numerical order) of 5 digit roman numerals < 300
      romans = []
      for i in irange(299, 1, step=-1):
        r = int2roman(i)
        if len(r) != 5: continue
        romans.append(r)
      n = len(romans)
      
      # i = row number
      # r = row index
      # rs = rows
      # c = column index
      # cs = columns
      def solve(i=0, r=0, rs=[], c=0, cs=[]):
        # are we done?
        if i == 5:
          print('\n'.join(rs))
          print('sum', '=', sum(roman2int(x) for x in rs + cs))
          return
        # row and column prefixes
        pr = concat(*(cs[j][i] for j in range(i)))
        pc = concat(*(rs[j][i] for j in range(i)))
        # try the next row
        for r1 in range(r, n):
          rn = romans[r1]
          if rn in cs or not rn.startswith(pr): continue
          # and the next column
          for c1 in range(c, n):
            cn = romans[c1]
            if i == 0 and not(c1 < r1): continue
            if cn == rn or cn in rs or not cn.startswith(pc + rn[i]): continue
            solve(i + 1, r1 + 1, rs + [rn], c1 + 1, cs + [cn])
            
      solve()
      
  2. Hugh Casement 4 February 2016 at 11:42 am

    By hand I found 66 Roman numerals of five characters.  My program then found two patterns with only one pair of letters swapped between them:

    C C L X X
    C L X X V
    X X X V I
    X X X I I 
    X X I I I
    
    C C L X X
    C L X X X
    X X X V I
    X X X I I 
    X V I I I

    either can presumably be reflected in the leading diagonal.  Did I miss anything?

Leave a Comment

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

%d bloggers like this: