zerosleeps

Since 2010

Advent of Code 2020 day 20

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.

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}}(#).{{{wrap}}}(#).{{4}}(##).{{4}}(##).{{4}}(###).{{{wrap}}}(#).{{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()))}')

Advent of Code 2020 day 19

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.

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

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!

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

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.

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

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?

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