Inspirowany przez A014486 .

Wyzwanie

Biorąc pod uwagę liczbę całkowitą w bazie 10, konstruuj reprezentację dla binarnego lasu odpowiadającą wartości wejściowej. Reprezentacje obejmują między innymi zagnieżdżone tablice i łańcuchy.

W jaki sposób?

Konwertuj dane wejściowe na binarne. 1s reprezentują gałęzie, a 0s przedstawiają liście.

Aby to łatwiej zrozumieć, 834użyjmy na przykład (1101000010 w wersji binarnej).

Zaczynamy od pierwszej cyfry. Pierwsza cyfra to 1, więc rysujemy gałęzie:

\ /
 1

lub jako tablica, {{1}}

Następna cyfra to 1, więc rysujemy więcej gałęzi (przechodzimy od lewej do prawej):

\ /
 1
  \ /
    1

lub jako tablica, {{1, {1}}}

Następna cyfra to 0, więc umieszczamy liść:

0
 \ /
  1
   \ /
     1

lub jako tablica, {{1, {1, 0}}}

Następna cyfra to 1, więc umieszczamy gałąź:

     \ /
0 1
 \ /
   1
      \ /
         1

lub jako tablica, {{1, {1, 0, {1}}}}

Powtarzając ten proces, otrzymujemy następujące drzewo po 8 cyfrze:

    0 0
     \ /
0 1
 \ /
   1 0
      \ /
         1

lub jako tablica, {{1, {1, 0, {1, 0, 0}}, 0}}

Dla pozostałych cyfr rysujemy więcej drzew:

Dziewiąta cyfra to 0, więc umieszczamy liść (aww, to młody pęd!)

    0 0
     \ /
0 1
 \ /
   1 0
      \ /
         1 0

lub jako tablica, {{1, {1, 0, {1, 0, 0}}, 0}, 0}

Kiedy używamy wszystkich cyfr, otrzymujemy:

    0 0
     \ /
0 1
 \ /
   1 0 0
      \ / \ /
         1 0 1

lub jako tablica, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0}}

To wygląda dziwnie, więc wpisujemy zero, aby ukończyć drzewo:

    0 0
     \ /
0 1
 \ /
   1 0 0 0
      \ / \ /
         1 0 1

lub jako tablica, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0, 0}}

Zauważ, że spłaszczanie tablicy daje pierwotną liczbę w postaci binarnej, ale z dopełnieniem zera.

Kryteria

• Dane wyjściowe muszą wyraźnie pokazywać rozdzielenie drzew i gałęzi (jeśli nie jest to zagnieżdżona tablica, wyjaśnij format wyjściowy).
• Wyodrębnienie wszystkich cyfr z danych wyjściowych musi być identyczne z binarną reprezentacją danych wejściowych (z wypełnionymi zerami z powyższego procesu).

Przypadki testowe

Dane wyjściowe mogą się różnić, o ile spełniają kryteria.

0 -> {0}
1 -> {{1, 0, 0}}
44 -> {{1, 0, {1, {1, 0, 0}, 0}}}
63 -> {{1, {1, {1, {1, {1, {1, 0, 0}, 0}, 0}, 0}, 0}, 0}}
404 -> {{1, {1, 0, 0}, {1, 0, {1, 0, 0}}}}
1337 -> {{1, 0, {1, 0, 0}}, {1, {1, {1, 0, 0}, {1, 0, 0}}, 0}}

Punktacja

To jest golf golfowy , więc wygrywa najmniej bajtów!

JavaScript (ES6), 96 89 80 79 74 73 bajty

f=($,_=~Math.log2($))=>0>_?[(g=f=>$&1<<~_++&&[1,g(),g()])(),...f($,_)]:[]

<input type="number" value="1337" oninput="document.querySelector('#x').innerHTML=JSON.stringify(f(+this.value))"/><br/><pre id="x"></pre>

Definiuje funkcję, fktóra zwraca tablicę zagnieżdżoną. Kod HTML służy tylko do testowania.

Befunge, 138 117 104 bajtów

p&1v
%2:_v#:/2p9p00+1:g00
3\9g<>$\:!v!:<
9g!v ^,"}"_1-\1-:
"0"_2\"1{",,:|:,
`#@_\:#v_"}",>$\:8
,"0":-1<^

Wypróbuj online!

Wyjaśnienie

Linia 1 odczytuje liczbę ze standardowego wejścia, a linia 2 konwertuje tę liczbę na sekwencję binarną, którą przechowuje na polu gry w linii 10. Linie 3 do 5 następnie iterują te cyfry binarne, generując odpowiednią reprezentację drzewa podczas przetwarzania każdej cyfry. Stos Befunge służy do śledzenia głębokości w drzewie i ilości miejsca na liściach na każdym poziomie, dzięki czemu wiemy, kiedy utworzyć nową gałąź. Linie 6 i 7 obsługują końcowe 0wypełnienie, aby wypełnić puste liście.

Aby zagrać w golfa tak bardzo, jak to możliwe, usunąłem przecinki z wyjścia, a także zewnętrzne szelki. To wciąż nie przebiło rozwiązania Mathematica, ale fajnie było próbować.

Jeśli chcesz zobaczyć, jak to wyglądało z oryginalnym gadatliwym formatu wyjściowego, uratowałem wcześniejszą wersję kodu tutaj (131 bajtów).

Mathematica, 167 161 bajtów

b=Append;a=If[#&@@#>0,a[Rest@#~b~0,a[#,#3[#,{1,#4,#2},##5]&,#3,#2,##4]&,#2,##3],
#2[Rest@#~b~0,0,##3]]&;a[#~IntegerDigits~2,If[c=#3~b~#2;Tr@#>0,a[#,#0,c],c]&,
{}]&

Funkcja anonimowa. Pobiera liczbę jako dane wejściowe i zwraca dowolnie zagnieżdżoną listę liczb jako dane wyjściowe. Dodano podział linii dla zachowania przejrzystości. Używa mechanizmu polegającego na kontynuacji, ale jestem zbyt zmęczony, aby o tym myśleć.

Mathematica, 115 109 108 104 98 bajtów

(i=#~IntegerDigits~2;f:=Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&

Generuje komunikaty o błędach, które można bezpiecznie zignorować. Tworzy las binarny. Różni się nieco od przykładowego wyniku, ponieważ 1jest to Headnie pierwszy element listy. (np. 1[0, 0]zamiast {1, 0, 0})

Wersja bezbłędna (104 bajty)

(i=#~IntegerDigits~2;f:=Switch[If[i=={},i={0}];(i={##2};#)&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&

Wyjaśnienie

i=#~IntegerDigits~2;

Konwertuj dane wejściowe na listę base-2. Przechowuj w i.

f:=

SetDelay fnastępujące (oceniane przy każdym fwywołaniu):

Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f]

Switch komunikat.

Po pierwsze, jeśli ijest puste, wyprowadza 0. Jeśli nie, wypisz pierwszy element ii upuść go z listy. Użyj wyniku jako zmiennej sterującej.

Jeśli zmienną sterującą jest 0, wyjście 0. Jeśli tak jest 1, wyjście 1[f, f](rekurencyjne).

NestWhileList[f&,f,i!={}&]

Chociaż inie jest pusty, nie przestawaj dzwonić f. Wyprowadź wynik zapakowany w List.

Przykład

(i=#~IntegerDigits~2;f:=Switch[If[i=={},0,i={##2};#]&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&])&[1337]

{1[0, 1[0, 0]], 1[1[1[0, 0], 1[0, 0]], 0]}

Alternatywne rozwiązanie (120 bajtów)

Identyczne z moim 104-bajtowym rozwiązaniem, ale konwertuje dane wyjściowe do formatu podanego w pytaniu.

(i=#~IntegerDigits~2;f:=Switch[If[i=={},i={0}];(i={##2};#)&@@i,0,0,1,f~1~f];NestWhileList[f&,f,i!={}&]//.1[a__]:>{1,a})&

Python 2, 133 118 117 bajtów

Częściowo rekurencyjne, częściowo iteracyjne. Próbowałem użyć liczby całkowitej, ale drzewo zaczyna się od najbardziej znaczących bitów, więc nie sądzę, żeby było warto.

def t():global b;a=b[:1];b=b[1:];return a and'0'<a and[1,t(),t()]or 0
b=bin(input())[2:]
L=[]
while b:L+=t(),
print L

Wypróbuj online

Java 8, 367 bajtów

Gra w golfa:

class f{static String r="";static int p=0;static void g(char[]s,int k){if(p>=s.length||s[p]=='0'){r+="0";p++;return;}else{r+="{1";p++;g(s,k+1);g(s,k+1);r+="}";}if(k==0&&p<s.length)g(s,0);}public static void main(String[]a){java.util.Scanner q=new java.util.Scanner(System.in);r+="{";g(Integer.toBinaryString(q.nextInt()).toCharArray(),0);r+="}";System.out.print(r);}}

Nie golfowany:

class f{
    static String r="";
    static int p=0;
    static void g(char[]s,int k){
        // if there's empty space in last tree or current character is a 0
        if(p>=s.length || s[p]=='0'){
            r+="0";
            p++;
            return;
        }
        // if current character is a 1
        else{
            r+="{1";
            p++;
            // left branch
            g(s,k+1);
            // right branch
            g(s,k+1);
            r+="}";
        }
        // if they're still trees that can be added
        if(k==0 && p<s.length)g(s,0);
    }
    public static void main(String[]a){
        java.util.Scanner q=new java.util.Scanner(System.in);
        r+="{";
        g(Integer.toBinaryString(q.nextInt()).toCharArray(),0);
        r+="}";
        System.out.print(r);
    }
}

DUP , 84 bajtów (82 znaków)

0[`48-$1_>][\10*+]#%1b:[$1>][2/b;1+b:]#[['{,1.b;1-b:FF'},][0.b;1-b:]?]⇒F[b;0>][F]#

Z powodów golfowych pozbyłem się zewnętrznych nawiasów klamrowych i przecinków, ponieważ nie są one konieczne do odtworzenia drzew.

Przykładowe wyniki:

0      → 0
1      → {100}
44     → {10{1{100}0}}
63     → {1{1{1{1{1{100}0}0}0}0}0}
404    → {1{100}{10{100}}}
1023   → {1{1{1{1{1{1{1{1{1{100}0}0}0}0}0}0}0}0}0}
1024   → {100}00000000
1025   → {100}0000000{100}
1026   → {100}000000{100}
1027   → {100}000000{1{100}0}
1028   → {100}00000{100}
1337   → {10{100}}{1{1{100}{100}}0}
4274937288 → {1{1{1{1{1{1{10{1{100}{1{1{100}{10{1{1{10{1{1{100}{100}}0}}0}0}}}0}}}0}0}0}0}0}0}
4294967297 → {100}00000000000000000000000000000{100}

Wyjaśnienie:

0[`48-$1_>][\10*+]#           While loop to read in the characters and convert them into a
                              base-10 integer.
0                             Push 0 (temporary value)
 [`48-$0>]       #            While input character-48 (digit)>-1
          [     ]
           \                      Swap top values
            10                    Push 10
              *                   Multiply (temporary value by 10)
               +                  Add to input value
%                                 Pop stack (EOL)
1b:                           Variable b=1 (bit count)
[$1>][2/b;1+b:]#              While loop to convert the number to base-2 digits on the
                              data stack, MSB on top. Each iteration increments bit count b.
[$1>]          #              While (DUP>1)
     [        ]#
      2                           Push 2
       /                          MOD/DIV (pushes both mod and div on the stack)
        b;1+b:                    Fetch b, increment, store b


[['{,1.b;1-b:FF'},][0.b;1-b:]?]⇒F     
[                             ]⇒F     Define operator F:
                                      pop top stack value
 [                ]          ?        if value != 0:
  '{,1.                                   print '{1'
       b;1-b:                             fetch b, decrement b, store b
             F                            execute operator F
              F                           execute operator F again
               '},                        print '}'
                   [        ]?        if value == 0:
                    0.                    print '0'
                      b;1-b:              fetch b, decrement b, store b
[b;0>][F]#
[b;0>]   #                            While (fetch b, b>0==true)
      [F]#                                execute operator F

Wypróbuj go za pomocą internetowego interpretera DUP JavaScript na quirkster.com lub sklonuj moje repozytorium GitHub mojego interpretera DUP napisane w Julii.