Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Image Enhancement

Advent of Code 2021 - Day 20

Day 20: Trench Map

Useful Links

‹›

Concepts and Packages Demonstrated

PIL

binaryanimation

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:

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:

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
                    pixels.add(Point(x, y))
        
        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:

    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:
                    new_pixels.add(pnt)
        
        # 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:
    data = f.read().split("\n\n")
    
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…

But the real data has a sneaky difference!

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:

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.

Some additional setup:

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:

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
        self._add_frame_count = include_frame_count
    
    def add_frame(self, image: Image.Image):
        """ 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)
        if self._add_frame_count:
            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[0].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:

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:
        animator.add_frame(self.render_image())

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:
    data = f.read().split("\n\n")
    
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
21:29:48.666:INFO:__main__:     Animation saved to c:\Users\djl\LocalDev\Python\Advent-of-Code\src\AoC_2021\d20_img_enhancement_pixel_map_bin_indexing\output\trench_anim.gif
21:29:49.595:INFO:__main__:     Execution time: 4.8548 seconds

The animation of the sample input looks like this:

Sample Trench Map Animation

And the animation of the real data looks like this:

Real Data Trench Map Animation

‹›