Cuando en Roma, ¿cuenta como lo hacen los romanos?

20

Antecedentes

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

ingrese la descripción de la imagen aquí

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

17

231

3105

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 , ¡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!

Don mil
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Mego

Respuestas:

3

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.

Neil
fuente
@ JonathanAllan Ah, entonces estás incluyendo múltiples pares sustractivos con el mismo número inicial, lo cual está mal.
Neil
2
@JonathanAllan Nueva reescritura, ¡coincidentemente para el mismo recuento de bytes!
Neil
5

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

Easton Bornemeier
fuente
Sí, creo que el caso n = 3 podría estar equivocado en el ejemplo. Originalmente recibía 93 con^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$
Easton Bornemeier
171 bytes
Dead Possum
1
@JonathanAllan Pasé alrededor de dos días preguntando en el intercambio de pila de Math tratando de asegurarme de que estas reglas tuvieran sentido. Supongo que no hice lo suficiente :(
Don Thousand
1
@RushabhMehta Este es un desafío muy bien formateado y divertido de programar, no se sienta mal por un desafortunado matiz en el meollo de la definición de números romanos. Es su desafío, especifíquelo como mejor le parezca. es viable en el otro sentido, simplemente más difícil
Easton Bornemeier
1
Esto no parece dar la respuesta correcta para 3. en 93lugar de105
Jo King
3

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?

N1

[...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:

0I,1M,2X,3L,4C,5D,6V

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
Arnauld
fuente
Santa vaca, ¡no esperaba que esto se hiciera en menos de 200 bytes en idiomas no esotéricos! ¿Te importaría explicar cómo funciona esto?
Don Thousand
Sin embargo, he notado que esto no funciona para * n *> 4 en TIO, lo cual es algo desafortunado.
Don Thousand
@RushabhMehta He agregado una versión no recursiva para probar valores más altos. Agregaré una explicación cuando termine de jugar golf.
Arnauld
0

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);}
Curtis Bechtel
fuente
1
Solo puedes publicar envíos válidos.
Okx
@CurtisBechtel Supongo que puede mantener la solución aquí, pero trataría de modificarla para satisfacer las reglas del desafío.
Don Thousand
1
Creo que puedes quitar el espacio entre F(X)yfor(X=10;X--;)
Zacharý