Avicenna

Based on the star distribution today (everyone who has solved part 1 also solved part2) I suspect at least part 2 is easy even if I can't make a dent on part1 yet

lol the explanation in the link almost sounds like "stupid PR forced us to use a hyped up title for the news but here is what we actually meant"

I did linear algebra with sympy over Q to reduce the search space to nullspace x [-N,N] grid (which is generally <=2 dimensional in these inputs and N<50 seems sufficient in most cases) then made easy work of it with vectorization. Similarly for part 2 did linear algebra over F2 but the search grid is also much smaller [0,1] x nullspace

uh-oh

yea becomes trivial if one uses a polygon library (I did too) but looking at the actual polygon, one can cook up some clever heuristics to do it quite quickly with some basic checks I think.

The graph in my input (and I assume everyone else's too) is DAG so one can use transfer matrices for the first part (after severing connections going out of "out") and the second one topological sorting and just count paths between each node separately and multiply them. First part could be done much easily using the machinery of part2 but I wanted to use my favourite object transfer matrices for the solution. Second part runs in about 0.09 seconds.

from pathlib import Path

import networkx as nx
import numpy as np

cwd = Path(__file__).parent.resolve()


def parse_input(file_path):
  with file_path.open("r") as fp:
    data = list(map(str.strip, fp.readlines()))

  nodes = [y for line in data for y in line.replace(':','').split(' ')]
  M = np.zeros((len(nodes), len(nodes)))

  for line in data:
    from_node = line.split(':')[0]
    to_nodes = line.split(': ')[-1].split(' ')
    I0 = nodes.index(from_node)
    I1 = [nodes.index(n) for n in to_nodes]
    M[I0, I1] = 1

  return M, nodes


def count_paths_between(ind0, ind1, M):
  '''
  counts paths by severing any outgoing connection from node ind1
  and using transfer matrices. Stopping condition is having the
  same positive number of paths for 10 cycles.
  '''

  vec = np.zeros((M.shape[0]))
  vec[ind0] = 1
  nhistory = []
  A = M.T.copy()
  A[:, ind1] = 0
  A[ind1, ind1] = 1
  counter = 0

  while True:
    vec = A@vec
    nhistory.append(vec[ind1])
    counter +=1

    if len(nhistory)>10 and (len(set(nhistory[-10:]))==1 and  nhistory[-1]!=0):
      return nhistory[-1]


def count_paths_dag(G, source, target):

  npaths = {node: 0 for node in G.nodes()}
  npaths[source] = 1

  for node in nx.topological_sort(G):
    for nbr in G.successors(node):
      npaths[nbr] += npaths[node]

  return npaths[target]


def solve_problem1(file_name, path_nodes=None):

  M, nodes = parse_input(Path(cwd, file_name))

  if path_nodes is None:
    npaths = count_paths_between(nodes.index("you"), nodes.index("out"), M)

  else:
    G = nx.from_numpy_array(M, create_using=nx.DiGraph(),
                            nodelist=nodes)

    # assumed G is a DAG, below will raise error if not
    sorted_nodes = list(nx.topological_sort(G))

    sorted_path_nodes = sorted(path_nodes, key=sorted_nodes.index)

    #make sure path nodes are not topoligically equivalent
    for node1, node2 in zip(sorted_path_nodes[:-1], sorted_path_nodes[1:]):
      assert nx.has_path(G, node1, node2)

    npaths = np.prod([count_paths_dag(G, node1, node2) for node1, node2 in
                      zip(sorted_path_nodes[:-1], sorted_path_nodes[1:])])

  return npaths

if __name__ == "__main__":

  assert solve_problem1("test_input1") == 5
  assert solve_problem1("input") == 431

  assert solve_problem1("test_input2", ["svr","dac","fft","out"]) == 2
  assert solve_problem1("input",  ["svr","dac","fft","out"]) == 358458157650450

"Solve your kid problems with this one simple trick"

I mean the lengths that people will go to make kids and then pretend like they don't exist is astonishing. "Lets make a kid and eagerly wait for the day we will send him to a boarding school". I haven't checked if this actually exists but wouldn't be entirely suprised if it did.

Yea yea got it, US geography is all nice and that but I am not trying to visit there until there is zero chance of getting detained by ICE or border control "because of reasons".

I replaced Molotov coctail with a fire cracker and it just didn't come out right. 1/10 wouldn't recommend.

is this where smurfs come from?

In this case, I formulated both questions as a linear algebra question. The first one is over the finite field F2, which I solved by using the library galois and some manual row reduction. The second was over positive integers which is not a field, so I solved it over Q using sympy and then looked for positive integer minimal solutions. In some cases these are under determined, and in some cases exactly solvable systems of the form Ax = b for x where A is the vector made from button switch vectors, b is the light switch pattern vector in the first case or jolts in the second. For under determined ones, your solutions are of the form particular + linear combinations of null space (mod 2 in the first case) so you only search for the minimal one there and in the second you have to search both minimal and positive integer one (because your solution will be over Q and not Z+) in the second case. Wonders of vectorization makes a quick work of these last parts (0.2 second in the first problem about 20s in the second). Also nullspace seems to generally have less than or equal to two dimensions so search space is much smaller than using all the button press vectors.

import itertools as it
from pathlib import Path

import numpy as np
import galois
from sympy import Matrix, symbols, linsolve

cwd = Path(__file__).parent
GF2 = galois.GF(2)

def convert_line(line):

  target = line.split('] ')[0][1:]
  vectors = line.split('] ')[1].split(' ')[:-1]
  jolts = line.split('] ')[1].split(' ')[-1].strip()

  ndims = len(target)

  target = np.array([0 if l=='.' else 1 for l in target], dtype=int)
  jolts = np.array(list(map(int,jolts[1:-1].split(','))))

  M = []

  for v in vectors:
    coords = [int(x) for x in v if x.isnumeric()]
    vec = np.zeros(ndims, dtype=int)
    vec[coords] = 1
    M.append(vec)

  return np.array(M).T,target,jolts


def parse_input(file_path):
  with file_path.open("r") as fp:
    manual = list(map(convert_line, fp.readlines()))

  return manual


def find_pivots(R):
    pivots = []
    m, n = R.shape
    row = 0

    for col in range(n):
      if row < m and R[row, col] == 1:
        pivots.append(col)
        row += 1

    return pivots


def solve_GF2(A, x):

  nullspace = A.null_space()

  M = GF2(np.hstack([np.array(A), np.array(x)[:,None]]))
  R = M.row_reduce()

  pivots = find_pivots(R)

  m, n = R.shape
  n -= 1

  particular = GF2.Zeros(n)

  for r, c in enumerate(pivots):
      particular[c] = R[r, n]

  return np.array(particular), nullspace


def solve_Q(M, x):
  b = symbols(" ".join([f"b{i}" for i in range(M.shape[1])]))
  solution = list(linsolve((M, x), b))[0]
  syms = list(solution.free_symbols)
  func = Matrix(solution)

  particular = np.array(func.subs({s:0 for s in syms}).tolist()).flatten().astype(float)
  nullspace = np.array([np.array(x.tolist()).flatten() for x in M.nullspace()]).astype(float)

  return particular, nullspace


def minimize(nullspace, particular, jolt):

  nvecs = nullspace.shape[0]

  if not jolt:
    coef = np.array(list(it.product(np.arange(0, 2), repeat=nvecs)))
    A = np.sum(np.mod(coef@np.array(nullspace) + particular[None,:],2),axis=-1)
    I = np.argmin(A)
    res = np.mod(coef[I]@np.array(nullspace) + particular[None,:],2)

    return np.sum(res)
  else:
    N = 100
    I = []

    while len(I)==0: # look for a positive integer solution, if does not exist increase N

      coef = np.array(list(it.product(np.arange(-N, N), repeat=nvecs)))
      A = coef@np.array(nullspace) + particular[None,:]
      mask = (A >= 0) & np.isclose(A, A.astype(int))
      I = np.where(mask.all(axis=1))[0]
      N += 500

    return np.min(np.sum(A[I,:],axis=-1))


def solve_problem(file_name, jolt=False):

  manual = parse_input(Path(cwd, file_name))
  sum_press = 0

  for ind,(M, light_target, jolt_target) in enumerate(manual):

    if not jolt:
      #part1 solve over GF2, looks for minimal solution of the form particular + null
      M = GF2(M)
      target = GF2(light_target)
      particular, nullspace = solve_GF2(M, target)

    else:
      #part2 solve over Q, look for minimal integer, positive solution of the form particular + null
      target = Matrix(jolt_target.astype(int))
      M = Matrix(M.astype(int))
      particular, nullspace = solve_Q(M, target)

    sum_press += minimize(nullspace, particular, jolt)

  return sum_press


if __name__ == "__main__":

  assert solve_problem("test_input") == 7
  assert solve_problem("input") == 475
  assert solve_problem("test_input", True) == 33
  assert solve_problem("input", True) == 18273

wish not granted