Les vignerons olympiques exécutent leurs routines dans des arbres standard. En particulier, l'arbre standard na des sommets pour le 0haut n-1et des bords reliant chaque sommet non nul aau sommet en n % adessous. Ainsi, par exemple, l'arbre standard 5 ressemble à ceci:

3
|
2   4
 \ /
  1
  |
  0

parce que le reste lorsque 5 est divisé par 3 est 2, le reste lorsque 5 est divisé par 2 ou par 4 est 1, et le reste lorsque 5 est divisé par 1 est 0.

Cette année, Tarzan défendra son or avec de nouvelles routines, chacune commençant au sommet n - 1, se balançant au sommet n - 2, se poursuivant au sommet n - 3, etc., jusqu'à ce qu'il finisse par descendre au sommet 0.

Le score pour une routine est la somme des scores pour chaque swing (y compris le démontage), et le score pour un swing est la distance dans l'arbre entre ses points de début et de fin. Ainsi, la routine de Tarzan sur Standard Tree 5 a un score de 6:

• un swing de 4à 3marque trois points (bas, haut, haut),
• un swing de 3à 2marque un point (vers le bas),
• un swing de 2à 1marque un point (vers le bas), et
• un démontage de 1à 0marque un point (vers le bas).

Écrivez un programme ou une fonction qui, étant donné un entier positif n, calcule le score de la routine de Tarzan sur l'arbre standard n. Exemples d'entrées et sorties:

 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

Les règles et la notation de code sont comme d'habitude pour le golf de code .

C, 98 97 octets

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

Cela calcule la distance entre chaque paire de points avec la formule suivante:

• Ajouter la distance de la racine au nœud A
• Ajouter la distance de la racine au nœud B
• Soustrayez 2 * la longueur de la racine commune de A et B

Cela a l'avantage que lorsqu'il est appliqué à toutes les paires, c'est la même chose que:

• Ajouter 2 * la distance de la racine à chaque nœud
• Soustrayez 2 * la longueur de la racine commune de chaque paire de nœuds
• Soustrayez la distance de la racine au premier nœud
• Soustrayez la distance de la racine au dernier nœud

Pour simplifier la logique, nous supposons que nous allons du nœud 0 au nœud n-1, plutôt que de n-1 à 0 comme l'indique la question. La distance du nœud racine au nœud 0 est évidemment 0 (ils sont les mêmes). Et nous pouvons voir que pour (la plupart) des arbres, la distance entre le dernier nœud et la racine est de 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

Cela signifie que nous avons quelques cas particuliers (n <2) mais nous pouvons les prendre en compte assez facilement.

Panne:

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
}

_{Merci @feersum pour 1 octet enregistré}

Bonus: des arbres!

J'ai écrit un programme rapide et sale pour voir à quoi ressemblent ces arbres. Voici quelques résultats:

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 octets

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 octets

Comprend +2 pour -ap

Exécutez avec la taille de l'arbre sur 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

Explication

Si vous réécrivez l'arbre

3
|
2   4
 \ /
  1
  |
  0

à un où chaque nœud contient l'ensemble de tous ses ancêtres et lui-même:

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

Ensuite, nous pouvons décrire par exemple tous les nœuds le chemin de 4 à 3 comme:

• Tous les nœuds qui contiennent 3 mais pas 4 (en descendant de 3)
• Tous les nœuds qui contiennent 4 mais pas 3 (en descendant de 4)
• Le nœud le plus élevé qui contient à la fois 3 et 4 (la jointure)

Le nombre d'arêtes est inférieur de un au nombre de nœuds afin que nous puissions l'utiliser pour ignorer le point de jointure, donc le nombre d'arêtes sur le chemin de 4 à 3 est 3 car:

• Le nombre de nœuds contenant 3 nœuds mais pas 4: 2
• Le nombre de nœuds contenant 4 nœuds mais pas 3: 1

Notez que cela fonctionne également pour un chemin qui descend directement vers sa cible, par exemple pour le chemin de 3 à 2, le nombre d'arêtes est 1 car:

• Le nombre de nœuds contenant 2 nœuds mais pas 3: 0
• Le nombre de nœuds contenant 3 nœuds mais pas 2: 1

On peut alors additionner toutes ces combinaisons.

Si vous regardez plutôt un nœud, par exemple le nœud 2 avec un ensemble d'ancêtres {2,3}. Ce nœud va contribuer une fois lors du traitement du chemin 2 to 1car il contient un 2 mais pas un 1. Il ne contribuera rien pour le chemin 3 to 2car il a à la fois 2 et 3, mais il contribuera une fois lors du traitement du chemin 4 to 3car il en a 3 mais non 4. En général, un nombre dans l'ensemble des ancêtres d'un nœud contribuera à un pour chaque voisin (un inférieur ou supérieur) qui n'est pas dans l'ensemble. Sauf pour l'élément maximum (4 dans ce cas) qui ne contribue que pour le voisin bas 3 car il n'y a pas de chemin5 to 4. Le 0 simulaire est unilatéral, mais puisque 0 est toujours à la racine de l'arbre et contient tous les nombres (c'est la jointure ultime et nous ne comptons pas les jointures), il n'y a jamais de contribution de 0, il est donc plus facile de simplement quitter le nœud 0 tout à fait.

Nous pouvons donc également résoudre le problème en examinant l'ensemble d'ancêtres pour chaque nœud, compter les contributions et additionner tous les nœuds.

Pour traiter facilement les voisins, je vais représenter les ensembles d'ancêtres sous la forme d'une chaîne d'espaces et de 1 où chaque 1 à la position p représente que n-1-p est un ancêtre. Ainsi, par exemple, dans notre cas d' n=5un 1 à la position 0, 4 indique un ancêtre. Je laisserai de côté les espaces de fuite. La représentation réelle de l'arbre que je vais construire est donc:

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

Notez que j'ai omis le nœud 0 qui serait représenté par "11111"car je vais ignorer le nœud 0 (il ne contribue jamais).

Les ancêtres sans voisin inférieur sont maintenant représentés par la fin d'une séquence de 1. Les ancêtres sans voisin supérieur sont maintenant représentés par le début d'une séquence de 1, mais nous devons ignorer tout début d'une séquence au début d'une chaîne car cela représenterait le chemin 5 to 4qui n'existe pas. Cette combinaison correspond exactement à l'expression régulière /.\b/.

La construction des chaînes ancêtres se fait en traitant tous les nœuds dans l'ordre n-1 .. 1et en définissant un 1 à la position du nœud lui-même et en faisant un "ou" dans le descendant.

Avec tout cela, le programme est assez facile à comprendre:

-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

Notez que le remplacement /.\b/par /\b/résout la version aller-retour de ce problème où tarzan prend également le chemin0 to n-1

Quelques exemples de l'apparence des chaînes ancêtres (données dans l'ordre 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 octets

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

-10 octets grâce à @feersum; -1 octet grâce à @MartinEnder

Ce qui suit est beaucoup plus rapide (mais plus long, malheureusement, à 158 octets ):

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

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

Usage:

   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

Essayez-le en ligne ici.

JavaScript (ES6), 118 116 octets

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

Le manque d'une fonction de différence définie fait vraiment mal, mais une récursivité créative réduit un peu le nombre d'octets. Edit: enregistré 2 octets en supprimant un paramètre inutile.