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.