Advent of Code 2021: Casi no llegamos edition

Acaban de indicarme en reddit que es posible que esté mal asumir que las dimensiones del array sean las de las máximas coordenadas:
https://old.reddit.com/r/adventofcode/comments/rfcfpt/yaxis_fold_not_in_middle_of_paper/

Debería haberlo notado cuando noté que las dimensiones del array eran impares, pero no caí en la cuenta...

El caso es que si miras las coordenadas, (y esto lo he comprobado contra el input de #276), deberían dar (1310, 894). A mi me dan (1310,893).
La forma guarra de solucionarlo es añadir un (0,894) a la entrada del input. La forma limpia que se me ocurre a bote pronto es calcular el % 2 de ambas dimensiones del array, si da que es impar, sumarle uno.

import re


def read_input(file_path: str) -> tuple[list[list[str]], list[str]]:
    points = set()
    max_row = 0
    max_col = 0
    with open(file_path, 'r') as fp:
        while line := fp.readline().strip():
            point = tuple(int(e) for e in line.split(','))
            x, y = point
            max_row = max(y, max_row)
            max_col = max(x, max_col)
            points.add(point)
        foldings = [line.strip() for line in fp.readlines()]
    matrix = [['#' if (j, i) in points else '.' for j in range(max_col + 1)] for i in range(max_row + 1)]
    return matrix, foldings


def fold_to_left(matrix: list[list[str]], folding_point: int):
    for i in range(len(matrix)):
        for j in range(folding_point):
            mirror_i = i
            mirror_j = folding_point + (folding_point - j)
            matrix[i][j] = '#' if '#' in (matrix[i][j], matrix[mirror_i][mirror_j]) else '.'


def fold_to_up(matrix: list[list[str]], folding_point: int):
    for i in range(folding_point):
        for j in range(len(matrix[i])):
            mirror_i = folding_point + (folding_point - i)
            mirror_j = j
            matrix[i][j] = '#' if '#' in (matrix[i][j], matrix[mirror_i][mirror_j]) else '.'


def fold_matrix(matrix: list[list[str]], foldings: list[str]) -> int:
    m = re.compile('([xy])=([0-9]+)')
    rows = len(matrix)
    cols = len(matrix[0])
    for folding in foldings:
        _type, val = m.search(folding).groups()
        if _type.lower() == 'x':
            cols = min(cols, int(val))
            fold_to_left(matrix, int(val))
        elif _type.lower() == 'y':
            rows = min(rows, int(val))
            fold_to_up(matrix, int(val))
    return sum([1 for i in range(rows) for j in range(cols) if matrix[i][j] == '#'])


if __name__ == '__main__':

matrix, foldings = read_input('input.txt')
ans = fold_matrix(matrix, foldings[:1])
print(ans)

import re


def read_input(file_path: str) -> tuple[list[list[str]], list[str]]:
    points = set()
    max_row = 0
    max_col = 0
    with open(file_path, 'r') as fp:
        while line := fp.readline().strip():
            point = tuple(int(e) for e in line.split(','))
            x, y = point
            max_row = max(y, max_row)
            max_col = max(x, max_col)
            points.add(point)
        foldings = [line.strip() for line in fp.readlines()]
    matrix = [['#' if (j, i) in points else '.' for j in range(max_col + 1)] for i in range(max_row + 1)]
    return matrix, foldings


def fold_to_left(matrix: list[list[str]], folding_point: int):
    for i in range(len(matrix)):
        for j in range(folding_point):
            mirror_i = i
            mirror_j = folding_point + (folding_point - j)
            matrix[i][j] = '#' if '#' in (matrix[i][j], matrix[mirror_i][mirror_j]) else '.'


def fold_to_up(matrix: list[list[str]], folding_point: int):
    for i in range(folding_point):
        for j in range(len(matrix[i])):
            mirror_i = folding_point + (folding_point - i)
            mirror_j = j
            matrix[i][j] = '#' if '#' in (matrix[i][j], matrix[mirror_i][mirror_j]) else '.'


def fold_matrix(matrix: list[list[str]], foldings: list[str]) -> list[list[str]]:
    m = re.compile('([xy])=([0-9]+)')
    rows = len(matrix)
    cols = len(matrix[0])
    for folding in foldings:
        _type, val = m.search(folding).groups()
        if _type.lower() == 'x':
            cols = min(cols, int(val))
            fold_to_left(matrix, int(val))
        elif _type.lower() == 'y':
            rows = min(rows, int(val))
            fold_to_up(matrix, int(val))
    return [[matrix[i][j] for j in range(cols)] for i in range(rows)]


if __name__ == '__main__':

matrix, foldings = read_input('input.txt')
ans = fold_matrix(matrix, foldings)
for row in ans:
    print(' '.join(map(lambda v: v if v == '#' else ' ', row)))

Al parecer, al doblar el papel, el cálculo se puede hacer de dos formas diferentes.
Dependiendo del punto de referencia, puedes imaginar que estás doblando por el centro o bien desde los extremos.

Doblando desde los extremos (mi solución inicial), lo que haces es calcular las nuevas coordenadas de cada punto tal que así:

|(maxX,0) - (x,y)| -> Para doblar hacia la izquierda

|(0,maxY) - (x,y)| -> Para doblar hacia arriba

Después de reubicar todos los puntos, recalculas los límites de maxX y maxY para la siguiente instrucción. El problema, claro está, es que no es fiable el input, igual te vienen 893 coordenadas y te la lía o te vienen 894 y funciona correctamente.

La opción B consiste en aplicar la fórmula desde el centro:

|(2*x1,0)-(x,y)| -> Para doblar hacia la izquierda, siendo x1 el punto donde se dobla

|(0,2*y1)-(x,y)| -> Para doblar hacia arriba, siendo y1 el punto donde se dobla

Una vez aplicada la fórmula de 2u-v, da el mismo resultado que desde los máximos, pero en este caso, no necesitas conocer los máximos ni dan ningún tipo de problema. He hecho la prueba sobre mi mismo código.

Que curioso todo esto.

from collections import Counter
lines_list = open('input.txt').read().splitlines()

polymer = [char for char in lines_list[0]]
pairs = { line.split(" -> ")[0]: line.split(" -> ")[1] for line in lines_list[2:] }
for step in range(10):
    new_polymer=[]
    for char1,char2 in zip(polymer, polymer[1:]):
        new_polymer.append(char1)
        if char1+char2 in pairs.keys():
            new_polymer.append(pairs[char1+char2])
    new_polymer.append(char2)
    polymer = new_polymer
counts = [polymer.count(char) for char in set(pairs.values())]
print("Part 1", max(counts) - min(counts))

polymer = [char for char in lines_list[0]]
count_pairs = Counter()
for pair in pairs.keys():
    if "".join(polymer).count(pair) > 0:
        count_pairs[pair] = "".join(polymer).count(pair)
count_chars = Counter()
for char in polymer:
    count_chars[char] += 1

generated_pairs_from_pair = {pair:(pair[0]+pairs[pair], pairs[pair]+pair[1]) for pair in pairs.keys() }
for step in range(40):
    new_count_pairs = count_pairs.copy()

    for counted_pair, current_count in count_pairs.items():
        for new_pair in generated_pairs_from_pair[counted_pair]:
            new_count_pairs[new_pair] += current_count
        new_count_pairs[counted_pair] -= current_count

        count_chars[pairs[counted_pair]] += current_count

    count_pairs = new_count_pairs.copy()
print("Part 2", max(count_chars.values()) - min(count_chars.values()))

https://github.com/Flashky/advent-of-code-2021/blob/master/src/main/java/com/adventofcode/flashk/day14/ExtendedPolymerization.java

Desde un principio vi que se parecía al de los Lanternfish, pero no terminaba de dar con la tecla para resolverlo.

def compute_score(max_i, max_j, evaluate_risk):
    score = {(i,j):1e6 if not (i==0 and j == 0) else 0 for i in range(max_i) for j in range(max_j)}
    visited = set()
    visited_neighs = set()
    current_node = (0,0)
    while not current_node == (max_i-1, max_j-1):
        i, j = current_node

        ini_time = time.time()
        neighbors = [(evaluate_risk(m,n), m, n) for m,n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] \
                    if 0 <= m < max_i and 0 <= n < max_j  \
                        and not (m,n) in visited]
        for neighbor in neighbors:
            neigh_value, n_i, n_j = neighbor
            distance = score[current_node] + neigh_value
            if distance < score[(n_i,n_j)]:
                score[(n_i,n_j)] = distance
            visited_neighs.add((n_i,n_j))
        visited.add(current_node)
        if current_node in visited_neighs:
            visited_neighs.remove(current_node)
        current_node = min(visited_neighs, key=lambda x: score[x])
    return score

def evaluate_risk_1(i,j):
    return risk_matrix[i][j]

def evaluate_risk_2(i,j):
    value = risk_matrix[i % len(risk_matrix)][j % len(risk_matrix[0])] + (j // len(risk_matrix[0])) + (i // len(risk_matrix[0]))
    if value > 9:
        value = value - 9
    return value

if __name__ == '__main__':

    risk_matrix = [[int(char) for char in line] for line in open('input.txt').read().splitlines()]
    max_i, max_j = len(risk_matrix), len(risk_matrix[0])

    score = compute_score(max_i, max_j, evaluate_risk_1)
    print("Part 1", score[max_i-1, max_j-1])

    score = compute_score(max_i*5, max_j*5, evaluate_risk_2)
    print("Part 2", score[max_i*5-1, max_j*5-1])

Solo cambiando esto

remaining = {(i, j): distances[(i, j)] for i in range(len(matrix)) for j in range(len(matrix[i]))}

por esto

remaining = {(start_row, start_col): 0}

se ha reducido muchisimo el tiempo. Claro que como se hace una busqueda del menor valor en cada iteracion del bucle externo, pues teniendo en cuenta las dimensiones de la matriz hay que recorrer muchos elementos. Ademas para tener todos con float('inf') pues se pueden quitar y dejar solo el valor del nodo inicial.

def read_input(file_path: str) -> list[list[int]]:
    with open(file_path, 'r') as fp:
        return [[int(n) for n in line.strip()] for line in fp.readlines() if line.strip()]


def manhattan(x1: int, y1: int, x2: int, y2: int) -> int:
    return abs(x1 - x2) + abs(y1 - y2)


def neighbors(row: int, col: int, matrix: list[list[int]], visited: set[tuple[int, int]]) -> list[tuple[int, int]]:
    neighs = []
    for i in range(row - 1, row + 2):
        if 0 <= i < len(matrix):
            for j in range(col - 1, col + 2):
                if (0 <= j < len(matrix[i])) and ((i, j) not in visited) and ((i, j) != (row, col)) and manhattan(row, col, i, j) == 1:
                    neighs.append((i, j))
    return neighs


def search_best_path(matrix: list[list[int]], start_row: int, start_col: int, end_row: int, end_col: int) -> int:
    distances = {(i, j): float('inf') for i in range(len(matrix)) for j in range(len(matrix[i]))}
    distances[(start_row, start_col)] = 0
    remaining = {(i, j): distances[(i, j)] for i in range(len(matrix)) for j in range(len(matrix[i]))}
    visited = set()

while remaining:
    row, col = min(remaining.items(), key=lambda t: t[1])[0]
    del remaining[(row, col)]
    visited.add((row, col))
    for i, j in neighbors(row, col, matrix, visited):
        distances[(i, j)] = min(distances[(i, j)], distances[(row, col)] + matrix[i][j])
        remaining[(i, j)] = distances[(i, j)]
return distances[(end_row, end_col)]


if __name__ == '__main__':

matrix = read_input('input.txt')
print(matrix)
ans = search_best_path(matrix, 0, 0, len(matrix) - 1, len(matrix[0]) - 1)
print(ans)

def read_input(file_path: str) -> list[list[int]]:
    with open(file_path, 'r') as fp:
        return [[int(n) for n in line.strip()] for line in fp.readlines() if line.strip()]


def expand_matrix(matrix: list[list[int]], times: int) -> list[list[int]]:
    orig_rows, orig_cols = len(matrix), len(matrix[0])
    rows, cols = len(matrix) * times, len(matrix[0]) * times
    expanded_matrix = [[None for _ in range(cols)] for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            val = ((matrix[i % orig_rows][j % orig_cols]) + ((i // orig_rows) + (j // orig_cols)))
            expanded_matrix[i][j] = val if val < 10 else (val % 10) + 1
    return expanded_matrix


def manhattan(x1: int, y1: int, x2: int, y2: int) -> int:
    return abs(x1 - x2) + abs(y1 - y2)


def neighbors(row: int, col: int, matrix: list[list[int]], visited: set[tuple[int, int]]) -> list[tuple[int, int]]:
    neighs = []
    for i in range(row - 1, row + 2):
        if 0 <= i < len(matrix):
            for j in range(col - 1, col + 2):
                if (0 <= j < len(matrix[i])) and ((i, j) not in visited) and ((i, j) != (row, col)) and manhattan(row, col, i, j) == 1:
                    neighs.append((i, j))
    return neighs


def search_best_path(matrix: list[list[int]], start_row: int, start_col: int, end_row: int, end_col: int) -> int:
    distances = {(i, j): float('inf') for i in range(len(matrix)) for j in range(len(matrix[i]))}
    distances[(start_row, start_col)] = 0
    remaining = {(start_row, start_col): 0}
    visited = set()

while remaining:
    row, col = min(remaining.items(), key=lambda t: t[1])[0]
    del remaining[(row, col)]
    visited.add((row, col))
    for i, j in neighbors(row, col, matrix, visited):
        distances[(i, j)] = min(distances[(i, j)], distances[(row, col)] + matrix[i][j])
        remaining[(i, j)] = distances[(i, j)]
return distances[(end_row, end_col)]


if __name__ == '__main__':

matrix = read_input('input.txt')
expanded_matrix = expand_matrix(matrix, 5)
ans = search_best_path(expanded_matrix, 0, 0, len(expanded_matrix) - 1, len(expanded_matrix[0]) - 1)
print(ans)