Rotina olímpica de balançar as videiras de Tarzan

32

As videiras olímpicas realizam suas rotinas em árvores comuns. Em particular, a Árvore Padrão npossui vértices para 0cima n-1e arestas que vinculam cada vértice diferente de zero aao vértice n % aabaixo dele. Então, por exemplo, a Árvore Padrão 5 se parece com isso:

3
|
2   4
 \ /
  1
  |
  0

porque o restante quando 5 é dividido por 3 é 2, o restante quando 5 é dividido por 2 ou por 4 é 1 e o restante quando 5 é dividido por 1 é 0.

Este ano, Tarzan estará defendendo seu ouro com novas rotinas, cada uma das quais começa no vértice n - 1, oscila para o vértice n - 2, continua para o vértice n - 3etc., até que finalmente desmonte para o vértice 0.

A pontuação de uma rotina é a soma das pontuações de cada giro (incluindo a desmontagem), e a pontuação de um giro é a distância dentro da árvore entre seus pontos inicial e final. Assim, a rotina de Tarzan na Árvore Padrão 5 tem uma pontuação de 6:

  • um balanço de 4para 3marcar três pontos (baixo, cima, cima),
  • um balanço de 3para 2marcar um ponto (para baixo),
  • um balanço de 2para 1marcar um ponto (para baixo), e
  • uma desmontagem de 1para 0marcar um ponto (para baixo).

Escreva um programa ou função que, dado um número inteiro positivo n, calcule a pontuação da rotina de Tarzan na Árvore Padrão n. Entradas e saídas de amostra:

 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

Regras e pontuação de código são como de costume para o .

Edward
fonte
9
Não consigo encontrar essa sequência no OEIS. Boa pergunta.
Leaky Nun
8
Excellent spec!
Xnor
11
@LeakyNun Deve ser adicionado embora. É uma sequência muito original! (Mesmo sem a história de fundo)
DanTheMan

Respostas:

12

C, 98 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;}

Isso calcula a distância entre cada par de pontos com a seguinte fórmula:

  • Adicione a distância da raiz ao nó A
  • Adicione a distância da raiz ao nó B
  • Subtraia 2 * o comprimento da raiz comum de A e B

Isso tem a vantagem de que, quando aplicado a todos os pares, é o mesmo que:

  • Adicione 2 * a distância da raiz a cada nó
  • Subtraia 2 * o comprimento da raiz comum de cada par de nós
  • Subtrair a distância da raiz ao primeiro nó
  • Subtrair a distância da raiz ao último nó

Para tornar a lógica mais simples, assumimos que estamos passando do nó 0 para o nó n-1, em vez de n-1 para 0, conforme a pergunta. A distância do nó raiz ao nó 0 é obviamente 0 (são iguais). E podemos ver que, para a maioria das árvores, a distância entre o último nó e a raiz é 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

Isso significa que temos alguns casos especiais (n <2), mas podemos explicá-los com bastante facilidade.

Demolir:

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
}

Obrigado @feersum por 1 byte salvo


Bônus: Árvores!

Eu escrevi um programa rápido e sujo para ver como são essas árvores. Aqui estão alguns dos 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
fonte
Existem alguns parênteses supérfluos na declaração de retorno.
feersum
@feersum d'oh! Eles nem sempre eram supérfluos, mas depois mudei o tratamento especial de casos. Obrigado!
Dave
3
Ame as visualizações!
Edward 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
fonte
7

Perl, 65 59 55 54 bytes

Inclui +2 para -ap

Execute com o tamanho da árvore no 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

Explicação

Se você reescrever a árvore

3
|
2   4
 \ /
  1
  |
  0

para aquele em que cada nó contém o conjunto de todos os seus ancestrais e ele próprio:

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

Então, podemos descrever, por exemplo, todos os nós do caminho de 4 a 3 como:

  • Todos os nós que contêm 3, mas não 4 (saindo de 3)
  • Todos os nós que contêm 4, mas não 3 (saindo de 4)
  • O nó mais alto que contém 3 e 4 (a junção)

O número de arestas é um a menos que o número de nós; portanto, podemos usá-lo para ignorar o ponto de junção; portanto, o número de arestas no caminho de 4 a 3 é 3 porque:

  • O número de nós que contêm 3, mas não nós 4: 2
  • O número de nós que contêm 4, mas não o nó 3: 1

Observe que isso também funciona para um caminho que desce diretamente para o seu destino, por exemplo, para o caminho de 3 a 2, o número de arestas é 1 porque:

  • O número de nós que contêm 2, mas não 3: 0 nós
  • O número de nós que contêm 3, mas não o nó 2: 1

Podemos então somar todas essas combinações.

Se você olhar apenas para um nó, por exemplo, nó 2 com conjunto de ancestrais {2,3}. Este nó contribuirá uma vez ao processar o caminho 2 to 1porque contém um 2, mas não um 1. Ele não contribuirá com nada para o caminho, 3 to 2pois possui 2 e 3, mas contribuirá uma vez ao processar o caminho . O Simular 0 é unilateral, mas como 0 está sempre na raiz da árvore e contém todos os números (é a junção final e não contamos junções), nunca há contribuição de 0, portanto é mais fácil deixar o nó 0 completamente.4 to 3 pois possui 3, mas não 4. Em geral, um número no conjunto ancestral de um nó contribuirá com um para cada vizinho (um menor ou mais alto) que não esteja no conjunto. Exceto pelo elemento máximo (4 neste caso), que apenas contribui para o vizinho baixo 3, pois não há caminho5 to 4

Portanto, também podemos resolver o problema observando o conjunto de ancestrais de cada nó, contar as contribuições e somar todos os nós.

Para processar vizinhos facilmente, vou representar os conjuntos de ancestrais como uma sequência de espaços e 1's, onde cada 1 na posição p representa que n-1-p é um ancestral. Então, por exemplo, no nosso caso de n=51 na posição 0, indica 4 é um ancestral. Vou deixar espaços à direita. Portanto, a representação real da árvore que construirei é:

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

Observe que eu deixei de fora o nó 0, que seria representado por, "11111"porque eu vou ignorar o nó 0 (ele nunca contribui).

Antepassados ​​sem vizinho inferior agora são representados no final de uma sequência de 1s. Antepassados ​​sem vizinho mais alto agora são representados pelo início de uma sequência de 1s, mas devemos ignorar qualquer início de uma sequência no início de uma sequência, pois isso representaria o caminho 5 to 4que não existe. Essa combinação é exatamente correspondida pelo regex /.\b/.

A construção das seqüências ancestrais é feita processando todos os nós na ordem n-1 .. 1e, em seguida, defina 1 na posição do próprio nó e fazendo um "ou" no descendente.

Com tudo isso, o programa é 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 a substituição /.\b/por /\b/resolve a versão de ida e volta desse problema em que o tarzan também segue o caminho0 to n-1

Alguns exemplos de como as seqüências de caracteres ancestrais são exibidas (em ordem 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
fonte
Opa, desculpe, eu não percebi que sua edição tinha apenas alguns segundos. Enfim, abordagem e explicação muito legais!
FryAmTheEggman
@FryAmTheEggman Sem problemas, estávamos apenas corrigindo exatamente o mesmo problema de layout. Enfim, sim, estou muito feliz com a forma como todas as peças se juntaram neste programa. Actualmente, eu não vejo nenhuma gordura a ser cortada ..
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 graças a @feersum; -1 byte graças a @MartinEnder

O seguinte é muito mais rápido (mas mais longo, infelizmente, com 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]])&
Martin
fonte
Eu acredito que você pode atribuir coisas sem usar With. Além disso, parece que toda vez que Rangeé usado, aé o argumento, para que possa ser fatorado.
feersum
11
r=Range[a=#-1]salva um 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

Experimente online aqui.

randomra
fonte
Eu estaria interessado em ver um detalhamento de como isso funciona. Também o serviço tryj.tk parece estar quebrado ( "não conseguiu ler a localStorage ..." e "$ (...) .terminal não é uma função")
Dave
@ Esse site não funciona para mim também no Chrome, mas funciona se eu tentar usar o IE ou o Edge, no entanto, recomendo instalar o J ( link ) se você estiver interessado!
miles
@miles Estranho, para mim funciona para todos os navegadores (FF, Chrome, IE).
randomra
Funcionou para mim usando o Chrome, mas parou de funcionar há alguns meses e começou a responder com uma mensagem de erro semelhante à de Dave
milhas
@ Edward Vai fazer quando eu encontrar algum tempo.
randomra
1

JavaScript (ES6), 118 116 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

A falta de uma função de diferença definida realmente dói, mas alguma recursão criativa reduz um pouco a contagem de bytes. Editar: salvou 2 bytes removendo um parâmetro desnecessário.

Neil
fonte