Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Folding paper

Advent of Code 2021 - Day 13

Day 13: Transparent Origami

Useful Links

Concepts and Packages Demonstrated

matplotlib

__str__()visualisationhashabledataclassscatter

Problem Intro

Phew. Back to something a bit quicker to solve. Take a moment to appreciate this challenge. After this one, you wont see me using the word trivial again!!

We want to activate the sub’s thermal imaging system. But to activate it, we need a code from the instruction manual. (Anyone else nostalgic for 90s copy protection?) In the manual is a transparent sheet with random dots, and a set of instructions on how to fold the paper.

The imput looks like this:

6,10
0,14
9,10
0,3
10,4
4,11
...
fold along y=7
fold along x=5

Part 1

We’re asked how many dots are visible, after performing the first fold instruction. (Remember that some dots will overlap.)

Setup

Nothing new here. I’m using matplotlib because I want to do some visualisation later.

from dataclasses import dataclass
import logging
import os
import time
from matplotlib import pyplot as plt

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
# INPUT_FILE = "input/sample_input.txt"

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(level=logging.DEBUG)

The solution

First, some basic dataclasses:

@dataclass
class Instruction:
    """ Paper fold instruction """
    axis: str   # x or y
    val: int
    
@dataclass(frozen=True)
class Point:
    x: int
    y: int

Note that we’ve made the Point class frozen. This makes instances of this class immutable and hashable. We need these Point objects to be hashable, because we’re going to store them in a set later.

We’ll now read in the data:

def process_data(data: str) -> tuple[set[Point], list]:
    """ Input has n rows of x,y coords, then an empty line, then rows of instructions """
    
    coords, _, instruction_lines = data.partition('\n\n')
    dots = set()
    for coord in coords.splitlines():    # e.g. [6, 10]
        x,y = map(int, coord.split(","))
        dots.add(Point(x, y))
    
    instructions = []
    for line in instruction_lines.splitlines():
        instr = line.replace("fold along ", "").split("=")
        instructions.append(Instruction(instr[0], int(instr[1])))
        
    return dots, instructions

This splits the input data at the blank line, since all the lines before the blank line are points, and the lines after are fold instructions.

We convert the fold instructions into Instruction objects, just to make this easier to read and use later.

Now we’ll create a Paper class, that stores the current state of our folded transparent paper:

class Paper():
    """ Represents transparent paper with dots at specified x,y locations.
    The paper knows how to fold itself, given an instruction with an x or y value to fold along. """
    def __init__(self, dots: set[Point]) -> None:
        self._dots: set[Point] = dots
    
    @property
    def dot_count(self) -> int:
        """ Total number of dots showing on the paper """
        return len(self._dots)
    
    def __str__(self) -> str:
        """ Convert the dots to a printable string """
        height = max(point.y for point in self._dots)
        width = max(point.x for point in self._dots)
        
        rows = []
        for row in range(height+1):
            row_str = ""
            for col in range(width+1):
                coord = Point(col, row)
                row_str += "#" if coord in self._dots else " "

            rows.append(row_str)
        
        return "\n".join(rows)

    def fold(self, instruction: Instruction):
        """ Fold along a given axis.  Returns the union set of 
        numbers before the fold line, and the flip of the numbers after the fold line. """
        assert instruction.axis in ('x', 'y'), "Instruction must be 'x' or 'y'"
        
        before_fold = set()
        after_fold = set()
        
        if instruction.axis == 'x':    # fold vertical
            before_fold = set(dot for dot in self._dots if dot.x < instruction.val)
            after_fold = set(dot for dot in self._dots if dot.x > instruction.val)
            folded = set(Point(instruction.val-(num.x-instruction.val), num.y) for num in after_fold)
        else:   # fold horizontal
            before_fold = set(dot for dot in self._dots if dot.y < instruction.val)
            after_fold = set(dot for dot in self._dots if dot.y > instruction.val)
            folded = set(Point(num.x, instruction.val-(num.y-instruction.val)) for num in after_fold)
        
        self._dots = before_fold | folded   

Notes about this class:

We run it like this:

input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
    dots, instructions = process_data(f.read())

paper = Paper(dots)

# Part 1 - First instruction only
paper.fold(instructions[0])
logger.info("Part 1: %d dots are visible", paper.dot_count)

Part 2

Now we’re told to perform all the remaining fold instructions. We’re told we ultimately need an 8 character sequence. So it stands to reason that the final position of the dots will represent these 8 characters.

We’ve already done all the work. All we need to do is perform the remaining folds, and print the Paper:

# Part 2 - All remaining instructions
for instruction in instructions[1:]:
    paper.fold(instruction)
    
logger.info("Part 2: %d dots are visible", paper.dot_count)
logger.info("Part 2 decoded:\n%s", paper)

Barely an inconvenience!!

With my real data, the result is this:

2022-01-20 21:21:17.505:INFO:__main__:  Part 1: 720 dots are visible
2022-01-20 21:21:17.510:INFO:__main__:  Part 2: 104 dots are visible
2022-01-20 21:21:17.513:INFO:__main__:  Part 2 decoded:
 ##  #  # ###  ###  ###   ##  #  # ####
#  # #  # #  # #  # #  # #  # #  #    #
#  # #### #  # #  # #  # #  # #  #   #
#### #  # ###  ###  ###  #### #  #  #
#  # #  # #    # #  #    #  # #  # #
#  # #  # #    #  # #    #  #  ##  ####
2022-01-20 21:21:17.516:INFO:__main__:  Execution time: 0.0038 seconds

So the solution answer was AHPRPAUZ. Easy!

But wait… Those letters are a bit difficult to read. Let’s make it a bit prettier!!

Visualisation

I’m going to use Matplotlib again. It’s hardly any work to turn our set of points into a scatter graph, and plot them.

All we need to do is add this method to our Paper class:

    def render_as_plt(self):
        """ Render this paper and its dots as a scatter plot """
        all_x = [point.x for point in self._dots]
        all_y = [point.y for point in self._dots]
        
        axes = plt.gca()
        axes.set_aspect('equal')
        plt.axis("off") # hide the border around the plot axes
        axes.set_xlim(min(all_x)-1, max(all_x)+1)
        axes.set_ylim(min(all_y)-1, max(all_y)+1)
        axes.invert_yaxis()
        
        axes.scatter(all_x, all_y, marker="o", s=50)
        plt.show()

Here’s how it works:

And it looks like this:

Manual code