This topic is about Day 23 of the Advent of Code 2021.
We have a private leaderboard (shared with users of the elixir forum):
https://adventofcode.com/2021/leaderboard/private/view/370884
The entry code is:
370884-a6a71927
3 Likes
Solved part 1 by hand since I didn’t have a clue how to approach that puzzle initially, took one attempt as it was somewhat obvious, for part 2 - brute force of states with memoization works quite well 
Also first time I get one or both starts in global top 1000 
3 Likes
Ugly solution:
main(File) ->
{ok, RawData} = file:read_file(File),
Data = [ list_to_atom([C]) || C <- string:to_lower(binary_to_list(RawData)),
lists:member(C, "abcd") ],
io:format("part 1: ~p~n", [solve1(Data)]),
io:format("part 2: ~p~n", [solve2(Data)]).
solve1(Data) ->
process(to_state(Data)).
solve2(Data) ->
First = lists:sublist(Data, 1, 4),
Second = lists:sublist(Data, 5, length(Data)),
Insert = [d, c, b, a, d, b, a, c],
process(to_state(First ++ Insert ++ Second)).
process(Stacks) ->
ets:new(memoize, [named_table, public, set]),
Depth = length(element(1, Stacks)),
try
process(Stacks, [], win_state(Depth), Depth, 0)
after
ets:delete(memoize)
end.
process(Stacks, [], WinStacks, _Depth, Cost)
when Stacks =:= WinStacks ->
Cost;
process(Stacks, Hallway, WinStacks, Depth, Cost) ->
case should_follow(Stacks, Hallway, Cost) of
true ->
case maybe_hallway_to_stack(Stacks, Hallway, Depth)
++ maybe_stack_to_hallway(Stacks, Hallway, Depth) of
[] -> infinity;
Moves ->
lists:min([ process(NewStacks, NewHallway, WinStacks, Depth, Cost + MoveCost)
|| {NewStacks, NewHallway, MoveCost} <- Moves ])
end;
false ->
infinity
end.
%% - - - - - + + + + +
%% 5 4 3 2 1 0 1 2 3 4 5
%% A B C D
%% A B C D
maybe_stack_to_hallway({As, Bs, Cs, Ds} = Stacks, Hallway, Depth) ->
HallwayPositions = [-5, -4, -2, 0, 2, 4, 5],
StackPositions = [{a, -3, As},
{b, -1, Bs},
{c, 1, Cs},
{d, 3, Ds}],
[
begin
[Elem|NewStack] = Stack,
NewStacks = pop_stacks(StackValue, Stacks),
NewHallway = orddict:store(HallwayPosition, Elem, Hallway),
MoveCost = cost(Elem, StackPos, HallwayPosition, NewStack, Depth),
{NewStacks, NewHallway, MoveCost}
end
|| {StackValue, StackPos, Stack} <- StackPositions,
Stack =/= [],
not is_stacked(StackValue, Stack),
HallwayPosition <- HallwayPositions,
not orddict:is_key(HallwayPosition, Hallway),
can_reach(StackPos, HallwayPosition, Hallway)
].
maybe_hallway_to_stack(State, Hallway, Depth) ->
[ K || P <- Hallway,
K <- hallway_to_stack(P, Hallway, State, Depth) ].
hallway_to_stack({HallwayPosition, Elem}, Hallway, {As, Bs, Cs, Ds} = Stacks, Depth) ->
{StackPos, Stack} = case Elem of
a -> {-3, As};
b -> {-1, Bs};
c -> { 1, Cs};
d -> { 3, Ds}
end,
case is_stacked(Elem, Stack) andalso can_reach(HallwayPosition, StackPos, Hallway) of
false -> [];
true ->
NewStacks = push_stacks(Elem, Stacks),
NewHallway = orddict:erase(HallwayPosition, Hallway),
MoveCost = cost(Elem, HallwayPosition, StackPos, Stack, Depth),
[{NewStacks, NewHallway, MoveCost}]
end.
cost(V, From, To, Stack, Depth) ->
mult(V) * (Depth - length(Stack) + abs(To - From)).
can_reach(From, To, Hallway) ->
Sign = case To > From of true -> 1; false -> -1 end,
case [ P || P <- lists:seq(From + Sign, To - Sign, Sign), lists:keymember(P, 1, Hallway) ] of
[] -> true;
_ -> false
end.
should_follow(Stacks, Hallway, Cost) ->
K = {Stacks, Hallway},
case ets:lookup(memoize, K) of
[{K, V}] when V =< Cost ->
false;
_ ->
ets:insert(memoize, {K, Cost}),
true
end.
pop_stacks(a, {As, Bs, Cs, Ds}) -> {tl(As), Bs, Cs, Ds};
pop_stacks(b, {As, Bs, Cs, Ds}) -> {As, tl(Bs), Cs, Ds};
pop_stacks(c, {As, Bs, Cs, Ds}) -> {As, Bs, tl(Cs), Ds};
pop_stacks(d, {As, Bs, Cs, Ds}) -> {As, Bs, Cs, tl(Ds)}.
push_stacks(a, {As, Bs, Cs, Ds}) -> {[a|As], Bs, Cs, Ds};
push_stacks(b, {As, Bs, Cs, Ds}) -> {As, [b|Bs], Cs, Ds};
push_stacks(c, {As, Bs, Cs, Ds}) -> {As, Bs, [c|Cs], Ds};
push_stacks(d, {As, Bs, Cs, Ds}) -> {As, Bs, Cs, [d|Ds]}.
is_stacked(V, [V, V, V, V]) -> true;
is_stacked(V, [V, V, V]) -> true;
is_stacked(V, [V, V]) -> true;
is_stacked(V, [V]) -> true;
is_stacked(_, []) -> true;
is_stacked(_, _) -> false.
mult(a) -> 1;
mult(b) -> 10;
mult(c) -> 100;
mult(d) -> 1000.
win_state(Depth) ->
list_to_tuple([ lists:duplicate(Depth, F) || F <- [a, b, c, d] ]).
to_state(Data) ->
to_state(lists:reverse(Data), {[], [], [], []}).
to_state([], State) -> State;
to_state([D,C,B,A|Rest], {As, Bs, Cs, Ds}) ->
to_state(Rest, {[A|As], [B|Bs], [C|Cs], [D|Ds]}).
5 Likes
Congratulations!
3 Likes