Part 1
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?
Proposed solution: represent dots as x, y tuples in a set and add + remove dot after translation to other side of the fold – e.g. for a fold on the y-axis, points with y greater than y fold will have a new position of (x, 2*(y-fold) - y) where (x, y) was the initial position
Time complexity: O(n) where n is the number of dots
Space complexity: O(1)
Assuming that the number of dots are distributed evenly on average across the two sides of the fold, we get O(n) time complexity since half of the dots will be removed from the set and their new coordinates will be added to the set. Addition/removal set operations are O(1) operations on average.
#!/usr/bin/env python3
import sys
if len(sys.argv) != 2:
print("Usage: {} <input file>".format(sys.argv[0]))
sys.exit(1)
file_input = open(sys.argv[1], "r").read().strip().split("\n")
i = 0
line = file_input[i]
dots = set()
while line != "":
x, y = [int(x) for x in line.split(",")]
dots.add((x,y))
i += 1
line = file_input[i]
plane, num = file_input[i+1].split()[-1].split("=")
num = int(num)
for x, y in set(dots):
if plane == "y":
if y > num:
dots.add((x,2*num-y))
dots.remove((x,y))
else:
if x > num:
dots.add((2*num-x,y))
dots.remove((x,y))
print("Number Dots: {}".format(len(dots)))
❯ python3 solution13.py input13
Number Dots: 802
Part 2
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?
Proposed solution: same solution but iterating through all folds this time – also some extra code to print the dots
Time complexity: O(f log(n)) where f is the number of folds
Space complexity: O(1)
#!/usr/bin/env python3
import sys
if len(sys.argv) != 2:
print("Usage: {} <input file>".format(sys.argv[0]))
sys.exit(1)
file_input = open(sys.argv[1], "r").read().strip().split("\n")
i = 0
line = file_input[i]
dots = set()
while line != "":
x, y = [int(x) for x in line.split(",")]
dots.add((x,y))
i += 1
line = file_input[i]
for i in range(i+1, len(file_input)):
if file_input[i] == "":
continue
plane, num = file_input[i].split()[-1].split("=")
num = int(num)
for x, y in set(dots):
if plane == "y":
if y > num:
dots.add((x,2*num-y))
dots.remove((x,y))
else:
if x > num:
dots.add((2*num-x,y))
dots.remove((x,y))
print("Number Dots: {}".format(len(dots)))
for y in range(10):
result = ""
for x in range(50):
if (x, y) in dots:
result += "#"
else:
result += "."
print(result)
Solution is now O(f log(n)). We can expect that some fraction of the dots are overlapping on every fold, reducing the total number of dots. Every fold will split the search space roughly in half making this fraction more likely to be larger after every fold.
❯ python3 solution13.py input13
Number Dots: 103
###..#..#.#..#.####.####..##..#..#.###............
#..#.#.#..#..#.#.......#.#..#.#..#.#..#...........
#..#.##...####.###....#..#....#..#.###............
###..#.#..#..#.#.....#...#.##.#..#.#..#...........
#.#..#.#..#..#.#....#....#..#.#..#.#..#...........
#..#.#..#.#..#.#....####..###..##..###............
..................................................
..................................................
..................................................
..................................................