Descrição do Desafio

Tivemos alguns desafios envolvendo a sequência de dizer e dizer . Lembrete rápido:

• A sequência começa com 1,
• Os termos subsequentes dessa sequência são gerados pela enumeração de cada grupo de dígitos repetidos no termo anterior,

Portanto, os primeiros termos são:

1        "one"
11       "one one" (we look at the previous term)
21       "two ones"
1211     "one two, one one"
111221   "one one, one two, two ones"
312211   "three ones, two twos, one one"

Agora vamos fazer a mesma coisa, mas use algarismos romanos . Começamos com Ie seguimos as mesmas regras (em vez disso, aplicamos a regra de contagem de dígitos aos caracteres, então lemos IVXcomo em one one, one five, one tenvez de one four, one tenou de outra maneira):

I           "one"
II          "one one"
III         "two ones" = "II" + "I"
IIII        "three ones" = "III" + "I"
IVI         "four ones" = "IV" + "I"
IIIVII      "one one, one five, one one"
IIIIIVIII   "three ones, one five, two ones" = ("III" + "I") + ("I" + "V") + ("II" + "I")

Dado um número inteiro positivo N:

• Emita os primeiros Nnúmeros desta sequência (qualquer separador razoável é bom, bem como["I", "II", "III", ...]
• Saída Nth termo desta sequência (pode ser indexado 0).

Lembre-se de tornar seu código o mais curto possível, pois esse é um desafio para o código-golfe !

EDIT: Eu acredito que sempre existe uma maneira padrão / preferida de expressar números inteiros como algarismos romanos (como 95-> em XCVvez de VC). Alguns conversores de números romanos que encontrei on-line corroboram minha opinião. Em caso de dúvida, use um conversor on-line , pois listar todos os possíveis casos extremos e regras específicas para escrever números romanos não é o objetivo desse desafio.

EDIT2: @PeterTaylor e @GregMartin apontou que apenas números menor ou igual a 5aparecer na seqüência, para que você não precisa se preocupar com a ambigüidade de algarismos romanos (números 1- 8são I, II, III, IV, V, VI, VII, e VIII)

Perl, 49 bytes

Inclui +1 para -p

Execute com o índice baseado em 0 no STDIN, por exemplo

ecce.pl <<< 14

ecce.pl:

#!/usr/bin/perl -p
s,(.)\1*,$&/$1%182 .$1,eg for($_=/$/)x$`;y;19;IV

Fórmulas mágicas são tão mágicas.

Normalmente, eu usaria ($_=//)x$'para reduzir o controle de loop em um byte mais curto, mas a pontuação neste site oferece um handicap de 2 para que ele termine 1 byte mais. Em perls mais antigos, você pode eliminar o espaço antes for. Algumas versões do perl forçam você a adicionar uma final ;para fechar a transliteração. Mas o que é dado acima é o código que funciona no meu sistema.

Explicação

Trabalhando de trás para frente da solução para o código:

As transformações de string que precisamos:

I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

Cada substituição termina com o caractere repetido. Vou obter uma sequência dos mesmos caracteres usando regex /(.)\1*/, portanto, isso pode ser feito anexando $1. A parte antes do ->está em $&. Com isso eu ainda preciso:

I     -> I
II    -> II
III   -> III
IIII  -> IV
IIIII -> V

V     -> I
VV    -> II

Escreva Icomo 1e Vcomo 9:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

9     -> 1
99    -> 11

Ao dividir a parte anterior ->pelo dígito repetido, isso se torna:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

1     -> 1
11    -> 11

Então agora o original repetido Vnão é mais uma exceção. Então, eu quero uma expressão que faça isso acontecer:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

E isso pode ser feito por um simples módulo 182:

1     % 182 = 1
11    % 182 = 11
111   % 182 = 111
1111  % 182 = 19
11111 % 182 = 9

(isso mesmo fica IIIIIIpara VIa direita, embora ele não é necessário aqui)

Tudo o que resta é inicializar a variável de trabalho 1para o índice 0, repetir essa transformação em um loop e, no final, substituir 1por Ie 9porV

1, 9e 182é a única combinação de parâmetros para a qual essa fórmula simples funciona.

Mathematica, 113 90 83 bytes

Agradecemos a Martin Ender pelas sugestões que reduziram o comprimento em mais de 25%!

Exibindo os comandos de alto nível no Mathematica.

Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&

Uma função pura, pegando um argumento N e gerando o enésimo elemento dessa sequência (indexada 0), como uma lista de caracteres. Espalhe um pouco:

Nest[
  Flatten[
    Characters @ {RomanNumeral@#,#2}& @@@
      Reverse @@@ Tally /@ Split@ #
    ]& ,
  {"I"}, #]&

O externo Nestitera a função de quatro linhas do meio, começando {"I"}N vezes. A linha 4 divide a lista de caracteres do numeral romano de entrada em execuções de caracteres semelhantes, conta cada execução com Tallye coloca as contagens antes dos caracteres que estão contando. A linha 3 renderiza as contagens como algarismos romanos e depois os divide em listas de caracteres. O Flattencomando reduz a lista de listas inteira para uma lista unidimensional.

Aqui está a versão inicial:

Nest[
  "" <> Flatten[{RomanNumeral@#[[1]], #[[2]]} & /@
    (Reverse@#[[1]] & /@ 
      Tally /@
        Split@Characters@#)] &,
  "I", #] &

CJam ( 33 30 bytes)

"I"{e`{(4md1$^'I*\'V*@}%e_}ri*

Demonstração online

A chave para a correção da implementação é o seguinte teorema:

Se a primeira geração for I, nenhum comprimento de execução será maior que cinco

Lema: se a primeira geração é I, nenhuma string contém VVV. A prova é por contradição. Suponha que exista um primeiro índice npara o qual a nquinta geração contenha VVV. Se isso VVVquebrar como (a)V VVa conversão da geração anterior é ruim: deveria ter sido (a+5)V. Assim deve ser VV V(d), e a geração anterior continha VVVVV, contradiz a escolha de n.

Agora, suponha que exista um primeiro índice mpara o qual a mquinta geração contenha ...IIIIII.... Observe que não pode haver dígitos além de Ie Vna sequência, porque nenhuma geração anterior teve uma execução de nove Iou nove Vs. No máximo quatro dos Is vêm de uma sequência de Is na cadeia anterior, portanto a seção correspondente da cadeia anterior deve estar ...IIIVV...fornecendo ... IIII IIV .... Como a VVgeração in m-1não vem VVVVV(consulte o lema), o segundo Vdeve ser um dígito de duração I, portanto, na geração m-1que temos ...IIIVVI.... E já que queremos que as iniciais Idêem IIIIe não IVIouVI, é precedido pelo início da sequência ou por a V.

Se temos (...V)?IIIVVI...em geração m-1, o que temos em geração m-2? Já observamos que o VVde gen. m-1deve ser analisado como (a)V V(I).

Suponha que tomemos a=2: (...V)?I IIV VI...Na verdade deve ser ...VI IIV VI..., embora essa liderança Vpossa fazer parte IV; então, na geração anterior, temos um (...V)? IIII VV IIIII...ou outro (...V)? IIIII VV IIIII. De qualquer maneira, encontramos problemas VVIIIII: o segundo Vdeve ser um comprimento de execução, mas ...VI IIII...requer um par seguinte (comprimento de execução, dígito) com o mesmo dígito.

Assim deve ser a=1: (...V)?II IV VI.... Desde que a geração mé a primeira com seis Is, isso deve ser (...V)? II IV VI..., de modo que a geração m-2é (...V)? I V IIIII.... ...VIVIIIII...é impossível: no entanto, escolhemos interpretar o segundo em Vque terminamos com dois pares consecutivos (comprimento de execução, dígito) com o mesmo dígito.

Portanto, a geração m-2deve ser ^IVIIIII...analisada como ^IV IIII I(V)...ou ^IV III II(V).... Estes dão respectivamente geração m-3como ^V III V ...ou ^V II VV....

Mas se olharmos para o início das strings começando pelo primeiro V, começamos um ciclo:

    VI IV I...
    IV III IV ...
    II IV IVI ...
    IIII IV II IV ...

e assim nenhuma geração começa com VIIIVou VIIVV. Devemos concluir que não existe m.

Dissecação

"I"          e# Initial generation
{            e# Loop...
  e`         e#   Run-length encode
  {          e#   Foreach [run-length char] pair...
    (        e#     Extract the run-length r
    4md1$^   e#     Get the number of Vs and the number of Is
             e#     The number of Vs is r/4 ; the number of Is is (r%4)^(r/4)
    'I*\'V*@ e#     Repeat strings the appropriate number of times and reorder
  }%
  e_         e#  Flatten to a simple string
}ri*         e# ... n times, where n is taken from stdin

Python 3, 195 bytes

Há muitos bytes desperdiçados nos algarismos romanos; portanto, é provável que haja golfe lá.

Obrigado a @ El'endiaStarman, @ Sherlock9 e @Shooqie

import re
def f(x,r=""):
 for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*a
 return r
s="I"
for i in[0]*int(input()):print(s);s=re.sub(r'(.)\1*',lambda m:f(len(m.group()))+m.group()[0],s)

Ideone it!

R, 110 107 bytes

as.romancombinado com rlefacilita isso. Abuso de escopo e comportamento <<-interno de gato economiza alguns bytes.

x="I"
replicate(scan(),{r=rle(strsplit(x,"")[[1]])
x<<-paste(rbind(paste(as.roman(r$l)),r$v),collapse="")})

Recebe N do console. Emite os primeiros 2 a N termos de sequência (que acredito estar dentro das especificações ...)

 [1] "II"                                                                                                                                                                                                                                     
 [2] "III"                                                                                                                                                                                                                                    
 [3] "IIII"                                                                                                                                                                                                                                   
 [4] "IVI"                                                                                                                                                                                                                                    
 [5] "IIIVII"                                                                                                                                                                                                                                 
 [6] "IIIIIVIII"                                                                                                                                                                                                                              
 [7] "VIIVIIII"                                                                                                                                                                                                                               
 [8] "IVIIIIVIVI"                                                                                                                                                                                                                             
 [9] "IIIVIVIIVIIIVII"                                                                                                                                                                                                                        
[10] "IIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                                                                                               
[11] "VIIVIIIIIVIVIIVVIIVIIII"                                                                                                                                                                                                                
[12] "IVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                                                                                                          
[13] "IIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                                                                                                                                   
[14] "IIIIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                                                                      
[15] "VIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                                                                                                                                                 
[16] "IVIIIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                                                                         
[17] "IIIVIVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                                                                                            
[18] "IIIIIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                           
[19] "VIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                                                                                              
[20] "IVIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                    
[21] "IIIVIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                             
[22] "IIIIIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIIVIVIIVIIIIIVVIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                      
[23] "VIIVIIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVVIIVIIIVIIIIVVIIIVIIIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                   
[24] "IVIIIIVVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIIVIIIIVIIIIIVIVIIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                             
[25] "IIIVIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIVIIVVIIVIIIVIIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"

JavaScript (ES6), 107

Função recursiva retornando o enésimo termo 0 com base em

f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

Teste

f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

function update() {
  O.textContent=f(I.value)
}

update()

<input id=I value=25 type=number oninput='update()'><pre id=O></pre>

Perl 6 , 62 bytes

{("I",{S:g/(.)$0*/{<I II III IV V>[$/.chars-1]~$0}/}...*)[$_]}

Função anônima que aceita um índice baseado em zero.

Utiliza o fato de que números romanos acima de 5 não são necessários, porque os únicos grupos de dígitos repetidos que podem ocorrer são:

I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

( experimente online )