Advent of Code, in Erlang: Day 13

After posting Day 1's write-up, I had about half an hour before the Day 13 puzzle was released. I stepped away from my computer, and played guitar … for an hour. After that, I could feel the day's cross-country skiing catching up, so I decided to stretch. And after that I decided it was too late, and I should just sleep and tackle Day 13 in the morning.

Parsing got a little more interesting today. All input up to now had lines of the same format, but today, there are three kinds of lines: dot descriptions, a separator, and fold descriptions. I handled the separator first, then the dots and folds separately:

parse_input(Data) ->
    {DotLines, [<<>>|FoldLines]} =
        lists:splitwith(fun(L) -> L =/= <<>> end,
                        string:split(Data, <<"\n">>, all)),
    {parse_dots(DotLines), parse_folds(FoldLines)}.

parse_dots(DotLines) ->
    ordsets:from_list([ begin
                            [X,Y] = string:split(L, <<",">>),
                            {binary_to_integer(X), binary_to_integer(Y)}
                        end
                        || L <- DotLines ]).

parse_folds(FoldLines) ->
    [ begin
          [XY, V] = string:split(Axis, <<"=">>),
          {case XY of <<"x">> -> 1; <<"y">> -> 2 end,
           binary_to_integer(V)}
      end
      || <<"fold along ", Axis/binary>> <- FoldLines ].

I have really enjoyed Erlang's pattern matching for these puzzles so far. I've used it plenty in the past for bit-level decoding, but it's working great for byte-sized processing as well. The functions above produce a list of dot coordinates, which are each a pair of {X,Y}, and a list of fold instructions, which are each a pair of {Axis,Value}. I've chosen to use Axis = 1 for "fold along x=…" and Axis = 2 for "fold along y=…". Here is my fold function to (*cough*sorry*cough*) explain why:

fold_paper(Dots, []) ->
    Dots;
fold_paper(Dots, [{Axis,Value}|Rest]) ->
    {AboveLeft, BelowRight} =
        lists:partition(fun(D) -> element(Axis, D) < Value end, Dots),
    Moved = [ setelement(Axis, D,
                         element(Axis, D) - 2 * (element(Axis, D) - Value))
              || D <- BelowRight ],
    fold_paper(ordsets:union(AboveLeft, ordsets:from_list(Moved)), Rest).

"fold along x=…" changes the X coordinate of each dot, which is element 1. "fold along y=…" changes the Y coordinate, which is element 2, so by coding the Axis of the instruction this way, my fold_paper function can directly access the correct coordinate value, without ever mentioning X or Y. I think that's fun.

You can now also see why I made dots an ordset (ordered set) - I can add the moved set of dots to the unmoved set of dots (via set-union), and de-duplication happens for me automatically.

{DotsA, [FoldsA|_]} = puzzle13:parse_input(Input).
17 = length(puzzle13:fold_paper(Dots, [FoldsA])).

Part 1 only wanted the number of dots left after the first fold, so I've only captured the first fold instruction, and then counted the resulting dots. Seventeen is correct for this example.

Part 2, as expected, wants the result of all folds … but unlike previous puzzles, where the renderings were merely visual aids, this time we need to do the rendering to get our answer!

render_dots(Dots) ->
    Width = 1 + lists:max([ X || {X,_} <- Dots ]),
    Height = 1 + lists:max([ Y || {_, Y} <- Dots ]),
    Image = lists:duplicate(Height, lists:duplicate(Width, $.)),
    render_dots(Dots, Image).

render_dots([], Image) ->
    lists:foreach(fun(L) -> io:format("~s~n", [L]) end, Image),
    Image;
render_dots([{X,Y}|Rest], Image) ->
    {RowsBefore, [Row|RowsAfter]} = lists:split(Y, Image),
    {ColumnsBefore, [_|ColumnsAfter]} = lists:split(X, Row),
    render_dots(Rest,
                RowsBefore ++ [(ColumnsBefore ++ [$#|ColumnsAfter])
                               |RowsAfter]).

My rendering goes in two steps. First, I figure out what the largest X and Y coordinates I need to plot are. Another way to do this would have been to find the smallest X and Y that we folded along, but that requires extra function parameters here, or extra state in the fold function, so I've gone with this to stay simple. I use those maximal values to create an "empty" image, full of . characters, as in the examples. Then I pass the list of dots and the empty image to the second stage, and plce a # character at each dot coordinate, again as in the examples. The return value is a list of lists - each inner list being one row of "pixels". I didn't check beforehand, but it turns out there were no fold instructions for positions that were less than halfway across the image. If there had been, my renderer would have stopped with a "bad argument" exception when it found a negative coordinate value.

{Dots, Folds} = puzzle13:parse_input(Input).
puzzle13:render_dots(puzzle13:fold_paper(Dots, Folds)).
%% Output
%% #####
%% #...#
%% #...#
%% #...#
%% #####

I added the io:format to the render_dots/2 function to handle small images like the example. Otherwise, each row is small enough, that they can all fit on the same terminal line, which is what the shell prefers. This image matches the example, so our code would be "O" if this were the full puzzle input.

Did anyone render first, and then write a fold-paper function that operated on pixels instead of points? I think it could have been fun to print each stage, and watch the image develop. Let me know on Twitter (@hobbyist) if you did. You can also find me, and this code on github. Good luck solving!

Categories: Development AdventOfCode