Olimpijscy swingersi wykonują swoje czynności na standardowych drzewach. W szczególności drzewo standardowe nma wierzchołki 0przechodzące w górę n-1i krawędzie łączące każdy niezerowy wierzchołek az wierzchołkiem n % aponiżej. Na przykład Standardowe drzewo 5 wygląda następująco:

3
|
2   4
 \ /
  1
  |
  0

ponieważ reszta, gdy 5 jest podzielona przez 3, wynosi 2, reszta, gdy 5 jest podzielona przez 2 lub przez 4, wynosi 1, a reszta, gdy 5 jest podzielona przez 1, wynosi 0.

W tym roku Tarzan będzie bronił swojego złota za pomocą nowych procedur, z których każda zaczyna się od wierzchołka n - 1, przechodzi do wierzchołka n - 2, kontynuuje do wierzchołka n - 3itp., Aż w końcu zejdzie do wierzchołka 0.

Wynik dla rutyny jest sumą wyników dla każdego zamachu (w tym zsiadania), a wynikiem dla zamachu jest odległość w drzewie między punktami początkowymi i końcowymi. Zatem procedura Tarzana na Standard Tree 5 ma wynik 6:

• huśtawka od 4do 3zdobycia trzech punktów (w dół, w górę, w górę),
• huśtawka z 3na 2jeden punkt (w dół),
• huśtawka od 2do 1zdobywa jeden punkt (w dół) i
• zejście z z 1do 0jednego punktu (w dół).

Napisz program lub funkcję, która przy dodatniej liczbie całkowitej noblicza wynik rutyny Tarzana na drzewie standardowym n. Przykładowe dane wejściowe i wyjściowe:

 1 ->  0
 2 ->  1
 3 ->  2
 4 ->  6
 5 ->  6
 6 -> 12
 7 -> 12
 8 -> 18
 9 -> 22
10 -> 32
11 -> 24
12 -> 34
13 -> 34
14 -> 36
15 -> 44
16 -> 58
17 -> 50
18 -> 64
19 -> 60
20 -> 66
21 -> 78
22 -> 88
23 -> 68
24 -> 82

Zasady i punktacja kodu są jak zwykle dla golfa kodu .

C, 98 97 bajtów

F(i){int c[i],t=i-2,n=0,p;for(;++n<i;)for(p=c[n]=n;p=i%p;c[p]=n)t+=c[p]<n-1;return i>2?t*2:i-1;}

Oblicza odległość między każdą parą punktów za pomocą następującego wzoru:

• Dodaj odległość od korzenia do węzła A.
• Dodaj odległość od korzenia do węzła B.
• Odejmij 2 * długość wspólnego pierwiastka z A i B.

Ma to tę zaletę, że po zastosowaniu do wszystkich par jest takie samo jak:

• Dodaj 2 * odległość od korzenia do każdego węzła
• Odejmij 2 * długość wspólnego katalogu głównego każdej pary węzłów
• Odejmij odległość od korzenia do pierwszego węzła
• Odejmij odległość od korzenia do ostatniego węzła

Aby uprościć logikę, zakładamy, że przechodzimy od węzła 0 do węzła n-1, a nie od n-1 do 0, jak stwierdza pytanie. Odległość od węzła głównego do węzła 0 wynosi oczywiście 0 (są takie same). Widzimy, że dla (większości) drzew odległość od ostatniego węzła do korzenia wynosi 2:

                    n+1 % n = 1  for all n > 1
and:                  n % 1 = 0  for all n >= 0
therefore:  n % (n % (n-1)) = 0  for all n > 2

Oznacza to, że mamy kilka specjalnych przypadków (n <2), ale możemy je łatwo wyjaśnić.

Awaria:

F(i){                               // Types default to int
    int c[i],                       // Buffer for storing paths
        t=i-2,                      // Running total score
        n=0,                        // Loop index
        p;                          // Inner loop variable
    for(;++n<i;)                    // Loop through all node pairs (n-1, n)
        for(p=c[n]=n;p=i%p;c[p]=n)  //  Recurse from current node (n) to root
            t+=c[p]<n-1;            //   Increase total unless this is a common
                                    //   node with the previous path
    return i>2?   :i-1;             // Account for special cases at 1 and 2
               t*2                  // For non-special cases, multiply total by 2
}

_{Dzięki @feersum za 1 bajt zapisany}

Bonus: Drzewa!

Napisałem szybki i brudny program, aby zobaczyć, jak wyglądają te drzewa. Oto niektóre wyniki:

6:

5 4  
| |  
1 2 3
 \|/ 
  0  

8:

  5      
  |      
7 3   6  
|  \ /   
1   2   4
'--\|/--'
    0    

13:

   08              
    |              
11 05   10 09 07   
 |   \ /    |  |   
02   03    04 06 12
 '-----\  /---'--' 
        01         
         |         
        00         

19:

   12                       
    |                       
   07   14                  
     \ /                    
     05    15 11            
       \  /    |            
17      04    08 16 13 10   
 |       '-\  /--'   |  |   
02          03      06 09 18
 '---------\ |/-----'--'--' 
            01              
             |              
            00              

49:

                         31                                                    
                          |                                                    
           30            18   36                                               
            |              \ /                                                 
           19   38 27      13    39 29    32                                   
             \ /    |        \  /    |     |                                   
   26        11    22 44      10    20 40 17   34                              
    |         '-\  /--'        '-\  /--'    \ /                                
47 23   46       05               09        15    45 43 41 37 33 25    35 28   
 |   \ /          '--------------\ |/-------'-----'   |  |  |  |  |     |  |   
02   03                           04                 06 08 12 16 24 48 14 21 42
 '----'--------------------------\ |/----------------'--'--'--'--'--'    \ |/  
                                  01                                      07   
                                   '-----------------\  /-----------------'    
                                                      00                       

Python 2, 85 bajtów

def f(a,i=1):h=lambda n:n and{n}|h(a%n)or{0};return i<a and len(h(i)^h(i-1))+f(a,i+1)

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

Mathematica, 113 103 102 bajtów

(r=Range[a=#-1];Length@Flatten[FindShortestPath[Graph[Thread[r<->Mod[a+1,r]]],#,#2]&@@{#,#-1}&/@r]-a)&

-10 bajtów dzięki @feersum; -1 bajt dzięki @MartinEnder

Następujące jest znacznie szybsze (ale niestety dłuższe, przy 158 bajtach ):

(a=#;If[a<4,Part[-{1,1,1,-6},a],If[EvenQ@a,-2,1]]+a+4Total[Length@Complement[#,#2]&@@#&/@Partition[NestWhileList[Mod[a,#]&,#,#!=0&]&/@Range@Floor[a/2],2,1]])&

J, 37 bajtów

[:+/2(-.+&#-.~)/\|:@(]|~^:(<@>:@[)i.)

Stosowanie:

   f=.[:+/2(-.+&#-.~)/\|:@(]|~^:(<@>:@[)i.)
   f 10
32
   f every 1+i.20
0 1 2 6 6 12 12 18 22 32 24 34 34 36 44 58 50 64 60 66

Wypróbuj online tutaj.

JavaScript (ES6), 118 116 bajtów

n=>[...Array(n)].map(g=(_,i)=>i?[...g(_,n%i),i]:[],r=0).reduce(g=(x,y,i)=>x.map(e=>r+=!y.includes(e))&&i?g(y,x):x)|r

Brak funkcji ustawiania różnicy naprawdę boli, ale niektóre kreatywne rekurencje nieco zmniejszają liczbę bajtów. Edycja: Zapisano 2 bajty, usuwając niepotrzebny parametr.