% Author: Mikołaj Gradowski
% E-mail: s180190@student.pg.edu.pl

% Info: made with SWI-Prolog version 8.2.3 for x86_64-darwin


% ___ ____ ____ _  _    _
%  |  |__| [__  |_/     |
%  |  |  | ___] | \_    | .
%


% Insert into an ordered list, preserving the order
insert(X, [], [X]).
insert(X, [H | T], [H | YS]) :-
    X > H,
    insert(X, T, YS).
insert(X, XS, [X | XS]).

% Sort a list (insertion sort)
sort_([], []).
sort_([H | T], Y) :-
    sort_(T, Y0),
    insert(H, Y0, Y).


% ___ ____ ____ _  _    _ _
%  |  |__| [__  |_/     | |
%  |  |  | ___] | \_    | | .
%


% Return smaller of the two
min(X1, X2, X1) :- X1 =< X2.
min(X1, X2, X2) :- X1  > X2.

% Return smallest element of a list
minList([X], X).
minList([X | XS], Y) :-
    minList(XS, Y0),
    min(X, Y0, Y).

% Skip first N elements of a list
skip(0, X, X).
skip(_, [], []).
skip(N, [_ | XS], Y) :-
    N0 is N-1,
    skip(N0, XS, Y).

% Take first N elements of a list
take(0, _, []).
take(N, [X | XS], [Y | YS]) :-
    Y = X,
    N0 is N-1,
    take(N0, XS, YS).

% Creates a list of integers 1, 2, ..., N
% Note: It's O(n^2) because it was easier.
range(0, []).
range(N, Y) :-
    N0 is N-1,
    range(N0, Y0),

    insert(N, Y0, Y).

% Replicates El N times
replicate(_, 0, []).
replicate(El, N, [El | Y0]) :-
    N0 is N-1,
    replicate(El, N0, Y0).

% Sum the elements in a list
sum([], 0).
sum([X | XS], Y) :-
    sum(XS, Y0),
    Y is X + Y0.

% Checks inequality for a single r
isGraphicAux_(Seq, R) :-
    length(Seq, N),
    take(R, Seq, LHSSeq),
    sum(LHSSeq, LHS),
    NR is N-R,
    replicate(R, NR, RS),
    skip(R, Seq, RHSSeq1),
    maplist(min, RS, RHSSeq1, RHSSeq2),
    sum(RHSSeq2, RHSSum),
    RHS is R * (R - 1) + RHSSum,
    !, LHS =< RHS.

% Checks if Seq is a graphic sequence
isGraphic(Seq) :-
    sum(Seq, Sum),
    0 is mod(Sum, 2),
    length(Seq, N),
    N0 is N-1,
    replicate(Seq, N0, Seqs),
    range(N0, RS),
    !, maplist(isGraphicAux_, Seqs, RS).

% ___ ____ ____ _  _    _ _ _
%  |  |__| [__  |_/     | | |
%  |  |  | ___] | \_    | | | .
%

isPotentiallyConnected(Seq) :-
    length(Seq, N),
    minList(Seq, MinDegree),
    MinDegree > 0,
    isGraphic(Seq),
    RHS is 2*(N-1),
    sum(Seq, SeqSum),
    !, SeqSum >= RHS.