%% File:  spam.pl
%% Author: Z Dodds
%% Stolen from: Ran Libeskind-Hadas
%% 
%% Purpose:  Solves the alien, spampede, spam problem
%%
%% Explanation:  
%%
%% A mudder wants to get three things across campus to CS60, 
%% but only one thing can fit on her skateboard at a time...
%%
%% The three things are (1) a can of spam, (2) a CS 60 spampede, 
%% and (3) a three-eyed alien. There are three constraints:
%% 1.  The skateboard can accommodate at most one other item.
%% 2.  The spampede cannot be left alone with the spam.
%% 3.  The alien cannot be left alone with the spampede.

%% A configuration is represented by  a list of two lists:
%% the first list in the pair consists of the items on the west side
%% and the second list consists of the items on the east side.
%% The mudder is considered to be an item.  The lists are kept in sorted
%% order such that mudder precedes alien precedes spampede precedes spam.

%% Thus the initial configuration is
%% [ [mudder, alien, spampede, spam], [] ]

%% First, some basic list predicates.

%% These rules are provided in case they're of use...



member(A, [A | _]).                 %% member predicate
member(A, [_ | R]) :- member(A, R).

perm([],[]).                        %% permutation generator (on right side only)
perm(L,[F|R]) :- nonvar(L), append( BF, [F|AF], L ), append( BF, AF, Other ), perm( Other, R ).

%% The sorted ordering for a configuration is stipulated here.

precedes(mudder, alien).            %% individual facts
precedes(alien, spampede).
precedes(spampede, spam).

ordered(X, Y) :- precedes(X, Y).    %% just for two elements
ordered(X, Y) :- precedes(X, Z), ordered(Z, Y).

sorted([]).                         %% for lists of elements
sorted([_]).
sorted([F,S|R]) :- ordered(F,S), sorted([S|R]).

%% A side is ok with the mudder or without a predator/prey pair:

ok(L) :- sorted(L), (member(mudder, L) ; \+predatorprey(L)).
predatorprey(L) :- member(alien, L), member(spampede, L).
predatorprey(L) :- member(spampede, L), member(spam, L).

%% The final configuration is defined here.

final([ [], [mudder, alien, spampede, spam] ]).

%% a dynamically defined predicate that will keep track of
%% states (configurations) we have already explored...

:- dynamic marked/1.      

%% what it means for a list of moves to solve the puzzle...

%% C is a configuration. 
solve(C, []) :- final(C).   %% you can retractall(marked(_)) after...

solve(C, [Move | R]) :-     %% Move is the next move to make
    [W, E] = C,             %% C is the [ West, East ] pair
    ok(W), ok(E),           %% keeping everything in order
    \+marked(C),            %% "if" we haven't visited this C
    assert(marked(C)),      %% we mark it
    valid(C, Move, NewC),   %% enforce that it's valid
    solve(NewC, R).         %% and solve the rest of the puzzle...


%% what it means for each move to be valid...
%%   Wb, Eb == west items before, east items before
%%   Wa, Ea == west items after, east items after

valid([Wb, Eb], mudder_goes_east, [Wa, Ea]) :-
    perm([mudder|Eb],Ea), perm(Wb,[mudder|Wa]), ok(Wa), ok(Ea).

valid([Wb, Eb], mudder_goes_west, [Wa, Ea]) :-
    perm(Eb,[mudder|Ea]), perm([mudder|Wb],Wa), ok(Wa), ok(Ea).

valid([Wb, Eb], mudder_takes_alien_east, [Wa, Ea]) :-
    perm([mudder,alien|Eb],Ea), perm(Wb,[mudder,alien|Wa]), ok(Wa), ok(Ea).

valid([Wb, Eb], mudder_takes_alien_west, [Wa, Ea]) :-
    perm(Eb,[mudder,alien|Ea]), perm([mudder,alien|Wb],Wa), ok(Wa), ok(Ea).

valid([Wb, Eb], mudder_takes_spampede_east, [Wa, Ea]) :-
    perm([mudder,spampede|Eb],Ea), perm(Wb,[mudder,spampede|Wa]), ok(Wa), ok(Ea).

valid([Wb, Eb], mudder_takes_spampede_west, [Wa, Ea]) :-
    perm(Eb,[mudder,spampede|Ea]), perm([mudder,spampede|Wb],Wa), ok(Wa), ok(Ea).

valid([Wb, Eb], mudder_takes_spam_east, [Wa, Ea]) :-
    perm([mudder,spam|Eb],Ea), perm(Wb,[mudder,spam|Wa]), ok(Wa), ok(Ea).

valid([Wb, Eb], mudder_takes_spam_west, [Wa, Ea]) :-
    perm(Eb,[mudder,spam|Ea]), perm([mudder,spam|Wb],Wa), ok(Wa), ok(Ea).

  /*

  solve( [ [mudder,spampede], [alien, spam] ], [mudder_takes_spampede_east] ).

  */