Prolog code to calculate the Bacon Number (or the "Six Degrees of Kevin Bacon" game)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% 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