Advent of Code, in Erlang: Day 20

I considered doing more bit mashing, bit masking, bit matching today. I really did. Advent of Code, Day 20 backs the time commitment down from Day 19 far enough that it was tempting to spend time on efficiency. But a very tiny amount of pre-processing of these images and enhancement algorithms, makes a simpler route much more fun:

hashdot_to_onezero(Bin) ->
    << <<(case B of $# -> $1; $. -> $0 end)>> || <<B>> <= Bin >>.

Replace every "#" character with a "1" character, and replace ever "." with a "0". Why? Because then the "image enhancement" lookup goes like this:

-record(i, {e,   % enhancement
            w,   % width
            h,   % height
            b,   % background
            d}). % data

enhanced_pixel(Image=#i{e=En}, X, Y) ->
    binary:at(En, enhancement_index(Image, X, Y)).

enhancement_index(Image, X, Y) ->
    list_to_integer([pixel_at(Image, C, R)
                     || {C, R} <- [{X-1, Y-1}, {X, Y-1}, {X+1, Y-1},
                                   {X-1, Y}, {X, Y}, {X+1, Y},
                                   {X-1, Y+1}, {X, Y+1}, {X+1, Y+1}]],
                    2).

pixel_at(#i{d=D, w=W, h=H}, X, Y) when X >= 0, X < W, Y >= 0, Y < H ->
    binary:at(D, Y*W+X);
pixel_at(#i{b=B}, _, _) ->
    B.

Zero bit manipulation. None. Just tell list_to_integer that the digits it is converting are in base 2. Is it the paragon of efficiency? For code production, yes, likely. I wouldn't try to use it on realtime video display.

enhance(Image) ->
    enhance(Image, -1, -1, []).

enhance(Image, X, Y, Acc) when X < Image#i.w+1 ->
    enhance(Image, X+1, Y, [enhanced_pixel(Image, X, Y)|Acc]);
enhance(Image, _, Y, Acc) when Y < Image#i.h+1 ->
    enhance(Image, -1, Y+1, Acc);
enhance(Image=#i{w=W,h=H}, _, _, Acc) ->
    Image#i{w=W+2, h=H+2, b=new_background(Image),
            d=list_to_binary(lists:reverse(Acc))}.

new_background(#i{e=En, b=B}) ->
    binary:at(En, list_to_integer(lists:duplicate(9, B), 2)).

My enhance function is a straightforward scan through every pixel from -1,-1 to Width+1,Height+1. I think the one interesting thing is a corner case I just happened to notice before I started coding: the background. The "image enhancement algorithm" in my puzzle input starts with a hash/one and ends with a dot/zero. This means when the scan area passes over an aread that is all dots/zeros, it inserts a hash/one pixel, and when it passes over an area that is all hashes/ones, it inserts a dot/zero pixel. This is rare in the middle of the interesting part of the image, but since we are to consider the canvas "infinite" it happens all the time! The "background" of my image blinks. My solution to the impossibility of flipping an infinite number of pixels was just to store which value all of them would have, and to get that value from flipping just one sample of all-background color.

count_on_pixels(#i{d=D}) ->
    lists:sum([ 1 || <<$1>> <= D ]).

To count on pixels, I used Erlang's binary generators and pattern matching to produce a list containing an integer 1 for every "1" character in the image. The sum of this list and its length are equivalent. Again, there ways to help the computer do this faster, but if I haven't worried about runtime efficiency yet today, why start now?

35 = puzzle20:count_on_pixels(puzzle20:enhance(puzzle20:enhance(Example))).
3351 = puzzle20:count_on_pixels(lists:foldl(fun(_, I) -> puzzle20:enhance(I) end, Example, lists:seq(1, 50))).

Today is another day where the difference between Part 1 and Part 2 is just, "run your code more times," like on Day 6, Day 14, and sort of Day 15. These images aren't large enough for the constraint to be an efficiency problem, though, even for naive solutions like mine. Was this an attempt to trip up solutions that pre-allocated the full finished image space?

It's good to see the puzzle difficulty step back a hair from Sunday. I thought that puzzle was fun, but I had plenty of time, focus, and energy to do it. I was not going to keep that up for six more days, though! As always, full code for my Day 20 solution is on github.

After watching more animations of people's solutions to each puzzle, I think I've realized that everyone's puzzle inputs are different (or at least that not everyone's are the same). If that's the case, tell me (@hobbyist): does your background blink?

Categories: Development AdventOfCode