%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CS 3304 Project 3                   %
% Suleiman Souhlal <ssouhlal@vt.edu>  %
% 904344811                           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Possible move given a set of drivers, and a set of things to move
possible_move(Drivers, All, Move) :- member(Driver, Drivers), member(Driver, All), (member(Other, All), not(Other = Driver), append([Driver], [Other], Move); append([Driver], [], Move)).

% Given a goal state, get the possible left and right parts of an initial state
make_initial([X], [X], []).
make_initial([X], [], [X]) :- !.
make_initial([X|Y], [X|LL], R) :- make_initial(Y, LL, R).
make_initial([X|Y], LL, [X|RL]) :- make_initial(Y, LL, RL).
make_initial([], [], []) :- !.

% Left and right part of a state
left_state([X|_], X).
right_state(X, Y) :- append(_, [Y], X).

% is the state invalid, given a set of invalid combinations?
invalid([X|_], State) :- permutation(X, State), !.
invalid([_|Y], State) :- invalid(Y, State).

% are two lists equal?
list_equal(X, Y) :- permutation(X, Y).

% are two states equal?
state_equal(X, Y) :- left_state(X, LX), left_state(Y, LY), list_equal(LX, LY),
	right_state(X, RX), right_state(Y, RY), list_equal(RX, RY), !.

% sort a plan step
sortstep([],[]).
sortstep([M|T],[M|ST]) :- sort(T,ST).

% sort all the steps in a plan
sortsteps([],[]).
sortsteps([X|Y],[T|Z]) :- sortstep(X,T), sortsteps(Y,Z).

% move to the left, given the initial state, the goal state, the invalid combinations, the drivers, the maximum plan length, and the plan
move_left(Initial_state, 
	  Goal_State,
	  Invalid_Combinations,
	  Drivers,
	  Max_Plan_Length,
	  Old_Plan,
	  New_Plan) :- 
	state_equal(Initial_state, Goal_State), New_Plan = Old_Plan; % have we reached the goal?
	not(Max_Plan_Length = 0), % make sure we can go on
	left_state(Initial_state, Left), 
	right_state(Initial_state, Right),
	possible_move(Drivers, Right, Move), % is the move possible?
	subtract(Right, Move, Resulting_Right),
	union(Left, Move, Resulting_Left),
	not(invalid(Invalid_Combinations, Resulting_Right)), % the right side after the move has to be valid
	append([go_left], [Move], Move2),
	flatten([Move2], Move3),
	append(Old_Plan, [Move3], Curr_Plan), % add the move to the plan
	New_Plan_Length is  Max_Plan_Length - 1,
	move_right([Resulting_Left, Resulting_Right], Goal_State, Invalid_Combinations, Drivers, New_Plan_Length, Curr_Plan, New_Plan). % move to the right

% move to the left, given the initial state, the goal state, the invalid combinations, the drivers, the maximum plan length, and the plan
move_right(Initial_state, 
	  Goal_State,
	  Invalid_Combinations,
	  Drivers,
	  Max_Plan_Length,
	  Old_Plan,
	  New_Plan) :- 
	state_equal(Initial_state, Goal_State), New_Plan = Old_Plan; % have we reached the goal?
	not(Max_Plan_Length = 0), % make sure we can go on
	left_state(Initial_state, Left),
	right_state(Initial_state, Right),
	possible_move(Drivers, Left, Move), % is the move possible?
	subtract(Left, Move, Resulting_Left),
	union(Right, Move, Resulting_Right),
	not(invalid(Invalid_Combinations, Resulting_Left)), % the right side after the move has to be valid
	append([go_right], [Move], Move2),
	flatten([Move2], Move3),
	append(Old_Plan, [Move3], Curr_Plan), % add the move to the plan
	New_Plan_Length is  Max_Plan_Length - 1,
	move_left([Resulting_Left, Resulting_Right], Goal_State, Invalid_Combinations, Drivers, New_Plan_Length, Curr_Plan, New_Plan). % move to the left

% are the initial state, goal state, and the plan all not bound?
all_vars(IS, GS, P) :- not(ground(IS)), not(ground(GS)), not(ground(P)).

% is the given state valid, given the set of invalid states?
valid_state(S, I) :- nonvar(S), left_state(S, X), right_state(S, Y), intersection(X, Y, []), not(invalid(I, X)), not(invalid(I, Y)). % nothing can be on both sides.
valid_state(S, _) :- var(S).

% is the input valid?
valid_input(IS, GS, I, D, PL, P) :- nonvar(I), nonvar(D), nonvar(PL), integer(PL), not(PL < 0), not(all_vars(IS, GS, P)), is_list(D), is_list(I), (valid_state(IS, I), valid_state(GS, I)).

% is the initial state valid?
check_initial([X, Y], _) :- ground([X, Y]). % no problem if it was given to us
check_initial([X, Y], Goal) :- not(ground([X, Y])), flatten(Goal, Z), make_initial(Z, X2, Y2), sort(X2, X), sort(Y2, Y).

% sort a state
sort_state([X, Y], [S, T]) :- not(ground([S, T])), sort(X, S), sort(Y, T).
sort_state([_, _], [S, T]) :- ground([S, T]). % don't sort if it was given

plan_transport( Initial_State,
                Goal_State,
                Set_of_Invalid_Combinations,
                Drivers,
                Max_Plan_Length,
                Plan ) :-
	check_initial(Initial_State, Goal_State), % check the initial state
	valid_input(Initial_State, Goal_State, Set_of_Invalid_Combinations, Drivers, Max_Plan_Length, Plan), % check the input
	(ground(Goal_State), move_right(Initial_State, Goal_State, Set_of_Invalid_Combinations, Drivers, Max_Plan_Length, [], SP), sortsteps(SP, Plan); % don't sort the goal state, if it was given to up
	    not(ground(Goal_State)), move_right(Initial_State, GS, Set_of_Invalid_Combinations, Drivers, Max_Plan_Length, [], SP), sortsteps(SP, Plan), sort_state(GS, Goal_State)). % sort the goal state if it wasn't given
