day10.erl

%%% @doc
%%% welcome to day TEN, the longest three letter day around
%%% @end
-module(day10).
-export([p1/0, p2/0]).
-export([best_point/1, debug_map/1, search_and_destroy/2, coords/1]).

p1() ->
    String = advent:input("day10"),
    {_,Ct} = best_point(String),
    Ct.

p2() ->
    String = advent:input("day10"),
    {X,Y} = search_and_destroy(String, 200),
    X*100 + Y.

debug_map(String) ->
    Map = coords(String),
    maps:from_list(search(Map)).

best_point(String) ->
    Map = coords(String),
    {Ct,Point} = lists:max([{Val,Key} || {Key, Val} <- search(Map)]),
    {Point, Ct}.

search(Map) ->
    Keys = maps:keys(Map),
    [search(Point, Keys -- [Point], 0, #{}) || Point <- Keys].

search(Point, [], Seen, _) -> {Point, Seen};
search({AX,AY}, [{BX,BY}|Points], Seen, Moves) ->
    Move = min_step({BX-AX, BY-AY}),
    case Moves of
        #{Move := true} -> search({AX,AY}, Points, Seen, Moves);
        #{} -> search({AX,AY}, Points, Seen+1, Moves#{Move => true})
    end.

% sorting order: {Angle, Steps, Move, Point}
% Steps = number of times a given gcd move is needed to reach point
% Angle = gcd move angle in quadrant
search_and_destroy(String, Nth) ->
    Map = coords(String),
    Keys = maps:keys(Map),
    {_,Origin} = lists:max([{Val,Key} || {Key, Val} <- search(Map)]),
    Moves = gather_moves(Origin, Keys--[Origin], []),
    Candidates =
       lists:sort([{abs(math:atan(X/Y)), Steps, {X,Y}, Point}
                   || {{X,Y}, Steps, Point} <- Moves, X >= 0, Y < 0]) ++
       lists:sort([{math:atan(Y/X), Steps, {X,Y}, Point}
                   || {{X,Y}, Steps, Point} <- Moves, X > 0, Y >= 0]) ++
       lists:sort([{abs(math:atan(X/Y)), Steps, {X,Y}, Point}
                   || {{X,Y}, Steps, Point} <- Moves, X =< 0, Y > 0]) ++
       lists:sort([{math:atan(Y/X), Steps, {X,Y}, Point}
                   || {{X,Y}, Steps, Point} <- Moves, X < 0, Y =< 0]),
    kill(Nth, [{Move, Point} || {_,_,Move,Point} <- Candidates]).

kill(Nth, Candidates) ->
    {_, Point} = kill_(Nth, Candidates),
    Point.

kill_(Nth, Candidates) ->
    {Visible, Invisible} = find_visible(Candidates),
    ToKill = length(Visible),
     if Nth-ToKill > 0 -> kill_(Nth-ToKill, Invisible);
        Nth-ToKill =:= 0 -> lists:last(Visible);
        Nth-ToKill < 0 -> lists:nth(Nth, Visible)
     end.

find_visible(List) -> find_visible(List, [], []).

find_visible([], Visible, Invisible) ->
    {lists:reverse(Visible), lists:reverse(Invisible)};
find_visible([{M,P}|T], [{M,_}|_] = Visible, Invisible) ->
    find_visible(T, Visible, [{M,P}|Invisible]);
find_visible([{M,P}|T], Visible, Invisible) ->
    find_visible(T, [{M,P}|Visible], Invisible).

gather_moves(_, [], Moves) ->
    Moves;
gather_moves({AX,AY}, [{BX,BY}|Points], Moves) ->
    {Move, Steps} = step_count({BX-AX, BY-AY}),
    gather_moves({AX,AY}, Points, [{Move, Steps, {BX,BY}}|Moves]).

min_step({0,Y}) ->
    {0,Y div abs(Y)};
min_step({X,0}) ->
    {X div abs(X),0};
min_step({A,B}) ->
    D = gcd(abs(A), abs(B)),
    {A div D, B div D}.

step_count({0,Y}) ->
    {{0,Y div abs(Y)}, abs(Y)};
step_count({X,0}) ->
    {{X div abs(X),0}, abs(X)};
step_count({A,B}) ->
    D = gcd(abs(A), abs(B)),
    {{A div D, B div D}, D}.

gcd(A,A) -> A;
gcd(A,B) when A > B -> gcd(A-B, B);
gcd(A,B) when A < B -> gcd(A, B-A).

coords(String) ->
    maps:from_list(
     [{Coord,0} || Coord <- coords(string:lexemes(String, "\n"), 0, 0)]
    ).

coords([], _, _) -> [];
coords([[]|T], _, Y) -> coords(T, 0, Y+1);
coords([[$.|Xs]|T], X, Y) -> coords([Xs|T], X+1, Y);
coords([[$#|Xs]|T], X, Y) -> [{X,Y}|coords([Xs|T], X+1, Y)].