Day 8: Space Image Format

---

Links:

• Puzzle on adventofcode.com
• Source Code

I wrote the converter from the one dimensional input format to the three dimensional representation before reading what the first part wanted from me. I’m mentioning this, because the first part can be solved using a single pass over the input. I, however, used 2 passes. The first one converts the input to the row = pixel[]; layer = row[]; ìmage = layer[] representation and the second one performs the “checksum” calculation. Since it “merely” doubled the workload and I could reuse the code for the second part I didn’t bother rewriting it though.

The only interesting thing I have to say about my solution for the second part is how I chose to merge the layers. There are two approaches I would like to highlight.

First we could take inspiration from the real life analogue of printing each layer, cutting away the transparent parts, and stacking them on top of each other to get the image. In code this could be accomplished by iterating over the layers in reverse and adding each non-transparent pixel to the resulting image.

The second approach is to iterate over each pixel in the resulting image and assign it the colour of the first non-transparent pixel in all layers. In other words, we take all pixels from the first layer and if there are transparent pixels, replace them with those from the second layer and if the second layer still has transparent pixels, take them from the third and so on.

Both approaches have the same asymptotic time complexity of $\mathcal{O}(w * h * l)$ (w: image width, h: image height, l: amount of layers), but the first one always iterates over each pixel in every layer whereas the second approach only iterates over as many layers as needed to get a non-transparent colour (i.e. $\Omega(w * h * l)$).

Given that all characters are at most 5 pixels wide and exactly 25 tall, one could feasibly implement a character detection algorithm to determine the characters in all of the 5 slots. The space is divided into five 5 pixel wide slots and most characters take up 4 pixels followed by a gap, but there are some characters (notably “Y”) which take up 5 pixels with no gap to the next character. One quick and dirty trick would be to check each slots against the representations of all possible characters to find the correct one. I didn’t do this because I couldn’t possibly derive all characters’ representations from my output and also because I really liked how the coloured output turned out.

---

Overview
Previous day Next day