42 lines
976 B
Perl
42 lines
976 B
Perl
|
numbers_strings([], []).
|
||
|
|
numbers_strings([A|As], [B|Bs]) :-
|
||
|
|
number_string(A, B),
|
||
|
|
numbers_strings(As, Bs).
|
||
|
|
|
||
|
|
read_file(Stream, X) :-
|
||
|
|
\+ at_end_of_stream(Stream),
|
||
|
|
read_line_to_codes(Stream, C),
|
||
|
|
string_chars(S, C),
|
||
|
|
split_string(S, ",", "", Y),
|
||
|
|
numbers_strings(X, Y),
|
||
|
|
at_end_of_stream(Stream).
|
||
|
|
|
||
|
|
main :-
|
||
|
|
open('../input/07', read, Stream),
|
||
|
|
read_file(Stream, Lines), !,
|
||
|
|
close(Stream),
|
||
|
|
msort(Lines, L),
|
||
|
|
min_list(L, A),
|
||
|
|
max_list(L, B),
|
||
|
|
bin_search(A, B, L, N),
|
||
|
|
print(N).
|
||
|
|
|
||
|
|
tri(A, B) :-
|
||
|
|
B is (A * (A + 1)) // 2.
|
||
|
|
|
||
|
|
calculate_diff([], _, 0).
|
||
|
|
calculate_diff([A|As], X, B) :-
|
||
|
|
calculate_diff(As, X, B0),
|
||
|
|
tri(abs(A - X), T),
|
||
|
|
B is B0 + T.
|
||
|
|
|
||
|
|
bin_search(L, L, A, Ans) :-
|
||
|
|
calculate_diff(A, L, Ans).
|
||
|
|
bin_search(L, R, A, Ans) :-
|
||
|
|
L < R,
|
||
|
|
M is (L + R) // 2,
|
||
|
|
((M >= R, A1 is 9999999999999999); bin_search(L, M, A, A1)),
|
||
|
|
((M =< L, A2 is 9999999999999999); bin_search(M, R, A, A2)),
|
||
|
|
Ans is min(A1, A2).
|
||
|
|
|