PerlSensitive Sunglasses  
PerlMonks 
(Golf) Minimizing the Bacon Numberby Masem (Monsignor) 
on May 14, 2001 at 21:56 UTC ( #80272=perlmeditation: print w/ replies, xml )  Need Help?? 
Note that this is related to, but certainly not the same problem, as Minimum Graph Distance.
First, the introduction. Unless you slept through the 90s, the socalled Bacon number is the number of actors between an actor and Kevin Bacon, where the connection between susseccive actors is a movie they costarred in. Kevin Bacon's number would be 0, those that costarred 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 costarred 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 nearcenter people). But people still play the game with Bacon. To programmers, this task is pretty much optimizing the root node of a arbitarilybranched 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
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  mneylonpm@masemware.com  "You've left the lens cap of your mind on again, Pinky"  The Brain
Back to
Meditations

