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

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

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

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

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