# Advent of Code 2021 - Day 4

This topic is about Day 4 of the Advent of Code 2021.

We have a private leaderboard (shared with users of the elixir forum):

The entry code is:
`370884-a6a71927`

6 Likes

Solutions are getting messier :

``````main(File) ->
[NumbersRaw|CardsRaw] = bin_split(RawData, <<"\n\n">>),
Numbers = [ binary_to_integer(N) || N <- bin_split(NumbersRaw, <<",">>) ],
Cards   = [ [ [ binary_to_integer(N)
|| N <- bin_split(Rows, <<" ">>), N =/= <<>> ]
|| Rows <- bin_split(C, <<"\n">>) ]
|| C <- CardsRaw ],
io:format("part 1: ~p~n", [solve1(Numbers, Cards)]),
io:format("part 2: ~p~n", [solve2(Numbers, Cards)]),
ok.

bin_split(Binary, Subj) ->
binary:split(Binary, Subj, [global, trim]).

solve1(Numbers, Cards) ->
{[Winner|_], _NewCards, N, _NewNumbers} = bingo(Numbers, Cards),
score(Winner) * N.

bingo([N|Numbers], Cards) ->
case lists:partition(fun is_winner/1, [ update_card(N, C) || C <- Cards ]) of
{[], NewCards} ->
bingo(Numbers, NewCards);
{Winners, NewCards} ->
{Winners, NewCards, N, Numbers}
end.

update_card(Number, Card) ->
[ [ case X of
Number -> false;
_      -> X
end || X <- Row] || Row <- Card ].

is_winner(Card) ->
check_rows(Card) orelse check_columns(Card).

check_rows(Card) ->
lists:any(fun (Row) -> not lists:any(fun is_integer/1, Row) end, Card).

check_columns([[false|_], [false|_], [false|_], [false|_], [false|_]]) -> true;
check_columns([[_|A],     [_|B],     [_|C],     [_|D],     [_|E]])     -> check_columns([A, B, C, D, E]);
check_columns([[],        [],        [],        [],        []])        -> false.

score(Card) ->
lists:sum([ N || Row <- Card, N <- Row, is_integer(N) ]).

solve2(Numbers, Cards) ->
case bingo(Numbers, Cards) of
{[Winner], [], N, _NewNumbers} ->
score(Winner) * N;
{_Winners, NewCards, _N, NewNumbers} ->
solve2(NewNumbers, NewCards)
end.
``````
6 Likes

Day 4 in Sesterl - this time I started using optional function arguments for recursion accumulators adventofcode/main.sest at master Â· michallepicki/adventofcode Â· GitHub

5 Likes

Iâ€™m not a big fan of the puzzles that require wasted effort in either writing a file parser, or else doing significant manipulation of the input data in your favourite editor.

5 Likes

You can get a significant number of results by looking at the input shape:

• split the first line on `,`
• each board is split by an empty line
• each board has 5 rows and 5 columns for a flat 25 entries
• all the values are fitting between 0 and 99 inclusively

You donâ€™t actually need to do fancy parsing; you can represent each board as a sequence (either a binary, a list) of integers (or use the `array` module); you only need to split on `" "` and append, until you hit an empty line which means you complete a board. Put all boards themselves put in a list.

On each run, look into each list, and â€śmarkâ€ť the matching number if any. If you use a list or a tuple (converted from a list), you can use a non-integer value (e.g. the atom `found`); if you use binaries, pick an out-of-bound value (100â€¦255 inclusively).

Checking for a win only requires checking rows (`N..N+5` where `N` is 1,6,11,â€¦) and columns (`N,N+5,N+10,N+15,...` where `N` is 1,2,3â€¦) for all entries being your marker. The score of a winning board is the sum of all non-marker values.

Itâ€™s one of the tricks for a lot of Advent of Codes: things look like a fancy datastructure (they use tons of matrices), but you can get a lot done with very little parsing if theyâ€™re regular-shaped â€“ always a square or a rectangle â€“ by just putting them in a map or binary or list and just hopping around by doing something very similar to C pointer arithmetic (`f[row][col] == f[row*width + col]`, with 0-indexing).

5 Likes

Here, I wipped up a quick one showing the principle there using lists:

``````-module(day4).
-export([main/1]).

main([File]) ->
Draws = [binary_to_integer(B) || B <- string:split(RawDraws, ",", all)],
Boards = [[binary_to_integer(RawNum)
|| RawNum <- re:split(RawBoard, "\\s+", [multiline]),
RawNum =/= <<>>]
|| RawBoard <- string:split(Rest, "\n\n", all)],
io:format("~p~n", [play(Draws, Boards)]),
halt(0).

win(L) ->
lists:any(fun(SL) -> length(SL)==5 end,
[lists:filter(fun(X) -> X==x end, lists:sublist(L, N, 5))
|| N <- [1,6,11,16,21]])
orelse
lists:any(fun(SL) -> length(SL)==5 end,
[lists:filter(fun(X) -> X==x end,
[lists:nth(N,L), lists:nth(N+5,L), lists:nth(N+10,L),
lists:nth(N+15,L), lists:nth(N+20,L)])
|| N <- [1,2,3,4,5]]).

mark([],_) -> [];
mark([X|T],X) -> [x|T];
mark([H|T],X) -> [H|mark(T,X)].

score(L) ->
lists:sum([X || X <- L, X=/=x]).

play([D|Ds], Boards) ->
NewBoards = [mark(B, D) || B <- Boards],
case [B || B <- NewBoards, win(B)] of
[] -> play(Ds, NewBoards);
[W] -> score(W)*D
end.
``````

Itâ€™s less effective than it could be because of all the calls to `lists:nth/2` being done eagerly, but thatâ€™s relatively easy to alter the data structure. The parsing is 6-7 lines of code.

6 Likes

I agree!
Maybe next week I will work on trying to clean a â€śmessyâ€ť solution, instead of writing my own.

5 Likes

Did you decide to make it work only on AoCâ€™s input file? Because it seems to me that Part 1 doesnâ€™t work on AoCâ€™s example.

3 Likes

Interesting the different styles of solving that. Here is mine:

Read, split tokenise and convert to numbers with a deep mapping.

Boards are list of list of integers. I attach the transpose to the board for columns.

Bingo steps are done by removing the played number from the lists, counting steps, sorting.

Conveniently I just need to add all integers in a board (everything played is removed) and divide by 2 (because I have the board normal and transposed).

``````p4() ->
Tab = lists:sort([{steps(Nums,B++transpose(B),0),B}
|| B <- Boards]),
{{_,L1,S1}, _}= hd(Tab),
{{_,L2,S2}, _}= lists:last(Tab),
{L1*(S1 div 2), L2*(S2 div 2)}.

steps([], _, Count) ->
{Count + 1, [], 0};
steps([Num|R], Board, Count) ->
B = play(Num, Board),
case bingo(B) of
true  -> {Count+1, Num, lists:sum(lists:flatten(B))};
false -> steps(R, B, Count+1)
end.

play(Num, Board) ->
[ [ E || E <- L, E =/= Num ] || L <- Board ].

bingo(Board) ->
lists:any(fun(X) -> X =:= [] end, Board).

[Nums|Boards] = string:split(string:trim(Bin), "\n\n", all),
deep_integer([string:split(Nums, ",", all),
[ [ string:lexemes(L, " ")
||  L <- string:split(B, "\n", all) ]
|| B <- Boards]]) .

deep_integer(L) when is_list(L) ->
[ deep_integer(E) || E <- L ];
deep_integer(B) when is_binary(B) ->
binary_to_integer(B).

transpose([[]|_]) ->
[];
transpose(LoL) ->
R = [hd(L) || L <- LoL],
Cs = [tl(L) || L <- LoL],
[R|transpose(Cs)].
``````
6 Likes

For a shorter solution this can be inlined, but its more readable this way

5 Likes

@adolfont example works for me on my code, if youâ€™re on windows - you need to convert line endings to unix, what error do you get?

4 Likes

Your code is here pensandoemelixir/adventofcode/2021/day04_2021 at main Â· adolfont/pensandoemelixir Â· GitHub as `danilagamma.erl`. I run main/0 (see image below) that contains:

``````main() ->
main("input_from_description.txt"),
main("input.txt").
``````

and it returns 2226, instead of 4512.

My input_from_description.txt file is here pensandoemelixir/input_from_description.txt at main Â· adolfont/pensandoemelixir Â· GitHub
and it was copied, as the name says, from the description.

3 Likes

Here is a bingo module a came up withâ€¦

``````-module(bingo).
-export([new_board/1, play/2, score/1, score/2]).

-record(cell, {val, marked = false}).
-record(board, {grid = #{}, win = false}).

-define(SIZE, 5).

new_board(List) ->
{Board, _} = lists:foldl(fun(X, Acc) -> reducer(X, Acc) end,
{#board{}, 0}, List),
Board.

play(#board{grid = Grid} = Board, Move) ->
Pred = fun(_Coord, #cell{val = Value}) -> Value == Move end,
case maps:filter(Pred, Grid) of
Map when map_size(Map) =:= 0 -> Board;
Map when map_size(Map) =:= 1 ->
[{Coord, Cell}|_T] = maps:to_list(Map),
NewGrid = maps:put(Coord, Cell#cell{marked = true}, Grid),
Board#board{grid = NewGrid, win = is_winning(NewGrid, Coord)}
end.

score({Board, Move}) -> score(Board, Move).
score(#board{grid = Grid}, Move) ->
List = maps:values(maps:filter(fun(_Coord, #cell{marked = Marked}) ->
Marked =:= false
end, Grid)),
X = lists:sum(lists:map(fun(#cell{val = Value}) -> Value end, List)),
X * Move.

reducer(Val, {Board, Current}) ->
Grid = maps:put(to_coord(Current), #cell{val = Val}, Board#board.grid),
{Board#board{grid = Grid}, Current + 1}.

to_coord(Index) ->
{Index div ?SIZE, Index rem ?SIZE}.

is_winning(Grid, {Row, Col}) ->
Pred = fun({_, #cell{marked = Marked}}) -> Marked =:= true end,
lists:all(Pred, get_line(row, Grid, Row)) or
lists:all(Pred, get_line(col, Grid, Col)).

get_line(row, Grid, Index) ->
maps:to_list(maps:filter(fun({Row, _Col}, _Cell) -> Row =:= Index end, Grid));
get_line(col, Grid, Index) ->
maps:to_list(maps:filter(fun({_Row, Col}, _Cell) -> Col =:= Index end, Grid)).
``````

I have been fighting a lot to replace the Elixir Enum module

My full Elixir code is here.

4 Likes

There is an empty whitespace in the end of the example file that shouldnâ€™t be there, removing it makes it return correct result

4 Likes

OKâ€¦ Here is my messy solution :
Part 1:

``````part1() ->
[H|T] = split(Text, <<"\n\n">>),
Numbers = split(H, <<",">>),
Cards = [lists:flatten([[ X || X <- split(R, <<" ">>), X /= <<>>] || R <- split(Card, <<"\n">>)]) || Card <- T],
play(Cards, Numbers).

split(Bin, Pattern) -> binary:split(Bin, Pattern, [global, trim]).

play(_, []) -> ok;
play(Cards, [Number|Numbers]) ->
UpdatedCards = check(Cards, Number),
case [Card ||Card <- UpdatedCards, is_win(Card)] of
[] -> play(UpdatedCards, Numbers);
[Winner] -> calculate(Winner, Number)
end.

check([], _) -> [];
check([H|T], Number) -> [is_exist(Number, H) | check(T, Number)].

is_win([]) -> false;
is_win([{_, true}, {_, true}, {_, true}, {_, true}, {_, true}|_]) -> true;
is_win([_, _, _, _, _|T]) -> is_win(T).

is_exist(Item, [Item|Rest]) -> [{Item, true} | is_exist(Item, Rest)];
is_exist(Item, [H|Rest]) -> [H | is_exist(Item, Rest)];
is_exist(_, []) -> [].

calculate(Card, Number) -> binary_to_integer(Number) * lists:sum([ binary_to_integer(C) || C <- Card, is_binary(C)]).
``````

Part 2:

``````part2() ->
[H|T] = split(Text, <<"\n\n">>),
Numbers = split(H, <<",">>),
Cards = [ [ [ X || X <- split(R, <<" ">>), X /= <<>> ] || R <- split(Card, <<"\n">>)] || Card <- T],
[{N, W}|_] = play(Cards, Numbers, []),
calculate(W, N).

split(Bin, Pattern) -> binary:split(Bin, Pattern, [global, trim]).

play([], _, Acc) -> Acc;
play(Cards, [Number|Numbers], Acc) ->
UpdatedCards = check(Cards, Number),
case [Card || Card <- UpdatedCards, is_win(Card)] of
[] ->
case is_win_down(UpdatedCards, UpdatedCards, []) of
[] -> play(UpdatedCards, Numbers, Acc);
Winner -> play(UpdatedCards -- Winner, Numbers, [{Number, Winner} | Acc])
end;
[Winner|_] = Z -> play(UpdatedCards -- Z, Numbers, [{Number, Winner} | Acc])
end.

check([], _) -> [];
check([H|T], Number) -> [[is_exist(Number, R) || R <- H] | check(T, Number)].

is_win([]) -> false;
is_win([[{_, true}, {_, true}, {_, true}, {_, true}, {_, true}|_]|_]) -> true;
is_win([[_, _, _, _, _]|T]) -> is_win(T).

is_win_down([], _, Acc) -> Acc;
is_win_down([[[{_, true}|_],[{_, true}|_],[{_, true}|_],[{_, true}|_],[{_, true}|_]]|T1], [H|T2], Acc) -> is_win_down(T1,T2,[H|Acc]);
is_win_down([[[_|T1],[_|T2],[_|T3],[_|T4],[_|T5]]|T], Cards, Acc) -> is_win_down([[T1,T2,T3,T4,T5]|T], Cards, Acc);
is_win_down([_|T], [_|T], Acc) -> is_win_down(T, T, Acc).

is_exist(Item, [Item|Rest]) -> [{Item, true} | is_exist(Item, Rest)];
is_exist(Item, [H|Rest]) -> [H | is_exist(Item, Rest)];
is_exist(_, []) -> [].

calculate(Card0, Number) ->
Card = lists:flatten(Card0),
binary_to_integer(Number) * lists:sum([ binary_to_integer(C) || C <- Card, is_binary(C)]).
``````
5 Likes