Descripción del desafío

Hemos tenido algunos desafíos relacionados con la secuencia de mirar y decir . Recordatorio rápido:

• La secuencia comienza con 1,
• Los términos posteriores de esta secuencia se generan enumerando cada grupo de dígitos repetidos en el término anterior,

Entonces, los primeros términos son:

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"

Ahora hagamos lo mismo, pero use números romanos en su lugar. Comenzamos con Iy seguimos las mismas reglas (aplicamos la regla de conteo de dígitos a los caracteres en su lugar, así que leemos IVXcomo en one one, one five, one tenlugar de one four, one teno de alguna otra manera):

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 un entero positivo N, ya sea:

• Imprime los primeros Nnúmeros de esta secuencia (cualquier separador razonable está bien, así como["I", "II", "III", ...]
• NTérmino de salida de esta secuencia (puede estar indexado a 0).

Recuerde hacer su código lo más corto posible, ya que este es un desafío de código de golf .

EDITAR: Creo que siempre hay una forma estándar / preferida de expresar enteros como números romanos, (como 95-> en XCVlugar de VC). Un par de convertidores de números romanos que encontré en línea corroboran mi opinión. En caso de duda, utilice un convertidor en línea , ya que enumerar todos los casos límite posibles y las reglas específicas de escribir números romanos no es el punto de este desafío.

Edit2: @PeterTaylor y @GregMartin señalaron que sólo los números menores o iguales a 5aparecer en la secuencia, por lo que no tiene que preocuparse por la ambigüedad de los números romanos (números 1- 8son I, II, III, IV, V, VI, VII, y VIII)

Perl, 49 bytes

Incluye +1 para -p

Ejecutar con el índice basado en 0 en STDIN, p. Ej.

ecce.pl <<< 14

ecce.pl:

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

Las fórmulas mágicas son tan mágicas.

Normalmente, usaría ($_=//)x$'para hacer que el control de bucle sea un byte más corto, pero la puntuación en este sitio le da una desventaja de 2, por lo que termina 1 byte más. En perls más antiguos, puede soltar el espacio antes for. Algunas versiones de perl te obligan a agregar una final ;para cerrar la transliteración. Pero lo que se da arriba es el código que funciona en mi sistema.

Explicación

Trabajando hacia atrás desde la solución al código:

Las transformaciones de cadena que necesitamos:

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

V     -> IV
VV    -> IIV

Cada reemplazo termina con el carácter repetido. Obtendré una secuencia de los mismos caracteres usando regex /(.)\1*/, por lo que esto se puede hacer agregando $1. La parte anterior a la ->está en $&. Con eso todavía necesito:

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

V     -> I
VV    -> II

Escribe Icomo 1y Vcomo 9:

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

9     -> 1
99    -> 11

Al dividir la parte anterior ->por el dígito repetido, esto se convierte en:

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

1     -> 1
11    -> 11

Así que ahora el original repetido Vya no es una excepción. Entonces quiero una expresión que haga que esto suceda:

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

Y esto se puede hacer mediante un simple módulo 182:

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

(Esto incluso llega IIIIIIa la VIderecha, aunque no es necesario aquí)

Todo lo que queda es inicializar la variable de trabajo 1para el índice 0, repetir esta transformación en un bucle y al final reemplazar 1por Iy 9porV

1, 9y 182es la única combinación de parámetros para la que funciona esta fórmula simple.

Mathematica, 113 90 83 bytes

¡Gracias a Martin Ender por las sugerencias que redujeron la longitud en más del 25%!

Mostrando los comandos de alto nivel en Mathematica.

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

Una función pura, que toma un argumento N y genera el enésimo elemento de esta secuencia (indexada en 0), como una lista de caracteres. Extender un poco:

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

El exterior Nestitera la función de cuatro líneas del medio, comenzando en {"I"}, N veces. La línea 4 divide la lista de caracteres del número romano de entrada en series de caracteres similares, cuenta cada serie Tallyy coloca las cuentas antes de los caracteres que están contando. La línea 3 representa los recuentos como números romanos, luego divide esos números romanos en listas de caracteres. El Flattencomando reduce toda la lista de listas a una lista unidimensional.

Aquí está la versión inicial:

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

CJam ( 33 30 bytes)

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

Demostración en línea

La clave para la corrección de la implementación es el siguiente teorema:

Si la primera generación es I, ninguna longitud de ejecución es nunca mayor que cinco

Lema: si la primera generación es I, ninguna cadena contiene nunca VVV. La prueba es por contradicción. Supongamos que hay un primer índice npara el que ncontiene la generación th VVV. Si eso se VVVrompe, (a)V VVentonces la conversión de la generación anterior es mala: debería haberlo sido (a+5)V. Así debe ser VV V(d), y la generación anterior contenida VVVVV, contradiciendo la elección de n.

Ahora, supongamos que hay un primer índice mque mcontiene la generación th ...IIIIII.... Tenga en cuenta que no puede haber dígitos distintos de Iy Ven la cadena, porque ninguna generación anterior ha tenido una ejecución de nueve Iso nueve Vs. Como máximo, cuatro de los Is provienen de una serie de Is en la cadena anterior, por lo que la sección correspondiente de la cadena anterior debe estar ...IIIVV...dando ... IIII IIV .... Como la VVgeneración m-1no proviene de VVVVV(ver lema), la segunda Vdebe ser una longitud de dígitos I, por lo que en generación m-1sí ...IIIVVI.... Y dado que queremos que la Is inicial dé IIIIy no IVIoVI, está precedido por el inicio de la cadena o por un V.

Si tenemos (...V)?IIIVVI...en generación m-1, ¿qué tenemos en generación m-2? Ya hemos observado que la VVde gen. m-1debe analizarse como (a)V V(I).

Supongamos que tomamos a=2: en (...V)?I IIV VI...realidad debe ser ...VI IIV VI..., aunque ese liderazgo Vpodría ser parte de IV; así que en la generación anterior tenemos (...V)? IIII VV IIIII...o (...V)? IIIII VV IIIII. De cualquier manera nos encontramos con problemas VVIIIII: el segundo Vdebe ser una longitud de ejecución, pero luego ...VI IIII...requiere un par siguiente (longitud de ejecución, dígito) con el mismo dígito.

Lo que debe ser a=1: (...V)?II IV VI.... Dado que la generación mes la primera con una carrera de seis Is, debe ser (...V)? II IV VI..., por lo que esa generación m-2es (...V)? I V IIIII.... ...VIVIIIII...es imposible: sin embargo, elegimos interpretar el segundo Vy terminamos con dos pares consecutivos (longitud de ejecución, dígitos) con el mismo dígito.

Por lo tanto, la generación m-2debe ser ^IVIIIII...analizada como ^IV IIII I(V)...o ^IV III II(V).... Estos dan respectivamente generación m-3como ^V III V ...o ^V II VV....

Pero si miramos el inicio de las cadenas que comienzan con la primera que comienza V, obtenemos un ciclo:

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

y entonces ninguna generación comienza con ninguno VIIIVo VIIVV. Debemos concluir que no existe tal m.

Disección

"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

Hay una gran cantidad de bytes desperdiciados en los números romanos, por lo que es probable que haya algo de golf allí.

Gracias a @ El'endiaStarman, @ Sherlock9 y @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 con rlehace esto fácil. Abuso de alcance y comportamiento de gato integrado de <<-guarda unos pocos bytes.

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

Toma N de la consola. Emite los primeros 2 a N términos de secuencia (que creo que está dentro de las especificaciones ...)

 [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

Función recursiva que devuelve el enésimo término basado en 0

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

Prueba

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}/}...*)[$_]}

Función anónima que acepta un índice basado en cero.

Hace uso del hecho de que no se necesitan números romanos superiores a 5, porque los únicos grupos de dígitos que se pueden repetir son:

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

V     -> IV
VV    -> IIV

( pruébalo en línea )