2021 Advent of Code (Python)

import numpy as np
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
mapping = {'.': 0, '>': 1, 'v': 2}
board1 = np.array([[mapping[x] for x in line] for line in data])
 
count, moved = 0, True
while moved:
    before = board1.copy()
 
    board2 = np.zeros_like(board1)
    board2[(np.roll(board1, 1, axis=1) == 1) & (board1 == 0)] = 1
    board2[(board1 == 1) & (np.roll(board1, -1, axis=1) != 0)] = 1
    board2[board1 == 2] = 2
 
    board1 = np.zeros_like(board2)
    board1[(np.roll(board2, 1, axis=0) == 2) & (board2 == 0)] = 2
    board1[(board2 == 2) & (np.roll(board2, -1, axis=0) != 0)] = 2
    board1[board2 == 1] = 1
 
    count += 1
    moved = not np.array_equal(before, board1)
print(count)

from typing import Iterable
 
Cmd = list[str]
 
 
class ALU:
    """The ALU unit for the puzzle."""
 
    def __init__(self, cmds: list[Cmd]) -> None:
        """Initialise the ALU unit with the given command set."""
        self.cmds = cmds
        self.reg: dict[str, int] = {"w": 0, "x": 0, "y": 0, "z": 0}
 
    def resolve(self, val: str) -> int:
        """Resolve either an int literal or a register into an int value."""
        if val in self.reg:
            return self.reg[val]
        else:
            return int(val)
 
    def __call__(self, inp: Iterable[int] | None = None) -> dict[str, int]:
        """Run the ALU command set on the given input."""
        inputs = iter(inp or [])
        for op, *params in self.cmds:
            match op:
                case "inp":
                    try:
                        val = next(inputs)
                    except StopIteration:
                        raise ValueError("Not enough inputs") from None
                    self.reg[params[0]] = val
                case "add":
                    self.reg[params[0]] += self.resolve(params[1])
                case "mul":
                    self.reg[params[0]] *= self.resolve(params[1])
                case "div":
                    self.reg[params[0]] //= self.resolve(params[1])
                case "mod":
                    self.reg[params[0]] %= self.resolve(params[1])
                case "eql":
                    a = self.resolve(params[0])
                    b = self.resolve(params[1])
                    self.reg[params[0]] = int(a == b)
                case _:
                    raise ValueError(f"Unknown operator: {op}")
 
        state = self.reg.copy()
        self.reg = {"w": 0, "x": 0, "y": 0, "z": 0}
 
        return state
 
 
def correct_input(inp: list[int], cmds: list[Cmd]) -> list[int]:
    """Correct an input sequence so that it passes the test.
 
    The input consists of 14 processing blocks - each for one of the inputs.
    Each of them has the same structure and is parametrized by three
    variables, let's call them "div", "chk", and "add". Written in
    pseudocode and using "inp" for the input value each block performs
    the following computation:
 
        x = (z % 26 + chk) != inp
        z //= div
        z *= 25 * x + 1
        z += (inp + add) * x
 
    This can be re-written using an if-block, which eliminates the x-register:
 
        if z % 26 + chk != inp:
            z //= div
            z *= 26
            z += inp + add
        else:
            z //= div
 
    We note that "div" can only be one of two value: either 1 or 26. This
    leads us to observe that all computations are manipulations of digits
    of the z-register written in base 26. So it's natural to define
    "div = 26**shf", so that "shf" will be either 0 or 1. We can use
    binary operators to denote operations in base 26 as follows:
 
        z * 26  = z << 1
        z // 26 = z >> 1
        z % 26  = z & 1
 
    With this we can write the program as follows:
 
        if z & 1 + chk != inp:
            z = z >> shf
            z = z << 1
            z = z + (inp + add)
        else:
            z = z >> shf
 
    We can also write the bitwise operations as follows:
 
        z & 1 = z.last_bit
        z >> 1 = z.pop()
        (z << 1) & a = z.push(a)
        (z >> 1) << 1) & a = z.pop_push(a)
 
    where pop/push refer to that bit stack of z in base 26 with the last
    bit on top. Therefore, z.pop() removes the last bit, z.push(a) appends
    the bit "a", and z.pop_push(a) replaces the last bit by "a".
 
    Given that shf can only be 0 or 1 we get the following two cases:
 
        if shf == 0:
            if z.last_bit + chk != inp:
                z.push(inp + add)
        elif shf == 1:
            if z.last_bit + chk != inp:
                z.pop_push(inp + add)
            else:
                z.pop()
 
    According to the puzzle input (our input) in all cases where shf == 0
    it's true that chk > 9. Given that 1 <= inp <= 9 the check
    (if z.last_bit + chk != inp) will therefore always be true. This gives:
 
        if shf == 0:
            z.push(inp + add)
        elif shf == 1:
            if z.last_bit + chk == inp:
                z.pop()
            else:
                z.pop_push(inp + add)
 
    We can summarize in words. View z as a stack of bits in base 26. Start
    with an empty stack. Whenever shf == 0 (div == 1) push (inp + add) on
    the stack. If, however, shf == 1, consider the last bit on the stack.
    If it's equal to (inp - chk), then remove it, otherwise replace it by
    (inp + add).
 
    We also observe from the puzzle input (our input) that among the 14
    instruction blocks for each of the inputs there are exactly 7 cases
    with shf == 0 and 7 with shf == 1. Given that for shf == 0 something
    is always added to the stack, our goal is to arrange the input so
    that for shf == 1 it's always popped from the sack, so that at the end
    of the program we end up with an empty bit stack, which means that
    z == 0, which makes the input pass the test.
 
    To arrange this start with an arbitrary array of 14 inputs denoted
    by [inp_0, inp_1, ..., inp_13]. If the first two instruction blocks
    have shf_0 == 0 and shf_1 == 0 then after the first two inputs two
    bits will have been pushed to the stack:
 
        z_stack = [inp_0 + add_0, inp_1 + add_1]
 
    If then shf_2 == 1 we want to set inp_2 so that the last bit is popped.
    The last bit is popped if
 
            z.last_bit + chk_2 == inp_2
        =>  inp_1 + add_1 + chk_2 == inp_2
 
    So we set (inp_2 = inp_1 + add_1 + chk_2). It can now occur that the
    condition 1 <= inp_2 <= 9 is violated. In this case we can add an
    arbitrary value to inp_2 to restore this condition. We will need to
    add the same value to inp_1 too in order to maintain the previous
    equality. We need to be careful that after these adjustments we also
    maintain 1 <= inp_1 <= 9. The least we can do is for cases where
    inp_2 < 1 to choose the value so that inp_2 = 1 and for cases with
    inp_2 > 9 to choose the value so that inp_2 = 9. If this still doesn't
    work for inp_1, then no other value will work for both either.
 
    This strategy can be used to take any wish input sequence and correct
    it so that it passes the test. So for part 1 we'll want to start with
    the highest possible input, 99999999999999, and for part 2 with the
    lowest, 11111111111111.
 
    Programmatically, to correct the input we go through code subroutines
    that handle each of the inputs and extract the (shf, chk, add) parameters.
    If shf == 0 we remember the "add" parameter by pushing it on a stack, and
    we also remember which input it corresponds to. If shf == 1 we pop the
    last "add" from the stack and use it to compute the corrected input.
 
 
    Args:
        inp: The input array to correct.
        cmds: The input commands
 
    Returns:
        The corrected input array.
    """
    # copy input array
    inp = list(inp)
 
    # correct input
    sub_len = 18  # length of the subroutine for each of the inputs.
    line_nos = [4, 5, 15]  # line numbers with the (div, chk, add) parameters.
    stack = []
    for i in range(14):
        div_chk_add = [cmds[i * sub_len + x][-1] for x in line_nos]
        div, chk, add = map(int, div_chk_add)
        if div == 1:
            stack.append((i, add))
        elif div == 26:
            j, add = stack.pop()
            # Set the input so that the test passes
            inp[i] = inp[j] + add + chk
            # Correct the input so that 1 <= inp <= 9
            if inp[i] > 9:
                inp[j] = inp[j] - (inp[i] - 9)
                inp[i] = 9
            if inp[i] < 1:
                inp[j] = inp[j] + (1 - inp[i])
                inp[i] = 1
 
    return inp
 
 
def check(inp: list[int], cmds: list[Cmd]) -> bool:
    """Check if the input sequence passes the test."""
    alu = ALU(cmds)
    reg = alu(inp)
    if reg["z"] == 0:
        return True
    else:
        return False
 
 
def solve(wish_inp: list[int], cmds: list[Cmd]) -> str:
    """Solve the puzzle by correcting the given wish input sequence."""
    inp = correct_input(wish_inp, cmds)
    solution = "".join(map(str, inp))
    if not check(inp, cmds):
        raise RuntimeError(f"Part 1 solution doesn't pass the test: {solution}")
 
    return solution
 
 
def run(data_s: str) -> tuple[str, str]:
    """Solve the puzzles."""
    cmds = [line.split() for line in data_s.splitlines()]
    part1 = solve([9] * 14, cmds)
    part2 = solve([1] * 14, cmds)
 
    return part1, part2
 
 
data = open("input.txt", "r", encoding="utf-8").read()
print(run(data))

import heapq
from alive_progress import alive_bar
import logging
 
 
logger = logging.getLogger()
logger.setLevel(logging.INFO)
 
 
HALL_LEN = 11
NUM_ROOMS = 4
 
ROOM_POS = {'A': 2, 'B': 4, 'C': 6, 'D': 8}
ROOMS = {'A': 0, 'B': 1, 'C': 2, 'D': 3}
ROOM_AT = [(2, 'A'), (4, 'B'), (6, 'C'), (8, 'D')]
MOVE_COSTS = {'A': 1, 'B': 10, 'C': 100, 'D': 1000}
NO_STOP = (2, 4, 6, 8)
 
 
class State:
    @classmethod
    def from_string(cls, state_str, room_size=2):
        hall_str = state_str[:HALL_LEN]
        hall = [room if room != '.' else None for room in hall_str]
 
        room_str = state_str[HALL_LEN + 1:]
        rooms = []
        for i in range(NUM_ROOMS):
            pods_in_room = tuple(pod if pod != '.' else None for pod in room_str[i * room_size:(i + 1) * room_size])
            rooms.append(pods_in_room)
 
        return State(hall, rooms, room_size)
 
    def __init__(self, hall, rooms, room_size) -> None:
        self.hall = hall
        self.rooms = rooms
        assert room_size == 2 or room_size == 4
        self.room_size = room_size
 
    def __eq__(self, other):
        return str(self) == str(other)
 
    def __hash__(self):
        return hash(str(self))
 
    def __lt__(self, other):
        return False
 
    def __repr__(self) -> str:
        return str(self)
 
    def __str__(self) -> str:
        hall_str = ''.join(hall if hall else '.' for hall in self.hall)
        room_str = ''
        for room in self.rooms:
            room_str += ''.join(section if section else '.' for section in room)
        return hall_str + "|" + room_str
 
    def final(self) -> bool:
        if self.room_size == 2:
            return str(self) == '...........|AABBCCDD'
        elif self.room_size == 4:
            return str(self) == '...........|AAAABBBBCCCCDDDD'
        else:
            return False
 
    def moves_from_hall(self, hall_i):
        pod = self.hall[hall_i]
 
        # if there is no pod in the hall
        # there is no move
        if not pod:
            return[]
 
        pod_room = ROOM_POS[pod]
 
        # if there is a pod between us and the room
        # we can't move there
        for hall_idx in between(hall_i, pod_room):
            if self.hall[hall_idx]:
                return []
 
        # check if we can get to the room
        room_move = self.moves_into_wanted_room(pod)
        if not room_move:
            return []
 
        # we can move to the room
        cost, new_rooms = room_move
        cost += dist(hall_i, pod_room) * MOVE_COSTS[pod]
        hall = self.hall[:]
        hall[hall_i] = None
        return [(cost, State(hall, new_rooms, self.room_size))]
 
    def moves_from_room(self, room_i):
        possible_moves_from_room_to_hall = self.moves_from_room_to_hall(room_i)
        if not possible_moves_from_room_to_hall:
            return []
 
        cost, pod, room_pos, new_rooms = possible_moves_from_room_to_hall
 
        possible_stops = []
        for pos in between(room_pos, HALL_LEN):
            if self.hall[pos]:
                # There is a pod in the way.
                break
            possible_stops.append(pos)
        for pos in between(room_pos, -1):
            if self.hall[pos]:
                # There is a pod in the way.
                break
            possible_stops.append(pos)
        possible_stops = [stop for stop in possible_stops if stop not in NO_STOP]
 
        out = []
        for stop in possible_stops:
            new_hall = self.hall[:]
            new_hall[stop] = pod
            out.append((cost + MOVE_COSTS[pod] * dist(room_pos, stop), State(new_hall, new_rooms, self.room_size)))
        return out
 
    def moves_from_room_to_hall(self, room_i):
        room_pos, room_pod = ROOM_AT[room_i]
        room = self.rooms[room_i]
 
        # check that we have occupants
        if not room[-1]:
            return None
 
        # check if room only has correct occupants
        only_correct = True
        for space in room:
            if space and space != room_pod:
                only_correct = False
                break
        if only_correct:
            return None
 
        # get the top occupant that can move
        steps = 1
        while not room[steps - 1]:
            steps += 1
 
        rooms = [list(room[:]) for room in self.rooms]
        pod = rooms[room_i][steps - 1]
        rooms[room_i][steps - 1] = None
        return [MOVE_COSTS[pod] * steps, pod, room_pos, rooms]
 
    def moves_into_wanted_room(self, pod):
        """
        Assuming you stand right outside the room
        what valid moves are there?
        returns: None or (cost, new rooms array)
        """
        room_idx = ROOMS[pod]
        room = self.rooms[room_idx]
 
        # check if room is full
        if room[0]:
            return None
 
        # check if room contains other pods
        for space in room:
            if space and space != pod:
                return None
 
        # get steps to bottom-most empty space
        steps = 0
        for space in room:
            if space:
                break
            steps += 1
 
        # Create a new room array usable for State()
        rooms = [list(room[:]) for room in self.rooms]
        rooms[room_idx][steps - 1] = pod
        return (MOVE_COSTS[pod] * steps, [tuple(room) for room in rooms])
 
    def valid_moves(self):
        out = []
 
        for i in range(HALL_LEN):
            out += self.moves_from_hall(i)
 
        for i in range(NUM_ROOMS):
            out += self.moves_from_room(i)
 
        return sorted(out)
 
 
def between(i1, i2):
    if i1 < i2:
        return range(i1 + 1, i2)
    return range(i1 - 1, i2, -1)
 
 
def dist(i1, i2):
    return abs(i1 - i2)
 
 
def tests():
    # final state
    assert State.from_string('...........|AABBCCDD').final()
    assert not State.from_string('...........|ABBACCDD').final()
    assert not State.from_string('A..........|.BBACCDD').final()
    assert not State.from_string('A..........|.ABBCCDD').final()
    assert not State.from_string('AA.........|..BBCCDD').final()
 
    # positions between
    assert list(between(5, 9)) == [6, 7, 8]
    assert list(between(9, 5)) == [8, 7, 6]
 
    # distance
    assert dist(9, 5) == 4
 
    # moves from hall
    logging.debug(State.from_string('B..........|AA.BCCDD').moves_from_hall(0))
    logging.debug(State.from_string('AB.........|.A.BCCDD').moves_from_hall(1))
    logging.debug(State.from_string('BA.........|.A.BCCDD').moves_from_hall(1))
    logging.debug(State.from_string('.....D.....|AABBCC.D').moves_from_hall(5))
 
    # moves from room to hall
    logging.debug(State.from_string('...........|.A.BCCDD').moves_from_room_to_hall(1))
    logging.debug(State.from_string('...........|.B.ACCDD').moves_from_room_to_hall(1))
    logging.debug(State.from_string('...........|.BBACCDD').moves_from_room_to_hall(1))
 
    # moves from room
    logging.debug(State.from_string('.C.........|BBAACCDD').moves_from_room(1))
 
    # valid moves
    logging.debug(State.from_string('...........|BACDBCDA').valid_moves())
    logging.debug(State.from_string('...B.......|BACD.CDA').valid_moves())
    logging.debug(State.from_string('...B.C.....|BA.D.CDA').valid_moves())
 
    # verify hash
    state1 = State.from_string('...........|BBAACCDD')
    state2 = State.from_string('...........|BBAACCDD')
    state_set = {state1, state2}
    assert len(state_set) == 1
 
 
def solve(input_state, room_size=2):
    start = State.from_string(input_state, room_size)
    visited = set()
 
    todo = [(0, start, ())]
 
    # this is only for the progress bar
    last_cost = 0
    if room_size == 2:
        max_cost = 13495
    else:
        max_cost = 53767
 
    with alive_bar(max_cost) as bar:
        while todo:
            cost, state, path = heapq.heappop(todo)
 
            if state in visited:
                logging.debug("already visited", state)
                continue
 
            # this is only for the progress bar
            bar(cost - last_cost)
            last_cost = cost
            logging.debug("cost", cost, "state", state)
 
            visited.add(state)
 
            if state.final():
                logging.debug("final", cost)
                for step in path:
                    logging.debug(step)
                return cost
 
            for move_cost, move_to_state in state.valid_moves():
                heapq.heappush(todo, (cost + move_cost, move_to_state, tuple(list(path) + [state])))
 
 
# RUN TESTS
# tests()
 
# TEST DATA
# print("Part 1:", solve("...........|BACDBCDA", 2))
# print("Part 2:", solve("...........|BDDACCBDBBACDACA", 4))
 
# TEST DATA
# print("Part 1:", solve("...........|ACDCADBB", 2))
# print("Part 2:", solve("...........|ADDCDCBCABADBACB", 4))
 
# REAL DATA
 
#############
#...........#
###C#C#B#D###
  #D#A#B#A#
  #########
 
# print("Part 1:", solve("...........|CDCABBDA", 2))
 
#############
#...........#
###C#C#B#D###
 
  #D#C#B#A#
  #D#B#A#C#
 
  #D#A#B#A#
  #########
 
print("Part 2:", solve("...........|CDDDCCBABBABDACA", 4))

import re
from typing import List, Tuple, Union
 
 
def read_input() -> List[List[Union[str, int]]]:
    lines = open('input.txt').read().splitlines()
    steps = []
    for line in lines:
        parts = re.match(r'(\w+) x=(-?\d+)\.\.(-?\d+),y=(-?\d+)\.\.(-?\d+),z=(-?\d+)\.\.(-?\d+)$', line).groups()
        steps.append([parts[0]] + [int(i) for i in parts[1:]])
    return steps
 
 
def overlapping(zone1: List[int], zone2: List[int]) -> Union[Tuple[int, ...], None]:
    maxx, maxy, maxz = [max(zone1[i], zone2[i]) for i in (0, 2, 4)]
    minx, miny, minz = [min(zone1[i], zone2[i]) for i in (1, 3, 5)]
 
    if minx >= maxx and miny >= maxy and minz >= maxz:
        return maxx, minx, maxy, miny, maxz, minz
    else:
        return None
 
 
def count_lit(steps):
    lit = 0
    counted_zones = []
    for step in reversed(steps):
        mode, box = step[0], step[1:]
        minx, maxx, miny, maxy, minz, maxz = box
        if mode == 'on':
            dead_zones = []
            for overlap in [overlapping(zone, box) for zone in counted_zones]:
                if overlap:
                    dead_zones.append(('on', *overlap))
            lit += (maxx - minx + 1) * (maxy - miny + 1) * (maxz - minz + 1)
            lit -= count_lit(dead_zones)
        counted_zones.append(box)
    return lit
 
 
def filter_outliers(steps, max_val=50, min_val=-50):
    new_steps = []
    for step in steps:
        minx, maxx, miny, maxy, minz, maxz = step[1:]
        if minx <= max_val and miny <= max_val and minz <= max_val and maxx >= min_val and maxy >= min_val and maxz >= min_val:
            new_steps.append(step)
    return new_steps
 
 
steps = read_input()
steps = filter_outliers(steps)
print("Part 1:", count_lit(steps))
 
steps = read_input()
print("Part 2:", count_lit(steps))

from functools import cache
 
def advance(position, score, roll_sum):
    new_position = ((position - 1 + roll_sum) % 10) + 1
    return new_position, score + new_position
 
# Part 1
def play_practice_game(positions) -> int:
    player = 0
    scores = [0, 0]
    num_rolls = 0
    roll = 0
 
    while max(scores) <= 1000:
        rolls = [roll := (roll % 100) + 1 for _ in range(3)]
        positions[player], scores[player] = advance(positions[player], scores[player], sum(rolls))
        player = 1 - player
        num_rolls += 3
 
    if scores[0] >= 1000:
        return scores[1] * num_rolls
    else:
        return scores[0] * num_rolls
 
# Part 2
throw_frequencies = {3: 1, 4: 3, 5: 6, 6: 7, 7: 6, 8: 3, 9: 1}
 
@cache
def get_wins(pos1, pos2, score1, score2, player=1):
    if score1 >= 21:
        return [1, 0]
 
    if score2 >= 21:
        return [0, 1]
 
    wins = [0, 0]
    for dice_sum, frequency in throw_frequencies.items():
        if player == 1:
            pos, score = advance(pos1, score1, dice_sum)
            wins1, wins2 = get_wins(pos, pos2, score, score2, 2)
        else:
            pos, score = advance(pos2, score2, dice_sum)
            wins1, wins2 = get_wins(pos1, pos, score1, score, 1)
 
        wins[0] += wins1 * frequency
        wins[1] += wins2 * frequency
 
    return wins
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
pos1 = int(data[0].split(" ")[-1])
pos2 = int(data[1].split(" ")[-1])
 
print("Part 1:", play_practice_game([pos1, pos2]))
print("Part 2:", max(get_wins(pos1, pos2, 0, 0)))

class Die:
    def __init__(self, sides=100):
        self.sides = sides
        self.value = 0
        self.rolled = 0
 
    def roll(self):
        self.rolled += 1
        self.value = self.value % self.sides + 1
        return self.value
 
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
position_1 = int(data[0].split(" ")[-1])
position_2 = int(data[1].split(" ")[-1])
score_1, score_2 = 0, 0
 
die = Die()
while True:
    position_1 = (position_1 + die.roll() + die.roll() + die.roll() - 1) % 10 + 1
    score_1 += position_1
    if score_1 >= 1000:
        print(score_2 * die.rolled)
        exit()
    position_2 = (position_2 + die.roll() + die.roll() + die.roll() - 1) % 10 + 1
    score_2 += position_2
    if score_2 >= 1000:
        print(score_1 * die.rolled)
        exit()

import numpy as np
from scipy.signal import convolve2d
 
def enhance(times):
    data = open("input.txt", "r", encoding="utf-8").read().splitlines()
    algo = [int(x == "#") for x in data[0]]
    img = np.array([[int(x == "#") for x in y] for y in data[2:]])
 
    matrix = np.array([[1, 2, 4], [8, 16, 32], [64, 128, 256]])
    fillvallue = 0
    for _ in range(times):
        idx = convolve2d(img, matrix, fillvalue=fillvallue)
        img = np.vectorize(lambda x: algo[x])(idx)
        fillvallue = algo[0] if fillvallue == 0 else algo[511]
    print(img.sum())
 
# part 1
enhance(2)
 
# part 2
enhance(50)

from collections import Counter
from typing import Tuple, List
 
 
def get_scanners():
    raw_scanners = [scanner for scanner in open('input.txt').read().split('\n\n')]
 
    scanners = []
    for raw_scanner in raw_scanners:
        scanner = [[int(d) for d in line.strip().split(',')] for line in raw_scanner.splitlines()[1:]]
        scanners.append(scanner)
 
    return scanners
 
 
def check_if_scanners_overlap(scanners, base: int, to_check: int) -> Tuple[List[int], List[Tuple[int, int]]]:
    """
    Check if two scanners overlap (have 12+ beacons in common)
    1. We can check this one "direction" at a time as there are no beacons with duplicate x, y, or z coordinates
    2. We can assume that the base scanner (0) is aligned at X, Y, Z (whatever its alignment is, well just call it X, Y, Z)
    3. The other scanner will be aligned at a random combo of [X, -X, Y, -Y, Z, -Z] (24 options)
    Once we find a direction where we have 12 common, we've found our scanner and know its orientation and offset
    If they overlap, offsets, and orientations will not be empty
    """
    offsets, orientation = [], []
    base_scanner = scanners[base]
    scanner_to_check = scanners[to_check]
 
    # the base scanner is aligned at X, Y, Z => Column [0, 1, 2]
    # We want to find the offset and the orientation of the pair scanner in all 3 dirs
    for base_i in range(3):
 
        # the scanner to check, can have any combination of [X, -X, Y, -Y, Z, -Z]
        # we check one orientation/direction at a time (X = (1,0) -Y = (-1, 1) etc.)
        for sign, dir in [(1, 0), (-1, 0), (1, 1), (-1, 1), (1, 2), (-1, 2)]:
 
            # get all the diffs between the base and the possible orientations/directions of the check_scanner
            diffs = [beacon0[base_i] - sign * beacon1[dir]
                     for beacon1 in scanner_to_check
                     for beacon0 in base_scanner]
 
            # if we have 12+ matched in any direction, we have found our pair scanner
            # and we know the offset, and also the orientation/direction of this column
            offset, matching_beacons = Counter(diffs).most_common()[0]
 
            if matching_beacons >= 12:
                offsets.append(offset)
                orientation.append((sign, dir))
 
    return offsets, orientation
 
 
def find_overlapping(scanner: int, to_check: List[int]) -> Tuple[int, List[int], List[Tuple[int, int]]]:
    for other_scanner in to_check:
        offsets, orientation = check_if_scanners_overlap(scanners, scanner, other_scanner)
        if len(offsets) > 0:
            return other_scanner, offsets, orientation
    return -1, [], []
 
 
def align_scanner(scanner, offsets, orientation):
    to_align = scanners[scanner]
 
    # align orientation
    sign0, col0 = orientation[0]
    sign1, col1 = orientation[1]
    sign2, col2 = orientation[2]
    to_align = [[sign0 * beacon[col0], sign1 * beacon[col1], sign2 * beacon[col2]] for beacon in to_align]
 
    # align offset
    to_align = [[beacon[0] + offsets[0], beacon[1] + offsets[1], beacon[2] + offsets[2]] for beacon in to_align]
 
    scanners[scanner] = to_align
 
 
def align_scanners(scanners):
    aligned_scanners = [0]
    un_aligned_scanners = [i for i in range(1, len(scanners))]
 
    all_offsets = []
 
    while un_aligned_scanners:
        for i in aligned_scanners:
            overlapping_scanner, offsets, orientation = find_overlapping(i, un_aligned_scanners)
            if overlapping_scanner != -1:
                print("Found overlapping scanners:", i, overlapping_scanner, offsets, orientation)
                align_scanner(overlapping_scanner, offsets, orientation)
                un_aligned_scanners.remove(overlapping_scanner)
                aligned_scanners.append(overlapping_scanner)
                all_offsets.append(offsets)
 
    return all_offsets
 
 
def count_beacons(scanners):
    unique_beacons = set()
 
    for scanner in scanners:
        for beacon in scanner:
            unique_beacons.add((beacon[0], beacon[1], beacon[2]))
 
    return len(unique_beacons)
 
 
def get_biggest_manhattan_distance(offsets) -> int:
    biggest_distance = 0
 
    for i in range(len(offsets)):
        for j in range(i + 1, len(offsets)):
            manhattan = abs(offsets[i][0] - offsets[j][0]) + abs(offsets[i][1] - offsets[j][1]) + abs(offsets[i][2] - offsets[j][2])
            biggest_distance = max(biggest_distance, manhattan)
 
    return biggest_distance
 
 
scanners = get_scanners()
offsets = align_scanners(scanners)
 
print("Part 01:", count_beacons(scanners))
print("Part 02:", get_biggest_manhattan_distance(offsets))

import re
 
def parse_snailfish(n):
    v = re.split(r"(\[|\]|,)", n)
    v = [x for x in v if x not in ("", ",")]
    v = [int(x) if x.isdigit() else x for x in v]
    return v
 
def add(a, b):
    return ["["] + a + b + ["]"]
 
def explode(n):
    depth = 0
    for i, s in enumerate(n):
        if s == "[":
            depth += 1
        elif s == "]":
            depth -= 1
 
        if (
            depth > 4
            and s == "["
            and isinstance(n[i + 1], int)
            and isinstance(n[i + 2], int)
            and n[i + 3] == "]"
        ):
            for j in range(i, 0, -1):
                if isinstance(n[j], int):
                    n[j] += n[i + 1]
                    break
            for j in range(i + 4, len(n)):
                if isinstance(n[j], int):
                    n[j] += n[i + 2]
                    break
            n = n[:i] + [0] + n[i + 4 :]
            return n, True
    return n, False
 
def split(n):
    for i, s in enumerate(n):
        if isinstance(s, int) and s >= 10:
            n = n[:i] + ["[", s // 2, s - s // 2, "]"] + n[i + 1 :]
            return n, True
    return n, False
 
def reduce(n):
    to_reduce = True
    while to_reduce:
        n, to_reduce = explode(n)
        if not to_reduce:
            n, to_reduce = split(n)
    return n
 
def magnitude(n):
    while len(n) > 1:
        for i, s in enumerate(n):
            if (
                s == "["
                and isinstance(n[i + 1], int)
                and isinstance(n[i + 2], int)
                and n[i + 3] == "]"
            ):
                n = n[:i] + [3 * n[i + 1] + 2 * n[i + 2]] + n[i + 4 :]
                break
    return n[0]
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
 
# Part 1
m = parse_snailfish(data[0])
for d in data[1:]:
    n = parse_snailfish(d)
    m = add(m, n)
    m = reduce(m)
print('part 01: ', magnitude(m))
 
# Part 2
max_magnitude = 0
for d1 in data:
    for d2 in data:
        if d1 != d2:
            m = parse_snailfish(d1)
            n = parse_snailfish(d2)
            mag = magnitude(reduce(add(m, n)))
            max_magnitude = max(max_magnitude, mag)
print('part 02: ', max_magnitude)

# Example: 'target area: x=230..283, y=-107..-57\n'
import re
data = open("input.txt", "r", encoding="utf-8").read()
data = re.findall('-?\d+',data)
data = [int(x) for x in data]
x1, x2, y1, y2 = data[0], data[1], data[2], data[3]
 
best_y, count = 0, 0
for init_vx in range(1, x2 + 1):  # cannot go higher than x2, or it will go throught the target area
    for init_vy in range(y1, 500):
        vx, vy = init_vx, init_vy
        x, y, max_y = 0, 0, y1
        while x <= x2 and y >= y1:
            max_y = max(max_y, y)
            if x1 <= x <= x2 and y1 <= y <= y2:
                count += 1
                best_y = max(best_y, max_y)
                break
            x += vx
            y += vy
            vx = max(0, vx - 1)
            vy -= 1
 
print(f"part 01: {best_y}")
print(f"part 02: {count}")

from functools import reduce
 
funcDict = {
    0: sum,
    1: lambda a: reduce(lambda x, y: x * y, a),
    2: min,
    3: max,
    5: lambda a: int(a[0] > a[1]),
    6: lambda a: int(a[0] < a[1]),
    7: lambda a: int(a[0] == a[1])
}
 
def evaluate(u):
    if packets[u][1] == 4:
        return packets[u][2]
 
    res = []
    for v in graph[u]:
        res.append(evaluate(v))
    return funcDict[packets[u][1]](res)
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
 
s = bin(int(data[0], 16))[2:]
for i in data[0]:
    if i != '0':
        break
    s = '0' * 4 + s
n = len(s)
if n % 4 != 0:
    s = '0' * (4 - n % 4) + s
n = len(s)
c = 0
packets = []
 
while c < n and '1' in s[c:]:
    v = int(s[c: c + 3], 2)
    c += 3
    t = int(s[c: c + 3], 2)
    c += 3
 
    if t == 4:
        num = ''
        while s[c] == '1':
            num += s[c + 1: c + 5]
            c += 5
        num += s[c + 1: c + 5]
        c += 5
        num = int(num, 2)
 
        packets.append([v, t, num, c])
    else:
        l = int(s[c], 2)
        c += 1
        if l == 0:
            num = int(s[c: c + 15], 2)
            c += 15
        else:
            num = int(s[c: c + 11], 2)
            c += 11
 
        packets.append([v, t, l, num, c])
 
stack = []
graph = [[] for _ in range(len(packets))]
 
for i, u in enumerate(packets):
    if len(stack) > 0:
        p = stack[-1]
        graph[p].append(i)
        packets[p][3] -= 1
        if packets[p][3] == 0:
            stack.pop()
 
    while len(stack) > 0:
        p = stack[-1]
        if packets[p][2] == 0 and packets[p][3] <= u[-1] - packets[p][-1]:
            stack.pop()
        else:
            break
 
    if u[1] != 4:
        stack.append(i)
 
print(evaluate(0))

data = open("input.txt", "r", encoding="utf-8").read().splitlines()
 
s = bin(int(data[0], 16))[2:]
n = len(s)
if n % 4 != 0:
    s = '0' * (4 - n % 4) + s
n = len(s)
res = 0
c = 0
 
while c < n and '1' in s[c:]:
    v = int(s[c: c + 3], 2)
    res += v
    c += 3
    t = int(s[c: c + 3], 2)
    c += 3
 
    if t == 4:
        num = ''
        while s[c] == '1':
            num += s[c + 1: c + 5]
            c += 5
        num += s[c + 1: c + 5]
        c += 5
        num = int(num, 2)
    else:
        l = int(s[c], 2)
        c += 1
        if l == 0:
            num = int(s[c: c + 15], 2)
            c += 15
        else:
            num = int(s[c: c + 11], 2)
            c += 11
 
print(res)

import networkx as nx
import numpy as np
 
data = open("input.txt", "r", encoding="utf-8").read()
df = np.array([[int(x) for x in line] for line in data.splitlines()])
row = np.hstack([(df + i - 1) % 9 + 1 for i in range(5)])
df = np.vstack([(row + i - 1) % 9 + 1 for i in range(5)])
w, h = df.shape
G = nx.grid_2d_graph(w, h, create_using=nx.DiGraph())
nx.set_edge_attributes(G, {e: df[e[1][0], e[1][1]] for e in G.edges()}, "cost")
print(nx.shortest_path_length(G, source=(0, 0), target=(w - 1, h - 1), weight="cost"))

import sys
from collections import defaultdict
from queue import PriorityQueue
import math
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
 
def initialise(data):
    #set up the initial grid, before the enlargement
    grid = {}
 
    for j, row in enumerate(data):
        for i, item in enumerate(row):
            grid[(i,j)] = int(item)
 
    visit = PriorityQueue()
    visit.put((0,(0,0)))
 
    distance = defaultdict(lambda: math.inf)
    distance[(0,0)] = 0
 
    target = (5*len(data[0])-1, 5*len(data)-1)
 
    return grid,visit,distance, target
 
def neighbour_coords(point,grid):
#returns a list of coords of points adjacent to (i,j) in the grid
    coords_list = []
    steps = [(1,0),(-1,0),(0,1),(0,-1)]
 
    for step in steps:
        (i,j) = point
        (dx,dy) = step
        if 0 <= i+dx <= (5*len(data[0])-1) and 0 <= j+dy <= (5*len(data)-1):
            coords_list.append((i+dx,j+dy))
 
    return coords_list
 
def get_node_value(point,grid):
    #use modular arithmetic to get the value of a node at any point in the enlarged grid
    #by referencing the initial grid (pre-enlargement)
    (x,y) = point
    x_len = len(data[0])
    y_len = len(data)
 
    value = grid[(x%x_len,y%y_len)] + x//x_len + y//y_len
 
    return (value-1)%9 + 1
 
def dijkstra(grid,visit,distance,target):
 
    while not visit.empty():
        (d,(x,y)) = visit.get()
 
        for nb in neighbour_coords((x,y), grid):
            if d + get_node_value(nb,grid) < distance[nb]:
                distance[nb] = d + get_node_value(nb,grid)
                visit.put((distance[nb], nb))
 
    return distance[target]
 
 
grid,visit,distance, target = initialise(data)
 
print(dijkstra(grid,visit,distance,target))

import networkx as nx
 
data = open("input.txt", "r", encoding="utf-8").read()
df = [[int(x) for x in line] for line in data.splitlines()]
w, h = len(df), len(df[0])
G = nx.grid_2d_graph(w, h, create_using=nx.DiGraph())
nx.set_edge_attributes(G, {e: df[e[1][0]][e[1][1]] for e in G.edges()}, "cost")
print(nx.shortest_path_length(G, source=(0, 0), target=(w - 1, h - 1), weight="cost"))

import sys
from collections import defaultdict
from queue import PriorityQueue
import math
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
 
def initialise(data):
    #set up the grid
    grid = {}
 
    for j, row in enumerate(data):
        for i, item in enumerate(row):
            grid[(i,j)] = int(item)
 
    visit = PriorityQueue()
    visit.put((0,(0,0)))
 
    distance = defaultdict(lambda: math.inf)
    distance[(0,0)] = 0
 
    target = (len(data[0])-1, len(data)-1)
 
    return grid,visit,distance,target
 
def neighbour_coords(point,grid):
#returns a list of coords of points adjacent to (i,j) in the grid
    coords_list = []
    steps = [(1,0),(-1,0),(0,1),(0,-1)]
 
    for step in steps:
        (i,j) = point
        (dx,dy) = step
        if 0 <= i+dx <= (len(data[0])-1) and 0 <= j+dy <= (len(data)-1):
            coords_list.append((i+dx,j+dy))
 
    return coords_list
 
def dijkstra(grid,visit,distance,target):
 
    while not visit.empty():
        (d,(x,y)) = visit.get()
 
        for nb in neighbour_coords((x,y), grid):
            if d + grid[(nb)] < distance[nb]:
                distance[nb] = d + grid[(nb)]
                visit.put((distance[nb], nb))
 
    return distance[target]
 
 
grid,visit,distance,target = initialise(data)
 
print(dijkstra(grid,visit,distance,target))

from collections import Counter
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
template = data[0]
rules = {a: b for a, b in [x.split(" -> ") for x in data[2:]]}
 
# Count each pair of letters in the template
pairs = Counter([template[i : i + 2] for i in range(len(template) - 1)]) # slicing
 
# Update pairs count at each step as per rules
for _ in range(40):
    new_pairs = Counter()
    for p, v in pairs.items():
        if p in rules:
            c = rules[p]
            new_pairs[p[0] + c] += v
            new_pairs[c + p[1]] += v
        else:
            new_pairs[p] += pairs[p]
    pairs = new_pairs
 
# Count letters by counting first letter of each pair,
# plus the final letter which is invariant during the whole process.
count = Counter()
for p, v in pairs.items():
    count[p[0]] += v
count[template[-1]] += 1
 
print(count.most_common()[0][1] - count.most_common()[-1][1])

from collections import Counter
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
template = data[0]
# for line 2 to last, split by delimiter, to list, to dict
rules = {a: b for a, b in [x.split(" -> ") for x in data[2:]]}
 
for _ in range(10):
    new = ""
    for i in range(len(template) - 1):
        pair = template[i : i + 2] # slicing
        new += pair[0]
        if pair in rules:
            new += rules[pair]
    new += template[-1]
    template = new
 
count = Counter(template).most_common()
print(count[0][1] - count[-1][1])

import re
import numpy as np
from imageio import imwrite
 
data = open("input.txt", "r", encoding="utf-8").read()
coords_section, folds_section = data.split("\n\n")
coords = {tuple(map(int, c.split(","))) for c in coords_section.splitlines()}
folds = [re.match(r"fold along (x|y)=(\d+)", f).groups() for f in folds_section.splitlines()]
folds = [(a, int(v)) for a, v in folds]
 
for axis, v in folds:
    if axis == 'y':
        coords = {(x, y) for x, y in coords if y < v} | {(x, v - (y - v)) for x, y in coords if y >= v}
    elif axis == 'x':
        coords = {(x, y) for x, y in coords if x < v} | {(v - (x - v), y) for x, y in coords if x >= v}
 
X, Y = max(c[0] for c in coords), max(c[1] for c in coords)
grid = np.zeros((X + 1, Y + 1), dtype=int)
for c in coords:
    grid[c] = 1
 
# .T = transpose (swap rows and columns)
print(grid)
print(grid.T)
imwrite("grid.png", grid.T)
 
# row of int values -> str
# replace 1 with █ and 0 with ░, print row
aa=[]
for i in range(0, len(grid.T)):
    aa.append(''.join([str(x) for x in grid.T[i]]))
    print(aa[i])
for a in aa:
    a=a.replace("1","█")
    a=a.replace("0","░")
    print(a)

import re
 
data = open("input.txt", "r", encoding="utf-8").read()
coords_section, folds_section = data.split("\n\n")
coords = {tuple(map(int, c.split(","))) for c in coords_section.splitlines()}
folds = [re.match(r"fold along (x|y)=(\d+)", f).groups() for f in folds_section.splitlines()]
folds = [(a, int(v)) for a, v in folds]
 
for axis, v in folds[0:1]:
    if axis == 'y':
        coords = {(x, y) for x, y in coords if y < v} | {(x, v - (y - v)) for x, y in coords if y >= v}
    elif axis == 'x':
        coords = {(x, y) for x, y in coords if x < v} | {(v - (x - v), y) for x, y in coords if x >= v}
 
print(len(coords))

data = open("input.txt", "r", encoding="utf-8").read()
lst = [line.split("-") for line in data.splitlines()]
edges = [[a, b] for a, b in lst if a != "end" and b != "start"]
edges += [[b, a] for a, b in lst if a != "start" and b != "end"]
 
 
def find_path_r(current_path, found_paths, repeat):
    current_node = current_path[-1]
    if current_node == "end":
        found_paths.append(current_path)
        return
    for edge in edges:
        if edge[0] == current_node:
            if edge[1].isupper() or edge[1] not in current_path:
                find_path_r(current_path + [edge[1]], found_paths, repeat)
            elif edge[1].islower() and edge[1] in current_path and repeat:
                find_path_r(current_path + [edge[1]], found_paths, False)
 
 
def find_paths(repeat):
    """Find the all the paths from start to the end node"""
    found_paths = []
    find_path_r(["start"], found_paths, repeat)
    return found_paths
 
 
print(f"Part 01: Paths, no repeat visit allowed:  {len(find_paths(False))}")
print(f"Part 02: Paths, one repeat visit allowed: {len(find_paths(True))}")

import numpy as np
from scipy import signal
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
df = np.array([[int(x) for x in line] for line in data])
 
step = 0
while True:
    energy = np.ones_like(df)
    flashed = np.zeros_like(df)
    while np.any(energy.astype(bool)):
        df += energy
        flashing = np.logical_and((df > 9), np.logical_not(flashed))
        energy = signal.convolve(flashing, np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]]), mode='same')
        flashed = np.logical_or(flashed, flashing)
    df[flashed] = 0
    step += 1
    if np.all(flashed):
        print(step)
        exit()

import numpy as np
from scipy import signal
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
df = np.array([[int(x) for x in line] for line in data])
 
total = 0
for i in range(100):
    energy = np.ones_like(df)
    flashed = np.zeros_like(df)
    while np.any(energy.astype(bool)):
        df += energy
        flashing = np.logical_and((df > 9), np.logical_not(flashed))
        energy = signal.convolve(flashing, np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]]), mode='same')
        flashed = np.logical_or(flashed, flashing)
    df[flashed] = 0
    total += np.sum(flashed)
print(total)

octopi = open("input.txt", "r", encoding="utf-8").read().splitlines()
octopi = [[int(x) for x in line] for line in octopi]
 
max_x = len(octopi[0]) - 1
max_y = len(octopi) - 1
total_octopi = (max_x + 1) * (max_y + 1)
 
neighbors = dict()
part1 = 0
 
for y in range(max_y + 1):
    for x in range(max_x + 1):
        d = neighbors.setdefault((x,y),list())
        if x > 0:
            d.append((x-1,y))
        if x < max_x:
            d.append((x+1,y))
        if y > 0:
            d.append((x,y-1))
        if y < max_y:
            d.append((x,y+1))
 
i = 0
while True:
    part2 = 0
    queue = list()
    for y in range(max_y + 1):
        for x in range(max_x + 1):
            v = octopi[y][x]
            if v == 9:
                part2 += 1
                octopi[y][x] = 0
                queue.append((x,y))
            else:
                octopi[y][x] = v + 1
    while len(queue) > 0:
        (x,y) = queue.pop(0)
        for yy in range(max(y-1,0),min(y+1,max_y)+1):
            for xx in range(max(x-1,0),min(x+1,max_x)+1):
                if (xx,yy) != (x,y):
                    v = octopi[yy][xx]
                    if v != 0:
                        if v == 9:
                            part2 += 1
                            octopi[yy][xx] = 0
                            queue.append((xx,yy))
                        else:
                            octopi[yy][xx] = v + 1
    i += 1
    part1 += part2
    if i == 100:
        print(f"Part 1: Number of total flashes after 100 steps: {part1}")
    if part2 == total_octopi:
        # print('\n'.join([''.join([str(x) for x in line]) for line in octopi]))
        print(f"Part 2: First step when all octopi are flashing: {i}")
        break

from statistics import median
 
def checker(line):
    stack = []
    for char in line:
        if char in '([{<':
            stack.append(char)
        elif char in ')':
            if stack.pop() != '(':
                return 0
        elif char in ']':
            if stack.pop() != '[':
                return 0
        elif char in '}':
            if stack.pop() != '{':
                return 0
        elif char in '>':
            if stack.pop() != '<':
                return 0
    score = 0
    d = {'(': 1, '[': 2, '{': 3, '<': 4}
    for char in stack[::-1]:
        score *= 5
        score += d[char]
    return score
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
scores = [checker(line) for line in data]
print(median([x for x in scores if x != 0]))

def checker(line):
    stack = []
    for char in line:
        if char in '([{<':
            stack.append(char)
        elif char in ')':
            if stack.pop() != '(':
                return 3
        elif char in ']':
            if stack.pop() != '[':
                return 57
        elif char in '}':
            if stack.pop() != '{':
                return 1197
        elif char in '>':
            if stack.pop() != '<':
                return 25137
    return 0
 
data = open("input.txt", "r", encoding="utf-8").read().splitlines()
print(sum(checker(line) for line in data))

import numpy as np
from skimage.measure import label, regionprops
 
df = np.array([list(map(int, [c for c in line])) for line in open("input.txt", "r", encoding="utf-8").read().splitlines()])
print(np.prod(sorted([r.area for r in regionprops(label(df < 9, connectivity=1))])[-3:]))

# We need to group the numbers between 0–8 (not 9), 
# so 9 will be like a wall that separates the groups.
# Then make a list of groups and the number of members in it.
# The result will be the product of the top three groups.
 
import math
 
def get_adjacents(i, j):
    adjacents = []
    if i+1 < len(grid[0]):
        adjacents.append(grid[j][i+1])
    if i-1 >= 0:
        adjacents.append(grid[j][i-1])
    if j+1 < len(grid):
        adjacents.append(grid[j+1][i])
    if j-1 >= 0:
        adjacents.append(grid[j-1][i])
    return adjacents
 
def count_groups(i, j):
    if j < 0 or j >= len(grid) or \
       i < 0 or i >= len(grid[0]) or \
       grid[j][i] == 9 or \
       grid[j][i] == -1:
        return
    grid[j][i] = -1
    groups[len(groups)-1] += 1
    count_groups(i+1, j)
    count_groups(i-1, j)
    count_groups(i, j+1)
    count_groups(i, j-1)
 
grid = open("input.txt", "r").read().splitlines()
grid = [list(map(int, x)) for x in grid]
 
groups = []
for i in range(0, len(grid)):
    for j in range(0, len(grid[0])):
        groups.append(0)
        count_groups(j, i)
print(math.prod(sorted(groups, reverse=True)[:3]))

import numpy as np
 
data = open("input.txt", "r", encoding="utf-8").read()
df = np.array([list(map(int, [c for c in line])) for line in data.splitlines()])
pad = np.pad(df, ((1, 1), (1, 1)), "constant", constant_values=10)
mask = (
    (df < pad[1:-1, 0:-2]).astype(int)  # left
    + (df < pad[1:-1, 2:]).astype(int)  # right
    + (df < pad[0:-2, 1:-1]).astype(int)  # top
    + (df < pad[2:, 1:-1]).astype(int)  # bottom
)
print((df + 1)[mask == 4].sum())

def get_adjacents(i, j):
    adjacents = []
    if i+1 < len(grid[0]):
        adjacents.append(grid[j][i+1])
    if i-1 >= 0:
        adjacents.append(grid[j][i-1])
    if j+1 < len(grid):
        adjacents.append(grid[j+1][i])
    if j-1 >= 0:
        adjacents.append(grid[j-1][i])
    return adjacents
 
grid = open("input.txt", "r").read().splitlines()
grid = [list(map(int, x)) for x in grid]
 
result = 0
for j in range(0, len(grid)):
    for i in range(0, len(grid[0])):
        if grid[j][i] < min(get_adjacents(i, j)):
            result += 1 + grid[j][i]
print(result)

data = open("input.txt", "r").read().splitlines()
data = [x.split('|') for x in data]
data = [(i.split(), o.split()) for i, o in data]
 
 
def intersect(a, b):
    return len(set(a).intersection(b))
 
 
total = 0
for d in data:
 
    # Find wires representations of 1, 4, 7, 8 based on number of wires used
    for n in d[0]:
        n = ''.join(sorted(n))
        length = len(n)
 
        # 1 has 2 segments
        if length == 2:
            one = n
        # 4 has 4 segments
        elif length == 4:
            four = n
        # 7 has 3 segments
        elif length == 3:
            seven = n
        # 8 has 7 segments
        elif length == 7:
            eight = n
 
    # Deduce others digits only by comparing wires with representation of 1, 4, 7, 8
    for n in d[0]:
        n = ''.join(sorted(n))
        length = len(n)
 
        # 0, 6 and 9 have 6 segments
        if length == 6:
            if intersect(n, four) == 4:
                nine = n
            elif intersect(n, one) == 2:
                zero = n
            else:
                six = n
 
        # 2, 3 and 5 have 5 segments
        if length == 5:
            if intersect(n, one) == 2:
                three = n
            elif intersect(n, four) == 2:
                two = n
            else:
                five = n
 
    match = {
        zero: '0',
        one: '1',
        two: '2',
        three: '3',
        four: '4',
        five: '5',
        six: '6',
        seven: '7',
        eight: '8',
        nine: '9'
    }
 
    value = ''.join(match[''.join(sorted(x))] for x in d[1])
    total += int(value)
 
print(total)

import numpy as np
 
data = open("input.txt", "r").read().splitlines()
data = [x.split('|') for x in data]
data = [(i.split(), o.split()) for i, o in data]
 
# Example:
# First line of input is split into a list of two values.  The two values are then split into a list each:
# fcdeba edcbag decab adcefg acdfb gdcfb acf fabe fa eacfgbd | aefb cfa acf cdabf
# ['fcdeba edcbag decab adcefg acdfb gdcfb acf fabe fa eacfgbd'],['aefb cfa acf cdabf']
# ['fcdeba','edcbag','decab','adcefg','acdfb','gdcfb','acf','fabe','fa','eacfgbd'],['aefb','cfa','acf','cdabf']
 
total = 0
for d in data: # process lines
    nb_segments = [len(x) for x in d[1]] # length of each string value in d[1]
    nb_segments = np.array(nb_segments)
    is1 = (nb_segments == 2).sum() # 1 has 2 segments
    is4 = (nb_segments == 4).sum() # 4 has 4 segments
    is7 = (nb_segments == 3).sum() # 7 has 3 segments
    is8 = (nb_segments == 7).sum() # 8 has 7 segments
    total += is1 + is4 + is7 + is8
 
print(total)

data = open('input.txt', encoding='utf-8').read()
df = list(map(int, data.split(',')))
p_min, p_max = min(df), max(df)
fuels = [sum(map(lambda x: abs(x - p) * (abs(x - p) + 1) // 2, df)) for p in range(p_min, p_max + 1)]
print(min(fuels))

data = open('input.txt', encoding='utf-8').read()
df = list(map(int, data.split(',')))
p_min, p_max = min(df), max(df)
fuels = []
for p in range(p_min, p_max + 1):
    # for this position, calculate total fuel spend over all crabs
    fuel = 0
    for i in range(len(df)):
        fuel += abs(df[i] - p) * (abs(df[i] - p) + 1) // 2
    fuels.append(fuel)
print(min(fuels))

data = open('input.txt', encoding='utf-8').read()
df = list(map(int, data.split(',')))
p_min, p_max = min(df), max(df)
fuels = [sum(map(lambda x: abs(x - p), df)) for p in range(p_min, p_max + 1)]
print(min(fuels))

data = open('input.txt', encoding='utf-8').read()
df = list(map(int, data.split(',')))
p_min, p_max = min(df), max(df)
fuels = []
for p in range(p_min, p_max + 1):
    # for this position, calculate total fuel spend over all crabs
    fuel = 0
    for i in range(len(df)):
        fuel += abs(df[i] - p)
    fuels.append(fuel)
print(min(fuels))

from collections import Counter
 
data = open("input.txt", encoding='utf-8').read()
df = Counter([int(x) for x in data.split(",")])
for i in range(-1, 9):
    if i not in df:
        df[i] = 0
 
for day in range(256):
    for i in range(9):
        df[i-1] = df[i]
    df[6] += df[-1]
    df[8] = df[-1]
    df[-1] = 0
    print(f"After {day+1} days:", df)
 
total = 0
for i in range(9):
    total += df[i]
print(total)

import numpy as np
 
data = open("input.txt", encoding='utf-8').read()
df = np.array([int(x) for x in data.split(",")])
 
for day in range(80):
    df -= 1
    new = np.sum(df < 0)
    df = np.where(df < 0, 6, df)
    if new:
        df = np.hstack([df, np.full(new, 8)])
    print(f"After {day+1} days:", df)
 
print(df.shape)