/** -----------------------------------------------------------------
    CSC384, Fall 2011, Assignment 1 submission file (electronic part)
--------------------------------------------------------------------- */

/* ------------------------------------------------------ */
% Name:
% Student Number:
/* ------------------------------------------------------ */


/* load the three search algorithms. Please do NOT change these lines */
:- ensure_loaded('astar.pl').
:- ensure_loaded('astarCC.pl').
:- ensure_loaded('idastar.pl').


/* ------------------------------------------------------- */

/* successors( +State, -Neighbors)

   Neighbors is a list of elements (Cost, NewState) where
   NewState is a state reachable from State by one action and
   Cost is the cost for that corresponding action (=1 in our
   case)
*/   
% successors( State, Succs ) :-
% 	...



/* ------------------------------------------------------- */


/* equality(+S1, +S2)

   holds if and only S1 and S2 describe the same state
*/      
%equality( ...



/* ------------------------------------------------------- */

/* hfn_null( +State, -V)

   V is the null heuristic for State (=0 irrelevant of the state)
   The implementation is given below.
*/
hfn_null(_State, 0).



/* hfn_misplaced( +State, -V)

   V is the number of misplaced tiles in State   
*/
% hfn_misplaced( State, V) :-  ...



/* hfn_manhattan( +State, -V)

   V is the sum over the manhattan distances between the current
   and the designated position of each tile.
*/
% hfn_manhattan( State, V ) :-  ...




/* ------------------------------------------------------- */


/* init( +Name, -State)
   State is the initial state for problem Name.
   please uncomment the followings and compelte the defintions.
*/
% init(a,  ...

% init(b,  ...

% init(c,  ...

% init(d, ...




/* ------------------------------------------------------- */

/* goal( +State )
   holds if and only if State is a goal state
*/   


% goal(S) :- ...





/* ------------------------------------------------------- */






/** ---------------------------------------------------------
  calling the search algorithms. Please do NOT change these.
  ---------------------------------------------------------- */

runastar(ProblemName, HFN) :-
	init(ProblemName, Init),
	astar(Init, successors, goal, HFN, Path, equality),
	writeln(Path).

runastarCC(ProblemName, HFN) :-
	init(ProblemName, Init),
	astarCC(Init, successors, goal, HFN, Path, equality),
	writeln(Path).

runidastar(ProblemName, HFN) :-
	init(ProblemName, Init),
	idastar(Init, successors, goal, HFN, Path, equality),
	writeln(Path).



/** ----------------------------------------------------------
    Tools
---------------------------------------------------------- */

/** memb( +List, ?Index, ?Element)
given a list List holds if and only if Index is the/an index
(starting from 0) of Element in List. */
memb( [E|_L], 0, E).
memb( [_|L], N, E) :- memb( L, N2, E), N is N2+1.

/** membGrid( +Grid, ?Position, ?Element)
given a grid structure Grid (represented as a list of rows) holds
if and only if Position is a list [X, Y] representing the/a
position (starting from [0, 0], X being the column, Y the row) of
Element in Grid. */
membGrid( Grid, [X,Y], Element) :-
        memb( Grid, X, ListX),
        memb( ListX, Y, Element).


/** ----------------------------------------------------------
    Auxiliary, only for convenience
---------------------------------------------------------- */

/**
pretty print a grid, given as a list of rows
*/
printGrid( G ) :-
        findMaxStringLength( G, MaxLength),
        printGrid( G, MaxLength).

/**
pretty print a grid
printGrid( G, T) prints the grid G and assumes string
length of the longest entry will be T
*/
printGrid( [], _T ).
printGrid( [H|L], T ) :-
        printList(H, T),
        printGrid(L, T).

/**
auxiliary: find longest string length in a possibly
multidimensional matrix.
findMaxStringLength( M, Length): Length is the value of
the longest string length anywhere in the matrix M.
*/
findMaxStringLength( [], 0) :- !.
findMaxStringLength( [H|L], Max) :-
        !,
        findMaxStringLength( H, M),
        findMaxStringLength( L, ML),
        (
          ML > M
        ->
          Max = ML
        ;
          Max = M
        ).
findMaxStringLength( X, L) :-
        atom_chars(X, List),
        length( List, L).

/**
pretty print a list
printList( L, T) prints the list L and assumes string
length of the longest entry will be T.
*/
printList([], _T) :- nl.
printList([H|L], T) :-
        atom_chars(H, HList),
        length( HList, HLength),
        (
          HLength < T
        ->
          Diff = T - HLength,
          makeSpaces( Diff, Spaces),
          append( Spaces, HList, HList2)
        ;
          HList2 = HList
        ),
        atom_chars( H2, HList2),
        write(H2), write(' '), printList(L, T).

/**
makeSpace( N, L): L is a list of N spaces (' ')
*/
makeSpaces( 0, []) :- !.
makeSpaces( N, [' '|L]) :-
        N2 is N-1,
        makeSpaces( N2, L).