the cat: “wake up and feed me instead of strangling me”

After reading multiple papers on stuff like polyomino and coverings etc over the weekend, I sat down to formulate an ILP approach. All the way through I had at the back of my mind “surely he would not expect people to solve something which requires reading research papers, there must be some angle to this which makes it easier”. I don’t think I have ever been more right in my life and I am really glad I made the obvious fail and succeed checks based on areas lol.

import numpy as np
import itertools as it
from pathlib import Path
from time import time

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

def timing(f):
  def wrap(*args, **kw):
    ts = time()
    result = f(*args, **kw)
    te = time()
    print(f"func{f.__name__} args: {args} took: {te-ts:.4f} sec")

    return result
  return wrap

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

  objects = []
  for i in range(6):
    i0 = data.index(f"{i}:")
    obj = np.array(list(map(list, data[i0+1:i0+4])))
    obj[obj=='#']=1
    obj[obj=='.']=0
    objects.append(obj.astype(int))

  i0 = data.index("5:")+5
  placements = []

  for line in data[i0:]:
    dims = list(map(int, line.split(':')[0].split('x')))
    nobjs = list(map(int, line.split(': ')[-1].split(' ')))
    placements.append((dims, nobjs))

  return objects, placements

@timing
def solve_problem(file_name):

  ref_objects, placements = parse_input(Path(cwd, file_name))
  areas = [np.count_nonzero(obj==1) for obj in ref_objects]

  counter_succesful = 0

  for grid_shape, nobjs in placements:
    obj_area = np.sum(np.array(nobjs)*areas)
    grid_area = np.prod(grid_shape)
    worse_area =  np.sum(np.array(nobjs)*9)

    if worse_area<=grid_area:
      counter_succesful += 1
      continue

    if obj_area>grid_area:
      continue

  return counter_succesful

if __name__ == "__main__":

  assert solve_problem("input") == 583

who does? FULU?

Ph’nglui mglw’nafh Cthulhu R’lyeh wgah’nagl fhtagn

lol this is golden

I suspect it mostly relates how much code base there is on internet about the topic. For instance if you make it use a niche library, it is quite common that it makes up methods that don’t exist in that library but exists in related libraries. When I point this out, it also hallucinates saying “It was removed after version bla”. I also may not be using the most cutting edge LLM (mix of freely available and open source ones).

The other day I asked it whether if there is a python library that can do linear algebra over F2, for which it pointed me to the correct direction (Galois) but when I asked it examples of how to do certain stuff it just came up with wrong functions over and over again:

In the end it probably was still faster than google searching this but all of these errors happened one after the other in the span of five minutes, so yeah. If I recall correctly, some of its claims about these namespaces, versions etc were also hallucinated. For instance vstack also does not exist in Galois but it does exist in a very popular package called numpy that can do regular linear algebra (and which this package also uses behind the scenes).

In my case it does hallucinate regularly. It makes up functions that don’t exist in that library but exists in similar libraries. So the end result is useful as a keyword though the code is not. My favourite part is if you point out that the function does not exists the answer is ALWAYS “I am sorry you are right, since version bla of this library this function no longer exists” whereas in reality it had never existed in that library at all. For me the best use case for LLMs is as a search engine and that is because of the shitty state most current search engines are in.

Maybe LLMs can be fine tuned to do the grinding aspects of coding (like boiler plates for test suites etc), with human supervision. But this will many times end up being a situation where junior coders are fired/no longer hired and senior coders are expected to baby sit LLMs to do those jobs. This is not entirely different from supervising junior coders except it is probably more soul destroying. But the biggest flaw in this design is it assumes LLMs one day will be good enough to do senior coding tasks so that when senior coders also retire*, LLMs take their place. If this LLM breakthrough is never realized and this trend of keeping low number of junior coders sticks, we will likey have a programmer crisis in future.

*: I say retire but for many CEOs, it is their wet dream to be able to let go all coders and have LLMs do all the tasks

Yea even a college kid could write a romance novel with a sexy billionaire vampire. Try writing it with this instead:

1a

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

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.

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

Yes I used a polygon library so what… I did eyeball the shape and guessed what the result should have been like but still more pleasing to write something that applies generally. Although I did put an area threshold (eyeballed) which subsets the corners to test, it only reduces run time to about 1/2 (from ~10s to ~5s) so that is not necessarily very critical. If I hadn’t used this library, I would probably do sth along the lines of defining my own rectangle classes with unions, intersections etc so wouldn’t be a more clever approach but much more time consuming.

from pathlib import Path

import numpy as np
import shapely

cwd = Path(__file__).parent

def parse_input(file_path):
  with file_path.open("r") as fp:
    data = list(map(lambda x: list(map(int,x.split(','))), fp.readlines()))

  return np.array(data)


def construct_shapes(coordinates, threshold):

  Itriu = np.triu_indices(coordinates.shape[0], k=2)
  squares = []

  for i0,i1 in zip(*Itriu):

    c0 = tuple(coordinates[i0,:])
    c1 = tuple(coordinates[i1,:])
    area = np.prod(abs(np.array(c0) - np.array(c1)) + np.array([1,1]))

    if area>threshold:
      c2 = (c0[0],c1[1])
      c3 = (c1[0],c0[1])
      squares.append(shapely.Polygon((c0,c3,c1,c2)))

  polygon = shapely.Polygon(coordinates)

  return polygon, squares


def solve_problem(file_name, redgreen=False, threshold=0):

  coordinates = parse_input(Path(cwd, file_name))

  if not redgreen:
    areas = np.prod(abs(coordinates[None,:] - coordinates[:,None]) +\
                    np.array([1,1])[None,None,:], axis=-1)
    max_area = np.max(areas)

  else:
    polygon, squares = construct_shapes(coordinates, threshold)
    max_area = -np.inf

    for inds,square in enumerate(squares):
      if square.area==0:
        continue

      if polygon.contains(square):
        c = np.array(list(zip(*square.exterior.coords.xy)))
        if (a:=np.prod(abs(c[0] - c[2]) + np.array([1,1])))>max_area:
          max_area = a

  return int(max_area)



if __name__ == "__main__":

  assert solve_problem("test_input") == 50
  assert solve_problem("input") == 4763509452
  assert solve_problem("test_input", True, 1) == 24
  assert solve_problem("input", True, 15000*80000) == 1516897893 # threshold by eyeballing the shape

I went here for graphs (to find connected components) and binary search (for efficiency)

#!/usr/bin/env python3
from pathlib import Path

import numpy as np
import networkx as nx

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


def parse_input(file_path):
  with file_path.open("r") as fp:
    coords = list(map(lambda x: list(map(int, x.split(','))), fp.readlines()))

  return np.array(coords)


def binary_search(G, dist):

  Itriu = np.triu_indices(dist.shape[0], k=1)
  dist = dist[Itriu]

  components = list(nx.connected_components(G))
  Isort = [(Itriu[0][i], Itriu[1][i]) for i in np.argsort(dist)]

  icurrent =  0
  ihist = []
  nhist =  []

  while len(ihist)<2 or ihist[-1]!=ihist[-2]:

    ihist.append(icurrent)
    G.add_edges_from(Isort[:icurrent])
    components = list(nx.connected_components(G))
    nhist.append(len(components))

    G.remove_edges_from(Isort[:icurrent])

    if len(components)>1:
      # if >1 component, go between this and closest next index with 1 component
      I = [ind for ind,n in enumerate(nhist) if n==1]

      if len(I)==0:
        inext = len(Isort)
      else:
        inext = min(np.array(ihist)[I])

      icurrent = icurrent + int(np.ceil((inext-icurrent)/2))

    else: 
      # if 1 component, go between nearest previous >1 components and this index
      I = [ind for ind,n in enumerate(nhist) if n>1]

      if len(I)==0:
        iprev = 0
      else:
        iprev = max(np.array(ihist)[I])

      icurrent = iprev + int(np.ceil((icurrent-iprev)/2))

  return Isort[icurrent-1]


def solve_problem(file_name, nconnect):

  coordinates = parse_input(Path(cwd, file_name))
  G = nx.Graph()
  G.add_nodes_from(range(coordinates.shape[0]))

  dist = np.sqrt(np.sum((coordinates[None,:] - coordinates[:,None])**2,
                        axis=-1))

  if nconnect != -1: # part 1
    Itriu = np.triu_indices(dist.shape[0], k=1)
    dist = dist[Itriu]
    Isort = [(Itriu[0][i], Itriu[1][i]) for i in np.argsort(dist)[:nconnect]]

    G.add_edges_from(Isort)
    components = sorted(list(nx.connected_components(G)), key=len)[::-1]

    return np.prod(list(map(len, components[:3])))
  else: # part 2
    indices = binary_search(G, dist)
    return np.prod(coordinates[indices,:],axis=0)[0]


if __name__ == "__main__":

  assert solve_problem("test_input", 10) == 40
  assert solve_problem("input", 1000) == 115885
  assert solve_problem("test_input", -1) == 25272
  assert solve_problem("input", -1) == 274150525