zerosleeps

Since 2010

Advent of Code 2020 day 12

Saturday 12 December 2020

Advent of Code 2020 day 12. This one was really good fun - my favourite yet. Of course, as soon as I’d finished cleaning up I had a look at some of the solutions other folks had come up, and immediately felt a bit dumb. Seems I overcooked the rotation thing with all that trigonometry. Sod ‘em: I’m still very pleased with the structure and readability of my solution!

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
from math import radians, sin, cos
from pathlib import Path

class Point:
    FACINGS = ('north', 'east', 'south', 'west')

    # +-------> +x
    # |
    # |
    # |
    # +y

    def move(self, direction, distance):
        if direction == 'north':
            self.coordinates[1] -= distance
        elif direction == 'south':
            self.coordinates[1] += distance
        elif direction == 'east':
            self.coordinates[0] += distance
        elif direction == 'west':
            self.coordinates[0] -= distance

    def run_instruction(self, instruction):
        value = int(instruction[1:])

        if instruction[0] == 'N':
            self.move('north', value)
        elif instruction[0] == 'S':
            self.move('south', value)
        elif instruction[0] == 'E':
            self.move('east', value)
        elif instruction[0] == 'W':
            self.move('west', value)
        elif instruction[0] == 'L':
            self.rotate(-value)
        elif instruction[0] == 'R':
            self.rotate(value)
        elif instruction[0] == 'F':
            self.move(self.facing, value)

    def normalise_rotation(self, degrees):
        if degrees < 0:
            return degrees + 360
        else:
            return degrees

    def manhattan_distance(self):
        return sum([abs(c) for c in self.coordinates])

class Ship(Point):
    def __init__(self, version=1):
        self.coordinates = [0, 0]
        self.facing = 'east'

    def rotate(self, degrees):
        self.facing = self.FACINGS[(self.FACINGS.index(self.facing) +
                      int(self.normalise_rotation(degrees)/90))%4]

class Waypoint(Point):
    def __init__(self):
        self.coordinates = [10,-1]
        self.ship = Ship()

    def rotate(self, degrees):
        r = radians(self.normalise_rotation(degrees))

        self.coordinates = [
            round(cos(r) * (self.coordinates[0] - self.ship.coordinates[0]) -
                  sin(r) * (self.coordinates[1] - self.ship.coordinates[1]) +
                  self.ship.coordinates[0]),
            round(sin(r) * (self.coordinates[0] - self.ship.coordinates[0]) +
                  cos(r) * (self.coordinates[1] - self.ship.coordinates[1]) +
                  self.ship.coordinates[1])
        ]

    def distance_from_ship(self):
        return [
            self.coordinates[0] - self.ship.coordinates[0],
            self.coordinates[1] - self.ship.coordinates[1]
        ]

    def run_instruction(self, instruction):
        if instruction[0] == 'F':
            for _ in range(int(instruction[1:])):
                # Store waypoint's current distance from ship
                distance = self.distance_from_ship()
                # Move ship to waypoint
                self.ship.coordinates = self.coordinates
                # Move waypoint to new relative distance
                self.coordinates = [
                    self.ship.coordinates[0] + distance[0],
                    self.ship.coordinates[1] + distance[1]
                ]
        else:
            super().run_instruction(instruction)

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

def parse_raw_input(raw_input):
    return [line.strip() for line in raw_input.strip().splitlines()]

def part_one(input):
    ship = Ship()
    for instruction in input:
        ship.run_instruction(instruction)
    return ship.manhattan_distance()

def part_two(input):
    waypoint = Waypoint()
    for instruction in input:
        waypoint.run_instruction(instruction)
    return waypoint.ship.manhattan_distance()

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 11

Friday 11 December 2020

Advent of Code 2020 day 11. Again this is a slightly sanitised version of the code used to submit my answers, but there’s a still a lot of duplication.

The trickiest and messiest part of this was dealing with negative list indexes for seats right at the edge of the grid. I briefly considered adding a gutter to the grid but that would only have caused a different assortment of edge cases.

Used pytest for this one as well. Nicer output than unittest, but for dead-simple cases like this I don’t see much difference.

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

def directions():
    return [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]

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

def parse_raw_input(raw_input):
    return [[char for char in line.strip()] for line in raw_input.strip().splitlines()]

def get_adjacent(grid, seat, position):
    if (y := seat[0]+position[0]) < 0:
        return None
    if (x := seat[1]+position[1]) < 0:
        return None
    try:
        return grid[y][x]
    except IndexError:
        return None

def get_visible(grid, seat, direction):
    y = seat[0]+direction[0]
    x = seat[1]+direction[1]

    try:
        while y >= 0 and x >= 0 and grid[y][x] == '.':
            y += direction[0]
            x += direction[1]
        if y >= 0 and x >= 0:
            return grid[y][x]
        else:
            return None
    except IndexError:
        return None

def count_all_occupied_adjacent(grid, seat):
    return len(
        [
            result for result
            in (get_adjacent(grid, seat, position_to_check) for position_to_check in directions())
            if result == '#'
        ]
    )

def count_all_occupied_visible(grid, seat):
    return len(
        [
            result for result
            in (get_visible(grid, seat, direction_to_check) for direction_to_check in directions())
            if result == '#'
        ]
    )

def count_all_occupied(grid):
    return len([seat for row in grid for seat in row if seat == '#'])

def tick(grid, method, trigger):
    new_grid = [[seat for seat in row] for row in grid]
    last_count = 0
    iterations = 0

    while last_count != count_all_occupied(new_grid) or last_count == 0:
        last_count = count_all_occupied(grid)

        for y, row in enumerate(grid):
            for x, seat in enumerate(row):
                current_seat = grid[y][x]
                if method == 'visible':
                    count_of_occupied = count_all_occupied_visible(grid, [y, x])
                else:
                    count_of_occupied = count_all_occupied_adjacent(grid, [y, x])

                if current_seat == 'L' and count_of_occupied == 0:
                    new_grid[y][x] = '#'
                elif current_seat == '#' and count_of_occupied >= trigger:
                    new_grid[y][x] = 'L'

        grid = [[seat for seat in row] for row in new_grid]

    return last_count

class TestExamples():
    @pytest.fixture
    def example_input(self):
        return """L.LL.LL.LL
            LLLLLLL.LL
            L.L.L..L..
            LLLL.LL.LL
            L.LL.LL.LL
            L.LLLLL.LL
            ..L.L.....
            LLLLLLLLLL
            L.LLLLLL.L
            L.LLLLL.LL"""

    def test_part_one_example(self, example_input):
        assert tick(parse_raw_input(example_input), 'adjacent', 4) == 37

    def test_part_two_example(self, example_input):
        assert tick(parse_raw_input(example_input), 'visible', 5) == 26

if __name__ == '__main__':
    print(tick(parse_raw_input(get_raw_input()), 'adjacent', 4))
    print(tick(parse_raw_input(get_raw_input()), 'visible', 5))

Advent of Code 2020 day 10 part 2

Friday 11 December 2020

Advent of Code 2020 day 10 part two. Not in the mood for this one. My solution has been stolen from /u/ald_loop’s incredibly thorough and generous explanation.

No amount of stepping through this line-by-line in a debugger has lifted the brain-fog. Obviously the code is programming-101 stuff, it’s simply that I’m unable to link the logic to the problem and the solution.

I’ll revisit this in the future, but for now I’m just going to let it go.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def part_two(parsed_input):
    # Add charging outlet and device to list of adapters
    parsed_input += [0, max(parsed_input)+3]
    parsed_input = sorted(parsed_input)

    dp = [0]*len(parsed_input)
    # There's only one path to the charging outlet
    dp[0] = 1
    for i in range(1, len(parsed_input)):
        sm = 0
        for j in range(1,4): # 1, 2, 3
            if i-j < 0:
                # Skip out-of-range checks at the start of the process
                continue
            if parsed_input[i]-parsed_input[i-j] <= 3:
                # Candidate adapter
                sm += dp[i-j]
        dp[i] = sm
    return dp[-1]

Advent of Code 2020 day 10

Thursday 10 December 2020

Advent of Code 2020 day 10 part one. I haven’t got a clue what knowledge I’m missing for part two. I have code that works fine with the example inputs, but it will take days to run for my actual input.

Folk on the subreddit are talking about concepts I’ve never heard of. Heck, even looking at some of the solutions for part one have me scratching my head. Can’t wrapt my head around the maths.

I’ll try again tomorrow. Here’s my Python solution for part one though:

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

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

def parse_raw_input(raw_input):
    return [int(line.strip()) for line in raw_input.strip().splitlines()]

def candidate_adapters(adapters, current_rating):
    return [adapter for adapter in adapters if (adapter > current_rating and adapter - current_rating <= 3)]

def part_one(parsed_input):
    current_rating = 0 # Initialised to charging outlet
    differences = {1: 0, 2: 0, 3: 0}
    while len(parsed_input) > 0:
        candidates = candidate_adapters(parsed_input, current_rating)
        next_adapter = sorted(candidates)[0]

        difference = next_adapter - current_rating
        differences[difference] += 1

        current_rating = next_adapter

        parsed_input.remove(next_adapter)

    differences[3] += 1 # For device's built-in adapter

    return differences

def distribution(differences):
    return differences[1] * differences[3]

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

Advent of Code 2020 day 9

Thursday 10 December 2020

Advent of Code 2020 day 9. This one was good fun. Got myself into a right mess with variable names - overuse of the word “combination”!

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

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

def parse_raw_input(raw_input):
    return [int(line.strip()) for line in raw_input.strip().splitlines()]

def combination_options(full_list, end, preample_len):
    return full_list[end-preample_len:end]

def combinations_to_check(combination_options):
    return combinations(combination_options, 2)

def part_one(parsed_input, preample_len):
    i = preample_len
    while len([
        combination
        for combination
        in combinations_to_check(combination_options(parsed_input, i, preample_len))
        if sum(combination) == parsed_input[i]
    ]) != 0:
        i += 1

    return parsed_input[i]

def part_two(parsed_input, preample_len):
    invalid_number = part_one(parsed_input, preample_len)
    i = 0 # First number to check
    j = 2 # Consecutive numbers to check
    while (i + j) < len(parsed_input):
        while sum(parsed_input[i:i+j]) < invalid_number:
            j += 1 # Try a longer sequence

        if sum(parsed_input[i:i+j]) == invalid_number:
            return min(parsed_input[i:i+j]) + max(parsed_input[i:i+j])

        # Increment starting position and reset sequence length
        i += 1
        j = 2

class TestExamples(unittest.TestCase):
    def setUp(self):
        self.example_input = """35
            20
            15
            25
            47
            40
            62
            55
            65
            95
            102
            117
            150
            182
            127
            219
            299
            277
            309
            576"""

    def test_part_one(self):
        self.assertEqual(part_one(parse_raw_input(self.example_input), 5), 127)

    def test_part_one(self):
        self.assertEqual(part_two(parse_raw_input(self.example_input), 5), 62)

if __name__ == '__main__':
    print(f'Part one: {part_one(parse_raw_input(get_raw_input()), 25)}') # 776203571
    print(f'Part two: {part_two(parse_raw_input(get_raw_input()), 25)}') # 104800569