Pathologically Eclectic Rubbish Lister PerlMonks

### Comment on

 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!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• 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
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
 [holli]: You see, I have a friend whose daughter has been damaged seriously because she wasn't vaccinated against measles. (Her mother being anti-vaxx). [LanX]: Contrary to Olivia newton John I don't like physical confrontations ... [LanX]: Oh, you spread measles in your saliva? [LanX]: ... and why did you bite hos daughter? [LanX]: *his [holli]: And this guy was also Anti-Vaxx and I just snapped. I shoed him all over the yard [james28909]: biting between the legs? now thats my kind of religion. [holli]: and back into the building, saw him later peeking out of the window looking scared. It was hilarious. [james28909]: wish i could stay and chat. i have an unsuspecting client to give an estimate to. muhhahaha

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (10)
As of 2017-12-13 18:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What programming language do you hate the most?

Results (373 votes). Check out past polls.

Notices?