zerosleeps

Since 2010

Advent of Code 2020 day 19

Sunday 20 December 2020

Advent of Code 2020 day 19. Had a few false starts to this before I landed on the approach of iterating over all the rules, building the mother of all regular expressions for each one, until there were no more rule reference to replace.

Part two was a real head scratcher though. I just couldn’t figure out what the puzzle was trying to get at. Once I understood the question making changes to my part one solution was actually pretty straight forward.

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

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

def parse_raw_input(raw_input):
    rules, messages = [
        [ line.strip() for line in section.splitlines() ]
        for section in raw_input.strip().split('\n\n')
    ]

    rules = {
        int(rule.split(': ')[0]): rule.split(': ')[1].replace('"', '')
        for rule in rules
    }

    return rules, messages

def check_rules(rules, messages):
    # While any rule other than zero contains a number that isn't it's own number
    while any([
        re.search(fr'(?!\b{rule_id}\b)\b\d+\b', rule)
        for rule_id, rule
        in rules.items()
        if rule_id != 0
    ]):
        for rule_id, rule in rules.items():
            if not re.search(r'\d', rule) or re.search(fr'\b{rule_id}\b', rule):
                # Rule contains no digits, or it references itself
                # Wrap in brackets to preserve any logical 'or'
                if '|' in rule:
                    rule = f'({rule})'
                # Replace any references to this rule in all rules
                for replacement_rule_id, replacement_rule in rules.items():
                    rules[replacement_rule_id] = re.sub(fr'\b{rule_id}\b', rule, replacement_rule)

    rule_zero = re.compile(rules[0].replace(' ',''))
    return len([message for message in messages if re.fullmatch(rule_zero, message)])

def part_two(raw_input):
    rules, messages = parse_raw_input(raw_input)
    rules.update({
        8: '42 | 42 8',
        11: '42 31 | 42 11 31'
    })
    return check_rules(rules, messages)

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

Advent of Code 2020 day 18

Saturday 19 December 2020

Advent of Code 2020 day 18. I enjoyed this one, and I was happy with my solution to part 1 which was pretty clean and easy to read. Then part 2 came along and totally messed up my arithmetic function!

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

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

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

def arithmetic(expression, part=1):
    if type(expression) == re.Match:
        expression = expression[0]

    # For part two, when given an add expression and nothing else, simply
    # return the result of that add
    if part == 2 and re.match(r'^\d+\+\d+$', expression):
        return str(eval(expression))

    result = None
    operator = None

    # For part two, first deal with all the additions
    while part == 2 and re.search(r'\+', expression):
        expression = re.sub(r'\d+\+\d+', arithmetic, expression, 1)

    # Using re.findall to group concurrent digits into one "char"
    for char in re.findall(r'(\d+|[()+*])', expression):
        if char.isdecimal():
            if result is None:
                result = int(char)
            else:
                if operator == '+':
                    result += int(char)
                elif operator == '*':
                    result *= int(char)
                # Reset operator for next component of the expression
                operator = None
        elif char in ['+', '*']:
            operator = char

    return str(result)

def parse_expression(expression, part=1):
    regex = re.compile(r'\([\d\+\*]+\)')

    while re.search(regex, expression):
        expression = re.sub(regex, lambda e: arithmetic(e, part), expression, 1)

    return int(arithmetic(expression, part))

def part_one(raw_input):
    return sum([parse_expression(expression) for expression in parse_raw_input(raw_input)])

def part_two(raw_input):
    return sum([parse_expression(expression, part=2) for expression in parse_raw_input(raw_input)])

class TestPartOne(unittest.TestCase):
    def test_example_1(self):
        self.assertEqual(part_one("1 + 2 * 3 + 4 * 5 + 6"), 71)
    def test_example_2(self):
        self.assertEqual(part_one("1 + (2 * 3) + (4 * (5 + 6))"), 51)
    def test_example_3(self):
        self.assertEqual(part_one("2 * 3 + (4 * 5)"), 26)
    def test_example_4(self):
        self.assertEqual(part_one("5 + (8 * 3 + 9 + 3 * 4 * 3)"), 437)
    def test_example_5(self):
        self.assertEqual(part_one("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))"), 12240)
    def test_example_6(self):
        self.assertEqual(part_one("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"), 13632)

class TestPartTwo(unittest.TestCase):
    def test_example_1(self):
        self.assertEqual(part_two("1 + 2 * 3 + 4 * 5 + 6"), 231)
    def test_example_2(self):
        self.assertEqual(part_two("1 + (2 * 3) + (4 * (5 + 6))"), 51)
    def test_example_3(self):
        self.assertEqual(part_two("2 * 3 + (4 * 5)"), 46)
    def test_example_4(self):
        self.assertEqual(part_two("5 + (8 * 3 + 9 + 3 * 4 * 3)"), 1445)
    def test_example_5(self):
        self.assertEqual(part_two("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))"), 669060)
    def test_example_6(self):
        self.assertEqual(part_two("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2"), 23340)

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 17

Friday 18 December 2020

Advent of Code 2020 day 17.

I spent ages trying to create a 3-dimension array for part 1 but gave up and went for a dictionary approach instead with nasty looking keys. Should have used tuples for the keys. It turns out that using a dict helped for part two anyway.

My solutions to the challenges are getting less-and-less production-quality as the days go on…

Here’s my solution for part two: part one was the same just without the ‘w’ dimension.

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
import re

class Cube4D(object):
    def __init__(self, raw_input):
        self.cube = {
            f'x{xi}y{yi}z0w0': x
            for yi, y in enumerate(raw_input.strip().splitlines())
            for xi, x in enumerate(y.strip())
        }

    def all_neighbours(self, c):
        x0, y0, z0, w0 = [int(i) for i in re.match(r'^x(-*\d+)y(-*\d+)z(-*\d+)w(-*\d+)$', c).groups()]
        return [
            self.cube.get(f'x{x}y{y}z{z}w{w}', '.')
            for w in range(w0-1, w0+2)
            for z in range(z0-1, z0+2)
            for y in range(y0-1, y0+2)
            for x in range(x0-1, x0+2)
            if (z, y, x, w) != (z0, y0, x0, w0)
        ]

    def count_active_neighbours(self, c):
        return len([ n for n in self.all_neighbours(c) if n == '#' ])

    def count_all_active(self):
        return len([ c for c in self.cube.values() if c == '#' ])

    def get_new_state(self, c):
        if self.cube.get(c, '.') == '#':
            if self.count_active_neighbours(c) in [2, 3]:
                return '#'
            else:
                return '.'
        elif self.cube.get(c, '.') == '.' and self.count_active_neighbours(c) == 3:
            return '#'
        else:
            return '.'

    def edges(self):
        xs = [ int(re.search(r'x(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        ys = [ int(re.search(r'y(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        zs = [ int(re.search(r'z(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        ws = [ int(re.search(r'w(-*\d+)', c).group(1)) for c in self.cube.keys() ]
        return min(xs), max(xs), min(ys), max(ys), min(zs), max(zs), min(ws), max(ws)

    def cycle(self):
        new_cube = {}
        xmin, xmax, ymin, ymax, zmin, zmax, wmin, wmax = self.edges()

        for x in range(xmin-1, xmax+2):
            for y in range(ymin-1, ymax+2):
                for z in range(zmin-1, zmax+2):
                    for w in range(wmin-1, wmax+2):
                        new_cube[f'x{x}y{y}z{z}w{w}'] = self.get_new_state(f'x{x}y{y}z{z}w{w}')

        self.cube = new_cube

if __name__ == '__main__':
    c = Cube4D(INPUT)
    for _ in range(6):
        c.cycle()
    print(c.count_all_active())

Advent of Code 2020 day 16

Wednesday 16 December 2020

Advent of Code 2020 day 16. What an arse I made of this, but it was incredibly satisfying to complete! I submitted an answer for part two about 5 times before I managed to work out what the heck the question was asking me to multiply together. Just added to the fun of this one though.

Nested loops anyone?

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

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

def parse_rule_ranges(raw_range):
    return [[int(n) for n in r.split('-')] for r in raw_range.split(' or ')]

def parse_raw_input(raw_input):
    sections = raw_input.strip().split('\n\n')
    rules = {
        line.strip().split(': ')[0]: parse_rule_ranges(line.strip().split(': ')[1])
        for line
        in sections[0].splitlines()
    }
    my_ticket = [int(e) for e in sections[1].splitlines()[-1].strip().split(',')]
    nearby_tickets = [[int(e) for e in l.strip().split(',')] for l in sections[-1].splitlines()[1:]]
    return rules, my_ticket, nearby_tickets

def check_value_against_rules(rules, value):
    # Returns True if value passes any of the rules
    return any(
        [
            any(
                [value >= element[0] and value <= element[1] for element in rule]
            )
            for rule in rules.values()
        ]
    )

def part_one(raw_input):
    rules, my_ticket, nearby_tickets = parse_raw_input(raw_input)
    return sum(
        [
            value for ticket in nearby_tickets
            for value in ticket
            if not check_value_against_rules(rules, value)
        ]
    )

def part_two(raw_input):
    rules, my_ticket, nearby_tickets = parse_raw_input(raw_input)
    valid_tickets = [
        ticket for ticket in nearby_tickets
        if all([check_value_against_rules(rules, value) for value in ticket])
    ]

    field_position_candidates = {
        rule_name: list(range(len(my_ticket)))
        for rule_name in rules.keys()
    }

    for ticket in valid_tickets:
        for i, value in enumerate(ticket):
            for rule_name, rule_definition in rules.items():
                if all([value < element[0] or value > element[1] for element in rule_definition]):
                    # Value at position i is not a candidate for whatever rule we're looking at
                    # Remove i from posible positions for the rule
                    try:
                        field_position_candidates[rule_name].remove(i)
                    except ValueError:
                        # i presumably already removed by a previous rule
                        pass

    final_field_positions = {}
    while any([len(candidates) > 1 for candidates in field_position_candidates.values()]):
        for rule_name, candidate_positions in field_position_candidates.items():
            if len(candidate_positions) == 1:
                final_field_positions[rule_name] = candidate_positions[0]
                for remaining_candidate_positions in field_position_candidates.values():
                    if len(remaining_candidate_positions) > 1:
                        try:
                            remaining_candidate_positions.remove(candidate_positions[0])
                        except ValueError:
                            pass

    return prod([
        my_ticket[position]
        for field, position
        in final_field_positions.items()
        if field.startswith('departure')]
    )

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 15

Tuesday 15 December 2020

Advent of Code 2020 day 15. Part one was simple but too slow for part two, so part two uses dictionary lookups. Couldn’t see a way of doing this without storing the last two times each number had been seen.

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
def part_one(input, turns):
    memory = list(input)
    for turn in range(len(input), turns):
        if memory[-1] not in memory[0:-1]:
            memory.append(0)
        else:
            memory.append(
                (len(memory) + 1) - (len(memory) - list(reversed(memory[0:-1])).index(memory[-1]))
            )
    return memory[-1]

def part_two(input, turns):
    memory = {
        n: [t]
        for t, n
        in enumerate(INPUT)
    }

    last_number = input[-1]

    for turn in range(len(input), turns):
        if len(memory[last_number]) == 1:
            # Number not seen before
            this_number = 0
        else:
            this_number = memory[last_number][1] - memory[last_number][0]

        if this_number in memory:
            memory[this_number] = [memory[this_number][-1]] + [turn]
        else:
            memory[this_number] = [turn]

        last_number = this_number

    return last_number

if __name__ == '__main__':
    print(f'Part one: {part_one(INPUT, 2020)}')
    print(f'Part two: {part_two(INPUT, 30000000)}')