Antecedentes

Este desafío está inspirado en este sitio web, que publicó el siguiente diagrama:

Este diagrama nos muestra que la expresión de número romano más larga por debajo de 250 es la de 188, que requiere 9 números para expresarse.

Desafío

Los símbolos estándar usados para expresar números más romanas son los siguientes: { I, V, X, L, C, D, M}, donde los valores numéricos de los personajes son M= 1000, D= 500, C= 100, L= 50, X= 10, V= 5, I= 1.

En este desafío, su objetivo es, dado un número entero positivo n , calcular el número de representaciones válidas de números romanos que se pueden componer mediante la concatenación de n de los símbolos estándar.

¡Entonces, su programa debe generar el resultado de este cálculo!

Entrada : Un entero positivo n .

Salida : El número de expresiones válidas de números romanos de longitud n .

Reglas para expresiones de números romanos

Los números romanos originalmente solo tenían un emparejamiento "aditivo", lo que significa que los números siempre se escribían en orden descendente, y la suma de los valores de todos los números era el valor del número.

Más tarde, el emparejamiento sustractivo, el uso de colocar un número más pequeño frente a uno más grande para restar lo más pequeño de lo más grande, se convirtió en un lugar común para acortar las expresiones de números romanos. Pares sustractivos no se pueden encadenar, como en la siguiente expresión válida: IXL.

Las siguientes son las reglas modernas para el emparejamiento aditivo y sustractivo.

1. Solo uno I, X y C pueden usarse como el número inicial en parte de un par sustractivo.
2. Solo puedo colocarme antes de V o X en un par sustractivo.
3. X solo se puede colocar antes de L o C en un par sustractivo.
4. C solo se puede colocar antes de D o M en un par sustractivo.
5. Además de los pares sustractivos, los números deben estar en orden descendente (lo que significa que si suelta el número inicial de cada par sustractivo, los números estarán en orden descendente).
6. M, C y X no pueden ser igualados o superados por denominaciones más pequeñas.
7. D, L y V solo pueden aparecer una vez.
8. Solo M puede repetirse 4 o más veces.

Notas adicionales

• No utilizaremos la notación de barra ; más bien, simplemente agregaremos más M s para expresar cualquier número.

• Estas son las únicas reglas que seguiremos para nuestros números romanos. Eso significa que las expresiones extrañas, como IVI, también se considerarán válidas en nuestro sistema.

• También recuerde que no estamos contando el número de números que tienen expresiones de longitud n , ya que algunos números tienen múltiples expresiones. En cambio, solo contamos el número de expresiones válidas.

Casos de prueba

1 → 7

2 → 31

3 → 105

Revisé lo anterior a mano, así que asegúrese de verificar los casos de prueba y agregar más si puede.

Criterios ganadores

Este es un desafío de código de golf , ¡así que diviértete! Solo aceptaré soluciones que puedan manejar al menos entradas del 1 al 9. ¡Más es un bono!

Editar

Según lo solicitado por los comentaristas, encuentre a continuación, o en este enlace de pastebin, los 105 combos que conté para n = 3

III IVI IXI IXV IXX VII XII XIV XIX XVI XXI XXV XXX XLI XLV XLX XCI XCV XCX XCL XCC LII LIV LIX LVI LXI LXV LXX CII CIV CIX CVI CXI CXV CXX CXL CXC CLI CLV CLX CCI CCV CCX CCL CCC CDI CDV CDX CMI CMV CMX CML CMC CMD CMM DII DIV DIX DVI DXI DXV DXX DXL DXC DLI DLV DLX DCI DCV DCX DCL DCC MII MIV MIX MVI MXI MXV MXX MXL MXC MLI MLV MLX MCI MCV MCX MCL MCC MCD MCM MDI MDC MDX MDL MDV MMX MML MMC MMD MMM

Edición 2:

Use el siguiente código no relacionado con el golf , como cortesía de Jonathan Allan para verificar sus resultados.

Edición 3:

Pido disculpas por todos los errores en este desafío. ¡Me aseguraré de hacer un mejor trabajo la próxima vez!

Retina , 111 bytes

~(`.+
*$(CM)CDXCXCXCXLIXIXIXIVII
.(.)
.+¶$$&$¶$$&$1$¶$$&$&¶L`.{0,$+}\b¶D`¶
¶$
¶.+¶$$&$¶$$&I¶L`[A-Z]{$+}\b¶D`¶.+

Pruébalo en línea! Esta es una reescritura completa ya que entendí mal la regla 1. que significa que solo se puede usar uno de sustractivo I, Xy C. Explicación: La primera parte del script expande la entrada en una cadena de CMpares seguida de los otros pares sustractivos posibles. Cada par es opcional, y el primer carácter de cada par también es opcional dentro del par. La tercera etapa luego expande la lista de pares en una lista de comandos Retina que toman la entrada y crean tres copias con la opción del segundo o ambos caracteres del par, luego recortan y deduplican los resultados. La etapa final luego agrega código para realizar las tareas finales: primero para expandir la entrada y posiblemente agregar una finalI, luego filtrar los resultados de la longitud incorrecta, luego deduplicar los resultados y finalmente contar los resultados. Luego se evalúa el script de Retina resultante.

Nota: En teoría, se podrían guardar 15 bytes desde el final de la 4ta línea, pero esto hace que el script sea demasiado lento para demostrarlo en TIO incluso para n=1.

Python 2 , 177168162 bytes

import re,itertools as q
f=lambda n:sum(None!=re.match("^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$",(''.join(m)))for m in q.product('MDCLXVI',repeat=n))

Pruébalo en línea!

Soy bastante nuevo, ¡ayúdame a jugar golf! Esto comprueba los números romanos reales, la expresión regular debe ajustarse para tener en cuenta los casos impares, comoIVI

-9 bytes gracias a @Dead Possum!

-6 bytes gracias a @ovs

JavaScript (ES7), 133 bytes

Editar : se corrigió para que coincida con los resultados devueltos por el código de Jonathan Allan , que se dio como implementación de referencia por parte del OP.

n=>[...Array(m=k=7**n)].reduce(s=>s+/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test((--k+m).toString(7).replace(/0[62]|2[34]|4[51]/g,s=>s[1])),0)

Pruébalo en línea!

¿Cómo?

$N$$1$

[...Array(m = k = 7 ** n)].reduce(s => … (--k + m).toString(7) …, 0)

De ahora en adelante, cada dígito se interpretará como un símbolo de número romano:

2) Reemplazamos todos los pares sustractivos válidos de la forma ABcon B:

.replace(/0[62]|2[34]|4[51]/g, s => s[1]))  // in the code
.replace(/I[VX]|X[LC]|C[DM]/g, s => s[1]))  // with Roman symbols

Ejemplos:

• XLIXIV se convierte LXV
• XIIVse convierte XIV, dejando un Ique hará que la próxima prueba falle
• ICpermanece sin cambios, lo que también deja un inválido Ien su lugar

3) Verificamos que los símbolos restantes estén en el orden correcto y no aparezcan más veces de las permitidas:

/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test(…)  // in the code
/^M*D?C{0,3}L?X{0,3}V?I{0,3}$/.test(…)  // with Roman symbols

C, 150 123 bytes

No leí la descripción con suficiente atención, por lo que esto produce el número de números romanos estándar (donde IVIno se cuentan expresiones como ). Como puse un poco de esfuerzo en ello, pensé en compartir de todos modos.

#define F(X) for(X=10;X--;)
x[]={0,1,2,3,2,1,2,3,4,2};f(i,o,a,b,c){for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];return o;}

Original (150 bytes):

#define F(X) for(X=10;X--;)
i,o,a,b,c,x[]={0,1,2,3,2,1,2,3,4,2};main(){scanf("%i",&i);for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];printf("%i\n",o);}