Roman Numeral Counting

Question

Roman numerals can be (mostly) written in a one column format, because each letter intersects the top and the bottom of the line. For example: I, or 1 intersects both the top and bottom of the line, and V or 5 intersects the bottom and top lines, the top twice and the bottom at one place.

The value of all roman numerals is as follows:
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

and the number of intersections (top, bottom) is:
I = 1,1
V = 2,1
X = 2,2
L = 1,2
C = 1,1
D = 1,1
M = 2,3

Your job is to take in 2 numbers, which represent the number of intersections on the top and bottom of your line (in that order), and output all possible valid combinations of roman numerals, from smallest by literal value to largest. Inputs will always be at or above 1.

Here are some test cases:

Input: 1,1  
Output: I,C,D

Input: 1,2  
Output: L

Input: 2,1  
Output: V

Input: 2,2   
Output: II, X, IC, CI, CC, ID, DI  
(note that DD is not a valid roman numeral, and thus should not be outputted, the value of all of these is (in order) 2, 10, 99, 101, 499, 501)

Input: 3,3  
Output: III, IX, XI, LV, XC, CII, CX, CCI, CCC, DII, DX, DCI, DCC 
(note that IIC, and IID are not valid numbers. DD (1000) is also not a valid number, as the correct numeral is M) The value of these numbers (in order) is: 3, 9, 11, 55, 90, 102, 110, 201, 300, 502, 510, and 601)

This is a usual code-golf, and needless to say, I'm interested to see how golf languages implement roman numeral counting rules. Best of luck!

Answer 1

05AB1E, 32 29 25 bytes

žDL.Xʒ•BÌË"•4в2ôsÇ87%èøOQ

-7 bytes thanks to @Grimy.

Try it online or verify all test cases.

Explanation:

žD                # Push builtin 4096 (the maximum Roman number is 3999)
  L               # Create a list in the range [1,4096]
   .X             # Convert each integer to a Roman number
     ʒ            # Filter this list by:
      •BÌË"•     "#  Push compressed integer 195646806
            4в    #  Convert it to base-4 as list: [2,3,2,2,2,1,1,1,1,1,1,1,1,2]
              2ô  #  Split it into parts of size 2:
                  #   [[2,3],[2,2],[2,1],[1,1],[1,1],[1,1],[1,2]]
      s           #  Swap to get the current Roman number we're filtering on
       Ç          #  Convert its characters to their unicode values
        87%       #  Take modulo-87 for each (I=73; V=86; X=1; L=76; C=67; D=68; M=77)
           è      #  Index those into the list of pairs (with automatic wrap-around)
            ø     #  Zip/transpose; so we have inner lists of top/bottom values
             O    #  Sum each inner list
              Q   #  And check if it's equal to the (implicit) input-pair
                  # (after the filter, the result is output implicitly)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •BÌË"• is 195646806 and •BÌË"•4в is [2,3,2,2,2,1,1,1,1,1,1,1,1,2].

Answer 2

My first try on Code Golf, please point out some optimizations!

Python 3.7, 465 449 364 363 284 Bytes

Edit: Thanks for the improvements! Jo King managed to squeeze this logic from 449 to just 364 bytes, I took a single Byte off it so I felt justified to update it. :D

Description of the old function, which remains can still be found in the code:

To formulate all numerals with certain amount (a and b) of cross points, m() subtracts number of cross points of every numeral from a and b, and recursively calls the function again for every case. If a and b are negative when called, the function exits, and if both are zero, the next function checks if it is a valid roman number, and prints accordingly.

To check if a character string is a roman number, t(c) checks if there are any 4 characters in a row, or two in the case of 50 and 500. It then checks for the possible subtraction numeral before any numeral (The possible subtraction roman numeral is either 2 or 1 positions after the real roman numeral in the list of 'MDCLXVI', depending on the parity of the roman numerals index on that list!) If any are found, they are replaced for the next part as with just the real numeral, without the subtraction numeral. SUB-NBR-SUB sandwiches, like IVI are falsified. The next part just checks if the list is ordered.

def m(c,i,a=''):
 d,e,s,*p=a,c|i,str,2,3,*[1]*5,*[2]*4,1,1,1
 for x in range(7):c+i>0==m(c-p[x*2],i-p[x*2+1],a+s(x));e|=any(s(z)in d for z in[s(x)*4,11,33,f"{x+~x%2+1}{x}{x+~x%2+1}"]);d=d.replace(s(x+~x%2+1)+s(x),s(x))
 e or[*d]==sorted(d)==print(''.join('MDCLXVI'[int(x)]for x in a))

Answer 3

Perl 5, 230 213 bytes

sub f{grep{($t,$b)=@_;map{($h='I1V21X2L12C1D1M23')=~/$_(.)(\d?)/;$t-=$1;$b-=$2||$1}/./g;!$t&&!$b}map{$r='I'x$_;for(qw(IVX XLC CDM)){($I,$V,$X)=/./g;$r=~s,$I{4}($I?),$1?$V:$I.$V,ge;$r=~s,$V($I?)$V,$1$X,g}$r}1..4e3}

Try it online!

With spaces and newlines added for readability:

sub f{
  grep{
    ($t,$b)=@_;
    map{
      ($h='I1V21X2L12C1D1M23')=~/$_(.)(\d?)/;
      $t-=$1;
      $b-=$2||$1
    }
    /./g;
    !$t&&!$b
  }
  map{
    $r = 'I' x $_;
    for( qw(IVX XLC CDM) ){
      ($I,$V,$X) = /./g;
      $r =~ s,$I{4}($I?),$1?$V:$I.$V,ge;
      $r =~ s,$V($I?)$V,$1$X,g
    }
    $r
  }
  1..4e3
}

The map at the end turns all integers 1 – 4000 into their roman equivalent. Since there is no letter for 5000 and 10000 and so on, it's reasonable to say that the maximum roman number is 3999=MMMCMXCIX. (One could just add more M's to get larger numbers, if so, just increase 4e3 here to whatever time you have to wait for the result...this is code golf where we optimize for code length, not runtime:)

The grep filters that list so that only the ones with the wanted input $t (top) and $b (bottom) numbers are returned. The maps inside grep decreases $t and $b by the right amount of "intersections" for each roman letter and the grep ends up being true for each roman number by !$t&&!$b if both $t and $b are zero (which means they started as the numbers we wanted in the input parameters).

Answer 4

Charcoal, 144 97 bytes

ＮθＮηΦＥ×φθ⁺×M÷ιφ⮌⭆⪪”{⧴9i…⪫χM⎚GＯWbπ↗sＰ÷n“<BÞＤ‴!w≡θ⟧Ｌ≡§Ａ≦Ｉ⍘∨Φ…ok”²⁹§⪪λ ÷ιＸχμ∧⁼θΣＥι⊕№VXMλ⁼ηΣＥι⊕№LXMMλ

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input the two values.

ΦＥ×φθ

Loop up to 1000 times the first number, which is well past the largest valid Roman numeral, keeping only those that satisfy the validity of both the top and bottom intersections (according to the condition at the end of the code).

⁺×M÷ιφ⮌⭆⪪”{⧴9i…⪫χM⎚GＯWbπ↗sＰ÷n“<BÞＤ‴!w≡θ⟧Ｌ≡§Ａ≦Ｉ⍘∨Φ…ok”²⁹§⪪λ ÷ιＸχμ

The compressed string expands to I II III VI V IV IIV IIIV XI X XX XXX LX L XL XXL XXXL CX C CC CCC DC D CD CCD CCCD MC. This is used to calculate the Roman numeral in reverse, working from the units up to the 100s, and then the reverse is concatenated to any further Ms needed.

∧⁼θΣＥι⊕№VXMλ⁼ηΣＥι⊕№LXMMλ

For each Roman numeral, count the number of times each letter thereof appears in the strings VXM and LXMM respectively, then add one for each letter, and compare the totals to the inputs.

Answer 5

Jelly, 129 bytes

ŒṗŒ!€ẎQ)p/ẈE$ƇZ€“(³l’ḃ9¤ḃ3¤ẹⱮŒpƊ€ẎŒgQ€QƑƊƇḂÐḟQƑ$ƇI<1kƲ€ḂḢ€ạẈƲỊẠƊƇIFṀ<ʋƇ3ị“¢¦½2d‘;.ȷ,ȷ¤ạ/€€S€Ụf<ƇS<ɗⱮ⁵*Ɱ3¤ẠaNÞƑƲ€T$ƲƊị$ị“IVXLCDM”K

Try it online!

A full program taking a pair of integers as its argument and printing to STDOUT a space-separated list of Roman numerals. Should produce all valid Roman numerals following the rules on Project Euler (so VIIII, IX and IIIIIIIII are all valid forms for 9, but VIV is not, and X is the only valid form for 10.)

Answer 6

Jelly, 61 bytes

1xⱮ4Ḷ¤$ؽṭ;2;Ɱ$Ʋ1,3ṭ+þ3Ḥ€Ż¤ṚŒpḣ4ȷF€ị“(³l’ḃ9¤ḃ3¤S⁼ɗƇị“IVXLCDM”

Try it online!

This monadic link takes a pair of integers as its argument and returns a list of strings representing the Roman numerals. Unlike my other Jelly answer, this one only uses the minimal (canonical?) representation of each Roman numeral, so it’s more straightforward to generate a list of all Roman numerals in order and filter them. It only generates Roman numerals up to 3999, but could be adapted to work for higher Roman numerals if needed. L