Puntúa la rutina olímpica de balanceo de la vid de Tarzán

32

Los swingers olímpicos realizan sus rutinas en árboles estándar. En particular, el Árbol estándar ntiene vértices para 0arriba n-1y bordes que unen cada vértice distinto de cero acon el vértice n % adebajo de él. Entonces, por ejemplo, Standard Tree 5 se ve así:

3
|
2   4
 \ /
  1
  |
  0

porque el resto cuando 5 se divide por 3 es 2, el resto cuando 5 se divide por 2 o por 4 es 1, y el resto cuando 5 se divide por 1 es 0.

Este año, Tarzán defenderá su oro con nuevas rutinas, cada una de las cuales comienza en el vértice n - 1, cambia al vértice n - 2, continúa al vértice n - 3, etc., hasta que finalmente desmonta al vértice 0.

El puntaje para una rutina es la suma de los puntajes para cada swing (incluido el desmontaje), y el puntaje para un swing es la distancia dentro del árbol entre sus puntos de inicio y final. Por lo tanto, la rutina de Tarzán en Standard Tree 5 tiene una puntuación de 6:

  • un swing de 4a 3anota tres puntos (abajo, arriba, arriba),
  • un swing de 3a 2anota un punto (abajo),
  • un swing de 2a 1anota un punto (abajo), y
  • un desmontaje de 1a 0anota un punto (abajo).

Escriba un programa o función que, dado un número entero positivo n, calcule el puntaje de la rutina de Tarzán en el Árbol estándar n. Muestra de entradas y salidas:

 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

Las reglas y la puntuación de código son las habituales para .

Eduardo
fuente
99
No encuentro esta secuencia en OEIS. Buena pregunta.
Leaky Nun
8
Excelente especificación!
xnor
1
@LeakyNun Sin embargo, debe agregarse. ¡Es una secuencia muy original! (Incluso sin la historia de fondo)
DanTheMan

Respuestas:

12

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

Esto calcula la distancia entre cada par de puntos con la siguiente fórmula:

  • Agregue la distancia desde la raíz al nodo A
  • Agregue la distancia desde la raíz al nodo B
  • Resta 2 * la longitud de la raíz común de A y B

Esto tiene la ventaja de que cuando se aplica a todos los pares, es lo mismo que:

  • Agregue 2 * la distancia desde la raíz a cada nodo
  • Reste 2 * la longitud de la raíz común de cada par de nodos
  • Resta la distancia desde la raíz hasta el primer nodo
  • Resta la distancia desde la raíz hasta el último nodo

Para simplificar la lógica, asumimos que vamos del nodo 0 al nodo n-1, en lugar de n-1 a 0 como dice la pregunta. La distancia desde el nodo raíz al nodo 0 es obviamente 0 (son lo mismo). Y podemos ver que para (la mayoría) de los árboles, la distancia desde el último nodo hasta la raíz es 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

Esto significa que tenemos algunos casos especiales (n <2) pero podemos dar cuenta de ellos con bastante facilidad.

Descompostura:

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
}

Gracias @feersum por 1 byte guardado


Bonus: ¡Árboles!

Escribí un programa rápido y sucio para ver cómo se ven estos árboles. Estos son algunos de los resultados:

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                       
Dave
fuente
Hay algunos paréntesis superfluos en la declaración de devolución.
feersum
@feersum d'oh! No siempre fueron superfluos, pero luego cambié el manejo de casos especiales. ¡Gracias!
Dave
3
Me encantan las visualizaciones!
Edward
7

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)
Feersum
fuente
7

Perl, 65 59 55 54 bytes

Incluye +2 para -ap

Ejecutar con el tamaño del árbol en 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

Explicación

Si reescribes el árbol

3
|
2   4
 \ /
  1
  |
  0

a uno donde cada nodo contiene el conjunto de todos sus antepasados ​​y a sí mismo:

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

Luego podemos describir, por ejemplo, todos los nodos, la ruta de 4 a 3 como:

  • Todos los nodos que contienen 3 pero no 4 (bajando de 3)
  • Todos los nodos que contienen 4 pero no 3 (bajando de 4)
  • El nodo más alto que contiene 3 y 4 (la unión)

El número de bordes es uno menos que el número de nodos, por lo que podemos usarlo para ignorar el punto de unión, por lo que el número de bordes en la ruta de 4 a 3 es 3 porque:

  • El número de nodos que contienen 3 pero no 4: 2 nodos
  • El número de nodos que contienen 4 pero no 3: 1 nodo

Tenga en cuenta que esto también funciona para una ruta que desciende directamente a su objetivo, por ejemplo, para la ruta de 3 a 2, el número de bordes es 1 porque:

  • El número de nodos que contienen 2 pero no 3: 0 nodos
  • El número de nodos que contienen 3 pero no 2: 1 nodo

Entonces podemos sumar todas estas combinaciones.

Si, en cambio, observa solo un nodo, por ejemplo, el nodo 2 con el conjunto ancestro {2,3}. Este nodo contribuirá una vez cuando procese la ruta 2 to 1porque contiene un 2 pero no un 1. No aportará nada para la ruta 3 to 2ya que tiene 2 y 3, pero contribuirá una vez cuando procese la ruta 4 to 3ya que tiene 3 pero no 4. En general, un número en el conjunto ancestro de un nodo contribuirá con uno para cada vecino (uno más bajo o más alto) que no esté en el conjunto. Excepto por el elemento máximo (4 en este caso) que solo contribuye para el vecino bajo 3 ya que no hay ruta5 to 4. El 0 simular es unilateral, pero dado que 0 siempre está en la raíz del árbol y contiene todos los números (es la unión final y no contamos las uniones), nunca hay ninguna contribución de 0, por lo que es más fácil dejar el nodo 0 fuera por completo.

Por lo tanto, también podemos resolver el problema mirando el conjunto de antepasados ​​para cada nodo, contar las contribuciones y sumar sobre todos los nodos.

Para procesar fácilmente a los vecinos, voy a representar los conjuntos de antepasados ​​como una cadena de espacios y 1 donde cada 1 en la posición p representa que n-1-p es un antepasado. Entonces, por ejemplo, en nuestro caso de n=5un 1 en la posición 0 indica que 4 es un antepasado. Dejaré los espacios finales. Entonces, la representación real del árbol que construiré es:

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

Observe que omití el nodo 0, que estaría representado por "11111"porque voy a ignorar el nodo 0 (nunca contribuye).

Los antepasados ​​sin vecino inferior ahora están representados por el final de una secuencia de 1. Los antepasados ​​sin vecino superior ahora están representados por el inicio de una secuencia de 1, pero deberíamos ignorar cualquier inicio de una secuencia al comienzo de una cadena ya que esto representaría la ruta 5 to 4que no existe. Esta combinación coincide exactamente con la expresión regular /.\b/.

La construcción de las cadenas ancestrales se realiza procesando todos los nodos en el orden n-1 .. 1y establece un 1 en la posición del nodo en sí y haciendo un "o" en el descendiente.

Con todo eso, el programa es lo suficientemente fácil de entender:

-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

Observe que reemplazar /.\b/por /\b/resuelve la versión de ida y vuelta de este problema donde tarzan también toma el camino0 to n-1

Algunos ejemplos de cómo se ven las cadenas ancestrales (dadas en orden 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
Ton Hospel
fuente
Vaya, lo siento, no me di cuenta de que tu edición tenía solo unos segundos. De todos modos, ¡enfoque y explicación muy ordenados!
FryAmTheEggman
@FryAmTheEggman No hay problema, estábamos solucionando exactamente el mismo problema de diseño. De todos modos, sí, estoy bastante contento con la forma en que todas las piezas se unieron en este programa. Actualmente no veo nada de grasa para cortar ...
Ton Hospel
3

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 gracias a @feersum; -1 byte gracias a @MartinEnder

Lo siguiente es mucho más rápido (pero más largo, desafortunadamente, en 158 bytes ):

(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]])&
martín
fuente
Creo que puedes asignar cosas sin usar With. También parece que cada vez que Rangese usa, aes el argumento, por lo que podría factorizarse.
feersum
1
r=Range[a=#-1]guarda un byte.
Martin Ender
2

J, 37 bytes

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

Uso:

   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

Pruébelo en línea aquí.

randomra
fuente
Me interesaría ver un desglose de cómo funciona esto. Además, el servicio tryj.tk parece estar roto ("no se pudo leer el localStorage ..." y "$ (...) .terminal no es una función")
Dave
@Dave ese sitio no funciona para mí también en Chrome, pero funciona si intento usar IE o Edge, sin embargo, ¡recomiendo instalar J ( enlace ) si estás interesado en él!
millas
@miles Raro, para mí funciona para todos los navegadores (FF, Chrome, IE).
randomra
Funcionó para mí usando Chrome, pero dejó de funcionar hace unos meses y comenzó a responder con un mensaje de error similar al de Dave
millas del
@ Edward lo hará cuando encuentre algo de tiempo.
randomra
1

JavaScript (ES6), 118116 bytes

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

La falta de una función de diferencia establecida realmente duele, pero cierta recursividad creativa reduce un poco el recuento de bytes. Editar: se guardaron 2 bytes eliminando un parámetro innecesario.

Neil
fuente