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):

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

6 Likes

Solutions are getting messier :sweat::

main(File) ->
    {ok, RawData} = file:read_file(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 :slight_smile: 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]) ->
    {ok,Bin} = file:read_file(File),
    [RawDraws|Rest] = string:split(Bin, "\n\n", leading),
    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() ->
    [Nums,Boards] = p4_read("priv/p04.txt"),
    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).
                       
p4_read(Fn) ->
    {ok, Bin} = file:read_file(Fn),
    [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 :slight_smile:

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 :stuck_out_tongue_winking_eye::
Part 1:

part1() ->
  {ok, Text} = file:read_file("input"),
  [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() ->
  {ok, Text} = file:read_file("input_test"),
  [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

Fixed. Thanks! Later I will try to learn more from your code.

2 Likes