Laba_Ebanaya

:- dynamic был/1, thread_local.
:- dynamic rpath/2.

route(вильнюс, брест, 531).
route(витебск, брест, 638).
route(витебск, вильнюс, 360).
route(воронеж, витебск, 869).
route(воронеж, волгоград, 581).
route(волгоград, витебск, 1455).
route(витебск, нижний_новгород, 911).
route(вильнюс, даугавпилс, 211).
route(калининград, брест, 699).
route(калининград, вильнюс, 333).
route(каунас, вильнюс, 102).
route(киев, вильнюс, 734).
route(киев, житомир, 131).
route(житомир, донецк, 863).
route(житомир, волгоград, 1493).
route(кишинев, киев, 467).
route(кишинев, донецк, 812).
route(санкт_петербург, витебск, 602).
route(санкт_петербург, калининград, 739).
route(санкт_петербург, рига, 641).
route(москва, казань, 815).
route(москва, нижний_новгород, 411).
route(москва, минск, 690).
route(москва, донецк, 1084).
route(москва, санкт_петербург, 664).
route(мурманск, санкт_петербург, 1412).
route(мурманск, минск, 2238).
route(орел, витебск, 522).
route(орел, донецк, 709).
route(орел, москва, 368).
route(одесса, киев, 487).
route(рига, каунас, 267).
route(таллин, рига, 308).
route(харьков, киев, 471).
route(харьков, симферополь, 639).
route(ярославль, воронеж, 739).
route(ярославль, минск, 940).
route(уфа, казань, 525).
route(уфа, самара, 461).

road(X, Y, R) :- route(X, Y, R).
road(X, Y, R) :- route(Y, X, R).

prepend(L, X, [X | L]).

bfs([[Goal | Rest] | _], _, Goal, [Goal | Rest]).

bfs([[State | Path] | Queue], Visited, Goal, Solution) :-
    findall(X, road(State, X, _), Next),
    subtract(Next, Visited, Next1),
    maplist(prepend([State | Path]), Next1, Next2),
    append(Queue, Next2, Queue2),
    append(Next1, Visited, Visited1),
    bfs(Queue2, Visited1, Goal, Solution).


bfs(Start, Goal, Path) :-
    bfs([[Start]], [Start], Goal, Path1),
    reverse(Path1, Path).

bds(Start, Goal, Path) :-
    bds_b([[Start]], [[Goal]], [Start], [Goal], Path).

bds_check([[BeginState | BeginPath] | BeginQueue], [[EndState | EndPath] | EndQueue], VisitedBegin, VisitedEnd, Solution) :-
    intersection(VisitedBegin, VisitedEnd, Intersection),
    Intersection \== [],
    road(BeginState, EndState, _),
    flatten(BeginPath, BNPath),
    reverse(BNPath, BPath),
    flatten(EndPath, EPath),
    append(BPath, EPath, Solution).

bds_b(BeginQueue, EndQueue, VisitedBegin, VisitedEnd, Solution) :-
    bds_check(BeginQueue, EndQueue, VisitedBegin, VisitedEnd, Solution), !.

bds_b([[BeginState | BeginPath] | BeginQueue], EndQueue, VisitedBegin, VisitedEnd, Solution) :-
    findall(X, road(BeginState, X, _), NextBegin),
    subtract(NextBegin, VisitedBegin, Next1Begin),
    maplist(prepend([BeginState, BeginPath]), Next1Begin, Next2Begin),
    append(BeginQueue, Next2Begin, BeginQueue2),
    append(Next1Begin, VisitedBegin, VisitedBegin1),
    bds_e(BeginQueue2, EndQueue, VisitedBegin1, VisitedEnd, Solution).

bds_e(BeginQueue, EndQueue, VisitedBegin, VisitedEnd, Solution) :-
    bds_check(BeginQueue, EndQueue, VisitedBegin, VisitedEnd, Solution), !.

bds_e(BeginQueue, [[EndState | EndPath] | EndQueue], VisitedBegin, VisitedEnd, Solution) :-
    findall(Y, road(EndState, Y, _), NextEnd),
    subtract(NextEnd, VisitedEnd, Next1End),
    maplist(prepend([EndState, EndPath]), Next1End, Next2End),
    append(EndQueue, Next2End, EndQueue2),
    append(Next1End, VisitedEnd, VisitedEnd1),
    bds_b(BeginQueue, EndQueue2, VisitedBegin, VisitedEnd1, Solution).



dfs(Start, Start, _, [Start]).

dfs(Start, Goal, Visited, [Start | Path]) :-
    road(Start, V, _),
    maplist(dif(V), Visited),
    dfs(V, Goal, [V | Visited], Path).



dfs(Start, Goal, Path) :- dfs(Start, Goal, [Start], Path).

dls(Start, Start, _, [Start], _, _).

dls(Start, Goal, Visited, [Start | Path], Depth, Acc) :-
    Depth1 is Acc + 1,
    Depth1 < Depth,
    road(Start, V, _),
    maplist(dif(V), Visited),
    dls(V, Goal, [V | Visited], Path, Depth,  Depth1).



dls(Start, Goal, Depth, Path) :- dls(Start, Goal, [Start], Path, Depth, 0).

eds(Start, Start, _, [Start], Depth, Acc) :-
    Depth == Acc.

eds(Start, Goal, Visited, [Start | Path], Depth, Acc) :-
    Depth1 is Acc + 1,
    Depth1 =< Depth,
    road(Start, V, _),
    maplist(dif(V), Visited),
    eds(V, Goal, [V | Visited], Path, Depth,  Depth1).

ids(Start, Goal, Path) :-
    ids(Start, Goal, Path, 1).

ids(Start, Goal, Path, Acc) :-
    eds(Start, Goal, [Start], Path, Acc, 0).

ids(Start, Goal, Path, Acc) :-
    Acc1 is Acc + 1,
    ids(Start, Goal, Path, Acc1).

gcs(Start, Goal) :-
    gcs(Start, Goal, [Start], 0).

gcs(Goal, Goal, Path, Cost) :-
    writeln(Path),
    writeln(Cost).

gcs(Current, Goal, Path, Cost) :-
    findall(C, (road(Current, X, C), not(member(X, Path))), R),
    R \== [],
    sort(R, RS),
    gcs(Current, Goal, Path, Cost, RS).

gcs(Current, Goal, Path, Cost, []) :- fail.

gcs(Current, Goal, Path, Cost, [H | T]) :-
    CityCost is H,
    road(Current, City, CityCost),
    append(Path, [City], Path1),
    Cost1 is Cost + CityCost,
    (gcs(City, Goal, Path1, Cost1) ; gcs(Current, Goal, Path, Cost, T)).

shorterPath([H|Path], Dist) :-
    rpath([H|T], D), !, Dist < D,
    retract(rpath([H|_],_)),
    assert(rpath([H|Path], Dist)).

shorterPath(Path, Dist) :-
    assert(rpath(Path,Dist)).

traverse(From, Path, Dist) :-
    road(From, T, D),
    not(memberchk(T, Path)),
    Dist1 is Dist + D,
    shorterPath([T,From|Path], Dist1),
    traverse(T,[From|Path],Dist1).

traverse(From) :-
    retractall(rpath(_,_)),
    traverse(From,[],0).

traverse(_).

make_heuristic(From) :-
    traverse(From).

astar(Start, Goal) :-
    make_heuristic(Goal),
    find_rpath(Start, Goal).

find_rpath(Start, Goal) :-
    rpath([Start | T], Cost),
    last(T, Goal),
    writeln([Start | T]),
    writeln(Cost).