zerosleeps

Since 2010

Advent of Code 2020 day 24

Thursday 24 December 2020

Advent of Code 2020 day 24. Two fun days in a row! Kinda wish I went a bit more object-orientated with this one - the result looks a bit messy and “scripty”.

I vaguely remembered a previous Advent of Code puzzle that used a hexagonal grid, and after a little poke around I used the cube coordinates system described by Red Blob Games.

Spent a while wondering why I wasn’t getting the correct answers for the part two examples, before I realised that I’d need to somehow cater for tiles beyond those I’d already looked at, as the puzzle clearly stated that they exist and default to white. pad_floor was therefore born.

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
from pathlib import Path
import re
import unittest

DIRECTIONS = {
    'e': [1, -1, 0],
    'se': [0, -1, 1],
    'sw': [-1, 0, 1],
    'w': [-1, 1, 0],
    'nw': [0, 1, -1],
    'ne': [1, 0, -1]
}

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

def parse_raw_input(raw_input):
    regexp = re.compile(r'e|se|sw|w|nw|ne')
    return [
        [direction for direction in re.findall(regexp, line.strip())]
        for line in raw_input.strip().splitlines()
    ]

def build_floor(parsed_input):

    tiles = {}
    # 0/None: white, 1: black

    for line in parsed_input:
        x, y, z = 0, 0, 0
        for direction in line:
            x += DIRECTIONS[direction][0]
            y += DIRECTIONS[direction][1]
            z += DIRECTIONS[direction][2]

        if tiles.get((x, y, z), 0) == 0:
            tiles[(x, y, z)] = 1
        else:
            tiles[(x, y, z)] = 0

    return tiles

def pad_floor(floor):
    new_tiles = {}
    for tile in floor:
        for adjacent_direction in DIRECTIONS.values():
            k = (
                tile[0] + adjacent_direction[0],
                tile[1] + adjacent_direction[1],
                tile[2] + adjacent_direction[2]
            )
            if k not in floor:
                new_tiles[k] = 0

    floor.update(new_tiles)
    return floor

def part_one(parsed_input):
    return len([tile for tile in build_floor(parsed_input).values() if tile == 1])

def adjacent_tile_colours(floor, tile):
    x, y, z = tile
    return [
        floor.get((x + 1, y - 1, z), 0),
        floor.get((x, y - 1, z + 1), 0),
        floor.get((x - 1, y, z + 1), 0),
        floor.get((x - 1, y + 1, z), 0),
        floor.get((x, y + 1, z - 1), 0),
        floor.get((x + 1, y, z - 1), 0)
    ]

def part_two(parsed_input):
    floor = build_floor(parsed_input)

    for day in range(100):
        floor = pad_floor(floor)
        changes = {}
        for position, colour in floor.items():
            adjacent_black_tiles = len([
                adjacent_colour
                for adjacent_colour
                in adjacent_tile_colours(floor, position)
                if adjacent_colour == 1
            ])
            if colour == 1 and (adjacent_black_tiles == 0 or adjacent_black_tiles > 2):
                changes[position] = 0
            elif colour == 0 and adjacent_black_tiles == 2:
                changes[position] = 1
        floor.update(changes)
    return len([tile for tile in floor.values() if tile == 1])

class TestExamples(unittest.TestCase):
    def setUp(self):
        self.example_input = """sesenwnenenewseeswwswswwnenewsewsw
                                neeenesenwnwwswnenewnwwsewnenwseswesw
                                seswneswswsenwwnwse
                                nwnwneseeswswnenewneswwnewseswneseene
                                swweswneswnenwsewnwneneseenw
                                eesenwseswswnenwswnwnwsewwnwsene
                                sewnenenenesenwsewnenwwwse
                                wenwwweseeeweswwwnwwe
                                wsweesenenewnwwnwsenewsenwwsesesenwne
                                neeswseenwwswnwswswnw
                                nenwswwsewswnenenewsenwsenwnesesenew
                                enewnwewneswsewnwswenweswnenwsenwsw
                                sweneswneswneneenwnewenewwneswswnese
                                swwesenesewenwneswnwwneseswwne
                                enesenwswwswneneswsenwnewswseenwsese
                                wnwnesenesenenwwnenwsewesewsesesew
                                nenewswnwewswnenesenwnesewesw
                                eneswnwswnwsenenwnwnwwseeswneewsenese
                                neswnwewnwnwseenwseesewsenwsweewe
                                wseweeenwnesenwwwswnew"""

    def test_part_one_example(self):
        self.assertEqual(part_one(parse_raw_input(self.example_input)), 10)

    def test_part_two_example(self):
        self.assertEqual(part_two(parse_raw_input(self.example_input)), 2208)

class TestPuzzleInput(unittest.TestCase):
    def test_part_one(self):
        self.assertEqual(part_one(parse_raw_input(get_raw_input())), 465)

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()))}")

Advent of Code 2020 day 23

Thursday 24 December 2020

Advent of Code 2020 day 23. Ooh I liked this one because it taught me something new: linked lists!

I took the “obvious” approach for part one, but almost nothing of that version is shown below as I first re-factored it, then stuck part_two_answer on top of 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
import unittest

class Game():
    def __init__(self, starting_circle, part=1):
        starting_circle = [int(char) for char in starting_circle]
        self.max_cup = max(starting_circle)
        self.min_cup = min(starting_circle)

        if part == 2:
            starting_circle += [ i for i in range(self.max_cup + 1, 1_000_000 + 1)]
            self.max_cup = 1_000_000

        self.circle = {
            cup: starting_circle[(i + 1) % len(starting_circle)]
            for i, cup in enumerate(starting_circle)
        }

        self.length = len(self.circle)
        self.current_cup = starting_circle[0]

    def move(self):
        crab = [
            self.circle[self.current_cup],
            self.circle[self.circle[self.current_cup]],
            self.circle[self.circle[self.circle[self.current_cup]]]
        ]

        destination = self.current_cup - 1

        if destination < self.min_cup:
            destination = self.max_cup

        while destination in crab:
            destination -= 1
            if destination < self.min_cup:
                destination = self.max_cup

        destination_original_link = self.circle[destination]
        chain_end_original_link = self.circle[crab[-1]]

        self.circle[destination] = crab[0]
        self.circle[crab[-1]] = destination_original_link
        self.circle[self.current_cup] = chain_end_original_link
        self.current_cup = chain_end_original_link

    def part_one_answer(self):
        cup = 1
        result = ""
        for i in range(self.length - 1):
            result += str(self.circle[cup])
            cup = self.circle[cup]
        return result

    def part_two_answer(self):
        return self.circle[1] * self.circle[self.circle[1]]

def part_one(input):
    game = Game(input)
    for _ in range(100):
        game.move()
    return game.part_one_answer()

def part_two(input):
    game = Game(input, 2)
    for _ in range(10_000_000):
        game.move()
    return game.part_two_answer()

class TestPartOne(unittest.TestCase):
    def test_part_one_example(self):
        self.assertEqual(part_one("389125467"), '67384529')

class TestPartTwo(unittest.TestCase):
    def test_part_two_example(self):
        self.assertEqual(part_two("389125467"), 149245887792)

if __name__ == '__main__':

    print(f"Part one: {part_one(INPUT)}")
    print(f"Part two: {part_two(INPUT)}")

Advent of Code 2020 day 21

Wednesday 23 December 2020

Advent of Code 2020 day 21. I’m out-of-sequence as I skipped day 21 to prioritise day 22 yesterday. As is often the case with Advent of Code, the actual coding was fine once I understood the trick the puzzle was trying to get at. In this instance, it took me ages to understand that an ingredient associated with an allergen must be in all the recipes that contain that allergen.

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
from pathlib import Path
import re
import unittest

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

class Food():
    def __init__(self, raw_line):
        self.raw_line = raw_line

    def parse_raw_line(self):
        regexp = re.compile(r'^(?P<ingredients>.*) \(contains (?P<contains>.*)\)$')
        return re.match(regexp, self.raw_line)

    @property
    def ingredients(self):
        return self.parse_raw_line()['ingredients'].split()

    @property
    def contains(self):
        return self.parse_raw_line()['contains'].split(', ')

def build_allergens(foods):
    allergens = {}
    for food in foods:
        for contains in food.contains:
            if contains in allergens:
                allergens[contains] &= set(food.ingredients)
            else:
                allergens[contains] = set(food.ingredients)

    while any([len(ingredients) > 1 for ingredients in allergens.values()]):
        # Find allergents with only one possible ingredient, and remove that
        # ingredient from all other allergens
        for allergen, ingredients in allergens.items():
            if len(ingredients) == 1:
                for update_allergen in allergens:
                    if update_allergen != allergen:
                        allergens[update_allergen] -= ingredients

    return allergens

def build_no_allergens(foods, allergens):
    return [
        ingredient
        for food in foods
        for ingredient in food.ingredients
        if ingredient not in [
            allergen_ingredient
            for allergen in allergens.values()
            for allergen_ingredient in allergen
        ]
    ]

def part_one(raw_input):
    foods = [Food(raw_line) for raw_line in raw_input.strip().splitlines()]
    allergens = build_allergens(foods)
    return len(build_no_allergens(foods,allergens))

def part_two(raw_input):
    foods = [Food(raw_line) for raw_line in raw_input.strip().splitlines()]
    allergens = build_allergens(foods)
    return ','.join([allergens[allergen].pop() for allergen in sorted(allergens)])

class TestPartOne(unittest.TestCase):
    def test_part_one_example(self):
        self.assertEqual(part_one("mxmxvkd kfcds sqjhc nhms (contains dairy, fish)\ntrh fvjkl sbzzf mxmxvkd (contains dairy)\nsqjhc fvjkl (contains soy)\nsqjhc mxmxvkd sbzzf (contains fish)"), 5)

class TestPartTwo(unittest.TestCase):
    def test_part_two_example(self):
        self.assertEqual(part_two("mxmxvkd kfcds sqjhc nhms (contains dairy, fish)\ntrh fvjkl sbzzf mxmxvkd (contains dairy)\nsqjhc fvjkl (contains soy)\nsqjhc mxmxvkd sbzzf (contains fish)"), 'mxmxvkd,sqjhc,fvjkl')

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

Advent of Code 2020 day 22

Tuesday 22 December 2020

Advent of Code 2020 day 22. I’ve skipped day 21 for the moment just so I could complete day 22 on day 22 (see my post about day 20 for more on that fiasco).

This one was great fun! Part one was very simple, which had me properly dreading part two but it wasn’t as bad as I feared. It took me a few attempts to understand the “if both players have at least as many cards remaining in their deck…” rule, but the example made it pretty clear.

There’s a bit of unnecessary repetition in this solution, and I can see how using OOP to model games/rounds/players would have helped me with this one, but this works so here I am.

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
from pathlib import Path

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

def parse_raw_input(raw_input):
    return {
        int(section.splitlines()[0].strip(':').split()[-1]):
        [ int(line) for line in section.splitlines()[1:] ]
        for section in raw_input.strip().split('\n\n')
    }

def play_round(players):
    if players[1][0] > players[2][0]:
        players[1].append(players[1].pop(0))
        players[1].append(players[2].pop(0))
        return players, 1
    else:
        players[2].append(players[2].pop(0))
        players[2].append(players[1].pop(0))
        return players, 2

def part_one(input):
    players = input

    while all([len(hand) for hand in players.values()]):
        players, winner = play_round(players)

    if len(players[1]) > 0:
        winner = 1
    else:
        winner =2

    return sum([ (i + 1) * card for i, card in enumerate(reversed(players[winner])) ])

def part_two(input, recursive=False):
    players = input
    previous_rounds = []

    while all([len(hand) for hand in players.values()]):
        if players in previous_rounds:
            return 1
        else:
            previous_rounds.append({player: list(cards) for player, cards in players.items()})

        cards_drawn = {player: cards[0] for player, cards in players.items()}

        if all([ len(players[player]) > cards_drawn[player] for player in players]):
            winner = part_two({player: [card for card in cards[1:(players[player][0]+1)]] for player, cards in players.items()}, True)
            if winner == 1:
                players[1].append(players[1].pop(0))
                players[1].append(players[2].pop(0))
            else:
                players[2].append(players[2].pop(0))
                players[2].append(players[1].pop(0))
        else:
            players, winner = play_round(players)

    if len(players[1]) > 0:
        winner = 1
    else:
        winner = 2

    if recursive:
        return winner
    else:
        return sum([ (i + 1) * card for i, card in enumerate(reversed(players[winner])) ])

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()))}')

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()))}')