Perl, 65 59 55 54 bajtów
Obejmuje +2 za -ap
Uruchom z rozmiarem drzewa na STDIN:
for i in `seq 24`; do echo -n "$i: "; vines.pl <<< $i; echo; done
vines.pl:
#!/usr/bin/perl -ap
$_=map{${"-@F"%$_}|=$_=$$_|$"x$p++.1;/.\b/g}1-$_..-1
Wyjaśnienie
Jeśli przepiszesz drzewo
3
|
2 4
\ /
1
|
0
do jednego, w którym każdy węzeł zawiera zbiór wszystkich swoich przodków i siebie samego:
{3}
|
{2,3} {4}
\ /
\ /
{1,2,3,4}
|
{0,1,2,3,4}
Następnie możemy opisać np. Wszystkie węzły ścieżki od 4 do 3 jako:
- Wszystkie węzły, które zawierają 3, ale nie 4 (przejście z 3)
- Wszystkie węzły, które zawierają 4, ale nie 3 (przejście z 4)
- Najwyższy węzeł, który zawiera zarówno 3, jak i 4 (złączenie)
Liczba krawędzi jest o jeden mniejsza niż liczba węzłów, więc możemy użyć tego do zignorowania punktu połączenia, więc liczba krawędzi na ścieżce od 4 do 3 wynosi 3, ponieważ:
- Liczba węzłów zawierających 3, ale nie 4: 2 węzłów
- Liczba węzłów, które zawierają węzeł 4, ale nie 3: 1
Zauważ, że działa to również dla ścieżki, która prowadzi bezpośrednio do celu, np. Dla ścieżki od 3 do 2 liczba krawędzi wynosi 1, ponieważ:
- Liczba węzłów, które zawierają 2, ale nie 3: 0 węzłów
- Liczba węzłów, które zawierają węzeł 3, ale nie 2: 1
Następnie możemy zsumować wszystkie te kombinacje.
Jeśli zamiast tego spojrzysz tylko na węzeł, np. Węzeł 2 z ustawionym przodkiem {2,3}. Ten węzeł przyczyni się jeden raz podczas przetwarzania ścieżki, 2 to 1ponieważ zawiera 2, ale nie 1. Nie wniesie nic do ścieżki, 3 to 2ponieważ ma zarówno 2, jak i 3, ale przyczyni się raz podczas przetwarzania ścieżki, 4 to 3ponieważ ma 3, ale nie 4. Zasadniczo liczba w zestawie przodków węzła przyczyni się do jednego dla każdego sąsiada (jeden niższy z wyższych), którego nie ma w zestawie. Z wyjątkiem elementu maksymalnego (w tym przypadku 4), który przyczynia się tylko do dolnego sąsiada 3, ponieważ nie ma ścieżki5 to 4. Simular 0 jest jednostronny, ale ponieważ 0 jest zawsze u podstawy drzewa i zawiera wszystkie liczby (jest to łączenie ostateczne i nie liczymy złączeń), nigdy nie ma żadnego wkładu od 0, więc najłatwiej jest po prostu opuścić węzeł 0 całkowicie.
Możemy więc również rozwiązać problem, patrząc na zestaw przodków dla każdego węzła, policz wkłady i sumę dla wszystkich węzłów.
Aby łatwo przetwarzać sąsiadów, zamierzam reprezentować zestawy przodków jako ciąg spacji i 1, gdzie każdy 1 w pozycji p oznacza, że n-1-p jest przodkiem. Tak więc np. W naszym przypadku n=51 w pozycji 0 wskazuje, że 4 jest przodkiem. Zostawię końcowe spacje. Rzeczywista reprezentacja drzewa, które zbuduję, to:
" 1"
|
" 11" "1"
\ /
\ /
"1111"
Zauważ, że pominąłem węzeł 0, który byłby reprezentowany, "11111"ponieważ zamierzam zignorować węzeł 0 (nigdy się nie przyczynia).
Przodkowie bez dolnego sąsiada są teraz reprezentowani przez koniec sekwencji 1. Przodkowie bez wyższego sąsiada są teraz reprezentowani przez początek sekwencji 1, ale powinniśmy zignorować każdy początek sekwencji na początku łańcucha, ponieważ reprezentowałby ścieżkę, 5 to 4która nie istnieje. Ta kombinacja jest dokładnie dopasowana przez wyrażenie regularne /.\b/.
Budowanie ciągów przodka odbywa się poprzez przetworzenie wszystkich węzłów w kolejności, n-1 .. 1a następnie ustawienie 1 w pozycji dla samego węzła i wykonanie „lub” w potomku.
Dzięki temu program jest wystarczająco łatwy do zrozumienia:
-ap read STDIN into $_ and @F
map{ }1-$_..-1 Process from n-1 to 1,
but use the negative
values so we can use a
perl sequence.
I will keep the current
ancestor for node $i in
global ${-$i} (another
reason to use negative
values since $1, $2 etc.
are read-only
$$_|$"x$p++.1 "Or" the current node
position into its ancestor
accumulator
$_= Assign the ancestor string
to $_. This will overwrite
the current counter value
but that has no influence
on the following counter
values
${"-@F"%$_}|= Merge the current node
ancestor string into the
successor
Notice that because this
is an |= the index
calculation was done
before the assignment
to $_ so $_ is still -i.
-n % -i = - (n % i), so
this is indeed the proper
index
/.\b/g As explained above this
gives the list of missing
higher and lower neighbours
but skips the start
$_= A map in scalar context
counts the number of
elements, so this assigns
the grand total to $_.
The -p implicitly prints
Zauważ, że zastąpienie /.\b/przez /\b/rozwiązuje wersję tego problemu w obie strony, w której tarzan również podąża ścieżką0 to n-1
Kilka przykładów wyglądu ciągów przodka (podanych w kolejności n-1 .. 1):
n=23:
1
1
1
1
1
1
1
1
1
1
1
11
1 1
1 1
1 1
11 11
1 1
11 1 1 11
1 1
1111 11 11 1111
111111111 111111111
1111111111111111111111
edges=68
n=24:
1
1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1 1
1 1
1 1
1 1 1 1
1 1
11 1 1 11
1 1 1 1
1 1 1 1
1 1
edges=82