%Solution to problem 3
%This heuristic creates a dynamic movement preference system, based on the previous movements. Simply, the preference
%is by default the last direction of movement in a straight path, but changes by 90° when an intersection is encountered.
%The preference changing system is also designed so that if a dead end is encountered, the preference order reverses to
%prevent accidental looping at an end point. I see this as an improvement over other solutions, because it helps
%to minimize any looping in the solution by adding a sense of randomness to the solution. However, for simpler
%maze problems this may create a round about solution in some instances, in which a longer solution might be produced.
%This could be improved with a preference system weighted towards the end point of the maze, or at least generally one
%where movements in that direction are prefered. 

%I chose this heuristic since I thought that the best way to travel a maze consistently without any knowledge of
%where the end point is would be to not necessaily travel in a straight line, since this could result in loop where
%there are two paths on opposite sides of an intersection which lead to a dead end. This fixes that by breaking up
%straight sections, and forcing a sense of controlled randomness in the solution. In the aspects of this maze, 
%the heuristic worked well in acomplishing its goal, despite the solution not being super direct. It would likely
%also work well in larger puzzles, but I believe it would be possible to rig a maze exploiting the order that
%preferences are assigned, possibly rendering this heuristic useless. However, this would only be a very small percentage
%of select puzzles.

% Row 1
wall([X,1]) :- X =\= 2.
% Row 2
wall([X,2]) :- X = 1; X = 4; X = 6.
% Row 3
wall([X,3]) :- X = 1; X = 2; X = 6.
% Row 4
wall([X,4]) :- X =\= 3,X =\= 5.
% Row 5
wall([X,5]) :- X = 1; X = 4; X = 6.
% Row 6
wall([X,6]) :- X =\= 2.
% Start / end
start([2,1]).
end([2,6]).
% Maze Size
mazeSize([6,6]).

badSpot([X,Y]) :- wall([X,Y]).
badSpot([X,Y]) :- X < 1; Y < 1.
badSpot([X,Y]) :- mazeSize([W, H]), (X > W; Y > H).

%up
move([CurrX, CurrY], [CurrX, NextY], up) :- NextY is CurrY - 1.
%down
move([CurrX, CurrY], [NextX, NextY], down) :- NextY is CurrY + 1, NextX = CurrX.
%left
move([CurrX, CurrY], [NextX, NextY], left) :- NextY = CurrY, NextX is CurrX - 1.
%right
move([CurrX, CurrY], [NextX, NextY], right) :- NextY = CurrY, NextX is CurrX + 1.

%peek: Check if movement leads to a bad spot.
peek(Location, Direction, Number, NewNumber):-
	move(Location, NewLocation, Direction),
	\+badSpot(NewLocation),
	NewNumber is Number + 1.
	
peek(Location, Direction, Number, NewNumber):-
	move(Location, NewLocation, Direction),
	badSpot(NewLocation),
	NewNumber = Number.

%inspect: Determine if location is in a path, at an intersection, or at a dead end.
inspect(Location, Result) :- 
	Number = 0,
	peek(Location, up, Number, NewNumber),
	peek(Location, down, NewNumber, NewNumber2),
	peek(Location, left, NewNumber2, NewNumber3),
	peek(Location, right, NewNumber3, Final),
	Final > 2,
	Result = intersection.
	
inspect(Location, Result) :- 
	Number = 0,
	peek(Location, up, Number, NewNumber),
	peek(Location, down, NewNumber, NewNumber2),
	peek(Location, left, NewNumber2, NewNumber3),
	peek(Location, right, NewNumber3, Final),
	Final = 2,
	Result = path.
	
inspect(Location, Result) :-
	%Exception so that start is treated as a path.
	%Otherwise, solution may loop at start.
	start(Location),
	Result = path.

inspect(Location, Result) :- 
	Number = 0,
	peek(Location, up, Number, NewNumber),
	peek(Location, down, NewNumber, NewNumber2),
	peek(Location, left, NewNumber2, NewNumber3),
	peek(Location, right, NewNumber3, Final),
	Final = 1,
	Result = end.

%select: Choose movement based on current preferences and locations of bad spots
select(Current, New, A, _, _, _, A) :- move(Current, New, A), \+badSpot(New).
select(Current, New, _, B, _, _, B) :- move(Current, New, B), \+badSpot(New).
select(Current, New, _, _, C, _, C) :- move(Current, New, C), \+badSpot(New).
select(Current, New, _, _, _, D, D) :- move(Current, New, D), \+badSpot(New).

%solve the maze.
solve(CurrentLocation, Path, _, _, _, _) :- end(CurrentLocation), Path = [CurrentLocation].

solve(CurrentLocation, Path, A, B, C, D) :-
	inspect(CurrentLocation, path),
	select(CurrentLocation, NewLocation, A, B, C, D, Dir),
	Dir = A,
    solve(NewLocation, RestOfPath, A, B, C, D), 
    Path = [CurrentLocation | RestOfPath].
	
solve(CurrentLocation, Path, A, B, C, D) :-
	inspect(CurrentLocation, path),
	select(CurrentLocation, NewLocation, A, B, C, D, Dir),
	Dir = B,
    solve(NewLocation, RestOfPath, B, A, D, C), 
    Path = [CurrentLocation | RestOfPath].

solve(CurrentLocation, Path, A, B, C, D) :-
	inspect(CurrentLocation, path),
	select(CurrentLocation, NewLocation, A, B, C, D, Dir),
	Dir = C,
    solve(NewLocation, RestOfPath, C, A, D, B), 
    Path = [CurrentLocation | RestOfPath].
	
solve(CurrentLocation, Path, A, B, C, D) :-
	inspect(CurrentLocation, intersection),
	select(CurrentLocation, NewLocation, B, C, A, D, Dir),
	Dir = B,
    solve(NewLocation, RestOfPath, B, C, A, D), 
    Path = [CurrentLocation | RestOfPath].
	
solve(CurrentLocation, Path, A, B, C, D) :-
	inspect(CurrentLocation, intersection),
	select(CurrentLocation, NewLocation, B, C, A, D, Dir),
	Dir = C,
    solve(NewLocation, RestOfPath, C, B, A, D), 
    Path = [CurrentLocation | RestOfPath].
	
solve(CurrentLocation, Path, A, B, C, D) :-
	inspect(CurrentLocation, end),
	select(CurrentLocation, NewLocation, D, C, B, A, _),
    solve(NewLocation, RestOfPath, D, C, B, A), 
    Path = [CurrentLocation | RestOfPath].

%Check which direction you're facing to start
solve() :- start(Start), start([X,_]), X = 1, solve(Start, Path, right, up, down, left), write(Path).
solve() :- start(Start), start([_,Y]), Y = 1, solve(Start, Path, down, right, left, up), write(Path).
solve() :- start(Start), start([X,_]), mazeSize([SX,_]), X = SX, solve(Start, Path, left, up, down, right), write(Path).
solve() :- start(Start), start([_,Y]), mazeSize([_,SY]), Y = SY, solve(Start, Path, up, right, left, down), write(Path).


drawCell(Column, Row, _) :- wall([Column, Row]), write("X"), !.
drawCell(Column, Row, _) :- start([Column, Row]), write("S"), !.
drawCell(Column, Row, _) :- end([Column, Row]), write("E"), !.
drawCell(Column, Row, Path) :- member([Column, Row], Path), write("P"), !.
drawCell(_, _, _) :- write("O").

drawRow(Row, Path) :- drawCell(1, Row, Path), tab(1), drawCell(2, Row, Path), tab(1), 
        drawCell(3, Row, Path), tab(1), drawCell(4, Row, Path), tab(1), 
        drawCell(5, Row, Path), tab(1), drawCell(6, Row, Path), nl.
                
draw :- drawRow(1, []), drawRow(2, []), drawRow(3, []), drawRow(4, []), drawRow(5, []), 
        drawRow(6, []).
draw(Path) :- drawRow(1, Path), drawRow(2, Path), drawRow(3, Path), drawRow(4, Path),
        drawRow(5, Path), drawRow(6, Path).