Thor's CS Problem of the Fortnight

Meandering through computer science since 1827

Last Fortnight's Question: Imagine that you are the leader of a party of glorious fantasy adventurers. As a part of your job, you routinely need to make the tough decisions about how to split up the various magical items that your stalwart comrades find. Suppose you've found three magical items: a Fireburst Sword +1, a Wand of Striking, and a Shield of Hope. How many ways are there to split these items up among your party? In general, how can you find out how many ways there are to split up items? Remember: no cutting items in half!

Its Answer: This question is a relatively thin veneer over the Set Partition problem. To restate: Given a set of elements, how many ways can it be split up into subsets? For example, the set {sword, wand, shield} can be partitioned as:

    {sword}, {wand}, {shield}
    {sword}, {wand, shield}
    {wand}, {sword, shield}
    {shield}, {sword, wand}
    {sword, wand, shield}

The number of partitions of a set with n elements is the nth Bell number. The 3rd Bell number is 5, so there are 5 ways to split up three magical items. These numbers can be generated via a Bell Triangle - a name, I'm told by an anonymous source, that was suggested by University of Waterloo Department of Computer Science Professor and Distinguished Scientist Jeffrey Outlaw Shallit. With a correctly created Bell Triangle, the Bell numbers starting from zero go down the left-hand side. To generate the Bell Triangle, put the number one on the first row of the page. Then, repeat the following steps: Start a new row. Put the rightmost number in the previous row at the start of the page. Then write each number of the row by summing up the number to the left of it and the number diagonally up and left of it. Here's an example:

---------
1
---------
1
1 2
---------
1
1 2
2 3 5
---------
1
1 2
2 3 5
5 7 10 15
---------

As we can see, B₀=1, B₁=1, B₂=2, and B₃=5, so there are 5 ways to split up the items.

This Fortnight's Question: A famous trivia game is the "Kevin Bacon Game". Its premise is that any actor in the world can be linked through film roles to Kevin Bacon. In the game, players start with an actor and try and create links through movie associations. For example: Val Kilmer was in Top Gun with Tom Cruise, and Tom Cruise was in A Few Good Men with Kevin Bacon. Reaching Bacon represents the end of the chain. Given a movie database containing actors and the movies they starred in, how would you check whether or not the game's premise holds for every actor in the database?

Thor