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 31 .
- 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.
code-golf
array-manipulation
balanced-string
ETHprodukcje
źródło
źródło
Odpowiedzi:
Python 2.7,
172 149 124118 bajtówWyjaśnienie:
Zdefiniuj bijection przez
[
↔1
i]
↔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 31 .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ę[[][]]
i110100
(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.
źródło
Python,
153128 bajtówMapujemy 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 32 .
[
.][
.][
.]
.Na koniec zamykamy wszystkie otwarte nawiasy.
źródło
Łyżka , 63 bajty (501 bitów)
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:
źródło
Galaretka , 28 bajtów
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!
źródło
Perl,
8079 bajtówPonownie 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
:Rozwiązanie Linusa to 64 bajty w perlu:
Rozwiązanie Dennisa to 59 bajtów na perl (coraz wolniejsze dla dużych liczb):
źródło
-p
liczony jest 1 dodatkowy bajtPython 3,
120114 bajtówPrzetestuj 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 ,
~n
daje 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.
Przelicz k na reprezentację ciągu binarnego, zaczynając od 0b .
Na przykład 44 ↦ „0b101100” .
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 [], [[],],„ .
Usuń pierwsze trzy znaki (odpowiadają „0b” ) i końcowy znak (miejmy nadzieję przecinek).
Na przykład, „], b [], [[],],„ ↦ ”[], [[],]” .
Spróbuj ocenić wygenerowany kod. Jeśli spowoduje to błąd, k nie jest mapowane na żadnej liście.
Na przykład „[], [[],]” ↦ ([], [[]]) .
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.
źródło
Haskell, 71 bajtów
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.
Funkcja
p
na wejściun
daje listę wszystkich zagnieżdżonych tablic wielkościn
(otwarte nawiasy kwadratowe). Odbywa się to rekurencyjnie. Każda taka tablica składa się z części głowyh
(pierwszego elementu) wielkościk
i części ogonat
(innych elementów) wielkościn-k
, przy czym oba rozmiary są niezerowe. Lub jest to pusta tablica dla rozmiarun==1
.Wyrażenie
p=<<[1..]
następnie spłaszczap(1), p(2), ...
się w jedną nieskończoną listę wszystkich tablic posortowanych według wielkościi 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 funkcja
p
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.źródło
Haskell,
8782 bajtówWysyła elementy tablicy. Przykład użycia:
(([0..]>>= \y->y#y)!!) 3
->"[][]"
.Funkcja
#
buduje wszystkie zagnieżdżone tablice jako ciągi znakówn
otwierających im
zamykających nawiasy, śledząc, ile z nich zostało. Zawsze zaczyna się odn == m
. Główna funkcja wywołujey # y
każdyy <- [0,1,...]
i wybiera element na podstawie indeksu podanego przez dane wejściowe.źródło
MATL , 31 bajtów
Wypróbuj online! Lub sprawdź kilka pierwszych przypadków testowych (zajmuje to kilka sekund).
Utworzone mapowanie to:
Wyjaśnienie
Kod ciągle testuje rosnące liczby binarne, z cyframi
0
zamienionymi na-1
; to znaczy za pomocą1
i-1
jako cyfry. Cyfra1
będzie reprezentować'['
i-1
bę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
i-1
)1
cyfr 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ę
1
na[
i-1
na]
, a następnie jest wyświetlany.Kod:
źródło