zerosleeps

Since 2010

Advent of Code 2020 day 20

Tuesday 22 December 2020

Advent of Code 2020 day 20. I hated everything about this, and as a result I hate my solution and I hate my code. It’s my own, and it works, but I hate it. This puzzle taught me nothing new, and it was tedious, and I hated it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
from math import prod
from pathlib import Path
import re

def get_raw_input():
    return (Path(__file__).parent / 'day_20_input.txt').read_text()

def parse_raw_input(raw_input):
    tiles = raw_input.strip().split('\n\n')
    return {
        int(re.search(r'\d+', tile).group()):
        [[char for char in line] for line in tile.splitlines()[1:]]
        for tile in tiles
    }

class Tile():
    def __init__(self, id, input):
        self.id = id
        self.pixels = input
        self.facing = 0
        self.rotation = 0

    def rotate(self):
        self.pixels = [list(x) for x in zip(*reversed(self.pixels))]
        self.rotation = ( self.rotation + 1 ) % 4

    def flip(self):
        self.facing = ( self.facing + 1 ) % 2
        self.pixels = [[pixel for pixel in reversed(row)] for row in self.pixels]

    def next_position(self):
        self.rotate()
        # If rotation is zero, we must have been through all
        # 4 rotations, so flip
        if self.rotation == 0:
            self.flip()

    def edge(self, edge):
        if edge == (1, 0):
            return self.pixels[0]
        elif edge == (-1, 0):
            return self.pixels[-1]
        elif edge == (0, 1):
            return [row[-1] for row in self.pixels]
        elif edge == (0, -1):
            return [row[0] for row in self.pixels]

    def remove_edges(self):
        del self.pixels[0]
        del self.pixels[-1]
        for row, content in enumerate(self.pixels):
            self.pixels[row] = content[1:-1]

class Image():
    def __init__(self):
        self.tiles = {}

    def open_edges_for_tile(self, tile_key):
        return [
            edge for edge in [(1,0),(-1,0),(0,1),(0,-1)]
            if (tile_key[0]+edge[0], tile_key[1]+edge[1]) not in self.tiles
        ]

    def tiles_with_open_edges(self):
        return set([
            tile for tile in self.tiles.keys()
            if len(self.open_edges_for_tile(tile)) > 0
        ])

    @property
    def min_y(self):
        return min([tile_position[0] for tile_position in self.tiles.keys()])

    @property
    def max_y(self):
        return max([tile_position[0] for tile_position in self.tiles.keys()])

    @property
    def min_x(self):
        return min([tile_position[1] for tile_position in self.tiles.keys()])

    @property
    def max_x(self):
        return max([tile_position[1] for tile_position in self.tiles.keys()])

def build_image(parsed_input):
    remaining_tiles = [Tile(id, input) for id, input in parsed_input.items()]

    image = Image()
    image.tiles[(0, 0)] = remaining_tiles.pop(0)

    while len(remaining_tiles) > 0:
        for open_tile in image.tiles_with_open_edges():
            for open_edge in image.open_edges_for_tile(open_tile):
                for tile in remaining_tiles:
                    for p in range(8):
                        if tile.edge((-open_edge[0],-open_edge[1])) == image.tiles[open_tile].edge(open_edge):
                            image.tiles[(open_tile[0]+open_edge[0],open_tile[1]+open_edge[1])] = tile
                            remaining_tiles.remove(tile)
                            break
                        else:
                            tile.next_position()

    return image

def part_one(parsed_input):
    image = build_image(parsed_input)
    return prod([
        image.tiles[(image.min_y, image.min_x)].id,
        image.tiles[(image.min_y, image.max_x)].id,
        image.tiles[(image.max_y, image.min_x)].id,
        image.tiles[(image.max_y, image.max_x)].id
    ])

def part_two(parsed_input):
    image = build_image(parsed_input)
    for tile in image.tiles.values():
        tile.remove_edges()

    final_image = []

    for tile_row in range(image.min_y, image.max_y+1):
        section = [ '' for i in range(len(image.tiles[(0,0)].pixels)) ]
        for tile_column in range(image.min_x, image.max_x+1):
            for row in range(len(image.tiles[(0,0)].pixels[0])):
                section[row] = section[row] + ''.join(list(reversed(image.tiles[(tile_row,tile_column)].pixels))[row])
        final_image.append(section)

    # Convert final image to a big tile so it can be flipped and rotated…
    final_tile = Tile(0, [ [ char for char in line ] for section in final_image for line in section])

    wrap = ( (len(final_tile.pixels[0]) - 20) + 1 )
    regexp = re.compile(f'(?=.18(#).}(#).4(##).4(##).4(###).}(#).2(#).2(#).2(#).2(#).2(#).3)')

    # …even though the monster search smooshes the whole tile into one string
    while len(list(re.finditer(regexp, ''.join([char for row in final_tile.pixels for char in row])))) == 0:
        final_tile.next_position()

    return ''.join([char for row in final_tile.pixels for char in row]).count('#') - (len(list(re.finditer(regexp, ''.join([char for row in final_tile.pixels for char in row])))) * 15)

if __name__ == '__main__':
    print(f'Part one: {part_one(parse_raw_input(get_raw_input()))}')
    print(f'Part two: {part_two(parse_raw_input(get_raw_input()))}')