# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python # Advent of Code 2021 - Day 20

## Problem Intro

We’re told we have an image from our scanners, but it needs enhancing. Our input contains two different things:

1. The image enhancement algorithm
2. The input image itself

The input looks something like this:

``````..#.#..#####.#.#.#.###.##.....###.##.#..###.####..### // .#.#.#...##..#.#..###..#####........#..####......#..#

#..#.
#....
##..#
..#..
..###
``````

The first line is actually 512 chars is length, but I’ve trimmed it above (indicated using `//`), for readability. Then we have a blank line, followed by the image we need to enhance, whihc is itself split over multiple lines. The image is a 2D grid of light pixels (indicated by `#`) and dark pixels (indicated by `.`).

The image enhancement algorithm does the following:

• Looks at each pixel in the 2D grid. For each pixel, determines the 3x3 grid of 9 pixels that have that pixel at its centre.
• Converts these 9 pixels into a binary representation, i.e. a 9-bit value, where `.=0` and `#=1`. (The 3x3 grid is read from top left to bottom right, across then down.) Thus, each pixel maps to a 9-bit value.
• Uses that 9-bit as an index to lookup a character position in the image enhancement line, using 0-based indexing. I.e. where an index of 0 is the first character, 1 is the second character, and so on.
• Note that a binary value of `0b000000000` = 0 in decimal. Thus, this would be a lookup to the first character in the algorithm.
• A binary value of `0b111111111` = 512 in decimal. Thus, this would be a lookup of the last character in the algorithm. (Since it’s a 512-character `str`.)
• The character found at that position is the output pixel.
• We’re told that the algorithm should apply to all pixels simultaneously. This makes life a bit easier.
• We’re told the image we’ve been provided with (in the input) is part of an image of infinite size. Throughout this walkthrough, I’m referring to this infinite background as the infinite canvas. We’re told that the infinit canvas is all dark pixels. We have to be mindful of these infinite canvas pixels, when we’re applyin the algorithm to any pixels at edges of our image.

## Part 1

Apply the image enhancement algorithm twice, and then determine how many pixels are lit.

### Setup

``````from __future__ import annotations
import logging
from pathlib import Path
import time
from typing import NamedTuple

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s",
datefmt='%Y-%m-%d %H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)

SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
``````

Let’s create a `Point` class. It’s very similar to what we’ve done before. The `neighbours()` method returns all 9 `Points` that are centered around this point, including this point itself.

``````class Point(NamedTuple):
""" Point class, which knows how to return a 3x3 grid of all Points centred on itself. """

DELTAS = [(dx,dy) for dy in range(-1, 2) for dx in range(-1, 2)]

x: int
y: int

def neighbours(self) -> list[Point]:
""" Return 3x3 grid of all points centered on itself """
return [Point(self.x+dx, self.y+dy) for dx,dy in Point.DELTAS]
``````

Here’s the game plan:

• Create an `ImageArray` class, passing in the 2D image, and the enhancement algorithm. Our `ImageArray __init__()` also takes a `canvas_char`, but we’ll come back to that later.
• Process the image with `_process_img_str()`, to convert the `str` image input to a set, storing only lit pixels.
• Determine the bounds of the `set`, i.e. the minimum and maximum x and y values stored in the `set`.
• We add a `render_as_str()` method, so that we see a text representation of the `ImageArray` object. This simply converts the stored `set` back to a `str` representation, by converting all lit pixels (i.e. those in the `set`) to `#`, and converting all other pixels (within the bounds) to `.`.
• Since our goal is to determine the number of lit pixels, we’ll add a `property` that returns this, by counting how many pixels are in the `set`.
``````class ImageArray():
""" Stores array of pixels (points) in a set.
Knows how many pixels are lit.  Is able to create a new ImageArray based on rules. """
LIGHT = "#" # 1
DARK = "."  # 0
BIN_MAP = { DARK: '0', LIGHT: '1'}

def __init__(self, image_data: str|set, img_enhancement_map: str, canvas_char='.') -> None:
""" Create a new ImageArray, containing a set of lit pixels.

Args:
image_data (str|set): Str representation or set.
img_enhancement_map (str): Map used for enhancing the image.
canvas_char (str, optional): Typically DARK, but can be lit depending on enhancement map.
"""
self._img_enhancement_map = img_enhancement_map

if isinstance(image_data, str):
self._pixels = self._process_img_str(image_data)    # convert to set
else:
assert isinstance(image_data, set)
self._pixels = image_data

# bounds of set, based on min and max coords in the set
self._min_x = min(pixel.x for pixel in self._pixels)
self._max_x = max(pixel.x for pixel in self._pixels)
self._min_y = min(pixel.y for pixel in self._pixels)
self._max_y = max(pixel.y for pixel in self._pixels)

# The background canvas char can be changed, depending on first and last chars of the enhancement map
self._canvas_char = canvas_char

def _process_img_str(self, image_data: str) -> set[Point]:
""" Take a str of image data and convert to a set. Only stores points that are lit. """
pixels = set()

for y, line in enumerate(image_data.splitlines()):
for x, char in enumerate(line):
if char == ImageArray.LIGHT:    # only store lit pixels

return pixels

def render_as_str(self) -> str:
""" Generate str representation """
lines = []
for y in range(self._min_y, self._max_y+1):
line = ""
for x in range(self._min_x, self._max_x+1):
char = ImageArray.LIGHT if Point(x,y) in self._pixels else ImageArray.DARK
line += char

lines.append(line)

return "\n".join(lines)

@property
def lit_count(self) -> int:
""" Return count of lit pixels """
return len(self._pixels)

def _outside_bounds(self, point: Point) -> bool:
""" Determine if the specified point is within the existing bounds of the image. """
return (point.x < self._min_x or point.x > self._max_x or
point.y < self._min_y or point.y > self._max_y)

def __repr__(self) -> str:
return self.render_as_str()
``````

We’ve been asked to enhance twice. The actual enhancement algorithm is implemented by the `ImageArray's enhance()` method. It works like this:

• We create a new `set` to store lit pixels after enhancement.
• We know that any pixels immediately outside of the current bounds will be at the centre of a 3x3 grid that has one edge within the bounds. For this reason, pixels immediately outside the current bounds may change. And for this reason, our image will grow with each application of the algorithm. That’s why our `enhance()` method looks looks at `ranges` in the x and y dimenions that are extended by 1 at each end.
• We call `_image_enhancement_index()` for each `Point`. This method:
• Gets all the pixels in the 3x3 grid that are centered on this `Point`.
• Returns a 1 or 0 for each of those 9 pixels, depending on whether lit or dark, and stores in a 9-digit binary `str`.
• Converts the 9-digit binary `str` to a decimal value, and returns it, using `int(bin_str, 2)`. For example, `int("000001010", 2)` returns `10`. This is our lookup index.
• You may be wondering what the `if self._canvas_char == ImageArray.LIGHT:` part is all about? We’ll come back to that!
• We use this lookup index to retrieve a character from the algorithm. This tells us whether the output pixel (for this given `Point`) is light or dark. If it’s light, we store in the new `set`.
• Finally, we return a new `ImageArray` object, using the new `set` of lit pixels as the new image.
• Of note: our `ImageArray __init__()` method can accept an input image in two formats:
1. A `str`, since this is what we’re provided with in the input data.
2. A `set`, since we’re only storing lit pixels, and this is much more efficient. Since we want to create new `ImageArray` instances from sets of lit pixels, it’s much more efficient to allow this directly, rather than converting to and from `str` objects each time.
``````    def enhance(self) -> ImageArray:
""" Process all squares simultaneously, i.e. based on current state of all pixels.
Returns: New ImageArray, which will 1px bigger in all directions. """
new_pixels = set()
# Process using rules, with a 1px border around existing bounds
for y in range(self._min_y-1, self._max_y+2):
for x in range(self._min_x-1, self._max_x+2):
pnt = Point(x,y)
enhancement_i = self._image_enhancement_index(pnt) # get enhancement index for this point
char = self._img_enhancement_map[enhancement_i] # determine type of pixel
if char == ImageArray.LIGHT:

# Update the char that should be used for the infinite canvas next time.
next_canvas_char = self._img_enhancement_map[ImageArray._surrounded_by_index(self._canvas_char)]
return ImageArray(new_pixels, self._img_enhancement_map, canvas_char=next_canvas_char)

@classmethod
def _surrounded_by_index(cls, char: str) -> int:
""" Get the mapping index for any char surrounded by . or #
I.e. where the 3x3 grid is all '.' (so int=0) or all '#' (so int=511). """
assert char in (ImageArray.DARK, ImageArray.LIGHT), "Can only be surrounded by . or #"
return ImageArray.convert_to_dec(9*ImageArray.BIN_MAP[char])

def _image_enhancement_index(self, point: Point) -> int:
""" Determine the decimal value of the 9-bit representation of this point.
The 9-bit representation of the point is based on the 3x3 grid of pixels with this point at the centre.
Pixel lit (#) = 1, else 0.
E.g. if only BR it lit, then the binary repr is 000000001.  If TL is lit, then 100000000.
If the infinite canvas should be lit,
then treat any pixels outside of the current boundary as a lit pixel. """

nine_box_bin = ""
for nine_box_point in point.neighbours():   # process pixel by pixel
if nine_box_point in self._pixels:  # If this is lit
nine_box_bin += ImageArray.BIN_MAP[ImageArray.LIGHT]
elif (self._outside_bounds(nine_box_point)): # in the infinite canvas area
if self._canvas_char == ImageArray.LIGHT:
nine_box_bin += ImageArray.BIN_MAP[ImageArray.LIGHT]
else:
nine_box_bin += ImageArray.BIN_MAP[ImageArray.DARK]
else:   # dark pixel, and within bounds
nine_box_bin += ImageArray.BIN_MAP[ImageArray.DARK]

return ImageArray.convert_to_dec(nine_box_bin)

@staticmethod
def convert_to_dec(input_str: str) -> int:
""" Convert bin str (e.g. '111110101') to int value """
assert len(input_str) == 9, "Valid input should be a nine-box str representation"
return int(input_str, 2)
``````

Let’s run it…

``````with open(INPUT_FILE, mode="rt") as f:

image_enhance_map, input_img = data
trench_image = ImageArray(input_img, image_enhance_map)

# Part 1 - Stop at 2 cycles
for i in range(2):
logger.debug("Image iteration %d", i)
trench_image = trench_image.enhance()

logger.info("Part 1: Lit=%d", trench_image.lit_count)
``````

But you may have spotted I’m doing some stuff in the code that wasn’t in my game plan. That’s because I tried my game plan with the sample data, and it worked!

“Well, that was easy,” I thought to myself.

But when I tried it with the actual data, it didn’t work (initially). Figures. It took me a while to work out why…

• The sample data has a `.` at index 0 of the algorithm, and a `#` at index 511 of the algorithm. (I.e. the index positions created by a 3x3 grid that are all `.` or all `#` respectively.)
• In our sample data, we’re told we have an infinite canvas of dark pixels. This means that in the infinite canvas area, the enhancement algorithm will always return a binary value of 0, which in turn will always return a dark pixel.

But the real data has a sneaky difference!

• The real data has a `#` at index 0 of the algorithm, and a `.` at index 511 of the algorithm. I.e. our first and last index chars are swapped! At least, my real data does, but I’m guessing everyone’s does!
• So, when we apply our algorithm for the first time, we start with an infinite canvas of dark pixels. Each of these pixels, when processed by our enhance method, will return a value of 0, which is now the index for a light pixel! So, every infinite canvas pixel becomes a lit pixel.
• So the result of our first round of image enhancement is that we now have an infinite canvas of lit pixels!!
• When we apply our algorithm to a an infite canvas of lit pixels, each of these pixels will return a value of 511. This is the index for a dark pixel. So, every infinite canvas pixel that was light becomes dark.
• In effect, each iteration of our `enhance()` algorithm toggles whether the infinite canvas is lit or dark!

So, we have to be mindful of whether our infinite canvas is made up of lit pixels, or dark pixels. And this is why my `ImageArray` class:

• Accepts a `canvas_char` in the `__init__()` method, but defaults to dark (“`.`”).
• Evaluates whether the infinite `canvas_char` should be lit or dark following this iteration of `enhance()`, by evaluating whether a 3x3 grid of the current infinite canvas pixel will return a “`#`” or a “`.`”. And of course, this is entirely dependent on the `algorithm` we’re given.
• Our `_image_enhancement_index()` method still determines the value returned by the 3x3 grid of pixels centered on this pixel. But if any of those pixels are outside of the current bounds (i.e. in the infinite canvas), then it must determine whether those infinite canvas pixels are lit or dark.

Phew, that fixed it!

## Part 2

Now we need to enhance 50 times.

Hurrah! No changes required. The code above is really efficient, so you can just run it for 50 cycles, no problem.

Here, I’m starting at 2, since we’ve already done 2 iterations, so there’s no need to repeat them.

``````# Part 2 - Stop at 50 cycles
for i in range(2, 50):
logger.debug("Image iteration %d", i)
trench_image = trench_image.enhance()

logger.info("Part 2: Lit=%d", trench_image.lit_count)
``````

## Visualisation

It would be cool to render an animation of our enhancing image! So, I’m going to use `PIL` again.

``````from PIL import Image, ImageDraw, ImageFont

...

RENDER = True
IMAGE_SIZE = 400
OUTPUT_FILE = Path(SCRIPT_DIR, "output/trench_anim.gif")
``````

Let’s add some code to render a pretty image, for a given `ImageArray` instance. We just add this method to the `ImageArray` class:

``````    def render_image(self) -> Image.Image:
""" Render as an image """
width = (self._max_x+1) - self._min_x
height = (self._max_y+1) - self._min_y

image = Image.new(mode='RGB', size=(width, height))
image_data = []

for y in range(width):
for x in range(height):
x_val = x + self._min_x
y_val = y + self._min_y
point = Point(x_val, y_val)

if point in self._pixels:
image_data.append((255, 255, 255)) # lit pixels
else:
image_data.append((128, 0, 0)) # dark pixels

image.putdata(image_data)
return image
``````

This is what it does:

• Creates a new `PIL Image` object.
• Creates a new `list`, to store RGB values as `tuples`.
• Creates a `Point` from each location in the `ImageArray`.
• If the `Point` is lit (i.e. in the `set`), set it to white. Else, set it to dark red. Ultimately, this creates a flattened list of RGB tuples.
• Finally, use the `putdata()` method to assign the RGB values to the `Image` object.

All well and good. But now we need to render this image for each iteration, and turn it into an animation. To do this, I’ve created an `Animator` class:

``````class Animator():
""" Creates an animation file of specified target size. """

FONT = ImageFont.truetype('arial.ttf', 24)
TEXT_COLOUR = (128, 128, 220, 255) # light blue

def __init__(self, file: Path, size: int,
duration: int, loop_animation=False, include_frame_count: bool=False) -> None:
""" Create an Animator. Suggest the file should be a .gif.
Target size is in pixels. Frame duration is in ms. Optionally superimpose frame count. """
self._outputfile = file
self._frames = []
self._target_size = size
self._frame_duration = duration

""" Add a frame by passing in a PIL Image. The frame is resized to the target size. """
image = image.resize((self._target_size, self._target_size), Image.NEAREST)
self._superimpose_frame_count(image)
self._frames.append(image)

def _superimpose_frame_count(self, image: Image.Image):
""" Add our cycle count text to the bottom right of the image """
image_draw = ImageDraw.Draw(image)
text = str(len(self._frames))
textwidth, textheight = image_draw.textsize(text, Animator.FONT)
im_width, im_height = image.size
margin = 10     # margin we want round the text to the edge
x_locn = im_width - textwidth - margin
y_locn = im_height - textheight - margin
image_draw.text((x_locn, y_locn), text, font=Animator.FONT, fill=Animator.TEXT_COLOUR)

def save(self):
""" Save to the target file. Creates parent folder if it doesn't exist. """
dir_path = Path(self._outputfile).parent
if not Path.exists(dir_path):
Path.mkdir(dir_path)

logger.info("Animation saved to %s", self._outputfile)
self._frames.save(self._outputfile, save_all=True,
duration=self._frame_duration, append_images=self._frames[1:])
``````

We initialise an `Animator` instance, passing in the file we want to save to, the image size (in pixels), the length of each frame (in milliseconds), and whether we want a frame count superimposed on the image. The `Animator`:

• Stores all the current frames in `_frames` instance variable.
• Exposes a method called `add_frame()`, which we will call from our `ImageArray` objects.
• If uses an `ImageDraw` object, to add our frame count text onto each frame.
• It exposes a `save()` method, which:
• Creates the parent folder if required.
• Generates an animated output file, with each frame of the specified duration. This works by calling `save()` on the first frame, which is itself a PIL `Image` object. We pass in all the remaining frames to the `append_images` attribute.

Now we need to make a couple of additional modifications to the `ImageArray` class:

``````def __init__(self, image_data: str|set, img_enhancement_map: str,
canvas_char='.', animator: Animator=None) -> None:

...

# Only render the image frame, if we have an Animator reference
self._animator = animator
if animator is not None:
``````

If we pass an `Animator` instance to the `ImageArray` constructor, then the `ImageArray` will store it, and call `animator.add_frame()`, passing in the output from its `render_image()` method.

Also, we need to make a change to our `enhance()` method:

``````def enhance(self) -> ImageArray:

...

return ImageArray(new_pixels, self._img_enhancement_map,
canvas_char=next_canvas_char, animator=self._animator)
``````

This ensures that we always pass the existing `Animator` object to the new `ImageArray` object we create, whenever we run `enhance()`. This way, each new `ImageArray()` will add a frame to the same `Animator`.

And finally, let’s update our calling code, so that it looks like this:

``````with open(INPUT_FILE, mode="rt") as f:

image_enhance_map, input_img = data

if RENDER:
animator = Animator(file=OUTPUT_FILE, size=IMAGE_SIZE,
duration=150, loop_animation=True, include_frame_count=True)
trench_image = ImageArray(input_img, image_enhance_map, animator=animator)
else:
trench_image = ImageArray(input_img, image_enhance_map)

# Part 1 - Stop at 2 cycles
for i in range(2):
logger.debug("Image iteration %d", i)
trench_image = trench_image.enhance()

logger.info("Part 1: Lit=%d", trench_image.lit_count)

# Part 2 - Stop at 50 cycles
for i in range(2, 50):
logger.debug("Image iteration %d", i)
trench_image = trench_image.enhance()

logger.info("Part 2: Lit=%d", trench_image.lit_count)

if animator:
animator.save()
``````

The output looks like this:

``````21:29:48.666:INFO:__main__:     Part 1: Lit=5464
21:29:48.666:INFO:__main__:     Part 2: Lit=19228  