Skip to content

Instantly share code, notes, and snippets.

Created November 7, 2017 18:59
What would you like to do?
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