day18.erl

%%% @doc
%%% welcome to day eighteen, which can legally drink here
%%% @end
-module(day18).
-export([p1/0, p2/0]).

%% Use processes to escape the dirty pdict-based cache I end up using as a work-around
p1() ->
    {Map, Keys, Doors, Pos} = to_map(advent:input("day18")),
    Parent = self(),
    spawn_link(fun() -> Parent ! cached_search(Pos, Map, Keys, Doors) end),
    receive X -> X end.

p2() ->
    {Map, Keys, Doors, Pos} = to_map(advent:input("day18p2")),
    Parent = self(),
    spawn_link(fun() -> Parent ! cached_search(Pos, Map, Keys, Doors) end),
    receive X -> X end.

cached_search(Pos, Map, Keys, Doors) ->
    Key = {Pos, maps:size(Map), Keys, Doors},
    case get(Key) of
        undefined ->
            R = search(Pos, Map, Keys, Doors),
            put(Key, R),
            R;
        R ->
            R
    end.

search(Pos, Map, Keys, Doors) ->
    NewPosKeys = search_keys(Pos, Map, Keys, Doors),
    FoundKeys = [{P, K, V} || {P, NewKeys} <- NewPosKeys,
                              {K,V} <- maps:to_list(NewKeys),
                              is_integer(V)],
    case FoundKeys of
        [] ->
            0;
        _ ->
            List = [cached_search(
                      swap_pos(OPos, maps:get(K, Keys), Pos),
                      Map,
                      maps:remove(K, Keys),
                      unlock(K, Doors)
                    ) + PathLength || {OPos, K, PathLength} <- FoundKeys],
            lists:min(List)
    end.

swap_pos(P, K, [P|T]) -> [K|T];
swap_pos(P, K, [H|T]) -> [H|swap_pos(P, K, T)].

search_keys(Pos, Map, Keys, Doors) ->
    [{P,search_key(P, Map, Keys, Doors)} || P <- Pos].

search_key(Pos, Map, Keys, Doors) ->
    search_key(Map, Keys, Doors, #{}, queue:from_list([{0, Pos}])).

search_key(Map, Keys, Doors, Seen, Q) ->
    case queue:out(Q) of
        {{value, {PathSeen, Pos}}, OldQ} ->
            case maps:get(Pos, Map, invalid) of
                invalid ->
                    search_key(Map, Keys, Doors, Seen, OldQ);
                open ->
                    NextQ = next(Pos, Map, Seen, PathSeen, OldQ),
                    search_key(Map, Keys, Doors, Seen#{Pos=>true}, NextQ);
                DoorOrKey when is_atom(DoorOrKey) ->
                    NextQ = next(Pos, Map, Seen, PathSeen, OldQ),
                    case Doors of
                        #{DoorOrKey := unlocked} ->
                            search_key(Map, Keys, Doors,
                                       Seen#{Pos=>true}, NextQ);
                        #{DoorOrKey := _} ->
                            search_key(Map, Keys, Doors,
                                       Seen#{Pos=>true}, OldQ);
                        _ when is_map_key(DoorOrKey, Keys) ->
                            search_key(Map, Keys#{DoorOrKey := PathSeen},
                                       Doors, Seen#{Pos=>true}, OldQ);
                        _ -> % key was found already
                            search_key(Map, Keys, Doors, Seen#{Pos=>true}, NextQ)
                    end
            end;
        {empty, _} ->
            Keys
    end.

next(Pos, Map, Seen, PathSeen, Q) ->
    Neighbours = find_neighbours(Pos, Map, Seen),
    enqueue_neighbours(Neighbours, PathSeen, Q).

find_neighbours({X,Y}, Map, Seen) ->
    [Pos || Pos <- [{X+1,Y},{X-1,Y},{X,Y+1},{X,Y-1}],
            maps:get(Pos, Map, wall) =/= wall,
            not maps:get(Pos, Seen, false)].

enqueue_neighbours([], _Seen, Q) ->
    Q;
enqueue_neighbours([H|T], Seen, Q) ->
    enqueue_neighbours(T, Seen, queue:in({Seen+1, H}, Q)).

unlock(Lowercase, Doors) ->
    [C] = atom_to_list(Lowercase),
    Door = list_to_atom([C-32]),
    Doors#{Door => unlocked}.

to_map(Str) ->
    to_map({0,0}, Str, #{}, #{}, #{}, []).

to_map(_, [], Map, Keys, Doors, Pos) ->
    {Map, Keys, Doors, Pos};
to_map({_,Y}, [$\n|T], Map, Keys, Doors, Pos) ->
    to_map({0,Y+1}, T, Map, Keys, Doors, Pos);
to_map({X,Y}, [C|T], Map, Keys, Doors, Pos) when C >= $a, C =< $z ->
    to_map({X+1,Y}, T,
           Map#{{X,Y} => list_to_atom([C])},
           Keys#{list_to_atom([C]) => {X,Y}},
           Doors, Pos);
to_map({X,Y}, [C|T], Map, Keys, Doors, Pos) when C >= $A, C =< $Z ->
    to_map({X+1,Y}, T,
           Map#{{X,Y} => list_to_atom([C])},
           Keys,
           Doors#{list_to_atom([C]) => {X,Y}},
           Pos);
to_map({X,Y}, [$@|T], Map, Keys, Doors, Pos) ->
    to_map({X+1,Y}, T, Map#{{X,Y} => open}, Keys, Doors, [{X,Y}|Pos]);
to_map({X,Y}, [$.|T], Map, Keys, Doors, Pos) ->
    to_map({X+1,Y}, T, Map#{{X,Y} => open}, Keys, Doors, Pos);
to_map({X,Y}, [$#|T], Map, Keys, Doors, Pos) ->
    to_map({X+1,Y}, T, Map, Keys, Doors, Pos).