Advent of Code 2022: no pato edition

import sys

ver, hor = {}, {}

for line in sys.stdin:
  points = list(map(
    lambda x: list(map(int, x.strip().split(','))), line.strip().split('->')
  ))
  for i in range(1, len(points)):
    prev, nxt = points[i - 1], points[i]
    map_to_add = hor if prev[1] == nxt[1] else ver
    idx = 0 if prev[1] == nxt[1] else 1
    map_to_add.setdefault(prev[1 - idx], []).append(
      [min(prev[idx], nxt[idx]), max(prev[idx], nxt[idx])]
    )


sand = (500, 0)
sand_dir = [
  [0, 1],
  [-1, 1],
  [1, 1]
]
max_y = max(k for k in hor)
t = 0
sand_points = set()


def _check_intervals(intvs, ref, lookup):
  for (l, r) in intvs.get(ref, []):
    if l <= lookup <= r:
      return True
  return False


while not sand in sand_points:
  cur = (sand[0], sand[1])
  can_move = True
  while can_move:
    can_move = False
    for vdir in sand_dir:
      nxt = (cur[0] + vdir[0], cur[1] + vdir[1])
      nx, ny = nxt
      if ny == max_y + 2 or nxt in sand_points or \
      _check_intervals(ver, nx, ny) or _check_intervals(hor, ny, nx):
        continue
      can_move = True
      cur = nxt
      break
  sand_points.add(cur)
  t += 1

print(t)

Te dicen que la solución es única, piensa en como sacar ventaja de ese hecho

Si la solución es única significa que está a distancia d + 1 de alguno de los sensores, con d = distancia a la baliza más cercana al sensor en cuestión.

Por qué? Porque si, para cada sensor, la solución estuviera en cualquier casilla con distancia d' > d + 1 entonces cualquier casilla con distancia d + 1 también valdría, por lo que tendríamos más de una solución, y por tanto no sería única, lo que contradice el enunciado

import sys
import re
from itertools import product
from collections import deque
import random


p, g = {}, {}

for line in sys.stdin:
  node, flow_str, neighbor_list = \
    re.match(
      r'Valve (.*) has flow rate=(.*); tunnel(?:s?) lead(?:s?) to valve(?:s?) (.*)',
      line.strip()
    ).groups()
  p[node] = int(flow_str)
  g[node] = list(map(str.strip, neighbor_list.split(',')))

name2index = {k: i for (i, k) in enumerate(p.keys())}
index2name = {i: k for (k, i) in name2index.items()}

dp = {}

def _calc(root, mask, t):
  def _add_mask(msk):
    ret = 0
    for i in range(len(p.keys())):
      if msk & (2 ** i) > 0:
        ret += p[index2name[i]]
    return ret

  if t == 0:
    return 0

  key = (root, mask, t)
  if dp.get(key, -1) == -1:
    now = _add_mask(mask)
    max_rec = 0
    for neighb in g[root]:
      max_rec = max(max_rec, now + _calc(neighb, mask, t - 1))
    dp[key] = max_rec
    if p[root] > 0:
      dp[key] = max(max_rec, now + _calc(root, mask | (2 ** name2index[root]), t - 1))

  return dp[key]


print(_calc('AA', 0, 30))

p0, pv = sum(1 for node in p if p[node] > 0), sum(p.values())
dp2 = {}
ans = 2402

def _calc2(root_a, root_b, mask, t, accm=0):
  global ans
  ans = max(ans, accm)
  print(ans)

  def _add_mask(msk):
    ret = 0
    for i in range(len(p.keys())):
      if msk & (2 ** i) > 0:
        ret += p[index2name[i]]
    return ret


  popcount = sum([1 for i in range(len(p.keys())) if mask & (2 ** i) > 0])



  if t == 0:
    return 0

  if accm + t * pv <= ans:
    return 0

  if popcount == p0:
    cand = accm + t * pv
    ans = max(ans, cand)
    return t * pv

  key = (root_a, root_b, mask, t)

  if dp2.get(key, -1) == -1:
    now = _add_mask(mask)
    dp2[key] = now
    if p[root_a] > 0 and p[root_b] > 0:
      dp2[key] = max(dp2[key], now + _calc2(root_a, root_b, mask | (2 ** name2index[root_a]) | (2 ** name2index[root_b]), t - 1, now + accm))
    if p[root_a] > 0:
      for neighb in g[root_b]:
        dp2[key] = max(dp2[key], now + _calc2(root_a, neighb, mask | (2 ** name2index[root_a]), t - 1, now + accm))
    if p[root_b] > 0:
      for neighb in g[root_a]:
        dp2[key] = max(dp2[key], now + _calc2(neighb, root_b, mask | (2 ** name2index[root_b]), t - 1, now + accm))
    max_rec = 0
    for (na, nb) in product(g[root_a], g[root_b]):
      max_rec = max(max_rec, now + _calc2(na, nb, mask, t - 1, now + accm))
    dp2[key] = max(dp2[key], max_rec)

  return dp2[key]

print(_calc2('AA', 'AA', 0, 26))

• La mayoria nodos tienen 0 de flow
• Si ya has encendido todos los nodos y te quedan t segundos puedes simpemente devolver t * sum(flows)
• Si ya has visitado un estado (nodo, nodos_visitados, segundos_restantes) puedes guardar el resultado en lugar de recalcular
• Si tienes un resultado accumulado "a", te quedan "t" segundos y a + t * sum(flows) < mejor_resultado_encontrado no tiene sentdio seguir buscando ahi

En lugar de ir nodo por nodo, precalcular las distancias entre todas las parejas de nodos y saltar de nodo con flow > 0 a nodo con flow > 0, contar la distancia como minutos para sumar el flow total, de ese modo, en mi test por ejemplo tendriamos que tener en cuenta 15 nodos en lugar de 50

monté un algoritmo de backtracking, pero me daba un resultado 4 unidades menor de lo esperado para el sample. Al final no pude terminarlo porque he tenido un día complicado . A ver si luego me da tiempo a mirarlo un poco mas! Tengo alguna idea en mente sobre lo que podría estar fallando.