% MIU

:- use_module(library(lists)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% UPPGIFT 1

% Regel 1: om sista symbolen är i, lägger man till u
successor(X, Y) :-
    name(X, Z),
%    last(105,Z),
    last(Z, 105),
    append(Z, [117], A),
    name(Y, A),
    trace('regel 1:  ', Y).

% Regel 2: om strängen är mX omvandlas den till mXX
successor(X, Y) :-
    name(X,[109|Tail]),
    append([109|Tail], Tail, Z),
    name(Y, Z),
    trace('regel 2:  ', Y).

% Regel 3: om strängen är XiiiY omvandlas den till XuY
successor(X, Y) :-
    name(X, Z),
    append(H, [105,105,105|T], Z),
    append(H, [117|T], Z2),
    name(Y, Z2),
    trace('regel 3:  ', Y).

% Regel 4: om strängen är XuuY omvandlas den till XY
successor(X, Y) :-
    name(X, Z),
    append(H, [117,117|T], Z),
    append(H, T, Z2),
    name(Y, Z2),
    trace('regel 4:  ', Y).

final_state(muiui).

% Kommentera bort följande regel för att se spårutskrifter under sökningens gång
%trace(_, _) :- !.

trace(Name, Successor) :-
    write(Name), 
    write(Successor), 
    nl.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% UPPGIFT 2
%
% Nja, sökvägarna kan bli oändligt långa, i vilket fall det inte går. Detta
% beror på i vilken ordning de olika successor-reglerna är arrangerade; med
% den ordning som finns i uppgift 1 ovan, kommer sökningen inte att terminera
% förräns internminnet tar slut, och då med en krasch. Om reglerna i stället
% arrangerats i ordning 3, 2, 1, 4 så skulle sökningen ge en lösning.
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% UPPGIFT 3

% depth_limited_iterative_deepening(+Start, +MaxDepth, -Solution)
% Start is the initial state,
% MaxDepth is the maximal depth and
% Solution is a path from the initial state to the final state.
depth_limited_iterative_deepening(Start, MaxDepth, Solution) :-
    trace('axiom:    ', Start),
    depth_limited_iterative_deepening(Start, Solution, 0, MaxDepth).

depth_limited_iterative_deepening(Start, Solution, Depth, MaxDepth) :-
    Depth =< MaxDepth,
    trace('Djup: ', Depth),
    depth_limited(Start, [Start], Solution, Depth).

depth_limited_iterative_deepening(_, _, Depth, MaxDepth) :-
    Depth > MaxDepth,
    !, fail.

depth_limited_iterative_deepening(Start, Solution, Depth, MaxDepth) :-
    NewDepth is Depth + 1,
    depth_limited_iterative_deepening(Start, Solution, NewDepth, MaxDepth).

% Kommentera bort följande regel för att få alla lösningar för ett visst maximalt djup
depth_limited(State, _, [State], _) :-
    final_state(State).

depth_limited(State, Solution, [State], _) :-
    final_state(State),
    print_solution(Solution),
    fail.

depth_limited(State, History, [State|Solution], Depth) :-
    Depth > 0,
    successor(State, NewState),
    \+ member(NewState, History),
    NewDepth is Depth - 1,
    depth_limited(NewState,[NewState|History], Solution, NewDepth).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% UPPGIFT 4

solve(Start, Solution) :-
	breadthfirst([[Start]], Solution, [Start]).

breadthfirst([[Node|Path]|_],[Node|Path], _) :-
	final_state(Node).

breadthfirst([Path|Paths],Solution, History) :-
	extend(Path, NewPaths, History, NewHistory),
	append(Paths,NewPaths,Paths1),
	write('kön:         '), write(Paths1),nl,
	breadthfirst(Paths1,Solution, NewHistory).

extend([Node|Path], NewPaths, History, NewHistory) :-
	bagof([NewNode,Node|Path], 
	      (successor(Node,NewNode), \+ member(NewNode, History)), 
	      NewPaths),
	nl, write('expansioner: '), write(NewPaths),nl,
	write('historian:   '), write(History),nl,
	extend_history(NewPaths, History, NewHistory),
	!.
extend(_,[]). % bagof failed: Node has no successor

extend_history([], H, H).

extend_history([[FirstHead|_]|Rest], OldHistory, [FirstHead|NewHistoryTail]) :-
	\+ member(FirstHead, OldHistory), !,
	extend_history(Rest, OldHistory, NewHistoryTail).

extend_history([_|Rest], OldHistory, NewHistoryTail) :-
	extend_history(Rest, OldHistory, NewHistoryTail).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Snabbpredikat för oss som är slöa

so :- solve(mi, X), print_solution(X).
dl(X) :- dl(mi, X, _).
dl(St, M, So) :- depth_limited_iterative_deepening(St, M, So), print_solution(So).
l :- [inl2].
s(X,Y) :- successor(X,Y).
fs(X) :- final_state(X).

print_solution(Sol) :-
    write('En lösning är:'),
    nl,
    print_sol(Sol),
    nl.
print_sol([]).
print_sol([X|So]) :-
    write(X),nl,
    print_sol(So).