Advent of Code 2021 - Day 8

This topic is about Day 8 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

Got a bit lost on that one, initially tried to figure out each individual letter mapping and then retranslate the digits… and I did solve it like that, solution is too ugly and upon gazing on it may induce madness in the reader, so I will not post it here.
After a small break I got the solution where instead of letters you map entire digits, that looks way more appropriate:

main(File) ->
    {ok, RawData} = file:read_file(File),
    Data = [ [ [ ordsets:from_list(binary_to_list(N))
                 || N <- binary:split(L,  <<" ">>, [global, trim]) ]
               || L <- binary:split(Line, <<" | ">>, [trim]) ]
             || Line <- binary:split(RawData, <<"\n">>, [global, trim]) ],
    io:format("part 1: ~p~n", [solve1(Data)]),
    io:format("part 2: ~p~n", [solve2(Data)]),
    ok.

solve1(Data) ->
    length([ O || [_, Output] <- Data, O <- Output, lists:member(length(O), [2, 3, 4, 7]) ]).

solve2(Data) ->
    lists:sum([ solve_line(Input, Output) || [Input, Output] <- Data ]).

%% 1 -> "cf"
%% 7 -> "acf"
%% 4 -> "bcdf"
%% 2 -> "acdeg"
%% 3 -> "acdfg"
%% 5 -> "abdfg"
%% 0 -> "abcefg"
%% 6 -> "abdefg"
%% 9 -> "abcdfg"
%% 8 -> "abcdefg"

solve_line(Input, Output) ->
    [One]   = find_len(Input, 2),
    [Four]  = find_len(Input, 4),
    [Seven] = find_len(Input, 3),
    [Eight] = find_len(Input, 7),
    [Three] = [ N || N <- find_len(Input, 5), length(ordsets:intersection(N, One)) =:= 2 ],
    [Nine]  = [ N || N <- find_len(Input, 6), length(ordsets:subtract(N, Three))   =:= 1 ],
    ZeroSix = [ N || N <- find_len(Input, 6), N =/= Nine ],
    [Zero]  = [ N || N <- ZeroSix,            length(ordsets:intersection(N, One)) =:= 2 ],
    [Six]   = ZeroSix -- [Zero],
    TwoFive = [ N || N <- find_len(Input, 5), N =/= Three ],
    [Five]  = [ N || N <- TwoFive,            length(ordsets:intersection(N, Four)) =:= 3 ],
    [Two]   = TwoFive -- [Five],
    Map = #{Zero  => $0, One   => $1, Two   => $2,
            Three => $3, Four  => $4, Five  => $5,
            Six   => $6, Seven => $7, Eight => $8,
            Nine  => $9},
    list_to_integer([ maps:get(O, Map) || O <- Output ]).

find_len(List, Len) ->
    [ L || L <- List, length(L) =:= Len ].
5 Likes

There is a chain of bitwise operations to deduce a wiring.

3 Likes

Awk ended up being a real weird but somewhat competent match for this:

6 Likes

Didn’t want to go with specialised code and wanted something somewhat more general.

From the digit patterns I deduce the single solution digits without putting them in a priori.

Then I use intersection sizes of these known digits with the unknown patterns, reducing the possibilities what it could be. I think it converged after one step of this so its totally over engineered, because I repeat with the newly learned sets of known digit patterns which seems not necessary :wink:

p8_2() ->
    lists:sum([ digit_solve(A,B) || {A,B}<- p8_read("priv/p08.txt") ]).


digit_solve(A,B) ->
    L = [ {P, [ S || S <- lists:seq(0,9), length(segs(S)) =:= length(P) ]} 
          || P <- A ],
    M = solve_steps(L),
    Res = lists:append([ element(2, lists:keyfind(D, 1, M))  ||  D <- B ]),
    list_to_integer([ R+$0 || R <- Res ]).

solve_steps(L) ->
    case lists:partition(fun({_, Ds}) -> length(Ds) =:= 1 end, L) of
        {Solved, []} -> Solved;
        {Solved, Un} -> 
            solve_steps(Solved ++ [ reduce(U, Solved) || U <- Un ])
    end.

reduce(U, Solved) ->       
    lists:foldl(fun reduce1/2, U, Solved).

reduce1({Sp, [D]},{Up, Uds}) ->     
    Diff = length(Up -- Sp),
    {Up, [ U || U <- Uds, length(segs(U) -- segs(D)) =:= Diff ]}.
     
p8_read(Fn) ->
    {ok, Bin} = file:read_file(Fn),
    Tab = [ lists:splitwith(fun(T) -> T =/= "|" end, [ canon_digit(D) 
        || D <- string:split(L, " ", all) ] ) 
      || L <- string:split(string:trim(Bin), "\n", all) ],
    [ {A, tl(B)} || {A,B} <- Tab ].
    
               
canon_digit(Bin) ->
    lists:sort([ C || <<C:8>> <= Bin ]). 

segs(0) ->
    "abcefg";
segs(1) ->
    "cf";
segs(2) ->
    "acdeg";
segs(3) ->
    "acdfg";
segs(4) ->
    "bcdf";
segs(5) ->
    "abdfg";
segs(6) ->
    "abdefg";
segs(7) ->
    "acf";
segs(8) ->
    "abcdefg";
segs(9) ->
    "abcdfg".

6 Likes

I spent way more time on this than I should have. Part 1 is quite simple, but I was stuck quite long with part 2. My solution for the second part was to deduce segments by intersecting numbers. For example, 1 is easy to find (as only two segments are active), but we need to determine which character in the input stream corresponds to the c segment, and which to f. To do this, the number 6 can be used: This is the only digit with a 6-segment representation that has only 1 character in common with 1. That allows filtering for 6, and then determining which segment of 1 is f (the one shared with 6). The approach is similar for the remaining segments.

3 Likes

Part 1 was too easy and Part 2 was too difficult for me. I quit. Maybe next year. I mean, maybe next year I will be able to solve a problem like this one. I will take a look at the solutions here and try to learn something.

2 Likes

This one reminds me of solving sudoku puzzles :slight_smile:

3 Likes

Beautiful solution. Congrats! It needs that
ordsets:from_list(binary_to_list(N))
during parsing to work right?
It took me some time to find it.

3 Likes

Yes, it’s needed there because I’m using ordsets:intersection/subtract and ordsets expects ordset (uniquely sorted list) underneath.

3 Likes