First, the introduction. Unless you slept through the 90s, the so-called Bacon number is the number of actors between an actor and Kevin Bacon, where the connection between susseccive actors is a movie they co-starred in. Kevin Bacon's number would be 0, those that co-starred with him in any movie would be 1, and so forth. For example, UPDATING THIS PART, since I fudged up big time Nicholos Cage would have a Bacon Number of 2, since he starred in The Rock with Ed Harris, who co-starred with Bacon in Apollo 13.
Now, it's been shown that Bacon is truly not the best 'center' of the actor universe, as the average Bacon number using Bacon is around 4, while using the best center brings it down to about 3.5 (The center person changes often with new movies, but when I last checked, there's a good 4 or 5 near-center people). But people still play the game with Bacon.
To programmers, this task is pretty much optimizing the root node of a arbitarily-branched tree structure in order to minimize the average depth.
So the challenge is: Given an arbitary tree structure, stored as %t; the keys of %t are the names of the nodes, while the value for each key is a list of nodes that are connected to that node. There are no disjoint parts of the tree, and it's possible to go from any one node to another by following a link. However, there are no 'loops', that is, there is only one distinct path between any two nodes. (If there were loops, this becomes a graph, and can make the problem a bit harder). You can assume that if there is a link from 'a' to 'b', 'b' will have a link back to 'a'.
Find the perl golf solution (min. number of characters in program), for a subroutine b( %t ) that returns the name of the node that, if considered to be the central node, minimizes the average Bacon number/depth for all nodes. To clairify it, the Bacon number is defined as the number of links between the central node and any other node, with the central node being 0, nodes directly connected to it as 1, and so forth.
For a test case: update typo fixed
my %t = ( Chicago=>[ 'Detroit', 'Cleveland', 'Denver' ], Cleveland=>[ 'Chicago', 'NYC' ], Detroit=>[ 'Chicago' ], NYC=>[ 'Cleveland' ], SF=>[ 'Denver', 'Fairbanks' ], Fairbanks=>[ 'SF','Tokyo' ], Tokyo=>[ 'Fairbanks', 'Moscow' ], Moscow=>[ 'Tokyo' ], Denver=>[ 'SF', 'Chicago' ] );
Extra Credit: Assume there are loops, such that %t can be a graph as opposed to a tree. Find the solution in this case.
Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain