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ł ojego 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 0na 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

[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]

[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]

Haskell, 44 bajty

f[n:k]=iterate f[k]!!n
f _=[]
g x=f[x]==[[]]

Definiuje funkcję, gktóra pobiera listę i zwraca wartość logiczną. Zobacz, jak przejdzie wszystkie testy .

Wyjaśnienie

Opiera się to na tym, że linearyzacje najpierw na głębokości i na szerokość najpierw wytwarzają te same tablice. Szczegółowe informacje można znaleźć w odpowiedziach Martina; w zasadzie oba dają ten sam warunek arytmetyczny na tablicy.

Funkcja fotrzymuje listę wejść zawiniętą w listę singletonów. Wyskakuje jeden numer nz listy, a następnie wywołuje się nrazy na pozostałej liście, aby przetworzyć elementy podrzędne węzła (najpierw głębokość). Wyskakiwanie pustej listy powoduje [], że używam jako stanu błędu. Ta funkcja gsprawdza, czy wynikiem końcowym jest [[]]unikalny, nie błędny stan bez nieprzetworzonych węzłów. Gdyby Haskell był słabo wpisany, mógłbym po prostu użyć 0czegoś takiego jako stanu błędu i nie musiałbym zawijać danych wejściowych na inną listę.

Mathematica, 38 bajtów

Last@#<0<=Min@Most@#&@Accumulate[#-1]&

Podstawową ideą jest to, że śledzimy liczbę węzłów do wypełnienia. Każdy element na liście zużywa jeden węzeł i dodaje tyle, ile ma dzieci. Więc każdy element izmienia całkowitą liczbę o i-1. Ta liczba jest pomniejszona o jeden, ponieważ powinna zaczynać się od 1(root), a nie 0.

Aby drzewo było ważne, a) nigdy nie możemy zejść poniżej 0listy, ponieważ nie musielibyśmy nigdzie umieszczać bieżącego węzła ib) -1musielibyśmy kończyć na końcu, w przeciwnym razie pozostaną nieużywane węzły.

Uzyskujemy tę działającą sumę pozostałych węzłów z Accumulate[#-1](która oblicza sumy prefiksów listy wejściowej minus jeden). A następnie sprawdzamy, czy ostatni element i tylko ostatni element zawiera -1:

Last@#<0<=Min@Most@#

Zauważ, że sprawdzenie, czy ostatni element jest ujemny, jest wystarczające, ponieważ nigdy nie możemy zmniejszyć o więcej niż 1, więc jeśli ostatnie wartości -2byłyby lub niższe, nie byłoby możliwe, aby pozostałe były nieujemne.

Siatkówka , 29 bajtów

\d+
$*
^(?<-1>(1)*,)*$(?(1)!)

Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii).

Wyjaśnienie

Podstawowa idea jest taka sama jak w mojej odpowiedzi Mathematica : śledzimy bieżącą sumę pozostałych węzłów, upewniając się, że nigdy nie spadnie poniżej zera, ale kończy się na zero. Jednak sposób, w jaki jest to realizowane za pomocą wyrażenia regularnego, jest zupełnie inny.

\d+
$*

To po prostu konwertuje dane wejściowe na jednoargumentowe, zmieniając każdą liczbę całkowitą nw n1s.

^(?<-1>(1)*,)*$(?(1)!)

To tam dzieje się prawdziwa magia. Jest to dość krótki regex, który pasuje tylko do prawidłowych drzew, ale jego mechanika jest dość subtelna.

Korzystam z grup równoważących, aby śledzić liczbę węzłów, które są sposobem na pracę ze stosami wewnątrz wyrażenia regularnego.

Po pierwsze, oczywiście taki stos nigdy nie może mieć ujemnej głębokości, więc nie możemy tak naprawdę kończyć się przedstawieniem -1na końcu, jak to ma miejsce w rozwiązaniu Mathematica. Możemy jednak zauważyć, że końcowy element danych wejściowych musi wynosić zero na prawidłowym stosie (w przeciwnym razie nie byłoby to możliwe -1). Okazuje się, że to rzeczywiście oszczędza bajtów aby sprawdzić zarówno , że skończy się na zero i zero pozostałych węzłów.

Oto podział wyrażenia regularnego:

^        e# Anchor the match to the beginning of the string.
(?<-1>   e# Each repetition of this group will match one number. 
         e# We can ignore the <-1> for now.
  (1)*   e#   Match each unary digit of the current number, pushing
         e#   a capture onto stack 1. This increments our total of
         e#   remaining nodes by 1 for each child.
  ,      e#   Match a comma. Note that this requires that there is at
         e#   least one more number in the list.
)*       e# At the end of the repetition the <-1> pops one capture from
         e# the stack. This is the node that the current number itself
         e# takes up.
$        e# Match the end of the string. This requires the input to end
         e# in a zero, because the last thing we matched was a comma.
(?(1)!)  e# Make sure that stack 1 is empty, so that we don't have any
         e# unused nodes.

CJam (20 bajtów)

{X0@{+\(_0>{\}*}/|!}

Zestaw testów online . Jest to anonimowy blok, który bierze tablicę na stos i pozostawia 0 lub 1 na stosie.

Sekcja

W pseudokodzie jest to:

p = 1
q = 0
foreach (i in input):
  q += i
  if (--p <= 0):      # in practice, if (--p == 0):
      p, q = q, p
return (p | q) == 0   # i.e. p == 0 && q == 0

qgromadzi sumę etykiet węzłów na bieżącym poziomie w drzewie; podlicza pozostałe węzły na bieżącym poziomie.

Labirynt , 17 bajtów

(
+?
;-)
,_"
@@,!

Wypróbuj online!

Prawda jest -1prawdziwa, 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:

>"F
 T

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:

• Nie współpracujemy tutaj z całkowitym licznikiem off-by-one. Zamiast tego a) pracujemy z licznikiem ujemnym ib) inicjalizujemy go -11tak, 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:

  1. Trafiliśmy w EOF, zanim osiągnęliśmy całkowitą liczbę zero. W takim przypadku pozostały nieużywane węzły i nic nie drukujemy.
  2. Osiągamy zero i jesteśmy na EOF. W tym przypadku mamy prawidłowe drzewo.
  3. Osiągamy zero i nie jesteśmy jeszcze w EOF. W tym przypadku zabrakło węzłów, zanim pokryliśmy wszystkie elementy, i nic nie drukujemy.

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 +?-)"_,;+:

+   Add the top two values. This does nothing on the first iteration,
    but gets rid of a helper-zero on subsequent iterations.
?   Read and push integer.
-   Subtract it from running total.
)   Increment.
"   No-op. There is a branch at this point. If the running total is zero,
    we move straight ahead onto the , (see below). Otherwise, the loop continues.
_   Push a zero. This is necessary to prevent the IP from turning south.
,   Read a character. This will either be the next separator (some positive
    number) or EOF (-1). If it's EOF, the IP turns south and the program
    terminates. Otherwise, the loop continues.
;   Discard the separator.

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 -1pomocą !. IP przebije się następnie w kierunku dolnej lewej części @nieco dziwną ścieżką do zakończenia programu.

Python, 82 bajty

lambda l:len(l)==sum(l)+1 and not any(list(l[x]>=len(l)-x for x in range(len(l))))

Potrzebujesz więcej przypadków testowych.

Pyth, 13 bajtów

qxsM._tMQ_1tl

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!