chars_digits([], []).
chars_digits([A|As], [B|Bs]) :-
    char_type(A, digit(B)),
    chars_digits(As, Bs).

read_file(Stream, []) :-
    at_end_of_stream(Stream).
read_file(Stream, [X|Xs]) :-
    \+ at_end_of_stream(Stream),
    read_line_to_codes(Stream, C),
    chars_digits(C, X),
    read_file(Stream, Xs).

main :-
    open('../input/09', read, Stream),
    read_file(Stream, Lines), !,
    close(Stream),
    low_points(Lines, Res),
    basins(Lines, Res, B0),
    msort(B0, B1),
    reverse(B1, [B2,B3,B4|_]),
    X is B2 * B3 * B4,
    print(X).

basins(_, [], []).
basins(A, [P|Ps], [B|Bs]) :-
    points_high_neighbors_all(A, [P], Bas),
    length(Bas, B),
    basins(A, Ps, Bs).

fetch_value(A, [X, Y], V) :-
    nth0(Y, A, R),
    nth0(X, R, V).

fetch_values(_, [], []).
fetch_values(A, [P|Ps], [V|Vs]) :-
    fetch_value(A, P, V),
    fetch_values(A, Ps, Vs).

low_point(A, X, Y) :-
    valid_paths(A, X, Y, P),
    fetch_values(A, P, V),
    fetch_value(A, [X, Y], V0),
    min_list(V, V1),
    V1 > V0.

low_points_rest([A|As], X, Y, Rs) :-
    length(A, W),
    (
        (X > 0, X0 is X - 1, low_points([A|As], X0, Y, Rs));
        (X = 0, Y > 0, X0 is W - 1, Y0 is Y - 1, low_points([A|As], X0, Y0, Rs))
    ).

low_points(A, 0, 0, [[0, 0]]) :- low_point(A, 0, 0).
low_points(A, 0, 0, []) :- \+ low_point(A, 0, 0).
low_points(A, X, Y, [[X, Y]|Rs]) :-
    low_point(A, X, Y),
    low_points_rest(A, X, Y, Rs).
low_points(A, X, Y, Rs) :-
    low_points_rest(A, X, Y, Rs).
low_points([A|As], Ret) :-
    length([A|As], H),
    length(A, W),
    X0 is W - 1,
    Y0 is H - 1,
    low_points([A|As], X0, Y0, Ret).

high_neighbor(A, [X1, Y1], [X0, Y0]) :-
    nth0(Y1, A, R1),
    nth0(Y0, A, R0),
    nth0(X1, R1, A1),
    A1 =\= 9,
    nth0(X0, R0, A0),
    A1 > A0.

high_neighbors(A, X, Y, P) :-
    valid_paths(A, X, Y, W),
    setof(Q, (member(Q, W), high_neighbor(A, Q, [X, Y])), P).
high_neighbors(A, X, Y, []) :-
    valid_paths(A, X, Y, W),
    \+ setof(Q, (member(Q, W), high_neighbor(A, Q, [X, Y])), _).

points_high_neighbors(_, [], []).
points_high_neighbors(A, [[X,Y]|Ps], N) :-
    points_high_neighbors(A, Ps, N1),
    high_neighbors(A, X, Y, N0),
    append(N0, N1, N2),
    sort(N2, N).

points_high_neighbors_all(A, P, P) :-
    points_high_neighbors(A, P, []).
points_high_neighbors_all(A, P, N) :-
    points_high_neighbors(A, P, N1),
    points_high_neighbors_all(A, N1, N2),
    append(P, N2, N3),
    sort(N3, N).

in_bounds(W, H, X, Y) :-
    X >= 0, X < W,
    Y >= 0, Y < H.

valid_paths([A|As], X, Y, P) :-
    length([A|As], H),
    length(A, W),
    valid_paths(W, H, X, Y, P).
valid_paths(W, H, X, Y, [P|Ps]) :-
    X0 is X - 1, in_bounds(W, H, X0, Y), P = [X0, Y], valid_paths_1(W, H, X, Y, Ps).
valid_paths(W, H, X, Y, Ps) :-
    X0 is X - 1,
    \+ in_bounds(W, H, X0, Y),
    valid_paths_1(W, H, X, Y, Ps).
valid_paths_1(W, H, X, Y, [P|Ps]) :-
    X0 is X + 1, in_bounds(W, H, X0, Y), P = [X0, Y], valid_paths_2(W, H, X, Y, Ps).
valid_paths_1(W, H, X, Y, Ps) :-
    X0 is X + 1, \+ in_bounds(W, H, X0, Y), valid_paths_2(W, H, X, Y, Ps).
valid_paths_2(W, H, X, Y, [P|Ps]) :-
    Y0 is Y - 1, in_bounds(W, H, X, Y0), P = [X, Y0], valid_paths_3(W, H, X, Y, Ps).
valid_paths_2(W, H, X, Y, Ps) :-
    Y0 is Y - 1, \+ in_bounds(W, H, X, Y0), valid_paths_3(W, H, X, Y, Ps).
valid_paths_3(W, H, X, Y, [P]) :-
    Y0 is Y + 1, in_bounds(W, H, X, Y0), P = [X, Y0].
valid_paths_3(W, H, X, Y, []) :-
    Y0 is Y + 1, \+ in_bounds(W, H, X, Y0).