day19.erl

%%% @doc
%%% See lines 55-60 for an optimization I came up with that cuts down to
%%% only 500ms, and weren't shown on either the main nor the bonus video
%%% @end
-module(day19).
-export([p1/0, p2/0]).
-export([square_fits_map/3]).

p1() ->
    Code = intcode:parse_program(advent:input("day19")),
    lists:sum(
      [(B-A)+1 || {_, {A,B}} <- define_map(Code, {0,0}, {49,49})]
    ).

p2() ->
    Code = intcode:parse_program(advent:input("day19")),
    Parent = self(),
    Pid = spawn_link(fun() -> loop(Code#{output => Parent}) end),
    {X,Y} = fit_square(Pid, 100, {200,200}, {1000,1000}),
    Pid ! halt,
    X * 10000 + Y.

loop(Code) ->
    _ = intcode:run_program(Code),
    receive
        halt -> ok
    after 0 ->
        loop(Code)
    end.

define_map(Code, TL, BR) -> define_map(Code, TL, BR, []).

define_map(_, {_,Y}, {_,MaxY}, Acc) when Y > MaxY ->
    lists:reverse(Acc);
define_map(Code, {X,Y}, {MaxX,_}=Max, Acc) ->
    FirstX = first_from_left(Code, X, Y, MaxX),
    case FirstX of
        undefined ->
            define_map(Code, {X,Y+1}, Max, [{Y, undefined} | Acc]);
        _ ->
            LastX = last_from_left(Code, FirstX, Y),
            define_map(Code, {FirstX,Y+1}, Max, [{Y,{FirstX,LastX}}|Acc])
    end.

fit_square(_, _Sq, {_,Y}, {_,MaxY}) when Y > MaxY ->
    no_fit;
fit_square(Pid, Sq, {X,Y}, {MaxX,_}=Max) ->
    FirstX = first_from_leftp(Pid, X, Y, MaxX),
    case FirstX of
        undefined ->
            fit_square(Pid, Sq, {X,Y+1}, Max);
        _ ->
            RightEdge = FirstX + (Sq-1),
            TopRow = Y-(Sq-1),
            %% only need to check the last edge, much faster!
            LastX = check_coordinatep(Pid, {RightEdge, Y}),
            case LastX =:= in
                 andalso check_coordinatep(Pid, {RightEdge, TopRow}) of
                in ->
                    {FirstX, TopRow};
                _ ->
                    fit_square(Pid, Sq, {FirstX,Y+1}, Max)
            end
    end.

square_fits_map(Y, Sq, Map) ->
    %% Bottom left corner
    TopRow = Y-(Sq-1),
    case Map of
        #{Y := {BL, _},
          TopRow := {RowL, RowR}} ->
            if RowL =< BL,
               RowR >= BL+(Sq-1) -> {true, {BL,TopRow}}
             ; true -> false
            end;
        _ ->
            false
    end.

first_from_left(_, X, _, MaxX) when X > MaxX ->
    undefined;
first_from_left(Code, X, Y, MaxX) ->
    case check_coordinate(Code, {X,Y}) of
        in -> X;
        out -> first_from_left(Code, X+1, Y, MaxX)
    end.

last_from_left(Code, X, Y) ->
    case check_coordinate(Code, {X,Y}) of
        out -> X-1;
        in -> last_from_left(Code, X+1, Y)
    end.

check_coordinate(Code, {X,Y}) ->
    P = intcode:spawn_program(Code, self()),
    P ! {io, X},
    P ! {io, Y},
    _ = intcode:collect_result(P),
    case intcode:collect_io() of
        [0] -> out;
        [1] -> in
    end.

first_from_leftp(_, X, _, MaxX) when X > MaxX ->
    undefined;
first_from_leftp(Pid, X, Y, MaxX) ->
    case check_coordinatep(Pid, {X,Y}) of
        in -> X;
        out -> first_from_leftp(Pid, X+1, Y, MaxX)
    end.

check_coordinatep(P, {X,Y}) ->
    P ! {io, X},
    P ! {io, Y},
    receive
        {io, 0} -> out;
        {io, 1} -> in
    end.