tło
Nieoznakowane drzewo może wyglądać następująco:
o
/ | \
o o o
| / \
o o o
Aby linearyzować to drzewo, najpierw oznaczamy każdy węzeł o
jego liczbą węzłów potomnych:
3
/ | \
1 0 2
| / \
0 0 0
a następnie zapisz liczby na liście w pierwszej kolejności, oznaczając wiersz po wierszu i od lewej do prawej:
[3, 1, 0, 2, 0, 0, 0]
Jest to unikalna i jednoznaczna reprezentacja drzewa powyżej, co oznacza, że żadne dwa różne czyste drzewa nie będą miały takich samych linearyzacji i że możemy odtworzyć oryginalne drzewo z listy.
Chociaż każde drzewo odpowiada pewnej liście liczb całkowitych, nie każda lista liczb całkowitych reprezentuje prawidłowe drzewo zlinearyzowane: Na przykład [2, 0, 0, 0]
nie reprezentuje prawidłowego drzewa, jeśli spróbujemy go zlinearyzować, otrzymamy to drzewo
[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
/ \ / \ / \
0 0 0
ale nadal mam 0
na liście miejsce i nie ma gdzie go umieścić. Podobnie, [2, 0]
nie jest to również prawidłowa linearyzacja drzewa, ponieważ zdlinizowane drzewo ma puste miejsce potomne:
2
/ \
0
Zadanie
Biorąc pod uwagę listę liczb całkowitych, zdecyduj, czy jest to poprawna linearyzacja drzewa, używając jak najmniej bajtów. Możesz napisać pełny program lub funkcję.
Dane wejściowe: niepusta lista liczb całkowitych nieujemnych.
Wynik : prawdziwa wartość, jeśli lista jest linearyzacją drzewa, w przeciwnym razie wartość fałszowania.
Przypadki testowe
Prawda[0]
[2, 0, 0]
[1, 1, 1, 1, 1, 0]
[3, 1, 0, 2, 0, 0, 0]
[2, 0, 2, 2, 0, 0, 2, 0, 0]
[3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0]
[1, 5, 3, 0, 2, 1, 4, 0, 1, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0]
Falsy
[0, 1]
[2, 0]
[2, 0, 0, 0]
[1, 0, 1]
[3, 2, 1, 0]
[2, 0, 0, 2, 0, 0]
[4, 1, 0, 3, 0, 0, 0, 0]
[4, 2, 0, 3, 1, 0, 0, 0, 0, 0]
{X0@{+\(_{\}&}/|!}
Myślę?@
.Labirynt , 17 bajtów
Wypróbuj online!
Prawda jest
-1
prawdziwa, a fałsz jest pusty. Określenie prawdy i fałszu w Labiryncie jest nieco trudne, ponieważ gałęzie Labiryntu są zasadniczo trójskładnikowe. Jednak jedynym sposobem, aby zbudować warunek z niezawodnie dwoma gałęziami, możesz to zrobić tylko:W takim przypadku rozważyłbym przemieszczenie się na wprost falsy (ponieważ kierunek ruchu pozostaje nienaruszony) i zwrócenie się w prawdę. Odpowiadają one odpowiednio zeru i niezerowi. Powodem, dla którego używam pustego wyjścia do reprezentowania zera, jest to, że jeśli chcesz przesłać dane wyjściowe z powrotem do innego programu Labiryntu, operator wejściowy
?
faktycznie wypchnie zero, jeśli wejście jest puste, więc uważam, że pusty ciąg jest prawidłowy reprezentacja zera.Wyjaśnienie
Algorytm jest nadal taki sam, jak w moich odpowiedziach Mathematica i Retina, ale z powodu przepływu sterowania Labiryntem tym razem działa nieco inaczej:
-11
tak, aby chcemy, aby licznik był ujemny na całej liście i osiągnął zero na ostatnim wejściu. To faktycznie upraszcza tutaj kontrolę.Zamiast budować pełną listę i sprawdzać, czy zawiera ona niepoprawną wartość, istnieją trzy możliwe warunki zakończenia:
Jeśli chodzi o rzeczywisty kod, zaczynamy w lewym górnym rogu.
(
Włącza niejawny zero na górze stosu w-1
, który będzie uruchomiony całkowite. Następnie wchodzimy w bardzo wąską główną pętlę programu+?-)"_,;+
:To pozostawia tylko przypadki, w których w pewnym momencie zmniejszyliśmy sumę bieżącą do zera. IP przesuwa się w prawym dolnym rogu
,
i odczytuje inną postać, aby sprawdzić, czy osiągnęliśmy EOF. Jeśli nie, wartość będzie dodatnia, a adres IP skręci na zachód w kierunku@
i program zakończy się. Gdybyśmy dotarli do EOF, IP skręca na wschód i drukuje za-1
pomocą!
. IP przebije się następnie w kierunku dolnej lewej części@
nieco dziwną ścieżką do zakończenia programu.źródło
Python, 82 bajty
Potrzebujesz więcej przypadków testowych.
źródło
list
jeśli jest to przynajmniej Python 2, a przestawiając i odwracając drugi warunek, możesz uzyskać go do 70 bajtów:lambda l:all(l[x]<len(l)-x for x in range(len(l)))and len(l)==sum(l)+1
all
sięx<len(l)-y for y,x in enumerate(l)
zaoszczędzić kolejne 2 bajty, aby ją do 68.Pyth, 13 bajtów
Zaczynamy od obliczenia bieżącej wypełnienia drzewa we wszystkich punktach reprezentacji wejściowej. Ta część pomysłu została w dużej mierze zapożyczona od Martina Endera, więc dzięki niemu.
sM._tMQ
Po uzyskaniu tej listy sprawdzamy, czy pierwszy indeks zawierający
-1
(x..._1
) jest długością wejściową minus jeden (q...tl(Q)
).Nie wierzysz, że to działa? Spróbuj sam!
źródło