13
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Would you be able to add the counting rules? \$\endgroup\$ – Jonathan Allan Nov 1 at 20:54
  • \$\begingroup\$ +1 Looks interesting \$\endgroup\$ – Poke Nov 1 at 21:00
  • 2
    \$\begingroup\$ Well written but upvoted mainly for sheer oddness of the challenge. \$\endgroup\$ – Jonah Nov 1 at 23:45
  • 5
    \$\begingroup\$ IC, ID are not valid roman numerals. \$\endgroup\$ – JBernardo Nov 2 at 3:04
  • 1
    \$\begingroup\$ projecteuler.net/about=roman_numerals \$\endgroup\$ – HiddenBabel Nov 2 at 3:17
4
\$\begingroup\$

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].

\$\endgroup\$
  • 1
    \$\begingroup\$ -2 by using the dictionary (either mild or divx works). -1 by using r once instead of s twice. TIO. \$\endgroup\$ – Grimmy Nov 4 at 14:23
  • \$\begingroup\$ @Grimmy Thanks! I tried a triple swap, but in that case I was needing two of them. Didn't think about reverse stack.. >.> And thanks for the dictionary string. \$\endgroup\$ – Kevin Cruijssen Nov 4 at 14:32
  • 1
    \$\begingroup\$ 25 \$\endgroup\$ – Grimmy Nov 4 at 16:16
  • \$\begingroup\$ @Grimmy Ah, nice find. \$\endgroup\$ – Kevin Cruijssen Nov 4 at 17:35
3
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! To save some bytes, (a,b)==(0,0) -> a==b==0, return(1) -> return 1, input("") -> input(), and you can save str as s=str at the beginning and use it as s(x) later. \$\endgroup\$ – Stephen Nov 3 at 17:47
  • \$\begingroup\$ Wow, Jo. Thanks a lot. Learned a ton. Also managed to pop one byte off your solution so the code is now updated :D \$\endgroup\$ – punkkapoika Nov 4 at 4:40
  • \$\begingroup\$ 284 bytes with some stuff I missed earlier. Feel free to use it even if you can't golf more (though you should be able to) \$\endgroup\$ – Jo King Nov 4 at 7:12
  • 1
    \$\begingroup\$ Cool. I couldn't make it any shorter but now the 2nd row now spells despacito \$\endgroup\$ – punkkapoika Nov 4 at 10:52
2
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ how did you learned this language? \$\endgroup\$ – rsonx Nov 3 at 17:24
  • \$\begingroup\$ @rsonx From the GitHub page linked above and reading answers from people like JonathanAllan \$\endgroup\$ – Nick Kennedy Nov 3 at 18:42
  • \$\begingroup\$ @rsonx If you want to learn it, check out Jelly Hypertraining :) \$\endgroup\$ – Bubbler Nov 4 at 0:04
  • \$\begingroup\$ @Bubbler how do you join? \$\endgroup\$ – Nick Kennedy Nov 4 at 0:09
  • \$\begingroup\$ @NickKennedy Go to the chat room and click the "request access" button. \$\endgroup\$ – Bubbler Nov 4 at 0:13
0
\$\begingroup\$

Charcoal, 144 97 bytes

NθNηΦE×φθ⁺×M÷ιφ⮌⭆⪪”{⧴9i…⪫χM⎚GOWbπ↗sP÷n“<BÞD‴!w≡θ⟧L≡§A≦I⍘∨Φ…ok”²⁹§⪪λ ÷ιXχμ∧⁼θΣEι⊕№VXMλ⁼ηΣEι⊕№LXMMλ

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

NθNη

Input the two values.

ΦE×φθ

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⎚GOWbπ↗sP÷n“<BÞD‴!w≡θ⟧L≡§A≦I⍘∨Φ…ok”²⁹§⪪λ ÷ιXχμ

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.

∧⁼θΣEι⊕№VXMλ⁼ηΣEι⊕№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.

\$\endgroup\$
  • \$\begingroup\$ TIO link still says 144 bytes. Also, question is ambiguous, but IIII and IV are both valid Roman numerals that express 4. \$\endgroup\$ – Nick Kennedy Nov 3 at 13:17
  • \$\begingroup\$ @NickKennedy Thanks, I've updated the TIO link now. \$\endgroup\$ – Neil Nov 3 at 17:20
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.