fundo

Esse desafio é inspirado neste site, que publicou o seguinte diagrama:

Este diagrama mostra-nos que a expressão mais longa do numeral romano abaixo de 250 é a do 188, que requer 9 números para ser expressa.

Desafio

Os símbolos padrão utilizados para expressar numerais mais romanos são os seguintes: { I, V, X, L, C, D, M}, em que os valores numéricos dos personagens são M= 1.000, D= 500, C= 100, L= 50, X= 10, V= 5, I= 1.

Nesse desafio, seu objetivo é, dado um número inteiro positivo n , calcular o número de representações válidas de números romanos que podem ser compostas através da concatenação de n dos símbolos padrão.

Então, seu programa deve gerar o resultado desse cálculo!

Entrada : Um número inteiro positivo n .

Saída : O número de expressões numéricas romanas válidas de comprimento n .

Regras para expressões numéricas romanas

Os algarismos romanos originalmente tinham apenas pareamento "aditivo", o que significa que os números sempre eram escritos em ordem decrescente, e a soma dos valores de todos os números era o valor do número.

Posteriormente, o emparelhamento subtrativo, o uso de colocar um número menor na frente de um maior para subtrair o menor do maior, tornou-se comum para encurtar as expressões do numeral romano. Pares subtrativos não pode ser acorrentado, como na seguinte expressão inválida: IXL.

A seguir, estão as regras modernas para o emparelhamento aditivo e subtrativo.

1. Somente um I, X e C podem ser usados ​​como o número inicial em parte de um par subtrativo.
2. Só posso ser colocado antes de V ou X em um par subtrativo.
3. X só pode ser colocado antes de L ou C em um par subtrativo.
4. C só pode ser colocado antes de D ou M em um par subtrativo.
5. Além dos pares subtrativos, os números devem estar em ordem decrescente (o que significa que, se você soltar o número inicial de cada par subtrativo, os números estarão em ordem decrescente).
6. M, C e X não podem ser igualados ou excedidos por denominações menores.
7. D, L e V podem aparecer apenas uma vez.
8. Somente M pode ser repetido 4 ou mais vezes.

Notas adicionais

• Não usaremos a notação de barra ; em vez disso, basta adicionar mais M s para expressar qualquer número.

• Estas são as únicas regras que seguiremos para os nossos algarismos romanos. Isso significa que expressões estranhas, como IVI, também serão consideradas válidas em nosso sistema.

• Lembre-se também de que não estamos contando o número de números que têm expressões de comprimento n , pois alguns números têm várias expressões. Em vez disso, estamos contando apenas o número de expressões válidas.

Casos de teste

1 → 7

2 → 31

3 → 105

Eu verifiquei o item à mão, por isso, verifique os casos de teste e adicione mais se puder!

Critérios Vencedores

Este é um desafio de código-golfe , então divirta-se! Só aceitarei soluções que possam lidar com pelo menos entradas de 1 a 9. Mais um bônus!

Editar

Conforme solicitado pelos comentaristas, encontre abaixo, ou neste link para colar, os 105 combos que eu contei 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 CCL CDL 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 MLX MCI MCV MCX MCL MCC MCD MCD MCD MDL MMX MML MMC MMD MMM

Edição 2:

Use o código a seguir , como cortesia de Jonathan Allan, para verificar seus resultados.

Edição 3:

Peço desculpas por todos os erros deste desafio. Vou fazer um trabalho melhor da próxima vez!

Retina , 111 bytes

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

Experimente online! Esta é uma reescrita completa, pois eu não entendi a regra 1., significando que você só poderia usar uma de cada subtrativa I, Xe C. Explicação: A primeira parte do script expande a entrada em uma sequência de CMpares seguida pelos outros pares subtrativos possíveis. Cada par é opcional e o primeiro caractere de cada par também é opcional dentro do par. O terceiro estágio expande a lista de pares em uma lista de comandos Retina que recebem a entrada e criam três cópias com a opção do segundo ou dos dois caracteres do par, depois apara e desduplica os resultados. O estágio final acrescenta o código para executar as tarefas finais: primeiro para expandir a entrada e, possivelmente, adicionar um finalI, para filtrar os resultados com tamanho incorreto, para desduplicar os resultados e, finalmente, para contar os resultados. O script Retina resultante é então avaliado.

Nota: Em teoria, 15 bytes podem ser salvos no final da 4ª linha, mas isso torna o script muito lento para demonstrar no TIO mesmo n=1.

Python 2 , 177 168 162 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))

Experimente online!

Eu sou muito novo, me ajude a jogar isso! Isso verifica os números romanos reais, a regex precisa ser ajustada para levar em consideração os casos ímpares, comoIVI

-9 bytes graças a @Dead Possum!

-6 bytes graças a @ovs

JavaScript (ES7), 133 bytes

Editar : corrigido para corresponder aos resultados retornados pelo código de Jonathan Allan , que foi fornecido como uma implementação de referência pelo 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)

Experimente online!

Quão?

$N$$1$

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

A partir de agora, cada dígito será interpretado como um símbolo de numeral romano:

$$\begin{array}{}0\longleftrightarrow \text{I}, & 1\longleftrightarrow \text{M}, & 2\longleftrightarrow \text{X}, & 3\longleftrightarrow \text{L},\\ 4\longleftrightarrow \text{C}, & 5\longleftrightarrow \text{D}, & 6\longleftrightarrow \text{V} \end{array}$$

2) Substituímos todos os pares subtrativos válidos do formulário ABpor 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

Exemplos:

• XLIXIV torna-se LXV
• XIIVtorna-se XIV, deixando um Ique fará com que o próximo teste falhe
• ICpermanece inalterado, o que também deixa um inválido Ino lugar

3) Verificamos se os símbolos restantes estão na ordem correta e não aparecem mais vezes do que o permitido:

/^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

Eu não li a descrição o suficiente, então isso produz o número de algarismos romanos padrão (onde expressões como IVInão são contadas). Desde que me esforcei, pensei em compartilhar de qualquer maneira.

#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);}