Rekurencyjny opis binarny

Niedawno włożyłem swój pierwszy wkład w OEIS, rozszerzając i dodając plik b do sekwencji A049064 . Sekwencja zaczyna się od 0, a następnie uzyskiwane są kolejne wartości z „binarnego opisu” ostatniego elementu.

Na przykład drugi termin byłby 10, ponieważ był jeden 0w pierwszym elemencie. Trzeci termin byłby 1110, ponieważ był jeden 1i jeden 0. Czwarty byłby 11110. ponieważ są trzy ( 11binarnie!) 1 i jeden 0. Poniżej znajduje się podział piątego terminu, aby wyjaśnić ten proces:

> 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)

Oto przykład przejścia od szóstej do siódmej kadencji:

> 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

Możesz sprawdzić program referencyjny ^φ zrobiłem do obliczania terminów.

Twoja praca

Musisz utworzyć program lub funkcję, która przyjmuje liczbę nza pomocą standardowych argumentów wejściowych lub funkcyjnych i wypisuje sekwencję od 1stterminu do (n+1)thterminu, oddzielone znakiem nowej linii. Jeśli chcesz rzucić okiem na niższe liczby, możesz odnieść się do pliku b ze strony OEIS. Jednak Twój program / funkcja powinna obsługiwać 0 <= n <= 30, tj. Do 31 kadencji. To niemały wyczyn, bo A049064(30)ma ponad 140 000 cyfr ^δ . Jeśli chcesz zobaczyć, jaki powinien być 31 termin, umieściłem go na Pastebin .

Przykład I / O

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

func(0)
0

func(3)
0
10
1110
11110

Jest tylko jedna zasada: brak standardowych luk!

To jest golf golfowy , więc wygrywa najmniejsza liczba bajtów.

^{φ - Gist można znaleźć tutaj , a tutaj jest demo ideone .}

^{δ - Na wypadek, gdybyś się zastanawiał, moje szacunki dotyczące długości 100 wyrażenia określają go na około 3,28 x 10 250 znaków, co byłoby całkiem sporo do obliczenia.}

CJam, 18 17 bajtów

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

Dzięki @ MartinBüttner za grę w golfa jednym bajtem!

Wypróbuj online w interpretatorze CJam .

Jak to działa

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 bajtów

J]0VQjk~JsjR2srJ8

Wypróbuj online: demonstracja

Dzięki @isaacg za zapisanie jednego bajtu.

Wyjaśnienie:

                     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

Wykorzystuje to fakt, że 0 i 1 w systemie binarnym to także 0 i 1.

Python 2, 125 116 110 bajtów

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

Zaoszczędzono 1 bajt dzięki @ Sp3000 i 5 bajtów, usuwając zbędne intwywołanie.

Starsza wersja:

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()

Zaoszczędź wiele, wiele bajtów dzięki @ Vioz-!

Orginalna wersja:

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))

Rubinowy, 80 72 69 bajtów

Jako funkcja:

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

Nazwij to na przykład za pomocą: f[6]

Python 2, 102 bajty

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

Jakoś połączenie itertoolsbycia dłuższym niż rei groupbyzwracanie grouperobiektów oznacza, że ​​użycie wyrażenia regularnego jest nieco krótsze ...

Kobra - 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 bajtów

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