Beefy Boxes and Bandwidth Generously Provided by pair Networks vroom
P is for Practical
 
PerlMonks  

Comment on

( #3333=superdoc: 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 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

In reply to (Golf) Minimizing the Bacon Number by Masem

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (4)
    As of 2014-04-20 03:34 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      April first is:







      Results (485 votes), past polls