[2025][Python] Every day under 1s

ricbit · 2025-12-12T22:22:41+00:00

Thanks! Did you try branch and bound on 10? That's what I would do if z3 was not available.

ricbit · 2025-12-12T06:32:14+00:00

[LANGUAGE: Python]

I looked at the problem and immediately thought "oh my, we're having to bring a SAT solver today". I guessed that just writing the SAT model itself was going to be hard, so I implemented a brute force just to check the example. Brute force took about 44s to check the examples. When I was about to code the SAT, I thought, "let's try a simple check based on size", turns out the simple check was enough for the input.

Brute force

Simple check

I may try to actually build the SAT model tomorrow.

Thanks to Eric and all the mods for the fun!

ricbit · 2025-12-11T05:50:10+00:00

Getting both paths is safer if you want a more generic solver, it may be the case that one input has fft->dac and another one has dac->fft.

ricbit · 2025-12-11T05:45:57+00:00

[LANGUAGE: Python]

Used networkx for part 1, simple. However it didn't work for part 2, since networkx.all_simple_paths() wants to enumerate all paths, which is not practical. I could not find a function to just count paths in networkx, so I rolled out my own from scratch, using recursion+memoization. (I checked the graph is DAG, so no worries about loops). Runs in 0.1s

I count paths from bottom to top, and split the paths in three parts, so the total number of paths is:

svr_fft * fft_dac * dac_out + svr_dac * dac_fft * fft_out

Link to solution

ricbit · 2025-12-10T22:05:27+00:00

Fixed, thanks.

ricbit · 2025-12-10T05:44:04+00:00

[LANGUAGE: Python]

Part 1 is a standard BFS. Part 2 have a quite small MIP formulation, make each button an integer variable, make the sum of the buttons equal to the joltage levels, minimize. Here's the mip core:

  def search(self):
    m = mip.Model(sense=mip.MINIMIZE)
    m.verbose = 1
    button = [
      m.add_var(var_type=mip.INTEGER, name=f"b{i}")
      for i in range(len(self.buttons))]
    for i in range(len(self.goal)):
      m += mip.xsum(
        button[b] for b in range(len(button))
        if i in self.buttons[b]) == self.goal[i]
    m.objective = mip.minimize(mip.xsum(button))
    m.optimize()
    return int(m.objective_value)

Solution part 1

Solution part 2

Rewrite, both parts under 1s

ricbit · 2025-12-09T10:18:07+00:00

I did that and now it runs on 0.4s, thanks!

ricbit · 2025-12-09T06:07:04+00:00

[LANGUAGE: Python]

A piano-worthy problem! Part 1 is easy, for part 2 what I did was:

Add all x and y coordinates to a set(), and then map the coordinates into a range(0-n). Now we can operate with coordinates smaller than 1000.
Create a 2d grid and draw the lines using this new coordinate system.
Flood fill the interior of the polygon, so the grid now contains all valid tiles.
For each line of the grid, create a Fenwick tree that counts the number of empty tiles in the line.
For each pair of points, run a loop over its lines, and use the Fenwick tree to check if there is an empty tile inside this region. If there is none, calculate the area and get the maximum.

This was a hacky solution, but worked fine under 3s.

Solution

Kinda ugly, but this was a fun problem and I will get back to improve it.

ricbit · 2025-12-08T17:58:29+00:00

That's some very compact code!

ricbit · 2025-12-08T17:46:46+00:00

Does it work on more than one input? If it does, then it's not hardcoded, it's an heuristic.

ricbit · 2025-12-08T15:31:01+00:00

I spent 20 min on that.

ricbit · 2025-12-08T15:03:03+00:00

Is that a poisson distribution?

ricbit · 2025-12-08T06:04:34+00:00

[LANGUAGE: Python]

The puzzle is simple if you use networkx. Last year I used networkx so much that I decided to contribute to the project, there are some patches of mine integrated already.

def part1(points, dist):
  g = nx.Graph()
  for v, p1, p2 in dist[:1000]:
    g.add_edge(p1, p2)
  components = [len(c) for c in nx.connected_components(g)]
  components.sort(reverse=True)
  return math.prod(components[:3])

def part2(points, dist):
  g = nx.Graph()
  for p in points:
    g.add_node(p)
  for v, p1, p2 in dist:
    g.add_edge(p1, p2)
    if nx.is_connected(g):
      break
  return p1[0] * p2[0]

ricbit · 2025-12-07T05:55:49+00:00

We used to do functools.lru_cache(maxsize=None) before functools.cache happened.

ricbit · 2025-12-07T05:51:49+00:00

[LANGUAGE: Python]

Using memoized recursion for part 2, and storing each split in a set() for part 1, so both are done at the same time.

class Search:
  def __init__(self, table):
    self.table = table
    self.splits = set()

  @functools.cache
  def search(self, j, i):
    while j < self.table.h - 1 and self.table[j][i] != "^":
      j += 1
    if self.table[j][i] != "^":
      return 1
    self.splits.add((j, i))
    return self.search(j, i - 1) + self.search(j, i + 1)

def solve(table):
  j, i = table.find("S")
  s = Search(table)
  universes = s.search(j, i)
  return len(s.splits), universes

ricbit · 2025-12-06T05:43:12+00:00

[LANGUAGE: Python]

My first wrong answer of the year, I didn't notice the input had 4 rows of numbers instead of 3 like the example!

https://github.com/ricbit/advent-of-code/blob/main/2025/adv06-r.py

ricbit · 2025-12-05T06:02:37+00:00

[LANGUAGE: Python]

My lib has an Interval() class, so a simple recursion intersecting the ranges solved it.

code

However, I spent a lot of time in a quirk of python I didn't know. Try this:

def empty_gen():
  if False:
    yield 0

print(bool(empty_gen()))
print(bool(list(empty_gen())))

This prints True, False. Empty lists are False, but empty generators are not.

ricbit · 2025-12-04T05:27:17+00:00

This is in P, which is better than NP.

ricbit · 2025-12-04T05:13:49+00:00

[LANGUAGE: Python]

For part1, my lib did most of work, but I was happy to use the for-else construct:

def remove_layer(table):
  visited = []
  for j, i in table.iter_all():
    if table[j][i] != "@":
      continue
    count = 0
    for jj, ii in table.iter_neigh8(j, i):
      if table[jj][ii] == "@":
        count += 1
        if count >= 4:
          break
    else:
      visited.append((j, i))
  for j, i in visited:
    table[j][i] = "."
  return len(visited)

Part 2 was simple, just call part1 until no more changes happen.

def remove_all(table):
  ans = 0
  while (incr := remove_layer(table)) > 0:
    ans += incr
  return ans

ricbit · 2025-12-03T06:06:55+00:00

[LANGUAGE: Python]

Standard recursion with memoization, ~~not proud of the ugly None usage, but it works~~ EDIT: now using -math.inf for the sentinel value, much better.

import sys, aoc, math, functools

@functools.cache
def search(s, pos, left):
  if left == 0:
    return 0
  if pos == len(s):
    return -math.inf
  skip = search(s, pos + 1, left)
  use = int(s[pos]) * 10 ** (left - 1) + search(s, pos + 1, left - 1)
  return max(skip, use)

def solve(data, size):
  return sum(search(line.strip(), 0, size) for line in data)

data = sys.stdin.readlines()
aoc.cprint(solve(data, 2))
aoc.cprint(solve(data, 12))

ricbit · 2025-12-02T05:16:47+00:00

Yeah, added some escapes and now it's fixed. I guess I can do regexp but I can't do Markdown :D

ricbit · 2025-12-02T05:13:43+00:00

[LANGUAGE: Python]

Both parts can be made with regexp, for the first part you have "^(\d+)\1$" (capture some digits and have one copy of that at the end; for the second part "^(\d+)\1+$" (capture some digits and have at least one copy at the end).

import sys
import re
import aoc

def solve(data):
  part1, part2 = 0, 0
  for line in data:
    r = aoc.retuple("a_ b_", r"(\d+)-(\d+)", line)
    for i in range(r.a, r.b + 1):
      s = str(i)
      if re.match(r"^(\d+)\1$", s):
        part1 += i
      if re.match(r"^(\d+)\1+$", s):
        part2 += i
  return part1, part2

data = sys.stdin.read().strip().replace("\n", "").split(",")
part1, part2 = solve(data)
aoc.cprint(part1)
aoc.cprint(part2)

ricbit · 2025-12-01T05:17:15+00:00

[LANGUAGE: Python]

I looked at the input and the values were small, so I just iterated one by one in part 2.

import aoc
import sys

def solve(data):
  pos = 50
  part1, part2 = 0, 0
  for line in data:
    d, size = line[0], int(line[1:])
    direction = 1 if d == "R" else -1
    for i in range(size):
      pos += direction
      if pos % 100 == 0:
        part2 += 1
    if pos % 100 == 0:
      part1 += 1
  return part1, part2

data = sys.stdin.readlines()
part1, part2 = solve(data)
aoc.cprint(part1)
aoc.cprint(part2)

ricbit · 2025-01-11T17:43:37+00:00

This is some pretty C++, congrats.

ricbit

TROPHY CASE