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. 1
s reprezentują gałęzie, a 0
s przedstawiają liście.
Aby to łatwiej zrozumieć, 834
uż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!
źródło
Odpowiedzi:
JavaScript (ES6),
968980797473 bajtyDefiniuje funkcję,
f
która zwraca tablicę zagnieżdżoną. Kod HTML służy tylko do testowania.źródło
$&
robi bez.replace
?” : PBefunge,
138117104 bajtówWypró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
0
wypeł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).
źródło
Mathematica,
167161 bajtówFunkcja 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ć.
źródło
#[[1]]
do#&@@#
powinien zapisać bajt.!#~FreeQ~1
zamiast#~MemberQ~1
zapisuje również bajt.Mathematica,
11510910810498 bajtówGeneruje komunikaty o błędach, które można bezpiecznie zignorować. Tworzy las binarny. Różni się nieco od przykładowego wyniku, ponieważ
1
jest toHead
nie pierwszy element listy. (np.1[0, 0]
zamiast{1, 0, 0}
)Wersja bezbłędna (104 bajty)
Wyjaśnienie
Konwertuj dane wejściowe na listę base-2. Przechowuj w
i
.SetDelay
f
następujące (oceniane przy każdymf
wywołaniu):Switch
komunikat.Po pierwsze, jeśli
i
jest puste, wyprowadza0
. Jeśli nie, wypisz pierwszy elementi
i upuść go z listy. Użyj wyniku jako zmiennej sterującej.Jeśli zmienną sterującą jest
0
, wyjście0
. Jeśli tak jest1
, wyjście1[f, f]
(rekurencyjne).Chociaż
i
nie jest pusty, nie przestawaj dzwonićf
. Wyprowadź wynik zapakowany wList
.Przykład
Alternatywne rozwiązanie (120 bajtów)
Identyczne z moim 104-bajtowym rozwiązaniem, ale konwertuje dane wyjściowe do formatu podanego w pytaniu.
źródło
Python 2,
133118117 bajtówCzęś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.
Wypróbuj online
źródło
Java 8, 367 bajtów
Gra w golfa:
Nie golfowany:
źródło
DUP , 84 bajtów (82 znaków)
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:
Wyjaśnienie:
Wypróbuj go za pomocą internetowego interpretera DUP JavaScript na quirkster.com lub sklonuj moje repozytorium GitHub mojego interpretera DUP napisane w Julii.
źródło