32
\$\begingroup\$

Olympic vine-swingers perform their routines in standard trees. In particular, Standard Tree n has vertices for 0 up through n-1 and edges linking each nonzero vertex a to the vertex n % a below it. So, for example, Standard Tree 5 looks like this:

3
|
2   4
 \ /
  1
  |
  0

because the remainder when 5 is divided by 3 is 2, the remainder when 5 is divided by 2 or by 4 is 1, and the remainder when 5 is divided by 1 is 0.

This year, Tarzan will be defending his gold with new routines, each of which begins at vertex n - 1, swings to vertex n - 2, continues to vertex n - 3, etc., until finally he dismounts to vertex 0.

The score for a routine is the sum of the scores for each swing (including the dismount), and the score for a swing is the distance within the tree between its start and end points. Thus, Tarzan's routine on Standard Tree 5 has a score of 6:

  • a swing from 4 to 3 scores three points (down, up, up),
  • a swing from 3 to 2 scores one point (down),
  • a swing from 2 to 1 scores one point (down), and
  • a dismount from 1 to 0 scores one point (down).

Write a program or function that, given a positive integer n, computes the score of Tarzan's routine on Standard Tree n. Sample inputs and outputs:

 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

Rules and code scoring are as usual for .

\$\endgroup\$
  • 9
    \$\begingroup\$ I fail to find this sequence in OEIS. Nice question. \$\endgroup\$ – Leaky Nun Aug 20 '16 at 14:44
  • 8
    \$\begingroup\$ Excellent spec! \$\endgroup\$ – xnor Aug 20 '16 at 14:46
  • 1
    \$\begingroup\$ @LeakyNun It should be added though. It is a very original sequence! (Even without the backstory) \$\endgroup\$ – DanTheMan Aug 21 '16 at 6:34
12
\$\begingroup\$

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

This calculates the distance between each pair of points with the following formula:

  • Add the distance from the root to node A
  • Add the distance from the root to node B
  • Subtract 2* the length of the common root of A and B

This has the advantage that when applied to all pairs, it's the same as:

  • Add 2* the distance from the root to each node
  • Subtract 2* the length of the common root of each node pair
  • Subtract the distance from the root to the first node
  • Subtract the distance from the root to the last node

To make the logic simpler, we assume we're going from node 0 to node n-1, rather than n-1 to 0 as the question states. The distance from the root node to node 0 is obviously 0 (they're the same). And we can see that for (most) trees, the distance from the last node to the root is 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

This means we have some special cases (n<2) but we can account for those easily enough.

Breakdown:

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
}

Thanks @feersum for 1 byte saved


Bonus: Trees!

I wrote a quick-and-dirty program to see what these trees look like. Here's some of the results:

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                       
\$\endgroup\$
  • \$\begingroup\$ There are some superfluous parentheses in the return statement. \$\endgroup\$ – feersum Aug 20 '16 at 19:31
  • \$\begingroup\$ @feersum d'oh! They weren't always superfluous, but then I changed the special case handling. Thanks! \$\endgroup\$ – Dave Aug 20 '16 at 19:34
  • 3
    \$\begingroup\$ Love the visualizations! \$\endgroup\$ – Edward Aug 20 '16 at 21:42
7
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

Perl, 65 59 55 54 bytes

Includes +2 for -ap

Run with the tree size on 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

Explanation

If you rewrite the tree

3
|
2   4
 \ /
  1
  |
  0

to one where each node contains the set of all its ancestors and itself:

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

Then we can describe e.g. all the nodes the path from 4 to 3 as:

  • All nodes that contain 3 but not 4 (going down from 3)
  • All nodes that contain 4 but not 3 (going down from 4)
  • The highest node that contains both 3 and 4 (the join)

The number of edges is one less than the number of nodes so we can use that to ignore the join point, so the number of edges on the path from 4 to 3 is 3 because:

  • The number of nodes that contain 3 but not 4: 2 nodes
  • The number of nodes that contain 4 but not 3: 1 node

Notice that this also works for a path that directly goes down to its target, e.g. for the path from 3 to 2 the number of edges is 1 because:

  • The number of nodes that contain 2 but not 3: 0 nodes
  • The number of nodes that contain 3 but not 2: 1 node

We can then sum over all these combinations.

If you instead look at just a node, e.g. node 2 with ancestor set {2,3}. This node is going to contribute once when processing the path 2 to 1 because it contains a 2 but not a 1. It will contribute nothing for the path 3 to 2 since it has both 2 and 3, but it will contribute once when processing the path 4 to 3 since it has 3 but no 4. In general a number in the ancestor set of a node will contribute one for each neighbour (one lower of higher) that is not in the set. Except for the maximum element (4 in this case) which only contributes for the low neighbour 3 since there is no path 5 to 4. Simular 0 is one sided, but since 0 is always at the root of the tree and contains all numbers (it is the ultimate join and we don't count joins) there is never any contribution from 0 so it's easiest to just leave node 0 out altogether.

So we can also solve the problem by looking at the ancestor set for each node, count the contributions and sum over all nodes.

To easily process neighbours I'm going to represent the ancestor sets as a string of spaces and 1's where each 1 at position p represents that n-1-p is an ancestor. So e.g. in our case of n=5 a 1 at position 0 indicates 4 is an ancestor. I will leave off trailing spaces. So the actual representation of the tree I will build is:

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

Notice that I left out node 0 which would be represented by "11111" because I'm going to ignore node 0 (it never contributes).

Ancestors with no lower neighbour are now represented by the end of a sequence of 1's. Ancestors with no higher neighbour are now represented by the start of a sequence of 1's, but we should ignore any start of a sequence at the start of a string since this would represent the path 5 to 4 which doesn't exist. This combination is exactly matched by the regex /.\b/.

Building the ancestor strings is done by processing all nodes in the order n-1 .. 1 and there set a 1 in the position for the node itself and doing an "or" into the descendant.

With all that the program is easy enough to understand:

-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

Notice that replacing /.\b/ by /\b/ solves the roundtrip version of this problem where tarzan also takes the path 0 to n-1

Some examples of how the ancestor strings look (given in order 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
\$\endgroup\$
  • \$\begingroup\$ Whoops, sorry I didn't realise your edit was only a few seconds old. Anyway, very neat approach and explanation! \$\endgroup\$ – FryAmTheEggman Aug 24 '16 at 21:21
  • \$\begingroup\$ @FryAmTheEggman No problem, we were just fixing the exact same layout problem. Anyway, yeah, I'm quite happy with how all the pieces came together in this program. I currently don't see any fat to be cut.. \$\endgroup\$ – Ton Hospel Aug 24 '16 at 21:29
3
\$\begingroup\$

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 thanks to @feersum; -1 byte thanks to @MartinEnder

The following is far quicker (but longer, unfortunately, at 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]])&
\$\endgroup\$
  • \$\begingroup\$ I believe you can assign things without using With. Also it looks like every time Range is used, a is the argument, so that could be factored out. \$\endgroup\$ – feersum Aug 20 '16 at 19:09
  • 1
    \$\begingroup\$ r=Range[a=#-1] saves a byte. \$\endgroup\$ – Martin Ender Aug 24 '16 at 14:09
2
\$\begingroup\$

J, 37 bytes

[:+/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

Try it online here.

\$\endgroup\$
  • \$\begingroup\$ I'd be interested to see a breakdown of how this works. Also the tryj.tk service seems to be broken ("failed to read the localStorage…" and "$(…).terminal is not a function") \$\endgroup\$ – Dave Aug 23 '16 at 11:58
  • \$\begingroup\$ @Dave that site doesn't work for me too on Chrome, but works if I try using IE or Edge, however I do recommend installing J (link) if you are interested in it! \$\endgroup\$ – miles Aug 24 '16 at 10:24
  • \$\begingroup\$ @miles Weird, for me it works for all browsers (FF,Chrome,IE). \$\endgroup\$ – randomra Aug 24 '16 at 11:29
  • \$\begingroup\$ It did work for me using Chrome, but it stopped working a few months ago and began responding with a similar error message to Dave's \$\endgroup\$ – miles Aug 24 '16 at 13:35
  • \$\begingroup\$ @Edward Will do when I find some time. \$\endgroup\$ – randomra Aug 26 '16 at 18:47
1
\$\begingroup\$

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

Lack of a set difference function really hurts, but some creative recursion reduces the byte count a bit. Edit: Saved 2 bytes by removing an unnecessary parameter.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.