/*                      Artificial Intelligence                         */

:-dynamic agenda/4.

goalreached(f).
successor(X,Y) :- piece_cost(X,Y,_).

not(X) :- call(X), !, fail.
not(_).

eval(a,8).
eval(b,7).
eval(c,8).
eval(d,5).
eval(e,3).
eval(f,1).
eval(g,2).
eval(h,0).

cost([X],0).
cost([X,Y|L],E):-piece_cost(Y,X,E2),cost([Y|L],E3),E is E2 + E3.

piece_cost(a,b,3).
piece_cost(a,d,5).
piece_cost(b,c,1).
piece_cost(b,d,2).
piece_cost(d,e,2).
piece_cost(d,g,3).
piece_cost(e,f,2).
piece_cost(e,g,1).
piece_cost(g,h,2).


astarsearch(Start,Goalpathlist):-cleandatabase,
  add_state(Start,[]),repeatifagenda,
  pick_best_state(State,Pathlist),
  add_successors(State,Pathlist),
  agenda(State,Goalpathlist,C,D),
  retract(agenda(State,Goalpathlist,C,D)), measurework.

pick_best_state(State,Pathlist):-
  asserta(beststate(dummy,dummy,dummy)),
  agenda(S,SL,C,D),beststate(S2,SL2,D2),special_less_than(D,D2),
  retract(beststate(S2,SL2,D2)),asserta(beststate(S,SL,D)),fail.
pick_best_state(State,Pathlist):-beststate(State,Pathlist,D),
  retract(beststate(State,Pathlist,D)),not(D=dummy),!.

add_successors(State,Pathlist):-goalreached(State),!.
add_successors(State,Pathlist):-successor(State,Newstate),
  add_state(Newstate,Pathlist),fail.
add_successors(State,Pathlist):-
  retract(agenda(State,Pathlist,C,D)),
  asserta(usedstate(State,C)),fail.

add_state(Newstate,Pathlist):-cost([Newstate|Pathlist],Cnew),!,
  agenda_check(Newstate,Cnew),!,
  usedstate_check(Newstate,Pathlist,Cnew),!,
  eval(Newstate,Enew),D is Enew+Cnew,
  asserta(agenda(Newstate,[Newstate|Pathlist],Cnew,D)),!.
add_state(Newstate,Pathlist):-
  not(cost([Newstate|Pathlist],Cnew)),
  write('Warning:your cost function failed on path list'),
  write(Pathlist),nl,!.
add_state(Newstate,Pathlist):-not(eval(Newstate,Enew)),
  write('Warning: your evaluation function failed on state'),
  write(Newstate),nl,!.

agenda_check(S,C):-agenda(S,P2,C2,D2),C<C2,
  retract(agenda(S,P2,C2,D2)),!.
agenda_check(S,C):-agenda(S,P2,C2,D2),!,fail.
agenda_check(S,C).

usedstate_check(S,P,C):-usedstate(S,C2),C<C2,
  retract(usedstate(S,C2)),asserta(usedstate(S,C)),!,
  fix_agenda(S,P,C,C2).
usedstate_check(S,P,C):-usedstate(S,C2),!,fail.
usedstate_check(S,P,C).

fix_agenda(S,P,C,OldC):-agenda(S2,P2,C2,D2),
  replace_front(P,S,P2,Pnew),cost(Pnew,Cnew),
  Dnew is D2+C-OldC,retract(agenda(S2,P2,C2,D2)),
  asserta(agenda(S2,Pnew,Cnew,Dnew)),fail.

replace_front(P,S,P2,Pnew):-append(P3,[S|P4],P2),
  append(P,[S|P4],Pnew),!.


repeatifagenda.
repeatifagenda:-agenda(X,Y,Z,W),repeatifagenda.

special_less_than(X,dummy):- !.
special_less_than(X,Y):- X<Y.


cleandatabase:-checkabolish(agenda,4),checkabolish(usedstate,2),
  checkabolish(beststate,1),checkabolish(counter,1).

checkabolish(P,N):-abolish(P,N),!, functor(Q,P,N),assert((Q:-fail)).
checkabolish(P,N).

measurework:-countup(agenda(X,Y,C,D),NA),
  countup(usedstate(S,C),NB),write(NA),
  write(' incompetely examined state(s) and '),
  write(NB),write(' examined state(s).'),!.

countup(P,N):-asserta(counter(0)),call(P),counter(K),
  retract(counter(K)),K2 is K + 1,asserta(counter(K2)),fail.
countup(P,N):-counter(N),retract(counter(N)),!.