Skip to content

Instantly share code, notes, and snippets.

Created Nov 7, 2017
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