You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
104 lines
4.2 KiB
104 lines
4.2 KiB
-module(day14).
|
|
|
|
-export([solve/1]).
|
|
|
|
solve(Input) ->
|
|
{part1(Input), part2(Input)}.
|
|
|
|
|
|
part1(Input) -> simulate(parse_map(Input), 0).
|
|
|
|
part2(Input) ->
|
|
simulate(parse_map2(Input), 0).
|
|
|
|
parse_map2(Input) ->
|
|
LineSegments = parse_instructions(Input),
|
|
FloorDepth = y_max(LineSegments, 0) + 2,
|
|
FlooredLineSegments = [{{500 - FloorDepth, FloorDepth}, {500 + FloorDepth, FloorDepth}} | LineSegments],
|
|
ChoppedSegments = chop_segments(FlooredLineSegments, []),
|
|
SegmentMap = maps:groups_from_list(fun({X, _, _}) -> X end, fun({_X, YStart, YEnd}) -> {YStart, YEnd} end, ChoppedSegments),
|
|
maps:map(fun (_Key, Segments) -> lists:foldl(fun rset_append/2, rset_new(), Segments) end, SegmentMap).
|
|
|
|
y_max([], Max) -> Max;
|
|
y_max([{{_, Y1},{_,Y2}}|Rest], Max) -> y_max(Rest, max(max(Y1, Y2), Max)).
|
|
|
|
parse_map(Input) ->
|
|
LineSegments = parse_instructions(Input),
|
|
ChoppedSegments = chop_segments(LineSegments, []),
|
|
SegmentMap = maps:groups_from_list(fun({X, _, _}) -> X end, fun({_X, YStart, YEnd}) -> {YStart, YEnd} end, ChoppedSegments),
|
|
maps:map(fun (_Key, Segments) -> lists:foldl(fun rset_append/2, rset_new(), Segments) end, SegmentMap).
|
|
|
|
parse_instructions(Input) ->
|
|
lists:foldl(fun parse_instruction/2, [], binary:split(Input, <<$\n>>, [global, trim_all])).
|
|
|
|
parse_instruction(Line, Acc) ->
|
|
{X1, <<$,, Rest0/binary>>} = parse_int(Line),
|
|
{Y1, Rest1} = parse_int(Rest0),
|
|
parse_instruction0(Rest1, {X1, Y1}, Acc).
|
|
|
|
parse_instruction0(<<>>, _Point, Acc) -> Acc;
|
|
parse_instruction0(<<" -> ", RestIn/binary>>, Point, Acc) ->
|
|
{X, <<$,, Temp/binary>>} = parse_int(RestIn),
|
|
{Y, RestOut} = parse_int(Temp),
|
|
NewPoint = {X, Y},
|
|
parse_instruction0(RestOut, NewPoint, [{Point, NewPoint}|Acc]).
|
|
|
|
parse_int(<<$-, Rest/binary>>) ->
|
|
{AbsoluteValue, Binary} = parse_int0(Rest, 0),
|
|
{-1 * AbsoluteValue, Binary};
|
|
parse_int(Binary) ->
|
|
parse_int0(Binary, 0).
|
|
|
|
parse_int0(<<Digit, Rest/binary>>, Acc) when Digit >= $0 andalso Digit =< $9 ->
|
|
parse_int0(Rest, Acc*10 + Digit - $0);
|
|
parse_int0(Binary, Acc) when is_binary(Binary) -> {Acc, Binary}.
|
|
|
|
chop_segments([], Acc) -> Acc;
|
|
chop_segments([{{X, Y1}, {X, Y2}} | Rest], Acc) -> chop_segments(Rest, [{X, min(Y1, Y2), max(Y1, Y2)} | Acc]);
|
|
chop_segments([{{X1, Y}, {X2, Y}} | Rest], Acc) -> chop_segments(Rest, [{X, Y, Y} || X <- lists:seq(min(X1, X2), max(X1, X2))] ++ Acc).
|
|
|
|
simulate(State, SandCount) ->
|
|
case attempt_place(State, {500, 0}) of
|
|
{500, 0} -> SandCount + 1;
|
|
{X, Y} -> simulate(State#{X := rset_append({Y, Y}, maps:get(X, State))}, SandCount+1);
|
|
falling -> SandCount
|
|
end.
|
|
|
|
% returns true if there is a block in that spot
|
|
test_spot(State, X, Y) ->
|
|
case State of
|
|
#{X := Column} -> rset_contains(Y, Column);
|
|
_ -> false
|
|
end.
|
|
|
|
attempt_place(State, {X, Y}) ->
|
|
Column = maps:get(X, State, []),
|
|
case fast_forward(Y, Column) of
|
|
[{Floor, _End} | _Rest] ->
|
|
case test_spot(State, X-1, Floor) of
|
|
false -> attempt_place(State, {X-1, Floor}); % can optimize by shrinking active state here
|
|
true ->
|
|
case test_spot(State, X+1, Floor) of
|
|
false -> attempt_place(State, {X+1, Floor}); % can optimize by shrinking active state here
|
|
true -> {X, Floor-1}
|
|
end
|
|
end;
|
|
[] -> falling
|
|
end.
|
|
|
|
fast_forward(_Any, []) -> [];
|
|
fast_forward(Item, [{_,End}|Rest]) when Item > End -> fast_forward(Item, Rest);
|
|
fast_forward(_Item, List) -> List.
|
|
|
|
rset_new() -> [].
|
|
|
|
% rangeset is a sorted set of discrete ranges. Adjacent ranges are merged.
|
|
rset_append(Entry, []) -> [Entry];
|
|
rset_append({_, End} = Entry, [{HeadStart, _} | _] = Set) when End < HeadStart - 1 -> [Entry | Set];
|
|
rset_append({Start, _} = Entry, [{_, HeadEnd} = Head | Rest]) when Start > HeadEnd + 1 -> [ Head | rset_append(Entry, Rest)];
|
|
rset_append({Start, End}, [{HeadStart, HeadEnd} | Rest]) -> rset_append({min(Start, HeadStart), max(End, HeadEnd)}, Rest).
|
|
|
|
rset_contains(_Item, []) -> false;
|
|
rset_contains(Item, [{Start, _}|_Rest]) when Item < Start -> false;
|
|
rset_contains(Item, [{_, End}|Rest]) when Item > End -> rset_contains(Item, Rest);
|
|
rset_contains(_Item, _Rest) -> true.
|