Wyzwanie jest proste: napisz program lub funkcję, która, gdy otrzyma skończoną nieujemną liczbę całkowitą, wyprowadza zagnieżdżoną tablicę.

Zasady

• Twój kod musi wygenerować unikalną poprawną tablicę zagnieżdżoną dla każdej liczby całkowitej 0 ‌ ≤ n ‌ <2 ³¹ .
• Każdy możliwa tablica zagnieżdżona z maksymalnie 16 otwartymi nawiasami musi być wyprowadzana w tym zakresie. (Nie oznacza to, że kod nigdy nie może wygenerować zagnieżdżonej tablicy z więcej niż 16 otwartymi nawiasami).
• Twój kod może wyświetlać ciąg reprezentujący zagnieżdżoną tablicę zamiast rzeczywistej tablicy (z przecinkami lub bez).

Jedno możliwe mapowanie:

0 -> []
1 -> [[]]
2 -> [[[]]]
3 -> [[], []]
4 -> [[[[]]]]
5 -> [[[], []]]
6 -> [[[]], []]
7 -> [[], [[]]]
8 -> [[], [], []]
9 -> [[[[[]]]]]
etc.

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Python 2.7, 172 149 124 118 bajtów

x=input();y="";z=0
for b in bin(x)[2+(x<1):]:y+="[]"[b<"1"];z+=b>"0"or-1;z+=99*(z<0)
print"["+(y,"[]"*(x+16))[z>0]+"]"

Wyjaśnienie:

Zdefiniuj bijection przez [↔ 1i ]↔ 0. Każde ustawienie nawiasów można następnie zapisać jako liczbę binarną i odwrotnie, na przykład [][]↔ 1010(10) i [[][]]↔ 110100(52). Wszystkie prawidłowe ustawienia do 15 otwartych nawiasów (łącznie 30 nawiasów) są objęte liczbami zawierającymi do 30 bitów (ignorując zera wiodące), czyli dokładnie mniej niż 2 ³¹ .

Pierwsza pętla for daje odwrotność tego bijectionu, przekształcając liczbę w układ nawiasów, sprawdzając jednocześnie, czy układ jest poprawny.

Niepoprawne ustalenia są zastępowane w instrukcji print długimi sekwencjami nawiasów, aby uniknąć kolizji. Na przykład 11(3) ↔ [[nie jest poprawny, więc zamiast tego łączymy nawiasy 3 + 16. Dzięki temu wszystkie aranżacje są unikalne.

Wynikowy układ jest umieszczany w parze nawiasów, aby utworzyć zagnieżdżoną tablicę, dzięki czemu 1010(10) staje się [[][]]i 110100(52) staje się [[[][]]]. Dodatkowy otwarty nawias oznacza, że ​​wszystkie tablice zostały już pokryte 16 otwartymi nawiasami.

Poniższego programu można użyć do ustalenia liczby dla danej tablicy z maksymalnie 16 nawiasami.

s=raw_input();o="";
for c in s[1:-1]:
 if c=="[":o+="1"
 if c=="]":o+="0"
print int(o,2)

Python, 153 128 bajtów

s=l=0;r="";n=input()
for d in bin(n)[2:]*(n>0):c=d<"1";l=[l,s>1][c];r+="]"*c+(1-l*c)*"[";s+=1-c-l*c
print"["+r+"["*l+"]"*(s+l+1)

Mapujemy liczbę n na zagnieżdżoną listę, patrząc na jej binarne cyfry od lewej do prawej. Ten algorytm działa dla dowolnej liczby, nie tylko poniżej 2 ³² .

1. Jeśli bieżącą cyfrą binarną jest 1, wyjście [ .
2. W przeciwnym razie, jeśli sekwencja nawiasów, które do tej pory wyprowadzaliśmy, byłaby zrównoważona przez jeden nawias zamykający, wynik ][ .
3. W przeciwnym razie, jeśli jest to ostatnie 0 w liczbie binarnej, wyprowadza ][ .
4. W przeciwnym razie wyjście ].

Na koniec zamykamy wszystkie otwarte nawiasy.

Łyżka , 63 bajty (501 bitów)

000001001001001011001101001010011011111001010001000000101010
101101100110100101101001000101100010001000000100011000010000
000000000000001110111110010000001110110110010100100100100100
000110011010001000000110110000010000001010110011011011011001
000000011010010010010001000000111011011011101001001001000110
110110010100100101011001000100000011010001000000111011011001
010010010010010001101101101001000110110010110001101101101101
100100010001010010001010011011001000000011001101001001010010
000001100101001000111

To jest następujący program pieprzenia mózgu przekonwertowany na łyżkę:

-[+[+<]>>+]<+++.[->+>+<<]>>++>>,[>-[<->-----]+<+++[-<+<<.>>>>-<]>[-<<-[->+<]<<<[-]>>>>[-<+<<<+>>>>]<<.>>+<[>-]>[-<+<<.>>>>]<<>>]<,]<<<<[>.>.<<[-]]>>>+[-<.>]+

Czyta całkowitą liczbę binarną na standardowym wyjściu i wyświetla zagnieżdżoną listę na standardowym wejściu. Wymaga wprowadzenia 0 jako pustego łańcucha (bez cyfr) i interpretera pieprzenia mózgu z 8-bitowymi komórkami. Ten sam algorytm jak moja odpowiedź w języku Python.

Wersja do odczytu:

-[+[+<]>>+]<+++.           push open bracket and print it
[->+>+<<]                  dup
>>++                       increment to close bracket

>>,[                       read input loop
    >-[<->-----]+<+++          subtract 48 and set up if/else
    [-                         if c == 1
        <+                         increment s
        <<.>>>                     output open bracket
    >-<]>[-<                   else
        <-[->+<]                   decrement and move s
        <<<[-]                     zero l
        >>>>[-<+<<<+>>>>]          l = s and restore s
        <<.>                       output close bracket
        >+<[>-]>[-                 if s == 0
            <+                         undo s decrement
            <<.                        output open bracket
        >>>>]<<
    >>]<
,]

<<<<[                      if l
    >.>.                   output pair
<<[-]]
>>>+[-<.>]                 output close bracket s+1 times

Galaretka , 28 bajtów

ḃ2-*µSN;+\>-Ạ
1Ç#Ṫḃ2ṭ2;1ị⁾][

Ten iteruje wszystkich ciągów znaków [i ]że zaczynać się [i kończyć się ], sprawdza, czy uchwyty pasują do siebie, a drukuje n ^y mecz.

Wypróbuj online!

Perl, 80 79 bajtów

Ponownie używa orlp algorytmu , ale tym razem najpierw sprawdziłem, czy działa ...

Obejmuje +1 dla -p

Podaj numer wejścia na STDIN

nest.pl <<< 8

nest.pl:

#!/usr/bin/perl -p
($_=sprintf"%b",$_).=2x(s^.^$&or++$n-pos&&/.0/g?++$n%1:$`&&21^eg-$n);y;102;();

Rozwiązanie Linusa to 64 bajty w perlu:

#!/usr/bin/perl -p
$_=sprintf"%b",/.+/g;$_=10x($&&&$&+16)if!/^(1(?1)*0)+$/;y;10;()

Rozwiązanie Dennisa to 59 bajtów na perl (coraz wolniejsze dla dużych liczb):

#!/usr/bin/perl -p
1while$_-=(sprintf"%b",$n++)=~/^(1(?1)*0)+$/;$_=$&;y;10;()

Python 3, 120 114 bajtów

def f(n,k=0):
 while~n:
  k+=1
  try:r=eval(bin(k).translate({48:'],',49:'['})[3:-1])+[];n-=1
  except:0
 print(r)

Przetestuj na Ideone .

Jak to działa

Zdefiniowana funkcja f przyjmuje dane wejściowe n i inicjuje k na 0 . Będziemy zwiększać wartość k, dopóki n + 1 wartości k nie da prawidłowego wyniku. Za każdym razem, gdy znajdziemy taką wartość k , n zmniejsza się, gdy osiągnie -1 , ~ndaje 0 , a lista r która odpowiada ostatniej wartości k drukowana jest .

Częściowe mapowanie z dodatnich liczb całkowitych na listy zagnieżdżone (tj. K ↦ r ) musi być bijectywne, ale nie ma innych ograniczeń. Ten użyty w tej odpowiedzi działa w następujący sposób.

1. Przelicz k na reprezentację ciągu binarnego, zaczynając od 0b .

   Na przykład 44 ↦ „0b101100” .

2. Zamień wszystkie zera (punkt kodowy 48 ) w reprezentacji ciągu na ciąg „]” i wszystkie 1 zera (punkt kodowy 49 ) na [ .

   Na przykład, „0b101100” ↦ ”], b [], [[],],„ .

3. Usuń pierwsze trzy znaki (odpowiadają „0b” ) i końcowy znak (miejmy nadzieję przecinek).

   Na przykład, „], b [], [[],],„ ↦ ”[], [[],]” .

4. Spróbuj ocenić wygenerowany kod. Jeśli spowoduje to błąd, k nie jest mapowane na żadnej liście.

   Na przykład „[], [[],]” ↦ ([], [[]]) .

5. Połącz wynik (jeśli istnieje) z pustą listą. Jeśli spowoduje to błąd, k nie jest mapowane na żadnej liście.

   Na przykład błędy ([], [[]]) + [], ponieważ + nie może łączyć list i krotek.

Haskell, 71 bajtów

p 1=["[]"]
p n=['[':h++t|k<-[1..n-1],h<-p k,_:t<-p$n-k]
((p=<<[1..])!!)

Główna funkcja ostatniego wiersza indeksuje do listy wszystkich zagnieżdżonych tablic, posortowanych według wielkości (liczba otwartych nawiasów). Tak więc wszystkie tablice wielkości maksymalnie 16 są wymienione jako pierwsze.

Najpierw spójrzmy na kod, który jest ładniejszy i krótszy, ale narzędzie do sprawdzania typów Haskell odmawia przyjęcia.

p 1=[[]]
p n=[h:t|k<-[1..n-1],h<-p k,t<-p$n-k]
((p=<<[1..])!!)

Funkcja pna wejściu ndaje listę wszystkich zagnieżdżonych tablic wielkości n(otwarte nawiasy kwadratowe). Odbywa się to rekurencyjnie. Każda taka tablica składa się z części głowy h(pierwszego elementu) wielkości ki części ogona t(innych elementów) wielkości n-k, przy czym oba rozmiary są niezerowe. Lub jest to pusta tablica dla rozmiaru n==1.

Wyrażenie p=<<[1..]następnie spłaszcza p(1), p(2), ...się w jedną nieskończoną listę wszystkich tablic posortowanych według wielkości

[ [], [[]], [[],[]], [[[]]], [[],[],[]], [[],[[]]], [[[]],[]], [[[],[]]], ...

i główna funkcja indeksuje się do niego.

... Lub, gdyby Haskell nie narzekał na „skonstruowanie [nieskończonego typu]: t ~ [t]”. Haskell nie może reprezentować nieskończonej listy powyżej, której elementy są dowolnie zagnieżdżonymi tablicami. Wszystkie jego elementy muszą mieć ten sam typ, ale typ t nie może być taki sam jak lista t. W rzeczywistości funkcjap samej nie można przypisać spójnego typu bez pisania zależnego, którego brakuje Haskellowi.

Zamiast tego pracujemy nad ciągami nawiasów, symulując działanie wad przez działanie na znaki [i ]. To zajmuje dodatkowe 9 bajtów. Zagrożenia związane z golfem w języku bezpiecznym dla typu.

Haskell, 87 82 bajtów

0#0=[""]
n#m=['[':x|n>0,x<-(n-1)#m]++[']':x|n<m,x<-n#(m-1)]
(([0..]>>= \y->y#y)!!)

Wysyła elementy tablicy. Przykład użycia: (([0..]>>= \y->y#y)!!) 3-> "[][]".

Funkcja #buduje wszystkie zagnieżdżone tablice jako ciągi znaków notwierających i mzamykających nawiasy, śledząc, ile z nich zostało. Zawsze zaczyna się od n == m. Główna funkcja wywołuje y # ykażdy y <- [0,1,...]i wybiera element na podstawie indeksu podanego przez dane wejściowe.

MATL , 31 bajtów

O`@BEqXJYs0&)0>w~hA+tG>~]x92J-c

Wypróbuj online! Lub sprawdź kilka pierwszych przypadków testowych (zajmuje to kilka sekund).

Utworzone mapowanie to:

0 -> []
1 -> [[]]
2 -> [[][]]
3 -> [[[]]]
4 -> [[][][]]
5 -> [[][[]]]
6 -> [[[]][]]
7 -> [[[][]]]
...

Wyjaśnienie

Kod ciągle testuje rosnące liczby binarne, z cyframi 0zamienionymi na -1; to znaczy za pomocą 1i -1jako cyfry. Cyfra 1będzie reprezentować '['i -1będzie reprezentować ']'.

Program liczy do momentu uzyskania n +1 poprawnych liczb. Liczba jest ważna, jeśli spełnione są następujące dwa warunki:

1. Suma cyfr wynosi zero (tzn. Jest równa liczba 1i -1)
2. Skumulowana suma cyfr jest zawsze dodatnia (to znaczy, skumulowana liczba 1cyfr zawsze przekracza liczbę -1), z wyjątkiem końca (gdzie wynosi zero według warunku 1).

Raz n +1 poprawnych liczb ostatnia jest transliterowana przez zmianę 1na [i -1na] , a następnie jest wyświetlany.

Kod:

O          % Push 0: initial count of valid numbers
`          % Do...while
  @        %   Push iteretation index k, starting at 1
  B        %   Convert to binary. For example, k=6 gives [1 1 0 0]
  Eq       %   Multiply by 2, subtract 1: transforms [1 1 0 0] into [1 1 -1 -1]
  XJ       %   Copy that to clipboard J, without popping it
  Ys       %   Cumulative sum: gives [1 2 1 0]
  0&)      %   Split array into its final element and the rest. Gives 0, [1 2 1]
  0>       %   Yields 1 for positive entries (condition 2). So in this case it
           %   gives [1 1 1]
  w        %   Swap: moves second-top element in the stack (0 in this case) to top
  ~        %   Negate: yields 1 if input is 0 (condition 1). Gives 1 in this case
  h        %   Concatenate horizontally. Gives [1 1 1 1]
  A        %   All: gives 1 if all elements are 1. Gives 1 in this case, meaning
           %   that this k is valid
  +        %   Add the result (0 or 1) to the count of valid numbers
  t        %   Duplicate
  G        %   Push input n
  >~       %   Loop condition: false (exit loop) if count exceeds input n
]          % End loop. At this point the result is in clipboard J, in 1/-1 format
x          % Delete count
92         % Push 92. Will be used to convert 1, -1 to '[', ']' (ASCII 91, 93)
J          % Push result in 1/-1 format
-          % Subtract: converts 1 to 91, -1 to 93
c          % Convert to char. Implicitly display