Advent of Code, in Erlang: Day 9

While we give people a few more hours to recover from Day 19 and delight in the relative ease of Day 20, let's take a trip back through time and discuss Advent of Code, Day 9. We're back to looking at a tile of numbers, and comparing them to their neighbors.

buffer_map([Head|_]=Map) ->
    DummyRow = lists:duplicate(length(Head)+2, 9),
    [DummyRow] ++
        [ [9] ++ R ++ [9] || R <- Map ]
        ++ [DummyRow].

I started my solution by ammending the map with a border of highest points. Since the scan of the map has to look at "neighbors" of each square, this puts neighbors next to the literal edge-cases, so my code doesn't have to worry about them.

score_low_spots([Above,This,Below|Rest]) ->
    ZipRow = lists:zip3(Above, This, Below),
    score_row(ZipRow) + score_low_spots([This,Below|Rest]);
score_low_spots(_) ->
    0.

score_row([{_, Left, _},{Above, This, Below}=T,{_, Right, _}=N|Rest])
  when This < Left,
       This < Above,
       This < Below,
       This < Right ->
    This + 1 + score_row([T,N|Rest]);
score_row([_|Rest]) ->
    score_row(Rest);
score_row([]) ->
    0.

I stored the map as a list of row-lists, as I've done on previous days. So, my risk scoring algorithm is a traversal of those lists, considering the first three elements of the remaining list in each pass. In the outer loop, that means I'm looking at the row Above and Below This current one. This is where my buffer comes in: Above will be the buffer row on the first pass, and Below will be the buffer row on the last pass. The call to lists:zip3 correlates the pixels in each column of those three rows, so that in the inner loop, it's easy to pick out exact the neighbors of each pixel (the first Left will be a buffer pixel, and the last Right will be a buffer pixel, as well).

15 = puzzle09:score_low_spots(puzzle09:buffer_map(Example)).

Part 2 asks for not low points but low regions. I wasn't sure how to approach this at first. Did I need to do some sort of spiraling walk out from the low spots? Then it hit me: overlapping ranges! That is, turn each row into a list of basin "ranges" that mark the starts and the ends of each sub-9 area in a row, and then merge the ranges across rows.

find_row_basins([Row|Rest], Acc) ->
    case lists:foldl(fun(9, {undef, L, Basins}) ->
                             {undef, L+1, Basins};
                        (9, {Start, L, Basins}) ->
                             {undef, L+1, [{Start, L-1}|Basins]};
                        (_, {undef, L, Basins}) ->
                             {L, L+1, Basins};
                        (_, {Start, L, Basins}) ->
                             {Start, L+1, Basins}
                     end,
                     {undef, 0, []},
                     Row) of
        {undef, _, Basins} ->
            find_row_basins(Rest, [Basins | Acc]);
        {Start, L, Basins} ->
            find_row_basins(Rest, [ [{Start, L-1}|Basins] | Acc])
    end;
find_row_basins([], Acc) ->
    Acc.

This code turns each row into a list of basin ranges. The fold is a little hard to follow, with so many clauses and unnamed arguments, but it works like this. The accumulator has three fields: the Start location of the current basin (if we're in one), the current Location we're considering, and the list of Basins so far. The first argument to the function is the height of the current location. Treat the clauses like a state machine:

1. If the value at the current location (the "event" the state machine is processing) is a 9, and we're not currently in a basin (the start is undefined), ignore it and move to the next location.
2. If the value is a 9 and we are currently in a basin, update our state to note we're no longer in a basin, and add a range noting the start and end of this basin ({Start, L-1}) to the list of Basins.
3. If the value is not a 9, and we're not in a basin, change our state to note that we're now in a basin (by setting the start field to the current Location).
4. If the value is not a 9, and we're already in a basin, leave our state as-is, and just move to the next value.

The function itself accumulates the list of basin ranges in a list of rows, for processing by the next function.

group_row_basins([Row|Rest], Acc) ->
    group_row_basins(Rest, group_row(Row, Acc));
group_row_basins([], Acc) ->
    Acc.

group_row([{Start,End}|Rest], Acc) ->
    {Overlapping, NotOverlapping} =
        lists:partition(
          fun({Spans, _, _}) ->
                  lists:any(
                    fun({SpanStart, SpanEnd}) ->
                            ((SpanStart =< Start) and (Start =< SpanEnd)) or
                                ((SpanStart =< End) and (End =< SpanEnd)) or
                                ((Start =< SpanStart) and (SpanStart =< End)) or
                                ((Start =< SpanEnd) and (SpanEnd =< End))
                    end,
                    Spans)
          end,
          Acc),
    case Overlapping of
        [] ->
            NewOverlapping = {[], [{Start, End}], End-Start+1};
        _ ->
            NewOverlapping =
                lists:foldl(
                  fun({Spans, NextSpans, Count},
                      {AccSpans, AccNextSpans, AccCount}) ->
                          {Spans ++ AccSpans,
                           NextSpans ++ AccNextSpans,
                           Count+AccCount}
                  end,
                  {[], [], 0},
                  [{[],[{Start,End}], End-Start+1}|Overlapping])
    end,
    group_row(Rest, [NewOverlapping|NotOverlapping]);
group_row([], Acc) ->
    [{NextSpans, [], Count} || {_, NextSpans, Count} <- Acc].

The first function, group_row_basins is simple: it recursively walks the list of row-ranges, and "groups" each row into its accumulator.

The mess in second function, group_row, I apologize for. It's a two-stage ordeal. The first stage partitions the Accumulated list of basins into those with ranges in the previous row that Overlap the current range in the current row, and those that do NotOverlap. The big and/or/and/or/and/or/and block is the comparison of range starts and ends, to determine if they're overlapping.

The second stage of the second function is the real magic. This fold takes basins that looked independent until now and connects them together. Each pass through the group_row function is looking at only one range in a row. If multiple ranges from the previous row overlap this one range, then those ranges, and this one, are part of the same basin. This fold will also do the opposite, grouping two different ranges in this row that both overlap the same larger range in the previous row, into the same basin.

The final one-line clause of group_row is book-keeping. We've been keeping the ranges from the current row of each basin in a separate list from the ranges of the previous row. When we've processed all of the ranges it this row, it becomes the previous row, so we overwrite the old ranges with the new ones.

Basins = puzzle09:group_row_basins(
             puzzle09:find_row_basins(
                 puzzle09:buffer_map(Example),
                 []),
             []).
[{_,_,A},{_,_,B},{_,_,C}|_] = lists:reverse(lists:keysort(3, Basins)).
1134 = A*B*C.

Once we have our basins, we only need to sort them in descending order by their size, which group_row_basins was kind enough to keep track of for us. The product of the sizes of the three larges was the puzzle's request.

One of my former coworkers liked to ask an interview question about combining overlapping ranges. Of course that whiteboard coding session (I know, I know) was never allowed to happen in Erlang, so I had never written such a fold before. But, I had done a similar exercise to see what we were asking of interviewees. That's something of a theme in these puzzles, which I may touch on in a wrap-up post when this event is complete. For now, if you can't stand the mess in group_row, the full module is up on github, for you to reorganize as you please.

Categories: Development AdventOfCode