You reach another volcanically active part of the cave. It would be nice if you could do some kind of thermal imaging so you could tell ahead of time which caves are too hot to safely enter.
Fortunately, the submarine seems to be equipped with a thermal camera! When you activate it, you are greeted with:
Congratulations on your purchase! To activate this infrared thermal imaging camera system, please enter the code found on page 1 of the manual.
Apparently, the Elves have never used this feature. To your surprise, you manage to find the manual; as you go to open it, page 1 falls out. It's a large sheet of transparent paper! The transparent paper is marked with random dots and includes instructions on how to fold it up (your puzzle input). For example:
6,10
0,14
9,10
0,3
10,4
4,11
6,0
6,12
4,1
0,13
10,12
3,4
3,0
8,4
1,10
2,14
8,10
9,0
fold along y=7
fold along x=5
The first section is a list of dots on the transparent paper. 0,0 represents the top-left coordinate. The first value, x, increases to the right. The second value, y, increases downward. So, the coordinate 3,0 is to the right of 0,0, and the coordinate 0,7 is below 0,0. The coordinates in this example form the following pattern, where # is a dot on the paper and . is an empty, unmarked position:
...#..#..#.
....#......
...........
#..........
...#....#.#
...........
...........
...........
...........
...........
.#....#.##.
....#......
......#...#
#..........
#.#........
Then, there is a list of fold instructions. Each instruction indicates a line on the transparent paper and wants you to fold the paper up (for horizontal y=... lines) or left (for vertical x=... lines). In this example, the first fold instruction is fold along y=7, which designates the line formed by all of the positions where y is 7 (marked here with -):
...#..#..#.
....#......
...........
#..........
...#....#.#
...........
...........
-----------
...........
...........
.#....#.##.
....#......
......#...#
#..........
#.#........
Because this is a horizontal line, fold the bottom half up. Some of the dots might end up overlapping after the fold is complete, but dots will never appear exactly on a fold line. The result of doing this fold looks like this:
#.##..#..#.
#...#......
......#...#
#...#......
.#.#..#.###
...........
...........
Now, only 17 dots are visible.
Notice, for example, the two dots in the bottom left corner before the transparent paper is folded; after the fold is complete, those dots appear in the top left corner (at 0,0 and 0,1). Because the paper is transparent, the dot just below them in the result (at 0,3) remains visible, as it can be seen through the transparent paper.
Also notice that some dots can end up overlapping; in this case, the dots merge together and become a single dot.
The second fold instruction is fold along x=5, which indicates this line:
#.##.|#..#.
#...#|.....
.....|#...#
#...#|.....
.#.#.|#.###
.....|.....
.....|.....
Because this is a vertical line, fold left:
#####
#...#
#...#
#...#
#####
.....
.....
The instructions made a square!
The transparent paper is pretty big, so for now, focus on just completing the first fold. After the first fold in the example above, 17 dots are visible - dots that end up overlapping after the fold is completed count as a single dot.
How many dots are visible after completing just the first fold instruction on your transparent paper?
# Python imports
from collections import defaultdict
from copy import copy
from pathlib import Path
from typing import Callable, Dict, Generator, Iterable, List, Set, Tuple
import numpy as np
# Paths to data
testpath = Path("day13_test.txt")
datapath = Path("day13_data.txt")
We need to parse dot locations and fold instructions. As this looks like a natural fit for numpy, we also get the required size of an array that would represent the paper.
def load_input(fpath: Path) -> Tuple[List, List, Tuple]:
"""Return data as lists of (col, row) values, and fold instructions
:param fpath: Path to data file
"""
with fpath.open("r") as ifh:
dots = [] # dot locations
folds = [] # fold instructions
xmax, ymax = 0, 0
state = "dots" # switch later from parsing dots to folds
for line in [_.strip() for _ in ifh.readlines()]:
if len(line) == 0: # switch from parsing dots to folds on a blank line
state = "folds"
elif state == "dots": # parse a dot location
pos = tuple([int(_) for _ in line.split(",")])
xmax, ymax = max(pos[0], xmax), max(pos[1], ymax)
dots.append(pos)
elif state == "folds": # parse a fold instruction
drn, val = tuple(line.split()[-1].split("="))
folds.append((drn, int(val)))
return dots, folds, (xmax + 1, ymax + 1)
As a literal approach to the problem, we can use a Paper class that wraps a Boolean numpy array. Then we can use numpy operations on the array, for convenience.
class Paper():
def __init__(self, dots: List[Tuple[int, int]], size: Tuple[int, int]) -> None:
"""Initialise paper with dots
:param dots: list of dot locations
:param size: paper size (x, y coords)
"""
self._paper = np.zeros(size).astype(bool) # blank sheet of paper
self.__add_dots(dots)
def __add_dots(self, dots: List[Tuple[int, int]]) -> None:
"""Add dots to the paper
:param dots: list of dot locations
"""
# numpy indexes the other way round, so this is the
# transpose of the co-ordinates on paper
for xpos, ypos in dots:
self._paper[xpos, ypos] = True
def fold(self, fold: Tuple[str, int]) -> None:
"""Folds the paper in the named direction along the specified row/col:
:param fold: fold instruction - (direction, row/col) tuple
"""
drn, val = fold # the tuple describes direction (axis) and row/col
# numpy indexes the other way round, so this is the
# transpose of the co-ordinates on paper
if drn == "x": # horizontal fold (vertical in numpy)
newarray = np.flipud(self._paper[val+1:, :])
self._paper[val - newarray.shape[0]:val, :] += newarray
self._paper = self._paper[:val, :]
else: # vertical fold (horizontal in numpy)
newarray = np.fliplr(self._paper[:, val+1:])
self._paper[:, val - newarray.shape[1]:val] += newarray
self._paper = self._paper[:, :val]
def __str__(self):
"""Return paper with dots, as a string"""
outstr = []
for row in self._paper.T: # transpose for correct paper orientation
outstr.append(" ".join(["." if not _ else "#" for _ in row]))
return "\n".join(outstr) + "\n"
@property
def shape(self) -> Tuple[int, int]:
"""Returns size of paper as (rows, cols) of numpy array
NOTE: this is transposed from x,y in the sense of the puzzle
"""
return self._paper.shape
@property
def dotcount(self) -> int:
"""Returns count of dots on paper"""
return self._paper.sum()
Trying this out on the test data:
dots, folds, size = load_input(testpath)
paper = Paper(dots, size)
print(paper)
for fold in folds:
paper.fold(fold)
print(paper, paper.dotcount)
. . . # . . # . . # . . . . . # . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . # . . . . # . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . # . # # . . . . . # . . . . . . . . . . . . # . . . # # . . . . . . . . . . # . # . . . . . . . . # # # # # # . . . # # . . . # # . . . # # # # # # . . . . . . . . . . 16
Then applying to the puzzle data:
dots, folds, size = load_input(datapath)
paper = Paper(dots, size)
paper.fold(folds[0])
paper.dotcount
706
Finish folding the transparent paper according to the instructions. The manual says the code is always eight capital letters.
What code do you use to activate the infrared thermal imaging camera system?
Luckily, the __str__() method already answers this for us.
dots, folds, size = load_input(datapath)
paper = Paper(dots, size)
for fold in folds:
paper.fold(fold)
print(paper)
# . . . . # # # . . # # # # . . . # # . # # # . . . . # # . # # # # . # . . # . # . . . . # . . # . # . . . . . . . # . # . . # . . . . # . # . . . . # . . # . # . . . . # . . # . # # # . . . . . # . # # # . . . . . # . # # # . . # # # # . # . . . . # # # . . # . . . . . . . # . # . . # . . . . # . # . . . . # . . # . # . . . . # . # . . # . . . . # . . # . # . . # . # . . # . # . . . . # . . # . # # # # . # . . # . # . . . . . # # . . # # # . . . # # . . # # # # . # . . # .
%%timeit
dots, folds, size = load_input(datapath)
paper = Paper(dots, size)
for fold in folds:
paper.fold(fold)
3.91 ms ± 269 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
and the code is LRFJBJEH
The numpy array is fine, and intuitive enough, but we don't need an array if we recognise that this is essentially a mapping problem for individual points.
We can load the dots into a set, and then modify the x/y values of set members as necessary. This may be faster than the numpy solution.
def fold(dots: Set[Tuple[int, int]], fold: Tuple[str, int]) -> Set[Tuple[int, int]]:
"""Returns the set of dot positions, after folding
:param dots: set of dots on paper
:param fold: fold instructions (direction/axis and row/col)
"""
drn, val = fold
newdots = set() # dot positions after folding
if drn == "x": # fold in x direction
for dot in dots: # map dots to new locations
if dot[0] < val:
newdots.add(dot)
elif dot[0] > val:
newdots.add((val - (dot[0] - val), dot[1]))
else: # fold in y direction
for dot in dots: # map dots to new locations
if dot[1] < val:
newdots.add(dot)
elif dot[1] > val:
newdots.add((dot[0], val - (dot[1] - val)))
return newdots
Check on the test data:
dots, folds, size = load_input(testpath)
dots = set(dots)
for _ in folds:
dots = fold(dots, _)
print(len(dots))
16
Apply to the puzzle data:
dots, folds, size = load_input(datapath)
dots = set(dots)
dots = fold(dots, folds[0])
print(len(dots))
706
To get an answer to puzzle 2, we need to visualise the dot set.
def dotvis(dots: Set[Tuple[int, int]]) -> str:
"""Return a visualisation of dots on paper as a string
:param dots: set of dots on the page
"""
# Calculate page size
xmax, ymax = 0, 0
for dot in dots:
xmax, ymax = max(dot[0], xmax), max(dot[1], ymax)
# Set up the "blank page"
image = []
for col in range(ymax + 1):
image.append(["."] * (xmax + 1))
# Add the dots to the page
for dot in dots:
image[dot[1]][dot[0]] = "#"
return "\n".join(["".join(_) for _ in image])
Test with the test data
dots, folds, size = load_input(testpath)
dots = set(dots)
for _ in folds:
dots = fold(dots, _)
print(dotvis(dots))
##### #...# #...# #...# #####
And apply to the puzzle data
dots, folds, size = load_input(datapath)
dots = set(dots)
for _ in folds:
dots = fold(dots, _)
print(dotvis(dots))
#....###..####...##.###....##.####.#..# #....#..#.#.......#.#..#....#.#....#..# #....#..#.###.....#.###.....#.###..#### #....###..#.......#.#..#....#.#....#..# #....#.#..#....#..#.#..#.#..#.#....#..# ####.#..#.#.....##..###...##..####.#..#
%%timeit
dots, folds, size = load_input(datapath)
dots = set(dots)
for _ in folds:
dots = fold(dots, _)
2.73 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Turns out it's only about 25% faster than using numpy, and a class - which surprised me.
What if we take parsing out of it?
dots, folds, size = load_input(datapath)
%%timeit
paper = Paper(dots, size)
for fold in folds:
paper.fold(fold)
2.38 ms ± 208 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
dots, folds, size = load_input(datapath)
%%timeit
mydots = set(dots[:])
for fld in folds:
mydots = fold(mydots, fld)
1.22 ms ± 65.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
The alternative solution is about twice as fast (taking into account the need to copy the dots list, each time for %%timeit).