Advent of Code 2018: segunda semana
Segunda semana del Advent of Code. En esta semana ya hemos tenido algunos problemas muy interesantes. Intentaré comentarlos de la mejor manera posible. Todo el código está aquí y en este otro post comenté mis soluciones de la primera semana.
Día 8
El día 8 se nos propone un problema de grafos también. Básicamente se nos define un árbol, donde cada nodo puede tener hijos y metadatos. En la primera parte nos piden sumar todos los metadatos.
Aquí al contrario que en el día 7, no voy a usar networkx. Era más difícil adaptar networkx al problema que hacer el árbol a mano. Uno de los puntos complicados de este problema es el parseo de la entrada, que hice de forma recursiva. Cada nodo es un diccionario con las propiedades tamaño, una lista de metadatos y una lista de nodos hijo.
En la segunda parte se define el concepto de valor de nodo y como calcularlo. También es bastante sencillo de implementar. Finalmente hacemos un recorrido por el árbol de tipo primero en anchura (BFS) con una deque de Python.
from collections import deque
def read_node(start,numbers):
length = 2
child_nodes = numbers[start]
metadata_entries = numbers[start+1]
children = list()
while child_nodes > 0:
child_node = read_node(start+length,numbers)
children.append(child_node)
length += child_node["length"]
child_nodes -= 1
metadata = list()
while metadata_entries > 0:
metadata.append(numbers[start+length])
length += 1
metadata_entries -= 1
node = dict([("length",length),("metadata",metadata),("children",children)])
return node
def read_file(file):
with open(file) as f:
line = f.readline()
numbers = [int(x) for x in line.split()]
G = read_node(0,numbers)
return G
def node_value(N):
if len(N["children"]) == 0:
return sum(N["metadata"])
else:
s = 0
for i in N["metadata"]:
if i-1 < len(N["children"]):
s += node_value(N["children"][i-1])
return s
def day8(file):
G = read_file(file)
to_visit = deque()
to_visit.append(G)
metadata_sum = 0
while len(to_visit) > 0:
N = to_visit.popleft()
metadata_sum += sum(N["metadata"])
to_visit.extend(N["children"])
print("METADATA SUM: %d" % metadata_sum)
print("NODE VALUE: %d" % node_value(G))Día 9
Este día fue muy interesante. Se nos explica un juego, que consiste en ir añadiendo canicas en una circunferencia y cuando el número de canica que añadimos es múltiplo de 23, obtenemos puntos y quitamos una canica 7 puestos por detrás.
Aquí tuve una mala decisión de diseño ya que al principio quise hacer esto con una lista de Python (el equivalente a vector en otros lenguajes de programación). La idea era sencilla y funcionaba hasta que llegó la parte 2. La parte 2 te pedría calcular los puntos teniendo en cuenta 100 veces más canicas. Esto fue un grave problema para mi código. Calculo que tardaría 6 horas en calcularlo, pero antes optimicé. La optimización consistía en usar una lista circular doblemente enlazada. ¿Esto qué es? Se trata de una lista enlazada, doblemente, porque cada nodo tiene referencia al elemento siguiente y al anterior. Y es circular porque ambos extremos están unidos. Esto permite las inserciones y borrados en O(1). Además los movimientos relativos (en este problema todos son así) son extremadamente sencillos. La implementación de esta estructura de datos en Python es muy sencilla (en otros lenguajes es más complicado). No me molesté en hacer funciones que me hiciesen sencilla la vida y las conexiones/desconexiones las hago a mano directamente en el código del problema.
from collections import defaultdict
class Marble:
def __init__(self,value,left=None,right=None):
self.value = value
self.left = left
self.right = right
if self.left == None:
self.left = self
if self.right == None:
self.right = self
def day9(PLAYERS,LAST_MARBLE):
SCORE = defaultdict(lambda: 0)
player = 0
marble = 0
current_marble_pos = 0
current_marble = None
while marble <= LAST_MARBLE:
if marble > 0 and marble % 23 == 0:
SCORE[player] += marble
pivote = current_marble.left.left.left.left.left.left.left
SCORE[player] += pivote.value
pivote.left.right = pivote.right
pivote.right.left = pivote.left
current_marble = pivote.right
else:
if current_marble == None:
current_marble = Marble(marble)
else:
current_marble = Marble(marble,current_marble.right,current_marble.right.right)
current_marble.left.right = current_marble
current_marble.right.left = current_marble
player += 1
player = player % PLAYERS
marble += 1
return max(SCORE.values())Curiosamente, en la propia librería de Python deque tiene una operación llamada rotate que permite hacer este problema en poquísimas líneas y de forma muy eficiente. Pero desconocía la existencia de esa función (que lo que hace es mover la "cabeza" de la lista enlazada que es deque).
Día 10
Este problema es muy interesante. Se nos da una serie de puntos que van moviéndose por la pantalla. En un determinado momento estos puntos se juntan y forman un mensaje en pantalla.
Aquí lo interesante no es mover los puntos, eso es trivial, simplemente es sumar la velocidad cada vez las coordenadas. Lo interesante es saber cuando parar. Existen varias ideas:
- Revisión humana de cada iteración
- Comprobar que no haya puntos separados del resto (con grafos)
- Comprobar que el área de concentración de puntos es mínima
Y alguna más. Para el ejemplo la primera idea servía. Pero en la prueba real, era más complicado. A mí se me ocurrió la tercera opción, la cuál es bastante eficiente. En cada iteración calculamos el área que contiene a todos los puntos, cuando ese área ya no se reduce más, hemos llegado al mensaje.
import re
def read_file(file):
stars = list()
p = re.compile("position=<([ -][0-9]+), ([ -][0-9]+)> velocity=<([ -][0-9]+), ([ -][0-9]+)>")
with open(file) as f:
lines = f.readlines()
for line in lines:
m = p.match(line.strip())
try:
pos_x = int(m.group(1))
except:
print(line)
pos_y = int(m.group(2))
vel_x = int(m.group(3))
vel_y = int(m.group(4))
stars.append([pos_x,pos_y,vel_x,vel_y])
return stars
def print_stars(stars):
stars = sorted(stars,key=lambda x: x[0],reverse=True)
min_width = stars[-1][0]
max_width = stars[0][0]
min_height = min(stars,key=lambda x: x[1])[1]
max_height = max(stars,key=lambda x: x[1])[1]
s = str()
for j in range(min_height,max_height+1):
p = [star for star in stars if star[1] == j]
for i in range(min_width,max_width+1):
if len(p) == 0:
s += "."
else:
if any(map(lambda star: star[0] == i and star[1] == j,p)):
s += "#"
else:
s += "."
s += "\n"
return s
def step(stars):
a = map(lambda x: [x[0]+x[2],x[1]+x[3],x[2],x[3]],stars)
return list(a)
# LA RESPUESTA CORRECTA TIENE AREA MINIMA
def area(stars):
stars = sorted(stars,key=lambda x: x[0], reverse=True)
min_width = stars[-1][0]
max_width = stars[0][0]
min_height = min(stars,key=lambda x: x[1])[1]
max_height = max(stars,key=lambda x: x[1])[1]
area = (max_width-min_width)*(max_height-min_height)
return area
def day10(file):
stars = read_file(file)
a = area(stars)
steps = 0
while area(step(stars)) < a:
stars = step(stars)
steps += 1
a = area(stars)
print_stars(stars)
print(steps)La parte de dibujado me costó y ahí tuve un fallo que me costó media hora aproximadamente en resolver. Una mejor opción, pero que no se me ocurrió, hubiese sido usar Pillow y crear una imagen. Es mucho más fácil que dibujar sobre una terminal (y posiblemente más rápido).
Día 11
Para este problema hay 3 posibles algoritmos. En la primera parte nos piden que de una matriz extraigamos el cuadrado de 3x3 con mayor valor. La matriz hay que construirla pero es trivial. Yo decido usar un diccionario, con clave la tupla de coordenadas. Vamos recorriendo todas las posiciones y calculamos el valor. Ahora para buscar el cuadrado, simplemente vamos probando todos los posibles cuadrados.
En la segunda parte nos dicen que bsuquemos el cuadrado máximo pero el tamaño puede ser cualquiera. Aquí con la fuerza bruta ya tarda demasiado. Mi solución fue usar programación dinámica, para ello la clave pasa a tener un valor más, el tamaño del cuadrado. Cuando creamos la tabla estamos asignando valor al cuadrado 1x1 de posición X,Y. Representado es la tupla (x,y,1). Según vamos avanzando hasta 300x300 vamos guardando los resultados intermedios, de modo que podamos reutilizarlos. Por ejemplo, el valor de (x,y,4) solamente es la suma de (x,y,2), (x+2,y,2), (x,y+2,2) y (x+2,y+2,2). Evidentemente esto solo funciona en los tamaños pares. En los tamaños impares decidí coger el cuadrado de dimensión inmediatamente menor y calcular los laterales con los cuadrados de tamaño 1. Este sistema funciona mucho mejor que la fuerza bruta pero es lento. Los profesionales usaron el algoritmo Summed Area Table (del que desconocía su existencia). Este algoritmo es el óptimo para este problema.
def generate_fuel(x,y,idg):
fuel = (((x+10)*y)+idg)*(x+10)
fuel %= 1000
fuel = (fuel // 100) - 5
return fuel
def generate_table(idg):
fuel = {(x,y,size):0 for x in range(1,301) for y in range(1,301) for size in range(1,301)}
for x in range(1,301):
for y in range(1,301):
fuel[(x,y,1)] = generate_fuel(x,y,idg)
return fuel
def find_best(fuel):
max_point = [-1,-1]
max_score = -1
for x in range(1,301):
for y in range(1,301):
if x+3 > 301 or y+3 > 301:
continue
score = fuel[(x,y,1)]+fuel[(x+1,y,1)]+fuel[(x+2,y,1)]+fuel[(x,y+1,1)]+fuel[(x+1,y+1,1)]+fuel[(x+2,y+1,1)]+fuel[(x,y+2,1)]+fuel[(x+1,y+2,1)]+fuel[(x+2,y+2,1)]
if score > max_score:
max_score = score
max_point = [x,y]
return max_point[0],max_point[1]
def find_best_any_size(fuel):
max_score = -1
max_point = [-1,-1,-1]
for size in range(2,300+1):
for x in range(1,301):
for y in range(1,301):
if x+size > 301 or y+size > 301:
continue
if size % 2 == 0:
mid = size // 2
fuel[(x,y,size)] = fuel[(x+mid,y,mid)]+fuel[(x,y+mid,mid)]+fuel[(x+mid,y+mid,mid)]+fuel[(x,y,mid)]
else:
fuel[(x,y,size)] = fuel[(x,y,size-1)]
for i in range(x,x+size-1):
fuel[(x,y,size)] += fuel[(i,y+size-1,1)]
for j in range(y,y+size-1):
fuel[(x,y,size)] += fuel[(x+size-1,j,1)]
fuel[(x,y,size)] += fuel[(x+size-1,y+size-1,1)]
score = fuel[(x,y,size)]
if score > max_score:
max_score = score
max_point = [x,y,size]
return max_point[0],max_point[1],max_point[2]
def day11():
fuel = generate_table(1133)
x,y = find_best(fuel)
print("BEST POINT: %d,%d" % (x,y))
x,y,size = find_best_any_size(fuel)
print("BEST POINT ANY SIZE: %d,%d,%d" % (x,y,size))
if __name__ == "__main__":
day11()Día 12
El día 12 me trajo recuerdos de un algoritmo con el que me peleé mucho, el denominado HashLife. El problema es un autómata celular unidimensional. Las reglas vienen dadas como patrones. La única diferencia es que hay que guardar su posición para luego calcular un número. La primera parte es bastante sencilla.
import re
from collections import defaultdict
def read_file(file):
rules = defaultdict(lambda: ".")
rule_prog = re.compile("([.#]+) => ([.#])")
with open(file) as f:
lines = f.readlines()
state = lines[0].split(": ")[1].strip()
for line in lines[2:]:
m = rule_prog.match(line.strip())
rules[m.group(1)] = m.group(2)
return state,rules
def parse_state(pots):
state = dict()
for i,p in enumerate(pots):
state[i] = p
return state
def find(rules,current):
if current in rules:
return rules[current]
else:
size = len(current)
mid = size // 2
left = find(rules,current[0:mid])
right = find(rules,current[mid:])
rules[current] = left + right
return rules[current]
def iter(state,rules):
new_state = dict()
xmin = min(state.keys())
xmax = max(state.keys())
for x in range(xmin-2,xmax+3):
current = ("%c%c%c%c%c" % (
state.get(x-2,"."),
state.get(x-1,"."),
state.get(x,"."),
state.get(x+1,"."),
state.get(x+2,".")
))
new = rules[current]
if new == "#" or xmin <= x <= xmax:
new_state[x] = new
return new_state
def sum_pots(state):
n = 0
for pot in state:
if state[pot] == "#":
n += pot
return n
def print_state(state):
xmin = min(state.keys())
xmax = max(state.keys())
s = str("XMIN %d : " % xmin)
for x in range(xmin-2,xmax+3):
s += state.get(x,".")
print(s)
def day12(file):
state,rules = read_file(file)
state = parse_state(state)
for i in range(20):
#print_state(state)
state = iter(state,rules)
#print_state(state)
n = sum_pots(state)
return n
if __name__ == "__main__":
day12("input.txt")
La segunda parte nos pedía lo mismo pero para el número ¡50000000000! Inmediatamente pensé en optimizarlo de forma similar a HashLife. La idea consiste en almacenar patrones mayores a los de las reglas (que son todos de tamaño 5), para poder evitar cálculos innecesarios.Además añadí un recolector de basura para ir eliminando por la izquierda las celdas inútiles.
No obstante, y aunque es muchísimo más eficiente, sigue sin ser capaz de procesar tal bestialidad de número en un tiempo razonable.
Y he aquí lo que me ha cabreado, porque no he podido sacarlo. A partir de cierto momento, el dibujo siempre es el mismo pero desplazándose a la derecha. De modo que el valor del siguiente paso siempre es la suma de una constante. Finalmente modifiqué el código para que buscase una situación en la que el número fuese resultado de una suma de una constante. Una vez hecho eso, calcula con una multiplicación lo que valdría cuando llegase a 50000000000.
import re
from collections import defaultdict
XMIN = -2
def find(rules,current):
if len(current) < 5:
return ""
if current in rules:
return rules[current]
elif len(current) == 5:
return "."
else:
size = len(current)
left=find(rules,current[0:size-1])
right=find(rules,current[size-5:])
rules[current] = left+right
return rules[current]
def read_file(file):
rules = defaultdict(lambda: ".")
rule_prog = re.compile("([.#]+) => ([.#])")
with open(file) as f:
lines = f.readlines()
state = lines[0].split(": ")[1].strip()
for line in lines[2:]:
m = rule_prog.match(line.strip())
rules[m.group(1)] = m.group(2)
return state,rules
def print_state(state):
print(state)
def sum_pots(state):
n = 0
for i,c in enumerate(state):
if c == "#":
n += i + XMIN
return n
def day12(file):
global XMIN
state,rules = read_file(file)
XMAX = len(state)+1
state = "..%s.." % state
sums = list()
i = 0
while len(sums) < 3 or sums[-1]-sums[-2] != sums[-2]-sums[-3]:
state = find(rules,"..%s.." % state)
if state[0] == "." and state[1] == "." and state[2] == "." and state[3] == ".":
state = state[2:]
XMIN += 2
if state[0] == "#" or state[1] == "#":
state = "..%s" % state
XMIN -= 2
if state[-1] == "#" or state[-2] == "#":
state = "%s.." % state
sums.append(sum_pots(state))
i += 1
diff = sums[-1]-sums[-2]
missing = 50000000000 - i
n = missing*diff + sums[-1]
return n
Y con esto pude finalmente calcular el resultado.
Día 13
El día 13 teníamos unas vías de tren. En estas vías había unos trenecitos que se desplazaban siguiendo unas normas. El objetivo en la primera parte era conocer el donde se producía el primer choque.
from PIL import Image
XMAX = 0
YMAX = 0
STEP = 0
nextDirection = dict()
nextDirection["start"] = "left"
nextDirection["left"] = "center"
nextDirection["center"] = "right"
nextDirection["right"] = "left"
def relative_direction(original,movement):
print("CROSS")
if movement == "center":
return original
if original == "v":
if movement == "left":
return ">"
else:
return "<"
elif original == ">":
if movement == "left":
return "^"
else:
return "v"
elif original == "^":
if movement == "left":
return "<"
else:
return ">"
else:
if movement == "left":
return "v"
else:
return "^"
def day13(file):
global XMAX
global YMAX
global STEP
plano = dict()
carts = list()
with open(file) as f:
lines = f.readlines()
YMAX = len(lines)
XMAX = len(lines[0])
for y,line in enumerate(lines):
for x,char in enumerate(line):
# SI HAY UN CARRITO, DEDUCIR TIPO DE VIA
if char == "^" or char == "v" or char == "<" or char == ">":
if (x,y-1) in plano:
plano[(x,y)] = "|"
else:
plano[(x,y)] = "-"
carts.append([x,y,char,"left"])
else:
plano[(x,y)] = char
end = False
while not end:
carts.sort(key=lambda x: x[1])
carts.sort(key=lambda x: x[0])
for cart in carts:
# CHECK CRASH
for crt in carts:
if cart[0] == crt[0] and cart[1] == crt[1] and id(cart) != id(crt):
print("CRASH AT %d-%d" % (cart[0],cart[1]))
end = True
try:
x = cart[0]
y = cart[1]
print(cart)
if cart[2] == ">":
if plano[(x+1,y)] == "/":
cart[2] = "^"
elif plano[(x+1,y)] == "\\":
cart[2] = "v"
elif plano[(x+1,y)] == "+":
cart[2] = relative_direction(cart[2],cart[3])
cart[3] = nextDirection[cart[3]]
cart[0] += 1
elif cart[2] == "<":
if plano[(x-1,y)] == "/":
cart[2] = "v"
elif plano[(x-1,y)] == "\\":
cart[2] = "^"
elif plano[(x-1,y)] == "+":
cart[2] = relative_direction(cart[2],cart[3])
cart[3] = nextDirection[cart[3]]
cart[0] -= 1
elif cart[2] == "^":
if plano[(x,y-1)] == "/":
cart[2] = ">"
elif plano[(x,y-1)] == "\\":
cart[2] = "<"
elif plano[(x,y-1)] == "+":
cart[2] = relative_direction(cart[2],cart[3])
cart[3] = nextDirection[cart[3]]
cart[1] -= 1
elif cart[2] == "v":
print()
if plano[(x,y+1)] == "/":
cart[2] = "<"
elif plano[(x,y+1)] == "\\":
cart[2] = ">"
elif plano[(x,y+1)] == "+":
cart[2] = relative_direction(cart[2],cart[3])
cart[3] = nextDirection[cart[3]]
cart[1] += 1
except:
breakpoint()
STEP += 1
print_train(plano,carts)
def print_train(plano,carts):
im = Image.new("RGB",(XMAX,YMAX))
for x,y in plano:
if plano[(x,y)] != " ":
im.putpixel((x,y),(255,255,255))
if plano[(x,y)] == "+":
im.putpixel((x,y),(120,120,120))
for cart in carts:
if cart[2] == ">":
im.putpixel((cart[0],cart[1]),(255,0,0))
elif cart[2] == "<":
im.putpixel((cart[0],cart[1]),(0,255,0))
elif cart[2] == "^":
im.putpixel((cart[0],cart[1]),(0,0,255))
else:
im.putpixel((cart[0],cart[1]),(0,120,120))
im.save("train-%d.png" % STEP,"PNG")
if __name__ == "__main__":