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
