Advent of Code, in Erlang: Day 11

I haven't tried Advent of Code Day 23 yet. I want to think about which approach to take. While I'm delaying that, why don't we talk about a puzzle writeup I've been delaying - Day 11.

I solved Day 11 on December 11, a day before I started blogging about my solutions. I didn't really enjoy the puzzle, though. I solved it with a three-stage process:

1. Increment all octopus energy.
2. Iterate through all octopi, and generate a "flash mask" - a map of energy to add to each flashing octopus's neighbors.
3. Apply the mask, then repeat steps 2 and 3 until an empty flash mask is generated.

It felt like a lot of tedium, and I've had trouble finding something interesting in the resulting code to write about.

So let's throw that solution away, and follow the path some other solvers are taking. Let's build a silly implementation, just because.

Two days ago, I noted that I hadn't used Erlang parallelization in my solutions yet. What if for Day 11, we dive all the way in. Let's make each octopus an independent process that actually sends energy to its neighbors. We'll also need one "observer" process, to tell the octopi when to start each round, and to sum up the flashes that happen each round. (Fig.1)

Let's design the messages all of these processes will send each other first. The observer is very simple. Each round, it will send an advance message to each octopus (Fig.2), and will then wait for a done message from each octopus. The done message will include the number of flashes that that octopus "caused".

Octopuses are a little more complicated. They'll first wait for an advance message from the observer (Fig.2). When they get one, they increment their energy.

If their energy is below the threshold, they send a done message with a zero flash count back to the observer. (Fig.3)

However, if their energy is high enough, they send a flash message to each of their neighbors (Fig.4), and then wait for replies from those neighbors. They wait for all the replies before sending their own done back to the observer.

When an octopus receives a flash message, it first checks to see if it has flashed this round. If it has not, it increments its energy and checks if it should flash now. If it should, it sends its own flash message to each of its own neighbors. (Fig.5) This might include the octopus from which it just received a flash! (This is the saddest moment [PDF] of octopus communication.)

If an octopus has already flashed this round, or the additional energy is not enough to make it flash, it replies to the flashing neighbor with a reflect message counting zero new flashes. (Fig.6)

When a flashing octopus receives all of its reflect replies, if the octopus's flash was in response to another octopus's flash, it sends its own reflect back to that octopus, with a flash count equal to the sum of its received reflect flash counts, plus one (its own flash). (Fig.7)

If instead, the octopus flashed in response to the observer's advance message, then when it receives all of its reflect messages, it finally sends its own done message to the observer, with the same sort of sum-of-recieved-reflects-plus-one count. (Fig.8) The observer sums the values in all of the done messages together to arrive at the total number of flashes that happened during this step.

I know Erlang programmers. They're all wondering what happens if these messages arrive out of order. I have a simple solution for that: every message is also tagged with the Step in which it was sent. I think the most important race is between the observer sending advance and a neighbor sending flash. But, the advance will be sent in step S, and the flash will be sent in step S+1. So, using selective receive, I can wait for the advance before I process the flash. Maybe you'd feel better reading the octopus code:

octopus(Observer, Neighbors, Step, Energy, Flashed) ->
    receive
        {Step, advance} ->
            case Energy + 1 of
                10 ->
                    _ = [ N ! {Step+1, {flash, self()}} || N <- Neighbors ],
                    octopus(Observer, Neighbors, Step+1, 0,
                            {self, length(Neighbors), 1});
                NewEnergy ->
                    Observer ! {Step+1, {done, 0}},
                    octopus(Observer, Neighbors, Step+1, NewEnergy, false)
            end;
        {Step, {flash, Neighbor}} ->
            case Flashed of
                {_, _, _} ->
                    Neighbor ! {Step, {reflect, 0}},
                    octopus(Observer, Neighbors, Step, Energy, Flashed);
                false ->
                    case Energy + 1 of
                        10 ->
                            _ = [ N ! {Step, {flash, self()}}
                                  || N <- Neighbors ],
                            octopus(Observer, Neighbors, Step, 0,
                                    {{reflect,Neighbor},
                                     length(Neighbors),
                                     1});
                        NewEnergy ->
                            Neighbor ! {Step, {reflect, 0}},
                            octopus(Observer, Neighbors, Step, NewEnergy,
                                    false)
                    end
            end;
        {Step, {reflect, Reflects}} ->
            case Flashed of
                {self, 1, Flashes} ->
                    Observer ! {Step, {done, Flashes+Reflects}},
                    octopus(Observer, Neighbors, Step, Energy,
                            {self, 0, Flashes+Reflects});
                {{reflect, Neighbor}, 1, Flashes} ->
                    Neighbor ! {Step, {reflect, Flashes+Reflects}},
                    octopus(Observer, Neighbors, Step, Energy,
                            {{reflect, Neighbor}, 0, Flashes+Reflects});
                {Who, Remaining, Flashes} ->
                    octopus(Observer, Neighbors, Step, Energy,
                            {Who, Remaining - 1, Flashes + Reflects})
            end;
        stop ->
            ok
    end.

There's a bit of duplication that could be cleaned up, but I think it's nice that the entirety of the octopus's behavior is captured in this one function.

observer(Steps, Pids) ->
    Flashes = lists:foldl(
                fun(Step, Flashes) ->
                        _ = [ P ! {Step, advance} || P <- Pids ],
                        observer_wait(Pids, Step+1, Flashes, length(Pids))
                end,
                0,
                lists:seq(0, Steps-1)),
    _ = [P ! stop || P <- Pids],
    Flashes.

observer_all_flash(MaxSteps, Pids, MaxSteps) ->
    _ = [P ! stop || P <- Pids],
    not_observed;
observer_all_flash(MaxSteps, Pids, Step) ->
    _ = [ P ! {Step, advance} || P <- Pids ],
    case observer_wait(Pids, Step+1, 0, length(Pids)) of
        Flashes when Flashes == length(Pids) ->
            _ = [P ! stop || P <- Pids],
            Step+1;
        _ ->
            observer_all_flash(MaxSteps - 1, Pids, Step+1)
    end.

observer_wait(Pids, Step, Flashes, Advance) ->
    receive
        {Step, {done, NewFlashes}} ->
            case Advance - 1 of
                0 ->
                    Flashes + NewFlashes;
                NewAdvance ->
                    observer_wait(Pids, Step, Flashes+NewFlashes, NewAdvance)
            end
    end.

While the core observer behavior is the same (P ! {Step,advance} followed by observer_wait), I have a different top-level observer function for Part 1 and Part 2, to capture the conditions requested.

Octopi = [ [ C - $0 || C <- binary_to_list(Row) ]
          || Row <- string:split(Example, <<"\n">>, all), Row =/= <<>> ].
1656 = puzzle11:count_flashes_for_round(100, Octopi).
195 = puzzle11:count_rounds_to_all_flash(1000, Octopi).

So there you have it - communicating octopus processes. There are a startup messages I didn't cover - octopi announcing their initial readiness to the observer, and the observer telling the octopi who their neighbors are - but if you're curious, the code is on github. There you can also find my earlier implementation, if you really want a list-manipulation workout.

Categories: Development AdventOfCode