:- module(task2, []).
:- use_module(library(clpfd)).

main :-
    writeln('task 2.1'),
    findall([Path, TotalDistance], (plan(c1, c2, Path, TotalDistance)), Solutions),
    forall(member([Path, Distance], Solutions), (
        atomic_list_concat(Path, ' -> ', PathStr),
        format('Solution: ~w (distance: ~w)~n', [PathStr, Distance])
    )),
    writeln('task 2.2'),
    findall([Path, TotalDistance], (bestplan(c1, c2, Path, TotalDistance)), BestSolutions),
    forall(member([Path, Distance], BestSolutions), (
        atomic_list_concat(Path, ' -> ', PathStr),
        format('Solution: ~w (distance: ~w)~n', [PathStr, Distance])
    )).


distance(c1, c2, 10, 1). distance(c1, c3, 0, 0). distance(c1, c4, 7, 1).
distance(c1, c5, 5, 1). distance(c2, c3, 4, 1). distance(c2, c4, 12, 1).
distance(c2, c5, 20, 1). distance(c3, c4, 0, 0). distance(c3, c5, 0, 0).
distance(c4, c5, 0, 0). distance(c2, c1, 10, 1). distance(c3, c1, 0, 0).
distance(c4, c1, 7, 1). distance(c5, c1, 5, 1). distance(c3, c2, 4, 1).
distance(c4, c2, 12, 1). distance(c5, c2, 20, 1). distance(c4, c3, 0, 0).
distance(c5, c3, 0, 0). distance(c5, c4, 0, 0).

% task 2.1

% arity 4 predicate
plan(Cabin1, Cabin2, Path, TotalDistance) :-
    plan(Cabin1, Cabin2, [Cabin1], Path, TotalDistance).

% base case
plan(Cabin1, Cabin2, Visited, Path, Distance) :-
    not(Cabin1 = Cabin2),
    distance(Cabin1, Cabin2, Distance, 1),
    append(Visited, [Cabin2], Path).

% recursive case
plan(Cabin1, Cabin2, Visited, Path, TotalDistance) :-
    not(Cabin1 = Cabin2),
    distance(Cabin1, CabinX, Distance, 1),
    \+ member(CabinX, Visited),
    append(Visited, [CabinX], NewVisited),
    plan(CabinX, Cabin2, NewVisited, Path, SubDistance),
    TotalDistance is Distance + SubDistance.

% task 2.2

bestplan(Cabin1, Cabin2, ShortestPath, ShortestDistance) :-
    findall([Path, Distance], (plan(Cabin1, Cabin2, Path, Distance)), Solutions),
    sort(2, @=<, Solutions, [ShortestSolution|_]),
    [ShortestPath, ShortestDistance] = ShortestSolution.