Podsumowanie pod przedstawicielstwem Zeckendorfa

14

Twierdzenie Zeckendorfa pokazuje, że każdą dodatnią liczbę całkowitą można jednoznacznie przedstawić jako sumę niesąsiadujących liczb Fibonacciego. W tym wyzwaniu musisz obliczyć sumę dwóch liczb w reprezentacji Zeckendorfa.


Niech F n będzie n-liczbą Fibonacciego gdzie

F 1 = 1,
F 2 = 2 i
dla wszystkich k > 2, F k = F k - 1 + F k - 2 .

Reprezentacja Zeckendorfa Z ( n ) nieujemnej liczby całkowitej n jest zbiorem liczb całkowitych dodatnich, takich jak

n = Σ i ∈ Z ( n ) F i   oraz
i ∈ Z ( n ) i + 1 ∉ Z ( n ).

(prosa: reprezentacja Zeckendorfa liczby n jest zbiorem liczb całkowitych dodatnich, tak że liczby Fibonacciego dla tych wskaźników sumują się do n, a żadne dwie sąsiednie liczby całkowite nie są częścią tego zbioru)

W szczególności reprezentacja Zeckendorf jest wyjątkowa. Oto kilka przykładów reprezentacji Zeckendorfa:

Z (0) = ∅ (pusty zbiór)
Z (1) = {1}
Z (2) = {2}
Z (3) = {3} ({1, 2} nie jest reprezentacją Zeckendorfa dla 3)
Z (10) = {5, 2}
Z (100) = {3, 5, 10}

W tym wyzwaniu reprezentacje Zeckendorfa są kodowane jako zestawy bitów, w których najmniej znaczący bit reprezentuje if 1jest częścią zestawu itp. Można założyć, że reprezentacje Zeckendorfa zarówno wejściowego, jak i wyjściowego pasują do 31 bitów.

Twoim zadaniem jest obliczenie Z ( n + m ) na podstawie Z ( n ) i Z ( m ). Rozwiązanie o najkrótszej długości w oktetach wygrywa.

Można znaleźć implementację referencyjną napisany w ANSI C tutaj . Można go również użyć do wygenerowania reprezentacji Zeckendorfa lub obliczenia liczby z jego reprezentacji Zeckendorfa.

Oto kilka par przykładowych danych wejściowych i wyjściowych, w których dwie pierwsze kolumny zawierają dane wejściowe, a trzecia kolumna zawiera dane wyjściowe:

73865           9077257         9478805
139808          287648018       287965250
34              279004309       279004425
139940          68437025        69241105
272794768       1051152         273846948
16405           78284865        83888256
9576577         4718601         19013770
269128740       591914          270574722
8410276         2768969         11184785
16384           340             16724
FUZxxl
źródło
4
Czy mógłbyś opracować Wejście / Wyjście?
flawr
@flawr Proszę spojrzeć na podaną implementację referencyjną. Możesz go użyć do wygenerowania własnego przykładowego wejścia.
FUZxxl,
3
Byłbym szczęśliwy, gdybyś mógł udokumentować tutaj dokładnie to, czego chcesz i podać kilka przykładów, tak jak ja, a być może inni też nie
mówią
Nie zgadzam się z argumentem wyjątkowości. Ponieważ sekwencja Fibonacciego zaczyna się od 1, 1, 2, możesz wyraźnie rozłożyć 3 na F0 + F2 = 1 + 2 = 3. F0 i F2 nie sąsiadują ze sobą.
orlp
1
@orlp Zdefiniowana tutaj sekwencja Fibonacciego zaczyna się od F1 = 1 i F2 = 2. Więc sposób, w jaki go czytam, F0 z twojej definicji nie jest częścią sekwencji użytej tutaj.
Reto Koradi,

Odpowiedzi:

5

K (ngn / k) , 45 43 42 41 bajtów

{2/<':(+/F@&+/'|2\x){y!x}\|F:64(+':1,)/0}

Wypróbuj online!

Algorytm Bubblera

{ } funkcja z argumentem x

64( )/0 wykonaj 64 razy, używając 0 jako wartości początkowej:

  • 1, prepend 1

  • +': dodaj każdy poprzedni (pozostaw pierwszy element nienaruszony)

F:przypisać do Fdla „sekwencji fibonacciego”

| odwrócić

(.. ){y!x}\.. zaczynając od wartości po lewej, oblicz skumulowane reszty (od lewej do prawej) dla listy po prawej. wartość po lewej stronie jest zwykłą sumą danych wejściowych bez reprezentacji Zeckendorfa:

  • 2\xbinarnie koduje wejścia. będzie to macierz nbits-by-2

  • | odwrócić

  • +/' zsumuj każdy

  • &gdzie są jedynki? - lista wskaźników. jeśli są jakieś 2, odpowiedni indeks jest powtarzany dwukrotnie.

  • F@ indeksowanie tablicy do F

  • +/ suma

<': mniej niż każdy poprzedni (pierwszy wynik zawsze będzie falsey)

2/ dekodowanie binarne

ngn
źródło
10

CJam, 76 74 70 63 59 bajtów

2q~{32{2\#I&},}fI+32_,*{WUer$Kf-[UU]/[-2X]*2,/2a*Kf+}fKf#1b

Wypróbuj online w interpretatorze CJam lub zweryfikuj wszystkie przypadki testowe jednocześnie .

Pomysł

Zaczynamy od zdefiniowania niewielkiej odmiany sekwencji w pytaniu:

G -2 = 0
G -1 = 1
G k = G k-1 + G k-2, gdy k jest liczbą całkowitą nieujemną

W ten sposób bit 0 (LSB) na wejściu bit tablic lub odpowiada wyjściowych do liczby Fibonacciego G 0 i, na ogół, nieco K do G K .

Teraz zamieniamy każdy ustawiony bit w Z (n) i Z (m) na kodowany przez niego indeks.

Na przykład wejście 532 10 = 1000010100 2 zostaje przekształcone na [2 4 9] .

Daje to dwie tablice liczb całkowitych, które możemy połączyć, tworząc jedną.

Na przykład, jeśli n = m = 100 , wynikiem jest A: = [2 4 9 2 4 9] .

Jeśli zastąpimy każdy k w A przez G k i dodać wyniki otrzymujemy n + m = 200 , więc jest sposób rozkładać 200 do liczb Fibonacciego, ale na pewno nie jeden z twierdzenie zeckendorfa.

Pamiętając, że G k + G k + 1 = G k + 2 i G k + G k = G k + G k-1 + G k-2 = G k + 1 + G k-2 , możemy zastąpić kolejne i zduplikowane indeksy przez innych (mianowicie (k, k + 1) przez k + 2 i (k, k) przez (k + 1, k - 2) ), powtarzając te podstawienia w kółko, aż do osiągnięcia reprezentacji Zeckendorfa. 1

Szczególny przypadek należy wziąć pod uwagę w przypadku wynikowych indeksów ujemnych. Ponieważ G -2 = 0 , indeks -2 można po prostu zignorować. Ponadto G -1 = 0 = G 0 , więc każdy wynikowy -1 musi zostać zastąpiony przez 0 .

W naszym przykładzie A otrzymujemy następujące (posortowane) reprezentacje, z których ostatnia to reprezentacja Zeckendorfa.

[2 2 4 4 9 9] → [0 3 4 4 9 9] → [0 5 4 9 9] → [0 6 9 9] → [0 6 7 10] → [0 8 10]

Na koniec konwertujemy z powrotem z tablicy liczb całkowitych na tablicę bitów.

Kod

2             e# Push a 2 we'll need later.
q~            e# Read and evaluate the input.
{             e# For each integer I in the input:
  32{         e#   Filter [0 ... 31]; for each J:
    2\#       e#     Compute 2**J.
    I&        e#     Compute its logical AND with I.
  },          e#   Keep J if the result in truthy (non-zero).
}fI           e#
+             e# Concatenate the resulting arrays.
32_,*         e# Repeat [0 ... 31] 32 times.
{             e# For each K:
  WUer        e#   Replace -1's with 0's.
  $           e#   Sort.
  Kf-         e#   Subtract K from each element.
  [UU]/[-2X]* e#   Replace subarrays [0 0] with [-2 1].
  2,/2a*      e#   Replace subarrays [0 1] with [2].
  Kf+         e#   Add K to each element.
}fK           e#
f#            e# Replace each K with 2**K.
1b            e# Cast all to integer (discards 2**-2) and sum.

1 Wdrożenie próbuje zastąpić 32 razy i nie sprawdza, czy rzeczywiście osiągnięto reprezentację Zeckendorf. Nie mam formalnego dowodu, że to wystarcza, ale przetestowałem wszystkie możliwe sumy reprezentacji 15-bitowych (których reprezentacje wymagają do 17 bitów) i dla wszystkich z nich wystarczyło 6 powtórzeń. W każdym razie zwiększenie liczby powtórzeń do 99 jest możliwe bez zwiększania liczby bajtów, ale pogorszyłoby to wydajność.

Dennis
źródło
10

APL (Dyalog Extended) , 39 bajtów

1↓⍧|/⌽(+/g[⍸⌽+/⊤⎕]),↑,\⌽g←(2+/,)⍣38⍨⍳2

Wypróbuj online!

Zmieniono na pełny program z jednym argumentem o długości 2, a także zmieniono generator Fibonacciego. Dzięki @ngn za wiele pomysłów.

Używa ⎕IO←0tak, że ⍳2ocenia 0 1.

Generator Fibonacciego (nowy)

Zauważ, że dwie ostatnie liczby są niedokładne, ale nie zmienia to wyniku działania programu.

(2+/,)⍣38⍨⍳2
 0 1 ((2+/,)⍣38) 0 1

Step 1
0 1 (2+/,) 0 1
 2+/ 0 1 0 1
 (0+1) (1+0) (0+1)  2+/ evaluates sums for moving window of length 2
 1 1 1

Step 2
0 1 (2+/,) 1 1 1
 2+/ 0 1 1 1 1
 1 2 2 2

Step 3
0 1 (2+/,) 1 2 2 2
 2+/ 0 1 1 2 2 2
 1 2 3 4 4

Zeckendorf na zwykły (częściowy)

⍸⌽+/⊤⎕
        Take input from stdin, must be an array of 2 numbers
        Convert each number to base 2; each number is mapped to a column
  +/     Sum in row direction; add up the counts at each digit position
        Reverse
        Convert each number n at index i to n copies of i

APL (Dyalog Extended) , 47 bajtów

g1↓(1,+\⍤,)⍣201
{⊥1↓⍧|/⌽⍵,↑,\⌽g}+⍥{+/g[⍸⌽⊤⍵]}

Wypróbuj online!

Zmieniono część 1 poprzedniej odpowiedzi, aby ponownie użyć liczb Fibonacciego. Upuść również duplikat 1, aby zapisać niektóre bajty w innych miejscach.

Część 1 (nowa)

{+/g[⍸⌽⊤⍵]}
       ⊤⍵     Argument to binary digits
     ⍸⌽       Reverse and convert to indices of ones
   g[    ]    Index into the Fibonacci array of 1,2,3,5,...
 +/           Sum

APL (Dyalog Extended) , 52 bajty

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣201}+⍥({+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤)

Wypróbuj online!

Jak to działa

Brak dodatkowego algorytmu do dodania w Zeckendorf, ponieważ APL nie jest znany z działania na poszczególnych elementach tablicy. Zamiast tego postanowiłem przekonwertować dwa wejścia z Zeckendorfa na zwykłe liczby całkowite, dodać je i przekonwertować z powrotem.

Część 1: Zeckendorf do zwykłej liczby całkowitej

{+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤   Zeckendorf to plain integer
                   Convert the input to array of binary digits (X)
{    (  ≢⊤⍵)  }     Take the length L of the binary digits and
      ⌽⍳              generate 1,2..L backwards, so L..2,1
{+∘÷⍣(     )⍨1}     Apply "Inverse and add 1" L..2,1 times to 1
                    The result looks like ..8÷5 5÷3 3÷2 2 (Y)
                   Mixed base conversion of X into base Y

Base |             Digit value
-------------------------------
13÷8 | (8÷5)×(5÷3)×(3÷22 = 8
 8÷5 |       (5÷3)×(3÷22 = 5
 5÷3 |             (3÷22 = 3
 3÷2 |                   2 = 2
 2÷1 |                   1 = 1

Część 2: Dodaj dwie zwykłe liczby całkowite

+⍥z2i   Given left and right arguments,
          apply z2i to each of them and add the two

Część 3: Przelicz sumę z powrotem na Zeckendorf

„Można założyć, że reprezentacje Zeckendorfa zarówno wejścia, jak i wyjścia pasują do 31 bitów” było całkiem przydatne.

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣201}   Convert plain integer N to Zeckendorf
                 (1,+\⍤,)⍣201    First 41 Fibonacci numbers starting with two 1's
                ⌽                ⍝ Reverse
             ↑,\                 ⍝ Matrix of prefixes, filling empty spaces with 0's
          ⌽⍵,                     Prepend N to each row and reverse horizontally
        |/                        Reduce by | (residue) on each row (see below)
                                 Nub sieve; 1 at first appearance of each number, 0 otherwise
  1↓¯1                           Remove first and last item
                                 Convert from binary digits to integer

Generator Fibonacciego

(1,+\⍤,)⍣201
 1 ((1,+\⍤,)⍣20) 1   Expand 
 Apply 1 (1,+\⍤,) x 20 times to 1

First iteration
1(1,+\⍤,)1
 1,+\1,1   Expand the train
 1,1 2     +\ is cumulative sum
 1 1 2     First three Fibonacci numbers

Second iteration
1(1,+\⍤,)1 1 2
 1,+\1,1 1 2   Expand the train
 1 1 2 3 5     First five Fibonacci numbers

20   ... Repeat 20 times

Wynika to z właściwości liczb Fibonacciego: jeśli Fibonacciego jest zdefiniowane jako

F0=F1=1;n0,Fn+2=Fn+1+Fn

następnie

n0,i=0nFi=Fn+21

Łączna suma 1,F0,,Fn (Tablica Fibonacciego poprzedzona 1) staje się F1,,Fn+2. Następnie przygotowuję 1 ponownie, aby uzyskać zwykłą tablicę Fibonacciego, zaczynając od indeksu 0.

Cyfry Fibonacciego do Zeckendorfa

Input: 7, Fibonacci: 1 1 2 3 5 8 13

Matrix
0 0 0 0 0 0 13 7
0 0 0 0 0 8 13 7
0 0 0 0 5 8 13 7
0 0 0 3 5 8 13 7
0 0 2 3 5 8 13 7
0 1 2 3 5 8 13 7
1 1 2 3 5 8 13 7

Reduction by residue (|/)
- Right side always binds first.
- x|y is equivalent to y%x in other languages.
- 0|y is defined as y, so leading zeros are ignored.
- So we're effectively doing cumulative scan from the right.
0 0 0 0 0 0 13 7 → 13|7 = 7
0 0 0 0 0 8 13 7 →  8|7 = 7
0 0 0 0 5 8 13 7 →  5|7 = 2
0 0 0 3 5 8 13 7 →  3|2 = 2
0 0 2 3 5 8 13 7 →  2|2 = 0
0 1 2 3 5 8 13 7 →  1|0 = 0
1 1 2 3 5 8 13 7 →  1|0 = 0
Result: 7 7 2 2 0 0 0

Nub sieve (⍧): 1 0 1 0 1 0 0
1's in the middle are produced when divisor  dividend
(so it contributes to a Zeckendorf digit).
But the first 1 and last 0 are meaningless.

Drop first and last (1↓¯1↓): 0 1 0 1 0
Finally, we apply base 2 to integer (⊥) to match the output format.
Bubbler
źródło
6

Haskell, 325 396 bajty

EDYCJA: nowa wersja:

s f[]=[]
s f l=f l
x((a:b):(c:d):(e:r))=x(b:d:(a:e):r)
x(a:b:((c:d:e):r))=x((c:a):b:e:((d:s head r):s tail r))
x[]=[]
x(a:r)=a:x r
w l|x l/=l=w.x$l|True=l
l=length
t n x=take n$repeat x
j 0=[]
j n=t(mod(n)2)1:j(div(n)2)
i n=[[],[]]++j n++t(32-(l$j n))[]
u[]=0
u(a:r)=2*u r+l a
o(_:a:r)=u r+l a
z a b=o$w$zipWith(++)(i a)(i b)

z wykonuje pracę.

Leif Willerts
źródło
Niektóre rzeczy można od razu skrócić - na przykład funkcja ma najwyższy priorytet, więc możesz pozbyć się rodziców wokół aplikacji funkcji, a także strażnicy też nie potrzebują rodziców - strażnicy zatrzymują się tam, gdzie =jest, więc rodzice nie są potrzebni i tak dalej, i tak dalej, i zauważcie, że :kojarzy się po prawej i możecie tam wyciąć trochę. Ale w każdym razie gratulacje! Wygląda na bardzo skomplikowane. Nie mogę się doczekać, aby dowiedzieć się, jak to działa!
dumny haskeller,
@proudhaskeller Bezużytecznie skomplikowane, zobacz moją edycję. Czy mam wyjaśnić podstawowy pomysł? Może być lepszy w inny sposób, ale na początku próbowałem dopasować jak najwięcej wzorców. Ach, przez rodziców masz na myśli nawiasy: golf!
Leif Willerts,
chillax, to twój pierwszy raz tutaj. Jeśli zostaniesz długo, będziesz rosnąć znacznie lepiej. Koniecznie
dumny haskeller
@proudhaskeller edit przybył ...
Leif Willerts,
4

ES6, 130 bajtów

(n,m)=>{for(a={},s=0,i=x=y=1;i<<1;i+=i,z=y,y=x,x+=z)s+=((n&i)+(m&i))/i*(a[i]=x);for(r=0;i;i>>>=1)s>=a[i]?(s-=a[i],r|=i):0;return r}

Początkowo próbowałem obliczyć sumę w miejscu (efektywnie zgodnie z implementacją CJam), ale wciąż brakowało mi tymczasowości, więc po prostu przekonwertowałem liczby do iz powrotem z prawdziwych liczb całkowitych.

(Tak, prawdopodobnie mogę zapisać bajt, używając eval.)

Neil
źródło
1

Rubinowy , 85 73 65 bajtów

->*a{r=(0..2*a.sum).select{|r|r^r*2==r*3};r[a.sum{|w|r.index w}]}

Wypróbuj online!

W jaki sposób?

Najpierw uzyskaj górną granicę zakodowanej sumy: (a + b) * 2 jest w porządku.

Teraz odfiltruj wszystkie liczby inne niż Zeckendorf z (0..limit).

Mamy tablicę przeglądową, stąd jest z górki.

GB
źródło
1

Python 3, 207 bajtów

def s(n):
 p=1
 while n>=2*p:
  p*=2
 return n if n<=p else s(n+p//2)if n>=3*p/2 else s(m)if (m:=s(n-p)+p)!= n else n
a=lambda n,m:(b:=n&m)>-1 and s(a(a(a(s((n|m)-b%4),b//4*2),b//4),b%4*2+b%4//2))if m else n

Wypróbuj online! (Sprawdź wszystkie przypadki testowe)

Wyjaśnienie

Ten program bezpośrednio manipuluje binarnymi tłumaczeniami reprezentacji Zeckendorf. Funkcja a(n,m)wykonuje główne obliczenia i s(n)jest funkcją pomocniczą, która pozbywa się sąsiednich liczb zawartych w reprezentacji Zeckendorfa.

Zacznijmy od funkcji s(n)(rozszerzonej dla przejrzystości):

def s(n): 
    p=1                  #This finds the highest digit of the binary form of n.
    while n>=2*p:
        p*=2
    if n<=p:             #If n is a power of two (i.e, our number is already a Fibonnaci number)...
        return n         #Then return it normally.  This also works for zero. (A)
    if n>=3*p/2:         #If n's first digit is followed by a 1 (i.e, it starts with 11X)
        return s(n+p//2) #Then replace that with 100X (B)
    m = s(n-p)+p         #Otherwise, apply s to the rest of the number (C)
    if m==n:             #If this is out final result, we're done! (D)
        return n
    return s(m)          #Otherwise, reapply it. (E)

Na przykład liczba 107 ( 1101011binarnie, reprezentująca 1 + 2 + 5 + 13 + 21 = 42), przechodzi następujący proces:

1+2+5+13+21 [1101011] -> 1+2+5+34 [10001011] (B)
1+2+5+34 [10001011] (C)
 1+2+5 [1011] (C)
  1+2 [11] -> 3 [100] (B)
 ->3+5 [1100] (A/E)
 (E):  3+5 [1100] -> 8 [10000] (B)
->8+34 [10010000] (A/E)
(E): 8+34 [10010000] (C)
->8+34 [10010000] (A/E)

Wypróbuj online! (s ze szczegółowymi danymi wyjściowymi)

Oto rozszerzona wersja a(n,m):

def a(n,m):
    if m==0:
        return n
    b=n&m
    t=s((n|m)-b%4)              #(A)
    t=a(t,b//4*2)               #(B)
    t=a(t,b//4)                 #(C)
    return s(a(t,b%4*2+b%4//2)) #(D)

Ta funkcja przekształca dwie reprezentacje Zeckendorfa w cztery liczby binarne, które można łatwiej łączyć. Linia (A) to bitowa OR dwóch binarnych reprezentacji Zeckendorfa - odpowiadają one jednej kopii każdej liczby Fibonacciego w każdej grupie. (B) i (C) to bitowe ORAZ z dwóch liczb odpowiednio przesuniętych w prawo 1 i 2 razy. Wiemy, że gdy odpowiednie liczby Fibonacciego dla (B) i (C) zostaną dodane razem, będą one równoważne bitowemu AND naszej ni mponieważ F (n) = F (n-1) + F (n-2) .

Powiedzmy na przykład, że mamy liczby binarne n = 101001 (odpowiadające 1 + 5 + 13) im = 110110 (2 + 3 + 8 + 13). Wtedy będziemy mieli (A) = 111111 (1 + 2 + 3 + 5 + 8 + 13), który jest konwertowany do 1010100 (3 + 8 + 21) przez naszą funkcję s, (B) = 10000 (8) i ( C) = 1000 (5). Możemy sprawdzić, czy (1 + 5 + 13) + (2 + 3 + 8 + 13) = (3 + 8 + 21) + (8) + (5) = 45. Ten proces powtarza się z ((3 + 8 + 21) + (8)) + (5) = ((3 + 8 + 21) + (5) + (3)) + (5) itp.

Jedyną trudnością związaną z tym systemem jest to, że nie działa on dla liczb Fibonacciego 1 i 2, ponieważ nie są one zgodne z właściwością F(n)=F(n-1)+F(n-2)(są to dwie najniższe liczby)! W związku z tym, gdy 1 lub 2 są zawarte w obu ni msą usuwane z A, B i C, po czym ich suma umieszczone D pod właściwości, 1 + 1 = 2 i 2 + 2 = 1 + 3. Na przykład, jeśli dodamy 1 + 3 (101) + 1 + 3 + 5 (1101), otrzymamy:

(A): 3 + 5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 2 (10)

Zauważ, że 3 i 5 zostały umieszczone w A, duplikat 3 został podzielony na 2 + 1 w B i C, a duplikaty 1 zostały usunięte z A, B i C, dodane razem i umieszczone w D. Podobnie, jeśli dodajmy 2 + 3 (110) + 2 + 3 + 5 (1110), otrzymujemy:

(A): 3 + 5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 1 + 3 (101)

Wypróbuj online! (ze szczegółowym wyjściem)

Madison Silver
źródło
0

Wolfram Language (Mathematica) , 218 bajtów

Fold[#+##&,Total@PadLeft@IntegerDigits[#,2]//.{{p=n_/;n>1,r=y___}:>{0,n,y},{q=x___,i_,p,j_,k_,r}:>{x,i+1,n-2,j,k+1,y},{q,i_,p,j_}:>{x,i+1,n-2,j+1},{q,i_,p}:>{x,i+1,n-2},{1,1,r}:>{1,0,0,y},{q,i_,1,1,r}:>{x,i+1,0,0,y}}]&

Wypróbuj online!

Po prostu dopasowanie wzoru.

Nie golfowany:

FromDigits[Total@PadLeft@IntegerDigits[#, 2] //.
   {{n_ /; n > 1, y___} :> {0, n, y},
    {x___, i_, n_ /; n > 1, j_, k_, y___} :> {x, i + 1, n - 2, j, k + 1, y},
    {x___, i_, n_ /; n > 1, j_} :> {x, i + 1, n - 2, j + 1},
    {x___, i_, n_ /; n > 1} :> {x, i + 1, n - 2},
    {1, 1, y___} :> {1, 0, 0, y},
    {x___, i_, 1, 1, y___} :> {x, i + 1, 0, 0, y}}, 2] &
alephalpha
źródło