Secuencia de mirar y decir: edición de números romanos

20

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 .

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)

shooqie
fuente
No hay una expresión de números romanos única para cada número entero. ¿Qué números podría ser necesario expresar y qué expresiones de esos números son válidas?
Peter Taylor
¿Qué quiere decir con "no hay una expresión de número romano único para cada número entero"? Me gusta 4/ IV/ IIII? O 95/ XCV/ VC? Puede que no siempre haya una forma única de expresar un número entero, pero estoy bastante seguro de que siempre hay uno preferido (estándar): corrígeme si me equivoco.
shooqie
1
¿hasta dónde tenemos que llegar con nuestros entusiastas romanos?
Maltysen
Sí, ambos casos. En el segundo caso, creo que es una cuestión de opinión que es preferible.
Peter Taylor
99
@shooqie si no se aclararan estos detalles, ¿cómo compararía las respuestas? Si quedan ciertos casos límite para la interpretación, los puntajes reales no tienen sentido porque podrían marcar una diferencia mayor que cualquier truco de golf que se te ocurra.
Martin Ender

Respuestas:

17

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.

Ton Hospel
fuente
2
Esto es genial! :)
Lynn
10

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", #] &
Greg Martin
fuente
3
Grrr Mathematica;)
Decaimiento Beta
Si usa en @@@lugar de /@puede usar #y en #2lugar de #[[1]]y #[[2]]. Además, las listas de caracteres son tipos de cadena aceptables, por lo que puede trabajar con ellos y evitar su uso Characters@.
Martin Ender
@MartinEnder ¡Ajá, sabía que debía haber un @@@atajo similar! En cuanto a las listas de caracteres que son tipos de cadena aceptables (lo que estoy de acuerdo acortaría el código): ¿hay alguna publicación en este sitio que me pueda señalar que describa los estándares de la comunidad?
Greg Martin
1
Unos pocos ahorros más: los Charactershilos automáticamente para que pueda usar @, Reverse@#&por supuesto , es lo mismo que simple Reverse, en cuyo caso tampoco necesita esos paréntesis. Y la notación de prefijo (en el caso de Flatten) no guarda nada si necesita agregar paréntesis para que funcione. Combinando todos esos:Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&
Martin Ender
8

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-1...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
Peter Taylor
fuente
6

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!

Decaimiento Beta
fuente
Puede omitir corchetes:for v,i in(5,"V"),(4,"IV"),(1,"I")
shooqie
@shooqie No tenía idea de que podrías hacer eso: D
Beta Decay
for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*aGuarda un byte.
Sherlock9
@ βετѧΛєҫαγ: Además, parece que no estás usando i(como en for i in range(...)). Traté de incursionar con, execpero esto escapó 1en el método 'sub' parece estar estropeando el código, no he podido encontrar una solución.
shooqie
@shooqie Lo acorté un poco deshaciéndome derange
Beta Decay
4

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"
Vlo
fuente
1

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>

edc65
fuente
1

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 )

smls
fuente