Based on thread http://www.daniweb.com/forums/thread323401.html, I did this recursive version for comparision. Thanks for posters of the thread!
Recursive connection
from collections import defaultdict
data = ["Apollo 13, Kevin Bacon, Tom Hanks, Gary Sinise",
"Hollow Man, Elisabeth Shue, Kevin Bacon, Josh Brolin",
"A Few Good Men, Tom Cruise, Demi Moore, Jack Nicholson, Kevin Bacon",
"One Crazy Summer, John Cusack, Demi Moore",
"Da Vinci Code, Tom Hanks, Ian McKellen, Audrey Tautou"]
def connection(start,end, previous = set()):
""" Find recursively connection without using previous between actors start and end"""
if not previous:
previous.add(start)
common = in_movies[start] & in_movies[end] # directly in same movie
if common:
return '\t%s was in %r with %s.' % (start, ', '.join(common), end)
else:
for title in in_movies[start]: # all start actor's movie titles
for actor in actors_in[title]- previous- set([start]): # actors in this start actors film
res = connection(actor, end, previous | set([actor]))
if res:
return '\t%s was in %r with %s,\n%s' % (start, title, actor, res)
# a dictionary of titles --> actors
actors_in = defaultdict(set)
# a dictionary of actors --> movie titles
in_movies = defaultdict(set)
for movie_bio in data:
info = (word.strip() for word in movie_bio.split(","))
movie_name = next(info)
for actor in info: ## all actors in the movie
actors_in[movie_name].add(actor)
in_movies[actor].add(movie_name)
for pair in (("John Cusack", "Tom Hanks"),
('Audrey Tautou', 'Tom Cruise'),
('Elisabeth Shue', 'John Cusack'),
('Tom Cruise', 'Kevin Bacon'),
('John Cusack', 'Kevin Bacon'),
('Tom Cruise', 'Arnold Swartzenegger')
):
print 'Connection between %s and %s:\n' % pair,connection(*pair)
print
Gribouillis
1,391
Programming Explorer
Team Colleague
TrustyTony
888
pyMod
Team Colleague
Featured Poster
TrustyTony
888
pyMod
Team Colleague
Featured Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.