Advent of Code 2021: Casi no llegamos edition

eZpit #241 Dic '21 Juntabrackets

Un poco tedioso hoy, pero esta original.

Para el 8 Pt 2, he buscado a ojo intersecciones que fuesen únicas:

NSFW

1

sergioRG #242 Dic '21 Juntabrackets

Dia 9 partes 1 y 2

spoiler

import sys
from itertools import product
from functools import reduce

m = [[int(x) for x in line.strip()] for line in sys.stdin]
N, M = len(m), len(m[0])


def get_adj(i, j):
  return \
    [
      (ii, jj) for (ii, jj) in
      product(
        range(max(0, i - 1), min(N, i + 2)),
        range(max(0, j - 1), min(M, j + 2))
      )
      if (ii != i) ^ (jj != j)
    ]


low_points = [
  (i, j) for (i, j) in product(range(N), range(M))
  if m[i][j] < min(m[ii][jj] for (ii, jj) in get_adj(i ,j))
]

print(sum(m[i][j] + 1 for (i, j) in low_points))


# part 2
def add_next(i, j, vis):
  if (i, j) not in vis:
    vis.add((i, j))
    for (ii, jj) in get_adj(i, j):
      if m[ii][jj] > m[i][j] and m[ii][jj] < 9:
        add_next(ii, jj, vis)
  return vis

basins = list(sorted([add_next(i, j, set()) for (i, j) in low_points], key=lambda x: -len(x)))

print(reduce(int.__mul__, [len(x) for x in basins[:3]]))

BeheritSp #243 Dic '21 Juntabrackets

Joder, hoy me ha costado la parte 2 porque estaba asumiendo que las basins necesitaban un vecino que fuera exactamente una unidad más (+1) que el low point. En el enunciado no lo dice en ningún sitio pero me he liado con el ejemplo

Day9


import numpy as np
smoke_matrix = [[int(char) for char in line] for line in open('input.txt').read().splitlines()]
risk_level = 0
low_points = set()
for i in range(len(smoke_matrix)):
    for j in range(len(smoke_matrix[i])):
        current = smoke_matrix[i][j]
        if not any(smoke_matrix[m][n] <= current for m,n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] \
                if 0 <= m < len(smoke_matrix) and 0 <= n < len(smoke_matrix[i])):
            risk_level += current + 1
            low_points.add((i,j))
print("Part 1", risk_level)

def search_basin(current, i, j, basin_path):
    neighbors = [(smoke_matrix[m][n], m, n) for m,n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] \
                if 0 <= m < len(smoke_matrix) and 0 <= n < len(smoke_matrix[i]) \
                and smoke_matrix[m][n] > current and not smoke_matrix[m][n]==9]
    for neighbor in neighbors:
        basin_path.add((neighbor[0],neighbor[1], neighbor[2]))
        basin_path = search_basin(neighbor[0], neighbor[1], neighbor[2], basin_path)
    return basin_path


basins=[]
for low_point in low_points:
    i,j = low_point
    current = smoke_matrix[i][j]
    basin_path = {(current, i,j)}
    basin_path=search_basin(current, i, j, basin_path)
    basins.append(len(basin_path))
print("Part 2",np.prod([basin for basin in reversed(sorted(basins))][0:3]))

1 1 respuesta

sergioRG #244 Dic '21 Juntabrackets

#243 Muchísimas gracias, porque me he atrapado en exactamente lo mismo.

Flashk #245 Dic '21

La parte 2 de hoy mola.

Day 9

Yo he optado por usar un algoritmo recursivo para la parte 2.
Una vez obtenido el tamaño de todas las basins, lo reordeno descendentemente y me quedo las tres mas grandes.

Code

public class SmokeBasin {

private Integer[][] heightMap;

private int maxCols;
private int maxRows;

public SmokeBasin(List<String> inputs) {
	
	maxCols = inputs.get(0).length();
	maxRows = inputs.size();
	
	heightMap = new Integer[maxRows][maxCols];
	
	int row = 0;
	for(String input : inputs) {

		String[] numbers = input.split("|");
		
		for(int col = 0; col < maxCols; col++) {
			heightMap[row][col] = Integer.valueOf(numbers[col]);
		}
		
		row++;
	}
}

public int solveA() {
	
	int result = 0;
	
	for(int row = 0; row < heightMap.length; row++) {
		for(int col = 0; col < heightMap[row].length; col++) {
			int lowerPointValue = calculateLowerPointValue(row,col);
			if(lowerPointValue != -1) {
				result += lowerPointValue;
			}
		}
	}
	
	return result;
}

public int solveB() {
	
	
	List<Integer> basinSizes = new ArrayList<>();
	
	for(int row = 0; row < heightMap.length; row++) {
		for(int col = 0; col < heightMap[row].length; col++) {
			int lowerPointValue = calculateLowerPointValue(row,col);
			if(lowerPointValue != -1) {
				basinSizes.add(searchBasin(row, col, new HashSet<>()));
			}
		}
	}
	
	List<Integer> orderedBasinSizes = basinSizes.stream().sorted(Comparator.reverseOrder()).limit(3).collect(Collectors.toList());
	
	int result = 1;
	for(Integer basinSize : orderedBasinSizes) {
		result *= basinSize;
	}
	return result;
}

private int searchBasin(int row, int col, Set<Position> visitedPositions) {
	
	if(isOutOfBounds(row,col)
		|| (heightMap[row][col] == 9) 
		|| (visitedPositions.contains(new Position(row,col)))) {
		return 0;
	}
	
	int result = 1;
	visitedPositions.add(new Position(row, col));
	
	result += searchBasin(row, col+1, visitedPositions); // Search right
	result += searchBasin(row, col-1, visitedPositions); // Search left
	result += searchBasin(row+1, col, visitedPositions); // Search down
	result += searchBasin(row-1, col, visitedPositions); // Search up
	
	return result;
	
}

private boolean isOutOfBounds(int row, int col) {
	return (col >= maxCols || col < 0) || (row >= maxRows || row < 0);
}

private int calculateLowerPointValue(int row, int col) {
	
	int right = col+1;
	int left = col-1;
	int up = row-1;
	int down = row+1;
	
	if((right < maxCols) && (heightMap[row][col] >= heightMap[row][right])) {
		return -1;
	}	
	
	if((left >= 0) && (heightMap[row][col] >= heightMap[row][left])) {
		return -1;
	}	
	
	if((up >= 0) && (heightMap[row][col] >= heightMap[up][col])) {
		return -1;
	}	
	
	if((down < maxRows) && (heightMap[row][col] >= heightMap[down][col])) {
		return -1;
	}	
	
	return heightMap[row][col] + 1;
}
}
[/spoiler]

1 respuesta

eZpit #246 Dic '21 Juntabrackets

#245 Idem pero es ineficiente (si has hecho igual que yo e iteras por todo todos los vecinos recursivamente). Tengo otra manera pensanda, pero ya para cuando acabe de currar xD

1 respuesta

PaCoX #247 Dic '21 Ant queen

ya he vuelto del puente... si tengo tiempo intentare hacer las anteriores pero me da palo xD

dia 9

Flashk #248 Dic '21

#246

spoiler

Primero parto únicamente desde aquellos puntos que sean un low point, no hago la recursividad con todo el tablero:

int lowerPointValue = calculateLowerPointValue(row,col);
if(lowerPointValue != -1) {
	basinSizes.add(searchBasin(row, col, new HashSet<>()));
}

Luego, una vez estoy en un low point recorro recursivamente cada camino hasta que se cumple una de estas tres condiciones:

Me salgo de límites.
La casilla tiene un 9.
Ya he visitado esa casilla.

		
if(isOutOfBounds(row,col)
	|| (heightMap[row][col] == 9) 
	|| (visitedPositions.contains(new Position(row,col)))) {
	return 0;
}

En esta línea añado la casilla actual como visitada:

visitedPositions.add(new Position(row, col));

Si ves la manera de hacerlo más eficiente, házmelo saber, pero al final tienes que recorrer todas las casillas que forman parte del basin al menos una vez.

Quizá podría mover la parte A del problema al constructor y guardar los lower points en un listado, de tal forma que cuando invoque el solveB(), directamente recorra los lower points y me ahorre tener que buscarlos; aunque en realidad lo único que estaría haciendo es dividir el tiempo de ejecución entre constructor + método en lugar de tenerlo todo en el método.

R

RsTTa #249 Dic '21

Bueno pues el de hoy parecido al del dia 6

spoiler

BeheritSp #250 Dic '21 Juntabrackets

El de hoy parecía de los duros en los que hay que pelearse con las strings pero al final no es para tanto:

Day 10

lines_list = open("input.txt").read().splitlines()
openers = {"(", "[", "{", "<"}
closer_map = {"(": ")", "[": "]", "{": "}", "<": ">"}
char_points = {")":3, "]":57, "}":1197, ">":25137}

failed_chars = []
to_complete_list = []
for line in lines_list:
    broken = False
    opener_list = []
    for char in line:
        if char in openers:
            opener_list.append(char)
        elif char == closer_map[opener_list[-1]]:
            opener_list.pop()
        else:
            failed_chars.append(char)
            broken = True
            break
    if not broken:
        to_complete = [closer_map[char]  for char in reversed(opener_list)]
        to_complete_list.append(to_complete)
print("Part 1", sum(char_points[char] for char in failed_chars))

complete_points = {")":1, "]":2, "}":3, ">":4}
points = []
for line in to_complete_list:
    score = 0
    for char in line:
        score = score*5+complete_points[char]
    points.append(score)
print("Part 2", sorted(points)[len(points)//2])

sergioRG #251 Dic '21 Juntabrackets

Dia 10, partes 1 y 2, quiza luego pienso como hacerlo menos guarro

spoiler

import sys

scores_1 = {')': 3, ']': 57, '}': 1197, '>': 25137}
scores_2 = {')': 1, ']': 2, '}': 3, '>': 4}

open2close = {'(': ')', '[': ']', '{': '}', '<': '>'}
close2open = {v: k for k, v in open2close.items()}

p1 = 0
p2_scores = []

for line in sys.stdin:
  st, err = [], False
  for c in line.strip():
    if c in open2close:
      st.append(c)
    elif not st or st.pop() != close2open[c]:
      p1 += scores_1[c]
      err = True
      break
  if not err:
    score = 0
    while st:
      score = score * 5 + scores_2[open2close[st.pop()]]
    p2_scores.append(score)

print(p1, sorted(p2_scores)[len(p2_scores) // 2])

1 respuesta

Flashk #252 Dic '21

#251 Menos guarro dice XD es superlimpio comparado con lo que me ha quedado a mi.

JonaN #253 Dic '21 Juntabrackets

Tenía sin hacer todos por haber estado fuera, pero he conseguido remontar entre ayer y hoy xd. Dejo el del día 10:

spoiler

import numpy as np
input=[[l for l in l.strip()] for l in open('./Input10.txt').readlines()]

pairs={')':'(',']':'[','}':'{','>':'<'}
scores={')':3,']':57,'}':1197,'>':25137}
scores2={'(':1,'[':2,'{':3,'<':4}
counter=0
leaderboard=[]

for row in input:
    tobeclosed=[]
    for x in range(len(row)):
        if row[x] in scores2:
            tobeclosed.append(row[x])
        elif pairs[row[x]]==tobeclosed[-1]: #If it matches the last one
            tobeclosed.pop() 
        else:
            counter+= scores[row[x]] ; break
        if x==len(row)-1: #If we got to the end w/o breaking:
            counter2=0
            tobeclosed.reverse()
            for item in tobeclosed:
                counter2=counter2*5 + scores2[item]
            leaderboard.append(counter2)

print(counter, np.median(leaderboard))

sergioRG #254 Dic '21 Juntabrackets

Hasta la tarde no podré ponerme hoy, a ver qué tal..

BeheritSp #255 Dic '21 Juntabrackets

Hoy un poco tedioso para debugear la parte 1 (si no te sale a la primera), pero una vez que tienes la parte 1, la parte 2 es casi inmediata.

Day 11

def mark_to_flash(matrix):
    return [[-1 if matrix[i][j] > 9 else matrix[i][j] for j in range(len(matrix[i]))] for i in range(len(matrix))]

def increase_neighbours(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] > 0:
                all_neighbours = [(i-1,j),(i+1,j),(i,j-1),(i,j+1), (i-1,j-1),(i+1,j-1),(i-1,j+1),(i+1,j+1)]
                neighbours = [(m,n) for m,n in all_neighbours if 0 <= m < len(matrix) and 0 <= n < len(matrix[i])]
                for m,n in neighbours:
                    if matrix[m][n] == -1:
                        matrix[i][j] += 1
    return matrix

def count_marked(matrix):
    return sum([sum([matrix[i][j] == -1 for j in range(len(matrix[i]))]) for i in range(len(matrix))])

def reset_flashed(matrix):
    return [[0 if matrix[i][j] == -1 else matrix[i][j] for j in range(len(matrix[i]))] for i in range(len(matrix))]

def count_flashes(matrix):
    return sum([sum([matrix[i][j] == 0 for j in range(len(matrix[i]))]) for i in range(len(matrix))])

def advance_step(matrix):
    matrix = [[value+1 for value in line] for line in matrix]
    matrix = mark_to_flash(matrix)
    marked_octopus = count_marked(matrix)
    while marked_octopus>0:
        matrix = mark_to_flash(reset_flashed(increase_neighbours(matrix)))
        marked_octopus = count_marked(matrix)
    matrix = reset_flashed(matrix)
    return matrix

if __name__ == "__main__":
    filename = "input.txt"
    octo_matrix = [[int(value) for value in line] for line in open(filename).read().splitlines()]
    steps = 100

    total_of_flashes = 0
    for step in range(steps):
        octo_matrix = advance_step(octo_matrix)
        total_of_flashes += count_flashes(octo_matrix)
    print("Part 1", total_of_flashes)


    octo_matrix = [[int(value) for value in line] for line in open(filename).read().splitlines()]
    step=0
    while not count_flashes(octo_matrix) == len(octo_matrix)*len(octo_matrix[0]):
        octo_matrix = advance_step(octo_matrix)
        step += 1
    print("Part 2", step)

Sleidom #256 Dic '21 Rocketeer

Dia 11 en Kotlin sin matrices:

spoiler

class Octopus(val point: Pair<Int, Int>, var energy: Int) {

var flashedTimes = 0
var flashedStep = 0

fun addEnergy(actualStep: Int) {
    if (actualStep != flashedStep)
        energy++
}

fun flash(actualStep: Int) {
    flashedTimes++
    flashedStep = actualStep
    energy = 0
}

fun ready() = energy > 9

}

fun main() {
    val input = File("src/input")
        .readLines()
        .flatMapIndexed { i, line ->
            line.mapIndexed { j, energy ->
                Pair(i, j) to Octopus(Pair(i, j), energy.toString().toInt())
            }
        }.toMap()

solve(input)
}

fun solve(input: Map<Pair<Int, Int>, Octopus>) {
    repeat(101) { step ->
        doOneStep(input, step)
    }

println("Part 1: " + input.values.sumOf { it.flashedTimes })

var firstStepAllFlash = 0
var step = 101
while (firstStepAllFlash == 0) {
    doOneStep(input, step)
    if (input.values.all { it.energy == 0 }) {
        firstStepAllFlash = step
    }
    step++
}
println("Part 2: $firstStepAllFlash")
}

private fun doOneStep(input: Map<Pair<Int, Int>, Octopus>, step: Int) {
    input.values.map {
        it.addEnergy(step)
    }

var octopusToFlash = input.values.filter { it.ready() }
while (octopusToFlash.isNotEmpty()) {
    octopusToFlash.map {
        it.flash(step)
        it.point.adjacentPoints().map {
            input[it]?.addEnergy(step)
        }
    }
    octopusToFlash = input.values.filter { it.ready() }
}
}

fun Pair<Int, Int>.adjacentPoints(): List<Pair<Int, Int>> {
    return listOf(
        Pair(this.first + 1, this.second),
        Pair(this.first - 1, this.second),
        Pair(this.first, this.second + 1),
        Pair(this.first, this.second - 1),
        Pair(this.first + 1, this.second + 1),
        Pair(this.first + 1, this.second - 1),
        Pair(this.first - 1, this.second + 1),
        Pair(this.first - 1, this.second - 1),
    )
}

eZpit #257 Dic '21 Juntabrackets

Dia 12 listo, corre un poco lento comparado con el resto, no se si hay truco o alguna fórmula para sacarlo más fácil.

NSFW

1 respuesta

Flashk #258 Dic '21

#257 Creo que hemos usado la misma solución por lo que describes

Day 12

1 respuesta

eZpit #259 Dic '21 Juntabrackets

#258 yo no he tocado nada

NSFW

1 respuesta

Flashk #260 Dic '21

#259 Voy a echar un ojo a lo que comentas, a ver si puedo simplificar el código, ¡gracias!

BeheritSp #261 Dic '21 Juntabrackets

La parte 2 me tarda más de 2 min, voy a ver si lo mejoro xd

Fyn4r #262 Dic '21 Inocente

Yo este finde no le hice ni caso a esto, pero bueno, es por una buena causa (espero xd)

Sleidom #263 Dic '21 Rocketeer

Dia 12 en Kotlin:

spoiler

Que haceis para que os tarde tanto? En mi caso no llega ni a 1 segundo.

3 respuestas

Flashk #264 Dic '21

#263 A mi me tarda algo más de 1 segundo también. Bonito código por cierto

BeheritSp #265 Dic '21 Juntabrackets

Bueno lo que me tardaba tanto era comprobar si había caminos duplicados. Ahora me tarda menos de 1 sec:

Day12

from collections import defaultdict
def read_input(filename):
    lines_list = open(filename).read().splitlines()
    caves=defaultdict(set)
    lower_case = set()
    for line in lines_list:
        start, end = line.split('-')
        caves[start].add(end)
        if not start == "start":
            caves[end].add(start)
        if start.islower() and not start == 'start':
            lower_case.add(start)
        if end.islower() and not end == 'end' and not end == 'start':
            lower_case.add(end)
    return caves, lower_case

def next_path(list_of_paths, starting_path, key, caves, lower_case=None):
    if key == 'end':
        list_of_paths.append(tuple(starting_path))
        return
    for cave in caves[key]:
        new_path = starting_path.copy()
        if not (cave.islower() and cave in new_path) or (cave == lower_case and new_path.count(cave) < 2):
            new_path.append(cave)
            next_path(list_of_paths, new_path, cave, caves, lower_case)


if __name__ == '__main__':
    caves, lower_case = read_input("input.txt")
    list_of_paths =  []
    for cave in caves["start"]:
        path = ["start", cave]
        next_path(list_of_paths, path, cave, caves)
    print("Part 1", len(list_of_paths))
    list_of_paths =  []
    for lower in lower_case:
        for cave in caves["start"]:
            path = ["start", cave]
            next_path(list_of_paths, path, cave, caves, lower)
    print("Part 2", len(list(dict.fromkeys(list_of_paths))))

eZpit #266 Dic '21 Juntabrackets

#263 me tarda 12ms en Rust, pero comprado con el resto que están en 50u-1ms me jode xD

2 respuestas

Sleidom #267 Dic '21 Rocketeer

#266 eso ya es enfermedad entonces xD

Flashk #268 Dic '21

#266 LOL!!!!!

Edit:

NSFW

R

RsTTa #269 Dic '21

la cosa sigue de dfs. es la soluciuon general este año xD

Unos 0.4 seg en Python la parte 2. Hago una copia de un dict en cada llamada que bueno, quitandola seguro que se ahorraria algo.

Parte 1

spoiler

from collections import defaultdict


def read_input(file_path: str) -> dict[str, set[str]]:
    graph = defaultdict(set)
    with open(file_path, 'r') as fp:
        for line in fp.readlines():
            cave1, cave2 = line.strip().split('-')
            if (cave1 != 'end') and (cave2 != 'start'):
                graph[cave1].add(cave2)
            if (cave2 != 'end') and (cave1 != 'start'):
                graph[cave2].add(cave1)
    return graph


def all_paths(graph: dict[str, set[str]], init_cave: str, final_cave: str, visited: set[str]) -> int:
    if init_cave == final_cave:
        return 1
    return sum(
        all_paths(graph, cave, final_cave, (visited | {cave}) if cave.islower() else visited)
        for cave in graph[init_cave]
        if cave not in visited
    )


if __name__ == '__main__':
    graph = read_input('input.txt')
    ans = all_paths(graph, 'start', 'end', set())
    print(ans)

Parte 2

spoiler

from collections import defaultdict


def read_input(file_path: str) -> dict[str, set[str]]:
    graph = defaultdict(set)
    with open(file_path, 'r') as fp:
        for line in fp.readlines():
            cave1, cave2 = line.strip().split('-')
            if (cave1 != 'end') and (cave2 != 'start'):
                graph[cave1].add(cave2)
            if (cave2 != 'end') and (cave1 != 'start'):
                graph[cave2].add(cave1)
    return graph


def all_paths(graph: dict[str, set[str]], init_cave: str, final_cave: str, small_caves_to_visits: dict[str, int], small_cave_visited_two_times: bool) -> int:
    if init_cave == final_cave:
        return 1
    if init_cave.islower():
        small_caves_to_visits[init_cave] += 1
        if small_caves_to_visits[init_cave] == 2:
            small_cave_visited_two_times = True
    paths = 0
    for cave in graph[init_cave]:
        if not ((cave in small_caves_to_visits) and small_cave_visited_two_times):
            paths += all_paths(graph, cave, final_cave, small_caves_to_visits.copy(), small_cave_visited_two_times)
    return paths


if __name__ == '__main__':
    graph = read_input('input.txt')
    ans = all_paths(graph, 'start', 'end', defaultdict(int), False)
    print(ans)

Flashk #270 Dic '21

Fucking segunda parte del día 13:

Day 13

1 respuesta

Usuarios habituales

Tags