Olympische Weinschwinger üben ihre Routinen in Standardbäumen aus. Insbesondere Standard - Baum nhat Eckpunkte für nach 0oben durch n-1und Kanten Verbinden jeden Nicht - Null - Scheitel azu dem Scheitelpunkt n % adarunter. So sieht Standard Tree 5 beispielsweise folgendermaßen aus:

3
|
2   4
 \ /
  1
  |
  0

weil der Rest, wenn 5 durch 3 geteilt wird, 2 ist, der Rest, wenn 5 durch 2 oder durch 4 geteilt wird, 1 ist und der Rest, wenn 5 durch 1 geteilt wird, 0 ist.

In diesem Jahr wird Tarzan sein Gold mit neuen Routinen verteidigen, von denen jede am Scheitelpunkt beginnt n - 1, zum Scheitelpunkt schwingt, zum Scheitelpunkt n - 2weitergeht n - 3usw., bis er schließlich zum Scheitelpunkt absteigt 0.

Die Punktzahl für eine Routine ist die Summe der Punkte für jeden Schwung (einschließlich des Abstiegs), und die Punktzahl für einen Schwung ist die Entfernung innerhalb des Baums zwischen seinem Start- und Endpunkt. Somit hat Tarzans Routine auf Standard Tree 5 eine Punktzahl von 6:

• ein Schwung von 4bis 3bringt drei Punkte (runter, rauf, rauf),
• ein Schwung von 3bis 2bringt einen Punkt (nach unten),
• ein Schwung von 2bis 1bringt einen Punkt (nach unten) und
• Ein Abstieg von 1bis 0bringt einen Punkt (nach unten).

Schreiben Sie ein Programm oder eine Funktion, die bei einer positiven Ganzzahl ndie Bewertung von Tarzans Routine auf Standard Tree berechnet n. Beispiele für Ein- und Ausgänge:

 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

Regeln und Code-Scoring sind wie beim Code-Golf üblich .

C 98 97 Bytes

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;}

Dies berechnet den Abstand zwischen jedem Punktepaar mit der folgenden Formel:

• Fügen Sie den Abstand von der Wurzel zum Knoten A hinzu
• Fügen Sie den Abstand von der Wurzel zum Knoten B hinzu
• Subtrahieren Sie 2 * die Länge der gemeinsamen Wurzel von A und B

Dies hat den Vorteil, dass es bei Anwendung auf alle Paare dasselbe ist wie:

• Addiere 2 * den Abstand von der Wurzel zu jedem Knoten
• Subtrahieren Sie 2 * die Länge der gemeinsamen Wurzel jedes Knotenpaares
• Subtrahieren Sie den Abstand von der Wurzel zum ersten Knoten
• Subtrahieren Sie den Abstand von der Wurzel bis zum letzten Knoten

Um die Logik zu vereinfachen, gehen wir davon aus, dass wir von Knoten 0 zu Knoten n-1 gehen und nicht von n-1 zu 0, wie in der Frage angegeben. Der Abstand vom Wurzelknoten zum Knoten 0 ist offensichtlich 0 (sie sind gleich). Und wir können sehen, dass für (die meisten) Bäume der Abstand vom letzten Knoten zur Wurzel 2 beträgt:

                    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

Dies bedeutet, dass wir einige Sonderfälle haben (n <2), aber wir können diese leicht genug erklären.

Nervenzusammenbruch:

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
}

_{Danke @feersum für 1 Byte gespeichert}

Bonus: Bäume!

Ich habe ein schnelles und schmutziges Programm geschrieben, um zu sehen, wie diese Bäume aussehen. Hier sind einige der Ergebnisse:

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 Bytes

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 Bytes

Beinhaltet +2 für -ap

Laufen Sie mit der Baumgröße auf 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

Erläuterung

Wenn Sie den Baum umschreiben

3
|
2   4
 \ /
  1
  |
  0

zu einem, wo jeder Knoten die Menge aller seiner Vorfahren und sich selbst enthält:

 {3}
  |
{2,3}   {4}
   \    /
    \  /
  {1,2,3,4}
      |
 {0,1,2,3,4}

Dann können wir zB für alle Knoten den Pfad von 4 nach 3 wie folgt beschreiben:

• Alle Knoten, die 3 aber nicht 4 enthalten (von 3 nach unten)
• Alle Knoten, die 4, aber nicht 3 enthalten (von 4 nach unten)
• Der höchste Knoten, der sowohl 3 als auch 4 enthält (der Join)

Die Anzahl der Kanten ist um eins niedriger als die Anzahl der Knoten, sodass der Verbindungspunkt ignoriert werden kann. Daher beträgt die Anzahl der Kanten auf dem Pfad von 4 bis 3 3, da:

• Die Anzahl der Knoten, die 3, aber nicht 4 enthalten: 2 Knoten
• Die Anzahl der Knoten, die 4, aber keinen 3: 1-Knoten enthalten

Beachten Sie, dass dies auch für einen Pfad funktioniert, der direkt zum Ziel führt, z. B. für den Pfad von 3 bis 2 ist die Anzahl der Kanten 1, weil:

• Die Anzahl der Knoten, die 2, aber keine 3: 0 Knoten enthalten
• Die Anzahl der Knoten, die 3, aber keinen 2: 1-Knoten enthalten

Wir können dann alle diese Kombinationen aufsummieren.

Betrachten Sie stattdessen nur einen Knoten, z. B. Knoten 2 mit gesetztem Vorfahren {2,3}. Dieser Knoten wird bei der Verarbeitung des Pfads einmal beitragen, 2 to 1da er eine 2, aber keine 1 enthält. Er wird nichts für den Pfad beitragen, 3 to 2da er sowohl 2 als auch 3 hat. Er wird jedoch bei der Verarbeitung des Pfads einmal beitragen, 4 to 3da er aber 3 hat nein 4. Im Allgemeinen trägt eine Zahl in der Vorfahrmenge eines Knotens eine Zahl für jeden Nachbarn bei (eine niedrigere oder eine höhere), die nicht in der Menge enthalten ist. Mit Ausnahme des maximalen Elements (in diesem Fall 4), das nur für den unteren Nachbarn 3 beiträgt, da kein Pfad vorhanden ist5 to 4. Gleichzeitige 0 ist einseitig, aber da sich 0 immer an der Wurzel des Baums befindet und alle Zahlen enthält (es ist die ultimative Verknüpfung und wir zählen keine Verknüpfungen), gibt es keinen Beitrag von 0, so dass es am einfachsten ist, den Knoten 0 zu verlassen insgesamt aus.

Wir können das Problem also auch lösen, indem wir uns den Vorfahrensatz für jeden Knoten ansehen, die Beiträge zählen und über alle Knoten summieren.

Um Nachbarn einfach zu verarbeiten, werde ich die Vorfahrensätze als eine Folge von Leerzeichen und Einsen darstellen, wobei jede 1 an Position p darstellt, dass n-1-p ein Vorfahr ist. So bedeutet zB in unserem Fall n=5einer 1 an Position 0, dass 4 ein Vorfahr ist. Ich werde Leerzeichen weglassen. Die tatsächliche Darstellung des Baums, den ich erstellen werde, lautet also:

" 1"
  |
" 11"   "1"
   \    /
    \  /
   "1111"

Beachten Sie, dass ich den Knoten 0 ausgelassen habe, der durch dargestellt wird, "11111"weil ich den Knoten 0 ignorieren werde (er trägt nie dazu bei).

Vorfahren ohne niedrigeren Nachbarn werden jetzt durch das Ende einer Folge von Einsen dargestellt. Vorfahren ohne höheren Nachbarn werden jetzt durch den Beginn einer Folge von Einsen dargestellt. Wir sollten jedoch jeden Beginn einer Folge am Anfang einer Zeichenfolge ignorieren, da dies den 5 to 4nicht vorhandenen Pfad darstellen würde . Diese Kombination ist genau auf den regulären Ausdruck abgestimmt /.\b/.

Das Erstellen der Vorfahrenzeichenfolgen erfolgt durch Verarbeiten aller Knoten in der Reihenfolge n-1 .. 1und Setzen einer 1 an der Position für den Knoten selbst und Ausführen eines "oder" in den Nachkommen.

Trotzdem ist das Programm leicht zu verstehen:

-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

Beachten Sie, dass durch Ersetzen /.\b/von /\b/die Roundtrip-Version dieses Problems behoben wird, bei der auch Tarzan den Pfad nimmt0 to n-1

Einige Beispiele, wie die Vorfahrzeichenfolgen aussehen (in der angegebenen Reihenfolge 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 Bytes

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

-10 Bytes dank @feersum; -1 Byte dank @MartinEnder

Das Folgende ist viel schneller (aber leider mit 158 Bytes länger ):

(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 Bytes

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

Verwendung:

   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

Probieren Sie es hier online aus.

JavaScript (ES6), 118 bis 116 Byte

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

Das Fehlen einer eingestellten Differenzfunktion schadet wirklich, aber eine kreative Rekursion verringert die Bytezahl ein wenig. Bearbeiten: 2 Bytes durch Entfernen eines unnötigen Parameters gespeichert.