Descripción binaria recursiva

Recientemente, hice mi primera contribución a OEIS extendiendo y agregando un archivo b a la secuencia A049064 . La secuencia comienza con 0, y luego los siguientes valores se derivan de dar una "descripción binaria" del último elemento.

Por ejemplo, el segundo término sería 10, porque había uno 0en el primer elemento. El tercer término sería 1110, porque había uno 1y uno 0. El cuarto sería 11110. porque hay tres ( 11en binario) 1 sy uno 0. A continuación se muestra un desglose del quinto término para aclarar este proceso:

> 11110
> 1111 0    (split into groups of each number)
> 4*1 1*0   (get count of each number in each group)
> 100*1 1*0 (convert counts to binary)
> 100110    (join each group back together)

Y aquí hay un ejemplo para pasar del sexto al séptimo término:

> 1110010110
> 111 00 1 0 11 0
> 3*1 2*0 1*1 1*0 2*1 1*0
> 11*1 10*0 1*1 1*0 10*1 1*0
> 111100111010110

Se puede extraer de un programa de referencia ^φ hice para calcular los términos.

Tu trabajo

Debe crear un programa o función que tome un número nmediante argumentos de entrada o función estándar e imprima la secuencia del 1sttérmino al (n+1)thtérmino, separados por una nueva línea. Si desea ver los números más bajos, puede consultar el archivo b desde la página OEIS. Sin embargo, su programa / función debe ser compatible 0 <= n <= 30, es decir, hasta el 31er término. Esto no es poca cosa, ya que A049064(30)tiene más de 140,000 dígitos de largo ^δ . Si desea ver cuál debería ser el 31er término, lo puse en Pastebin .

Ejemplo de E / S

func(10)
0
10
1110
11110
100110
1110010110
111100111010110
100110011110111010110
1110010110010011011110111010110
1111001110101100111001011010011011110111010110
1001100111101110101100111100111010110111001011010011011110111010110

func(0)
0

func(3)
0
10
1110
11110

Solo hay una regla: ¡ No hay lagunas estándar!

Este es el código de golf , por lo que gana el conteo de bytes más bajo.

^{φ - Gist se puede encontrar aquí , y una demostración de ideone está aquí .}

^{δ - En caso de que te lo estés preguntando, mis estimaciones sobre la duración del centésimo término lo sitúan en aproximadamente 3.28x10 250 caracteres, lo que sería bastante para que cualquiera lo calcule.}

CJam, 18 17 bytes

0{sN1$e`2af.b}ri*

¡Gracias a @ MartinBüttner por jugar golf en un byte!

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

0                 e# Push 0.
 {           }ri* e# Repeat int(input)) times:
  s               e#   Stringify the element on top of the stack.
                       EXAMPLE: [[[1 1] '1] [[1] '0]] -> "11110"
   N              e#   Push a linefeed.
    1$            e#   Copy the last stack.
      e`          e#   Perform run-length encoding.
                  e#   EXAMPLE: "100110" -> [[1 '1] [2 '0] [2 '1] [1 '0]]
        2a        e#   Push [2].
          f.b     e#   For each pair [x 'y], execute: [x 'y][2].b
                  e#   This pushes [x2b 'y], where b is base conversion.

Pyth, 18 17 bytes

J]0VQjk~JsjR2srJ8

Pruébelo en línea: demostración

Gracias a @isaacg por guardar un byte.

Explicación:

                     implicit: Q = input number
 ]0                  create an initial list [0]
J                    and store in J
   VQ                for loop, repeat Q times:
              rJ8       run-length-encoding of J
             s          sum, unfolds lists
          jR2           convert each value to base 2
         s              sum, unfolds lists
       ~J               store the result in J

                        but return the old list,
     jk                 join it and print it

Esto utiliza el hecho de que 0 y 1 en binario también son 0 y 1.

Python 2, 125 116 110 bytes

from itertools import*
v='0'
exec"print v;v=''.join(bin(len(list(g)))[2:]+k for k,g in groupby(v));"*-~input()

Se guardó 1 byte gracias a @ Sp3000 y 5 bytes al eliminar una intllamada redundante .

Versión antigua:

import itertools as t
v='0'
exec"print v;v=''.join(bin(int(len(list(g))))[2:]+k for k,g in t.groupby(v));"*-~input()

¡Ahorré muchos, muchos bytes gracias a @ Vioz-!

Versión original:

import itertools as t
v='0'
for n in range(input()+1):print v;v=''.join(bin(int(len(list(g))))[2:]+k for k,g in t.groupby(v))

Ruby, 80 72 69 bytes

Como una función:

f=->m{l=?0;0.upto(m){puts l;l.gsub!(/1+|0+/){$&.size.to_s(2)+$&[0]}}}

Llámalo por ejemplo con: f[6]

Python 2, 102 bytes

import re
o='0'
exec"print o;o=''.join(bin(len(x))[2:]+x[0]for x in re.findall('0+|1+',o));"*-~input()

De alguna manera, la combinación de itertoolsmás largo que rey groupbyvolver groupersignifica que los objetos que el uso de expresiones regulares es un poco más corto ...

Cobra - 128

do(i)=if(i-=1,(r=RegularExpressions).Regex.replace(f(i),'1+|0+',do(m=r.Match())=Convert.toString('[m]'.length,2)+'[m]'[:1]),'0')

Haskell, 136 130 Bytes

import Text.Printf
import Data.List
f n=putStr.unlines.take(n+1).iterate(concatMap(\n->(printf"%b"$length n)++[head n]).group)$"0"