Advent of Code 2016, Day 11

advent11.erl

-module(advent11).
-export([main/1]).

-record(state, { elevator = 1, floors }).

-define(TOP_FLOOR, 4).
-define(LIMIT, 120).

%% some housekeeping funcs for creating items
-define(MICRO(Cat), { microchip, Cat }).
-define(GEN(Cat), { generator, Cat }).

visited_init() -> sets:new().
% returns table with the element added, and returns whether it was
% already there.
visited(Visited_Table, State) ->
      { sets:is_element(normalise(State), Visited_Table),
	sets:add_element(normalise(State), Visited_Table) }.

%% Right - no normalise, all we need to know in a state (besides the
%% elevator location) is on what floor the micro is for each
%% generator.
%%
%% So, we go through the floors, and for each generator item, we
%% replace it with the floor that the corresponding micro is on. We
%% can then sort these numbers so that it doesn't matter what level we
%% find the micro on.

findItem(Item, [ { FloorNum, Floor } | Floors ]) ->
  case lists:member(Item, Floor) of
    true -> FloorNum;
    false -> findItem(Item, Floors)
  end.

% floors is where everything is, so we can find the corresponding micro
normGenerator(Cat, Floors) ->
  findItem(?MICRO(Cat), Floors).

normFloor({ FloorNum, Items }, Floors) ->
  Nitems = lists:filtermap(
	     fun ({ generator, Cat }) -> { true, normGenerator(Cat, Floors) };
		 (_) -> false
	     end,
	     Items),
  { FloorNum, lists:sort(Nitems) }.

normalise(#state{elevator = Ev, floors = Floors}) ->
  { Ev, lists:map(fun (Floor) -> normFloor(Floor, Floors) end, Floors) }.

micro(X) -> ?MICRO(X).
gen(X) -> ?GEN(X).

part1() ->
  Start = #state {
	     floors = [ { 1, [ gen(strontium), micro(strontium), gen(plutonium), micro(plutonium) ] },
			{ 2, [ gen(thulium), gen(ruthenium), micro(ruthenium), gen(curium), micro(curium) ] },
			{ 3, [ micro(thulium) ] },
			{ 4, [] } ]
	    },
  search(Start).
part2() ->
  Start = #state {
	     floors = [ { 1, [ gen(elerium), micro(elerium), gen(dilithium), micro(dilithium), gen(strontium), micro(strontium), gen(plutonium), micro(plutonium) ] },
			{ 2, [ gen(thulium), gen(ruthenium), micro(ruthenium), gen(curium), micro(curium) ] },
			{ 3, [ micro(thulium) ] },
			{ 4, [] } ]
	    },
  search(Start).

%% a device is { Type, Cat }
%%
%%   where Type is: generator or microchip.
%%   and Cat one of the types of radiation.

%% returns true if the Floor contains a generator of a type other than
%% that provided.
has_other_gen([], _) -> false;
						% any micro is ok
has_other_gen([{microchip, _} | Items], Cat) -> has_other_gen(Items, Cat);
						% ok because same cat
has_other_gen([{generator, Cat} | Items], Cat) -> has_other_gen(Items, Cat);
						% else, another generator exists
has_other_gen([{generator, _} | _], _) -> true.

has_gen(Floor, Cat) -> lists:member({ generator, Cat}, Floor).

%% returns true if a single item is allowed to be in the Floor
%% according to the rules.
is_valid(Floor, { microchip, Cat }) ->
  has_gen(Floor, Cat) orelse (not has_other_gen(Floor, Cat));
% anything else is valid
is_valid(_, _) -> true.

floors_are_valid(Floors) when is_list(Floors) ->
  % check all of the floors
  lists:all(fun ({_FloorNum, Floor}) -> floor_is_valid(Floor) end, Floors).

state_is_valid(#state{elevator = Ev, floors = Floors}) ->
  (Ev > 0) andalso (Ev =< ?TOP_FLOOR) andalso
  floors_are_valid(Floors).

%% returns true if the floor matches the rules for a safe floor
floor_is_valid(Floor) ->
  lists:all(
    fun (IsValid) -> IsValid end,
    lists:map(fun (Item) -> is_valid(Floor, Item) end, Floor)
   ).

applyMove(#state{floors = Floors}, Move) ->
  { _, ToFloor, _ } = Move,
  #state{ elevator = ToFloor, floors = lists:map(fun (Floor) -> applyMove(Floor, Move) end, Floors) };
applyMove({ FloorNum, Floor }, { FromFloor, _ToFloor, Items }) when FloorNum =:= FromFloor ->
  {FloorNum, lists:subtract(Floor, Items) };
applyMove({ FloorNum, Floor }, { _FromFloor, ToFloor, Items }) when FloorNum =:= ToFloor ->
  {FloorNum, lists:append(Floor, Items) };
applyMove(Floor, _) -> Floor.			% move not applicable, ret Floor unchanged

pairs([]) -> [];
pairs([ H | T]) -> [ [ H, A ] || A <- T ] ++ pairs(T).

generateMoves(#state{elevator = Elevator, floors = Floors}) ->
  { _, EvFloor } = lists:keyfind(Elevator, 1, Floors),
  lists:flatmap(
    fun (Items) ->
	Up = if Elevator > 1 -> [ { Elevator, Elevator - 1, Items } ];
		true -> []
	     end,
	Down = if Elevator < ?TOP_FLOOR -> [ { Elevator, Elevator + 1, Items } ];
		true -> []
	     end,
	Up ++ Down
    end,
    pairs(EvFloor) ++ [ [Item] || Item <- EvFloor ]
   ).

is_complete(#state{floors=Floors}) ->
  is_complete(Floors);
is_complete([ { ?TOP_FLOOR, _ } | _ ]) -> true;
is_complete([ { _, [] } | T ]) -> is_complete(T);
is_complete(_) -> false.

nextStates(State) ->
  NewStates = [ applyMove(State, Move) || Move <- generateMoves(State) ],
  lists:filter(fun state_is_valid/1, NewStates).

search(State) -> search([ { 0, State } ], visited_init()).

search([], _) -> noresult;
search([ { Count, _State } | Rest ], Seen) when Count > ?LIMIT -> search(Rest, Seen);
search([ { Count, State } | Rest ], Seen) ->
  { Visited, NewSeen } = visited(Seen, State),
  case Visited of
    true -> search(Rest, NewSeen);
    false ->
      case is_complete(State) of
	false ->
	  NewStates = nextStates(State),
	  search(
	    Rest ++ [ { Count + 1, S } || S <- NewStates ],
	    NewSeen);
	true ->
	  Count
      end
  end.

main([]) ->
  io:format("Part 1: ~B~n", [part1()]),
  io:format("Part 2: ~B~n", [part2()]).

I am pretty sure I don't need the visited process (implemented by visited/0) that keeps track of which items we have seen, I should just be passing the set directly into the recursive function as an argument and do the look up on that.

update: removed in rev 2, it was trivially easy to do this as I was already passing the Seen argument, which was a pid, was nothing to pass the actual set into that arg instead. The lookup function returns a tuple of a true/false value as well as a new set with it added.