16
\$\begingroup\$

Or Fix American Kennel Club's database

As covered by the recent video by Matt Parker, the American Kennel Club permits thirty-seven (37) dogs of each breed to be assigned the same name (source), because of a database restriction for Roman numeral length.

Given an integer, your task is to output the length of its Roman representation.

Rules

  • Your input will be an integer in the range 1-3899.
  • Conversion to Roman is performed using the standard subtractive notation (so 4=IV, 9=IX, 95=XCV, 99=XCIX).
  • This is , the usual rules apply.

Test-cases

input  output
1      1
2      2
3      3
4      2
5      1
6      2
9      2
10     1
37     6
38     7
95     3
99     4
288    10
2022   6
3089   9
3899   11
\$\endgroup\$
3

18 Answers 18

20
\$\begingroup\$

Python 2, 44 bytes

f=lambda x:x and 5739180/5**(x%10)%5+f(x/10)

Attempt This Online!

The magic number 5739180 encodes the list [2, 4, 3, 2, 1, 2, 3, 2, 1, 0] in base 5, which correspond to the Roman numeral lengths for the decimal digits 9 to 0. 5**(x%10)%5 extracts the x%10th base-5 digit, and the rest is a recursive function to compute the sum per decimal digit of x.

\$\endgroup\$
10
\$\begingroup\$

Vyxal, 3 bytes

øṘL

Try it Online!

I love it when there's built-ins for things like this.

Explained

øṘL
øṘ  # Convert input to Roman numerals
  L # and return the length of that.
\$\endgroup\$
2
  • \$\begingroup\$ Isn't the second character of your program 2 bytes long? \$\endgroup\$
    – sarema
    Apr 19 at 14:10
  • 5
    \$\begingroup\$ @sarema Vyxal uses a custom Single Byte Character Set which makes it only 1 byte \$\endgroup\$
    – lyxal
    Apr 19 at 14:12
10
\$\begingroup\$

JavaScript (ES6), 37 bytes

f=n=>n&&+"0123212342"[n%10]+f(n/10|0)

Try it online!

How?

In standard subtractive notation, the lengths of the digits are the same for units, tens, hundreds and thousands (up to 3000). So we can just recursively compute the total length.

   | units | tens | 100's | 1000's | length
---+-------+------+-------+--------+--------
 0 | -     | -    | -     | -      |   0
 1 | I     | X    | C     | M      |   1
 2 | II    | XX   | CC    | MM     |   2
 3 | III   | XXX  | CCC   | MMM    |   3
 4 | IV    | XL   | CD    |        |   2
 5 | V     | L    | D     |        |   1
 6 | VI    | LX   | DC    |        |   2
 7 | VII   | LXX  | DCC   |        |   3
 8 | VIII  | LXXX | DCCC  |        |   4
 9 | IX    | XC   | CM    |        |   2

JavaScript (ES6), 40 bytes

This is an attempt to find a short formula instead of a lookup table. But it's still longer.

f=n=>n&&f(n/10|0)+(30%(n%=10)&171/n^n%4)

Try it online!

36 bytes

It does come out shorter if we can take the input as a list of digits:

a=>a.map(n=>t+=30%n&171/n^n%4,t=0)|t

Try it online!

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Shorter formula: (n%10)**50%6816%5 \$\endgroup\$ Apr 20 at 1:45
  • \$\begingroup\$ @dingledooper Nice one! \$\endgroup\$
    – Arnauld
    Apr 20 at 1:54
  • 1
    \$\begingroup\$ @tsh I think I've figured out why people hate JS?? (though I'd be interested in what causes this behavior) \$\endgroup\$ Apr 20 at 2:38
  • 1
    \$\begingroup\$ @dingledooper My Firefox outputs 2 for n=9, while Chrome claims it is 4. Maybe this can be changed into a SpiderMonkey specified answer (?) \$\endgroup\$
    – tsh
    Apr 20 at 2:47
  • 2
    \$\begingroup\$ @dingledooper I ran into a similar issue here and posted a related question on SO. \$\endgroup\$
    – Arnauld
    Apr 20 at 13:51
6
\$\begingroup\$

Python 2, 41 bytes

Uses @Arnauld's idea of computing the length of each decimal digit separately. A magic hash in the form x**a%b%5 seems to work well.

f=lambda n:n and(n%10)**24%8684%5+f(n/10)

Try it online!

Other magic:

lambda n:sum(7125144/ord(c)%5for c in`n`)   # 41
f=lambda n:n and(n%5+n/5%2>>n%5/4)+f(n/10)  # 42 (has actual strategy)

Python 2, 41 bytes

Alternatively, the same length, but who doesn't love a little magic hash?

lambda n:sum(hash(c+'WQDE')%5for c in`n`)

Try it online!

The little C script below finds all possible 4-byte long suffixes to seed the hash, and takes roughly a second to complete. Interestingly, out of the 12 valid solutions, 'WQDE' is the only one with all uppercase characters. If you think about it, the chances of this occurrence are only 26^4/127^4 ~ 0.176%!

// https://github.com/python/cpython/blob/v2.7/Objects/stringobject.c#L1263

#include <stdio.h>
#include <time.h>

int py_mod(long long x, int m) { int ret = x % m; return ret >= 0 ? ret : ret + m; }

const long long h[10] = {6144036912055440, 6272037681056595, 6400038450057750, 6528039219058905, 6656039988060060, 6784040757061215, 6912041526062370, 7040042295063525, 7168043064064680, 7296043833065835};
long long h0[10], h1[10], h2[10];

int main() {
    clock_t sclock = clock();
    for (int c0 = 1; c0 < 128; c0++) {
        for (int i0 = 0; i0 < 10; i0++) h0[i0] = (h[i0] ^ c0) * 1000003;
        for (int c1 = 1; c1 < 128; c1++) {
            for (int i1 = 0; i1 < 10; i1++) h1[i1] = (h0[i1] ^ c1) * 1000003;
            for (int c2 = 1; c2 < 128; c2++) {
                for (int i2 = 0; i2 < 10; i2++) h2[i2] = (h1[i2] ^ c2) * 1000003 ^ 5;
                for (int c3 = 1; c3 < 128; c3++) {
                    if (py_mod(h2[0] ^ c3, 5) != 0) continue;
                    if (py_mod(h2[1] ^ c3, 5) != 1) continue;
                    if (py_mod(h2[2] ^ c3, 5) != 2) continue;
                    if (py_mod(h2[3] ^ c3, 5) != 3) continue;
                    if (py_mod(h2[4] ^ c3, 5) != 2) continue;
                    if (py_mod(h2[5] ^ c3, 5) != 1) continue;
                    if (py_mod(h2[6] ^ c3, 5) != 2) continue;
                    if (py_mod(h2[7] ^ c3, 5) != 3) continue;
                    if (py_mod(h2[8] ^ c3, 5) != 4) continue;
                    if (py_mod(h2[9] ^ c3, 5) != 2) continue;
                    printf("found: (%d,%d,%d,%d) [%c%c%c%c]\n",
                        c0, c1, c2, c3, c0, c1, c2, c3);
                }
            }
        }
    }
    printf("Time elapsed: %.3fs\n", (double) (clock() - sclock) / CLOCKS_PER_SEC);
    return 0;
}
\$\endgroup\$
5
\$\begingroup\$

Ruby, 39 37 bytes

->n{n.digits.sum{|x|x%5>3?2:x/5+x%5}}

Try it online!

Thanks dingledooper for -2 bytes (pointing out that 37 and 39 are two different numbers, which I didn't realize)

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can you save two bytes by inserting x%5 directly into the expression? \$\endgroup\$ Apr 19 at 17:25
  • \$\begingroup\$ I'm afraid not, I would need to enclose it in brackets, or repeat it twice. \$\endgroup\$
    – G B
    Apr 20 at 5:58
  • \$\begingroup\$ Repeating it twice saves two bytes no? \$\endgroup\$ Apr 20 at 6:05
  • \$\begingroup\$ Yes it does. Looks like I can't tell the difference between 37 and 39. \$\endgroup\$
    – G B
    Apr 20 at 6:13
5
\$\begingroup\$

x86-64 machine code, 27 bytes

97 31 C9 67 8D 71 05 99 F7 F6 F6 C2 04 D1 D8 74 02 D1 EA 11 D1 85 C0 75 EE 91 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes a number in EDI and returns a number in EAX.

In assembly:

f:  xchg edi, eax     # Exchange the input number into EAX.
    xor ecx, ecx      # Set ECX to 0. ECX will hold the running total.
    lea esi, [ecx+5]  # Set ESI to 5.
l:  cdq           # Sign-extend, setting up for the next instruction.
    div esi       # Divide by 5, putting the quotient in EAX and the remainder in EDX.
    test dl, 4    # Set flags based on the bitwise AND of the low byte of EDX with 4.
                  #  This makes the zero flag (ZF) 1 iff the remainder is not 4.
                  #  Also, the carry flag (CF) becomes 0.
    rcr eax, 1    # Rotate EAX together with CF right by 1.
                  #  With CF being 0, this halves EAX, putting the remainder into CF.
                  #  This also leaves ZF unchanged.
    jz s          # Jump, to skip one instruction, if ZF is 1.
    shr edx, 1    # (For remainder 4) Shift EDX right by 1,
                  #  changing it from 4 to 2 and making CF 0.
s:  adc ecx, edx  # Add EDX+CF to the total in ECX.
    test eax, eax # Set flags based on EAX.
    jnz l         # If it's not zero, jump back to repeat.
    xchg ecx, eax # Exchange the total from ECX into EAX.
    ret           # Return.
\$\endgroup\$
5
\$\begingroup\$

Excel, 15 bytes

=LEN(ROMAN(A1))

It feels like a rare win to use an Excel built-in for a programming challenge.

Screenshot

\$\endgroup\$
4
\$\begingroup\$

Jelly, 10 bytes

“Mḅṗʋ’D⁸ṃS

A monadic Link that accepts a positive integer and yields the Roman numeral count as a positive integer.

Try it online!

How?

“Mḅṗʋ’D⁸ṃS - Link: positive integer, N
“Mḅṗʋ’     - base 250 integer = 1232123420
      D    - to decimal -> X = [1,2,3,2,1,2,3,4,2,0]
       ⁸   - N
        ṃ  - base-decompress using X as the the new digits [1,...,9,0]
         S - sum

Note that “Mḅṗʋ’D saves one byte over using the pattern of the lengths themselves with 3,4R;0j2
i.e. [3,4] -> [[1,2,3],[1,2,3,4]] -> [[1,2,3],[1,2,3,4],0] -> [1,2,3,2,1,2,3,4,2,0].

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 26 bytes

StringLength@*RomanNumeral

Try it online!

More built-ins.

\$\endgroup\$
4
\$\begingroup\$

R, 30 29 bytes

\(n)nchar(paste(as.roman(n)))

Attempt This Online!

Convert to roman, use paste to convert to character, then find the number of characters.

-1 thanks to pajonk.

\$\endgroup\$
3
  • \$\begingroup\$ -1 by using paste for converting to character. Also, do you happen to know why as.roman's upper bound is 3899? The help states that bigger numbers don't have unique representation, but I don't see any issue in 3900-3999... \$\endgroup\$
    – pajonk
    Apr 19 at 13:26
  • \$\begingroup\$ ah paste; I was looking through methods(class="roman"), saw format, and didn't think about paste. \$\endgroup\$
    – Giuseppe
    Apr 19 at 13:37
  • 1
    \$\begingroup\$ As to the other one, wikipedia indicates the limit should be 3,999 but perhaps it was wrong at an earlier edit or from another source and the R authors took it as true? \$\endgroup\$
    – Giuseppe
    Apr 19 at 13:40
3
\$\begingroup\$

05AB1E, 3 bytes

.Xg

Try it online or verify all test cases.

Without Roman-numeral builtin (10 bytes):

•’λåK•RÅвO

Try it online or verify all test cases.

Explanation:

.X          # Convert the (implicit) input-integer to a Roman-numeral string
  g         # Pop and push its length
            # (after which the result is output implicitly)

•’λåK•      # Push compressed integer 2432123210
      R     # Reverse it: 0123212342
       Åв   # Convert the (implicit) input-integer to custom-base "0123212342";
            # basically convert the integer to base-length as list (base-10 in
            # this case), and index the base-values into the string
         O  # Sum the list together
            # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •’λåK• is 2432123210.

\$\endgroup\$
3
\$\begingroup\$

Factor + roman, 17 bytes

[ >roman length ]

Try it online!

Non-builtin version:

Factor + math.unicode, 56 bytes

[ >dec 48 v-n [ 5 /mod [ 3 > 2 rot ] keep + ? ] map Σ ]

Port of @GB's Ruby answer.

enter image description here

\$\endgroup\$
3
\$\begingroup\$

Jelly, 13 bytes

D‘ị“ȤɱȯẎ’DU¤S

Attempt This Online!

D               digits
 ‘              add 1 to each (because Jelly uses 1-based indexing)
  ị        ¤    index into:
   “ȤɱȯẎ’         compressed integer 2432123210
         D        digits
          U       reversed
            S   sum
\$\endgroup\$
2
3
\$\begingroup\$

Vyxal, 10 bytes

(without roman numeral builtin)

»ḣ₈ɖ¢»fṘτ∑

Try it Online! or Verify all the test cases

How?

»ḣ₈ɖ¢»fṘτ∑
»ḣ₈ɖ¢»      # Push compressed integer 2432123210
      f     # Convert to list of digits: [2, 4, 3, 2, 1, 2, 3, 2, 1, 0]
       Ṙ    # Reverse
        τ   # Convert the (implicit) input to this custom base
         ∑  # Summate
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 19 bytes

T`d`0-321-42
.
$*
1

Try it online! Link includes test cases. Explanation:

T`d`0-321-42

Translate the digits 0-9 into the digits 0123212342.

.
$*

Convert to unary.

1

Take the sum and convert to decimal.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 14 bytes

IΣ⭆S§”)⊞⎚mS”Iι

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

   S            Input string
  ⭆             Map over characters and join
     ”)⊞⎚mS”    Compressed string `0123212342`
    §           Indexed by
             ι  Current character
            I   Cast to integer
 Σ              Take the sum
I               Cast to string
                Implicitly print

The Sum of a string of digits (as distinct from an array of digit characters) is the sum of all the integer values of the digits, which saves having to cast them back to integer manually.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 49 bytes

Port of @Arnauld's JS answer.

f=lambda n:n and int('0123212342'[n%10])+f(n//10)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Pyth, 17 bytes

s@L_j5739180 5jQT

Test suite

Explanation:
s@L_j5739180 5jQT | Full program
------------------+------------------------------------
  L           jQT | Map over each digit d of the input:
 @L               |  Get the dth element of the list
   _j5739180 5    |   [0, 1, 2, 3, 2, 1, 2, 3, 4, 2]
s                 | Sum the resulting list
\$\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.