% Name: Tarik Abou-Saddik
% ID: 27518722
% Date: February 18, 2019

% Goal.
numberlink((BoardSize, NumOfPaths, EndPoints)) :-
    parse(EndPoints, Paths, Visited),
    length(Paths, NumOfPaths),
    map_paths(Paths,BoardSize,Visited,UpdatedPaths).
    length(UpdatedPaths, NumOfPaths),
    flatten(UpdatedPaths, X), length(X, FlatListLength),
    ActualLength is FlatListLength - NumOfPaths, Area is BoardSize ^ 2,
    ActualLength =:= Area,
    format('~s~w,~w, ~n',["(",BoardSize, NumOfPaths]),
    output_paths(UpdatedPaths).

% Output result in approrpiate format.
output_paths([]).
output_paths(Paths) :-
    Paths = [[NumPath|Cells]|T],
    format('~s~w~s ',["(",NumPath,":"]),
    format_cells(Cells),!,
    format('~s~n',[")"]),
    output_paths(T),!.

% Format cells.
format_cells([]).
format_cells([Cell|Rest]) :-
    Cell = cell(X,Y),
    (Rest = [] ->
        format('~s~w,~w~s',["(",X,Y,")"])
        ;
        format('~s~w,~w~s, ',["(",X,Y,")"])
    ),
    format_cells(Rest).

% Parse the given input.
parse([],[],[]).
parse(Cells, Paths, Visited) :-
    Cells =.. [_|T],
    (T = [(NumPath: (X1,Y1), X2,Y2) | [Rest]] ; T = [NumPath: (X1,Y1), (X2,Y2) | Rest]),
    parse(Rest, RestOfPaths, RestOfVisited),!,
    Paths = [path(NumPath,cell(X1, Y1), cell(X2,Y2)) | RestOfPaths],
    Visited = [cell(X1,Y1), cell(X2,Y2) | RestOfVisited].

% Remove an item from a list.
remove_item([Item|Tail], Item, List) :- List = Tail.
remove_item([H|T], Item, List) :-
    remove_item(T, Item, Tail),
    List = [H|Tail].

% Move to the right.
move(cell(X,Y), cell(X1,Y)) :- X1 is X + 1.
% Move to the left.
move(cell(X,Y),cell(X1,Y)) :- X1 is X - 1.
% Move upward.
move(cell(X,Y), cell(X,Y1)) :- Y1 is Y - 1.
% Move downward.
move(cell(X,Y), cell(X,Y1)) :- Y1 is Y + 1.

% Check to see if you're within the confines of the board.
validCell(cell(X,Y), Limit) :- X < Limit + 1, Y < Limit + 1, X > 0, Y > 0.

% Map each Start/End cell entry in list connected_path/5 rule.
map_paths([],_,_,[]).
map_paths(Paths, BoardSize, Visited, NewPaths) :-
    Paths = [path(NumPath,StartCell,EndCell) | Rest],
    remove_item(Visited, EndCell, PathsVisited),
    connected_path(BoardSize, StartCell, PathsVisited, NewVisited, EndCell),
    append(Visited, NewVisited, X), sort(X, NewBoardLayout),
    map_paths(Rest,BoardSize,NewBoardLayout,UpdatedPaths),
    append([NumPath], NewVisited, Head),
    NewPaths = [Head|UpdatedPaths],!.

% Distance between two cells.
distance(cell(X1,Y1), cell(X2,Y2), Distance) :-
    X is X2 - X1, Y is Y2 - Y1, Distance is abs(X) + abs(Y).

% Unifies with this once endpoint is reached.
connected_path(_,EndCell,_,[EndCell],EndCell).
connected_path(BoardSize, StartCell, PrevVisited, NewVisited, EndCell) :-
    move(StartCell, NextCell),
    validCell(NextCell, BoardSize),\+ member(NextCell, PrevVisited),
    append([NextCell], PrevVisited, UpdatedVisited),
    connected_path(BoardSize, NextCell, UpdatedVisited, NextVisited, EndCell),
    NewVisited = [StartCell|NextVisited].