zerosleeps

Since 2010

Advent of Code 2022 day 13 is done

I figured out my problem: I wasn’t correctly handing the scenario where a list had been exhausted with no result. I was incorrectly assuming that when either side of the list had been exhausted, a result must have been obtained.

Final code:

from functools import cmp_to_key
from utils import get_raw_input_as_str

def parse_raw_input(raw_input):
    return [[eval(packet) for packet in pair.splitlines()] for pair in raw_input.split("\n\n")]

def compare(left, right):
    if type(left) == type(right) == list:
        result = None
        i = 0
        while result is None:
            if len(left) != len(right) and len(left) <= i:
                return 1
            elif len(left) != len(right) and len(right) <= i:
                return -1
            elif len(left) == i and len(right) == i:
                return None
            else:
                result = compare(left[i], right[i])
                i += 1
        return result
    elif type(left) == type(right) == int:
        if left < right:
            return 1
        elif left > right:
            return -1
        else:
            return None
    elif type(left) == int and type(right) != int:
        return compare([left], right)
    elif type(right) == int and type(left) != int:
        return compare(left, [right])
    else:
        raise Exception

def part_one(input):
    return sum([i + 1 for i, pair in enumerate(input) if compare(pair[0], pair[1]) == 1])

def part_two(input):
    flattened_input = [packet for pair in input for packet in pair] + [[[2]]] + [[[6]]]
    sorted_packets = sorted(flattened_input, key=cmp_to_key(compare), reverse=True)
    return (sorted_packets.index([[2]]) + 1) * (sorted_packets.index([[6]]) + 1)

if __name__ == '__main__':
    print(f"Part one: {part_one(parse_raw_input(get_raw_input_as_str('day_13_input.txt')))}")
    print(f"Part one: {part_two(parse_raw_input(get_raw_input_as_str('day_13_input.txt')))}")

Advent of Code 2022 day 13

Not-quite-working solution for Advent of Code 2022 day 13. Works for both parts of the example input, doesn’t work for my actual input. I’ll come back to this.

from functools import cmp_to_key
from utils import get_raw_input_as_str

def parse_raw_input(raw_input):
    return [[eval(packet) for packet in pair.splitlines()] for pair in raw_input.split("\n\n")]

def compare(left, right):
    if type(left) == type(right) == int:
        if left < right:
            return 1
        elif left > right:
            return -1
        else:
            return None
    elif type(left) == type(right) == list:
        result = None
        i = 0
        while result is None:
            if len(left) <= i and len(right) >= i:
                return 1
            elif len(right) <= i and len(left) >= i:
                return -1
            else:
                result = compare(left[i], right[i])
                i += 1
        return result
    elif type(left) == int and type(right) != int:
        return compare([left], right)
    elif type(right) == int and type(left) != int:
        return compare(left, [right])
    else:
        return None

def part_one(input):
    return sum([i + 1 for i, pair in enumerate(input) if compare(pair[0], pair[1]) == 1])

def part_two(input):
    flattened_input = [packet for pair in input for packet in pair] + [[[2]]] + [[[6]]]
    sorted_packets = sorted(flattened_input, key=cmp_to_key(compare), reverse=True)
    return (sorted_packets.index([[2]]) + 1) * (sorted_packets.index([[6]]) + 1)

if __name__ == '__main__':
    print(part_one(parse_raw_input(get_raw_input_as_str("day_13_input.txt"))))
    print(part_two(parse_raw_input(get_raw_input_as_str("day_13_input.txt"))))

Advent of Code 2022 day 12

Well this is an embarrassing mess. I swear on my eyes, the tricky stuff is an adaption of the pseudocode on the Wikipedia page for A* search algorithm 🤦‍♂️

Just part one for now. I’m falling behind. Fingers crossed the next puzzle is more my jam.

import heapq
from string import ascii_lowercase
from utils import get_raw_input


class Heightmap:
    def __init__(self, raw_input):
        self.input_to_heightmap(raw_input)

    def input_to_heightmap(self, raw_input):
        self.heightmap = []
        for y, line in enumerate(raw_input):
            row = []
            for x, char in enumerate(line):
                if char == "S":
                    self.start = (x, y)
                    row.append(0)
                elif char == "E":
                    self.goal = (x, y)
                    row.append(25)
                else:
                    row.append(ascii_lowercase.index(char))
            self.heightmap.append(row)

    @property
    def node_keys(self):
        return [
            (x, y)
            for y in range(len(self.heightmap))
            for x in range(len(self.heightmap[y]))
        ]

    def node_value(self, node_key):
        if node_key in self.node_keys:
            return self.heightmap[node_key[1]][node_key[0]]
        return None

    def get_neighboring_nodes(self, node):
        candidates = [
            (node[0], node[1] - 1),
            (node[0] + 1, node[1]),
            (node[0], node[1] + 1),
            (node[0] - 1, node[1]),
        ]
        return [
            candidate
            for candidate in candidates
            if candidate in self.node_keys
            and self.node_value(candidate) - self.node_value(node) <= 1
        ]

    def manhattan_distance(self, current, neighbor):
        return abs(current[0] - neighbor[0]) + abs(current[1] - neighbor[1])

    def reconstruct_path(self, came_from, current):
        final_path = [current]
        while current in came_from.keys():
            current = came_from[current]
            final_path.insert(0, current)
        return final_path

    def a_star(self):
        open_set = [(0, self.start)]
        came_from = {}
        g_score = {self.start: 0}
        while open_set:
            current = heapq.heappop(open_set)[1]
            if current == self.goal:
                return self.reconstruct_path(came_from, current)
            for neighbor in self.get_neighboring_nodes(current):
                tentative_g_score = g_score[current] + 1
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    heapq.heappush(
                        open_set,
                        (
                            tentative_g_score
                            + self.manhattan_distance(current, neighbor),
                            neighbor,
                        ),
                    )


if __name__ == "__main__":
    heightmap = Heightmap(get_raw_input("day_12_input.txt"))
    print(f"{len(heightmap.a_star())=}")

Advent of Code 2022 day 11

Part one solution for Advent of Code 2022 day 11. The problem description made a bit of a fuss about the exact order things happen in, so I’ve over-engineered this a bit. Couldn’t make up my mind whether to create a class for items or not either.

But part two? Nah forget it. Those are the puzzles that turn me off. Some sort of mathematics is required, and I don’t have enough knowledge to even know what knowledge I don’t have. I don’t have the inclination to find out either - maths has never interested me.

import math
import re
import utils


class Monkey:
    def __init__(self, starting_items, operation, test, true, false):
        self.items = self.parse_starting_items(starting_items)
        self.operation = operation
        self.test = int(test)
        self.true = int(true)
        self.false = int(false)
        self.items_inspected = 0

    def parse_starting_items(self, starting_items):
        return [int(n) for n in starting_items.split(", ")]

    def inspect_items(self):
        self.items = [
            eval(f"{self.operation.replace('old','item')}") for item in self.items
        ]
        self.items = [int(item / 3) for item in self.items]
        self.items_inspected += len(self.items)

    def throw_items(self):
        items = [
            {
                "worry_level": item,
                "throw_to": self.true if bool(item % self.test == 0) else self.false,
            }
            for item in self.items
        ]
        self.items = []
        return items


if __name__ == "__main__":
    raw_input = utils.get_raw_input_as_str("day_11_input.txt")
    monkeys = {
        int(m["monkey"]): Monkey(
            *m.group("starting_items", "operation", "test", "true", "false")
        )
        for m in re.finditer(
            r"^.*(?P<monkey>\d+):\n.*: (?P<starting_items>.*)\n.*= (?P<operation>.*)\n.* (?P<test>\d+)\n.*(?P<true>\d+)\n.*(?P<false>\d+)",
            raw_input,
            re.MULTILINE,
        )
    }

    for _ in range(20):
        for k, monkey in monkeys.items():
            monkey.inspect_items()
            for item in monkey.throw_items():
                monkeys[item["throw_to"]].items.append(item["worry_level"])

    for k, monkey in monkeys.items():
        print(f"{k=} {monkey.items=} {monkey.items_inspected=}")

    print(
        math.prod(sorted([monkey.items_inspected for monkey in monkeys.values()])[-2:])
    )

Advent of Code 2022 day 10

My Python solution for Advent of Code 2022 day 10. Just the right amount of frustrating to keep it fun and interesting. I spent ages debugging part two because I kept confusing the “sprite” with the CRT’s current position - I was adding padding to the CRT’s position not the sprite’s position, so I kept getting answers that were always slightly off by weird amounts.

Anyway, here we go. (I’ve chopped out the “large example” input and the right-hand side of the part two equality test from this code block.)

import math
from unittest import TestCase
from utils import get_raw_input


class Process:
    def __init__(self, x_register=1):
        self.x_register = x_register
        self.current_instruction = None
        self.current_step = 0
        self.inputs = None

    def tick(self):
        if self.current_instruction:
            exec(f"self.{self.current_instruction}()")

    def new_instruction(self, instruction, inputs=None):
        if self.current_instruction != None:
            raise Exception("Already got an instruction")
        else:
            self.current_instruction = instruction
            self.current_step = 0
            self.inputs = inputs

    def noop(self):
        self.current_instruction = None

    def addx(self):
        if self.current_step < 1:
            self.current_step += 1
        else:
            self.x_register += int(self.inputs)
            self.current_instruction = None

    @property
    def ready(self):
        return not bool(self.current_instruction)


def run_program(process, instructions):
    cycles = [process.x_register]
    for i, instruction in enumerate(instructions):
        try:
            process.new_instruction(instruction.split()[0], instruction.split()[1])
        except IndexError:
            process.new_instruction(instruction)

        while not process.ready:
            process.tick()
            cycles.append(process.x_register)
    return cycles


def extract_signal_strength(cycles):
    return [(i + 1, value) for i, value in enumerate(cycles) if ((i % 40) - 19) == 0]


def calculate_signal_strength(signal_strengths):
    return sum([math.prod(strength) for strength in signal_strengths])


def build_screen(cycles):
    crt = []
    for y in range(6):
        row = []
        for x in range(40):
            sprite_centre = cycles[x + (y * 40)]
            if x in range(sprite_centre - 1, sprite_centre + 2):
                row.append("#")
            else:
                row.append(".")
        crt.append(row)
    return "\n".join(["".join(row) for row in crt])


def part_one(input):
    process = Process()
    cycles = run_program(process, input)
    return calculate_signal_strength(extract_signal_strength(cycles))


def part_two(input):
    process = Process()
    cycles = run_program(process, input)
    return build_screen(cycles)


class TestPartOne(TestCase):
    def setUp(self):
        self.small_example = [
            "noop",
            "addx 3",
            "addx -5",
        ]
        self.large_example = [
            REMOVED
        ]
        self.process = Process()

    def test_first_example_x_register(self):
        run_program(self.process, self.small_example)
        self.assertEqual(self.process.x_register, -1)

    def test_second_example_registers(self):
        cycles = run_program(self.process, self.large_example)
        self.assertEqual(cycles[19], 21)
        self.assertEqual(cycles[59], 19)
        self.assertEqual(cycles[99], 18)
        self.assertEqual(cycles[139], 21)
        self.assertEqual(cycles[179], 16)
        self.assertEqual(cycles[219], 18)

    def test_part_one_final_example(self):
        self.assertEqual(part_one(self.large_example), 13140)

    def test_part_two_example(self):
        self.assertEqual(
            part_two(self.large_example),
            REMOVED,
        )


if __name__ == "__main__":
    input = get_raw_input("day_10_input.txt")
    print(f"Part one: {part_one(input)}")
    print(f"Part two: \n{part_two(input)}")