Prolog code to calculate the Bacon Number (or the "Six Degrees of Kevin Bacon" game)
%% Kevin Bacon movies | |
cast(['Kevin Bacon', 'Lori Singer', 'John Lithgow', 'Dianne Wiest']). %% Footloose (1984) | |
cast(['Tom Cruise', 'Jack Nicholson', 'Demi Moore', 'Kevin Bacon']). %% A Few Good Men (1992) | |
cast(['Tom Hanks', 'Bill Paxton', 'Kevin Bacon', 'Gary Sinise']). %% Apollo 13 (1995) | |
%% Tom Cruise movies | |
cast(['Tom Cruise', 'Kelly McGillis', 'Val Kilmer', 'Anthony Edwards']). %% Top Gun (1985) | |
cast(['Tom Cruise', 'Cuba Gooding Jr.', 'Renée Zellweger', 'Kelly Preston']). %% Jerry Maguire (1996) | |
cast(['Tom Cruise', 'Rebecca De Mornay', 'Joe Pantoliano', 'Richard Masur']). %% Risky Business (1983) | |
%% Val Kilmer movies | |
cast(['Val Kilmer', 'Meg Ryan', 'Kyle MacLachlan', 'Frank Whaley']). %% The Doors (1991) | |
cast(['Val Kilmer', 'Tommy Lee Jones', 'Jim Carrey', 'Nicole Kidman']). %% Batman Forever (1995) | |
%% Renée Zellweger movies | |
cast(['Jim Carrey', 'Renée Zellweger', 'Anthony Anderson', 'Mongo Brownlee']). %% Me, Myself & Irene (2000) | |
cast(['Renée Zellweger', 'Gemma Jones', 'Celia Imrie', 'James Faulkner']). %% Bridget Jones's Diary (2001) | |
%% tells whether two actors starred together in some movie | |
co_starred(X, Y) :- cast(L), member(X, L), member(Y, L), X \== Y. | |
%% depth-first-search algorithm | |
next_node(C, N, P) :- | |
co_starred(C, N), | |
\+ member(N, P). | |
dfs(G, G, _, [G]). | |
dfs(S, G, V, [S|P]) :- | |
next_node(S, NN, V), | |
dfs(NN, G, [NN|V], P). | |
%% counts the edges in a path represented by a list | |
count_edges([_], 0). | |
count_edges([_|T], N) :- | |
count_edges(T, N1), N is N1 + 1. | |
bacon_number(X, N) :- | |
setof((L, P), (dfs('Kevin Bacon', X, [], P), length(P, L)), [(_, SP)|_]), | |
count_edges(SP, N). |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment