9ms * 35 LOC is ~0.350 tho

Python

0.248 line-seconds (sixth simplest so far after days 6, 2, 1, 4 and 9).

import collections
import re

from .solver import Solver


def _hash(string: str) -> int:
  result = 0
  for c in string:
    result = (result + ord(c)) * 17 % 256
  return result

def _assert_full_match(pattern: str, string: str):
  m = re.fullmatch(pattern, string)
  if not m:
    raise RuntimeError(f'pattern {pattern} does not match {string}')
  return m

class Day15(Solver):
  input: list[str]

  def __init__(self):
    super().__init__(15)

  def presolve(self, input: str):
    self.input = input.rstrip().split(',')

  def solve_first_star(self) -> int:
    return sum(_hash(string) for string in self.input)

  def solve_second_star(self) -> int:
    boxes = [collections.OrderedDict() for _ in range(256)]
    for instruction in self.input:
      label, op, value = _assert_full_match(r'([a-z]+)([=-])(\d*)', instruction).groups()
      box = boxes[_hash(label)]
      match op:
        case '-':
          if label in box:
            del box[label]
        case '=':
          box[label] = value
    return sum((1 + box_idx) * (1 + lens_idx) * int(value)
                for box_idx, box in enumerate(boxes)
                for lens_idx, (_, value) in enumerate(box.items()))

Oh yeah, great idea, thanks!

Python

import numpy as np

from .solver import Solver


def _tilt(row: list[int], reverse: bool = False) -> list[int]:
  res = row[::-1] if reverse else row[:]
  rock_x = 0
  for x, item in enumerate(res):
    if item == 1:
      rock_x = x + 1
    if item == 2:
      if rock_x < x:
        res[rock_x] = 2
        res[x] = 0
      rock_x += 1
  return res[::-1] if reverse else res

class Day14(Solver):
  data: np.ndarray

  def __init__(self):
    super().__init__(14)

  def presolve(self, input: str):
    lines = input.splitlines()
    self.data = np.zeros((len(lines), len(lines[0])), dtype=np.int8)
    for x, line in enumerate(lines):
      for y, char in enumerate(line):
        if char == '#':
          self.data[x, y] = 1
        elif char == 'O':
          self.data[x, y] = 2

  def solve_first_star(self) -> int:
    for y in range(self.data.shape[1]):
      self.data[:, y] = _tilt(self.data[:, y].tolist())
    return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0]))

  def solve_second_star(self) -> int:
    seen = {}
    order = []
    for i in range(1_000_000_000):
      order += [self.data.copy()]
      s = self.data.tobytes()
      if s in seen:
        loop_size = i - seen[s]
        remainder = (1_000_000_000 - i) % loop_size
        self.data = order[seen[s] + remainder]
        break
      seen[s] = i
      for y in range(self.data.shape[1]):
        self.data[:, y] = _tilt(self.data[:, y].tolist())
      for x in range(self.data.shape[0]):
        self.data[x, :] = _tilt(self.data[x, :].tolist())
      for y in range(self.data.shape[1]):
        self.data[:, y] = _tilt(self.data[:, y].tolist(), reverse=True)
      for x in range(self.data.shape[0]):
        self.data[x, :] = _tilt(self.data[x, :].tolist(), reverse=True)
    return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0]))

33.938 line-seconds (ranks 3rd hardest after days 8 and 12 so far).

Lines of code can be arbitrarily reduced, and seconds to solve depends to a large extent on how good my hardware is. So both metrics are useless, and multiplying them makes a useless-squared metric.

I love it!

Here are my stats for the solutions so far (with no optimisation beyond the initial solution):

+-----+-----------+-------+---------------+
| Day | Time (s)  | Lines | line-seconds  |
+-----+-----------+-------+---------------+
|  1  |  0.003    |   35  |   0.098       |
|  2  |  0.001    |   47  |   0.042       |
|  3  |  0.006    |   60  |   0.348       |
|  4  |  0.003    |   41  |   0.115       |
|  5  |  0.077    |   74  |   5.708       |
|  6  |  0.000    |   45  |   0.001       |
|  7  |  0.005    |   87  |   0.395       |
|  8  | 10.175    |   60  | 610.476       |
|  9  |  0.004    |   31  |   0.128       |
| 10  |  0.084    |  103  |   8.634       |
| 11  |  0.240    |   49  |  11.771       |
| 12  |  2.448    |   93  | 227.633       |
| 13  |  0.009    |   83  |   0.707       |
+-----+-----------+-------+---------------+

Python

from .solver import Solver


def is_mirrored_x(pattern: set[tuple[int, int]], max_x: int, max_y: int,
                  x_mirror: int, desired_errors: int = 0) -> bool:
  min_x = max(0, 2 * x_mirror - max_x)
  max_x = min(max_x, 2 * x_mirror)
  errors = 0
  for y in range(max_y):
    for x in range(min_x, x_mirror):
      mirrored = 2 * x_mirror - x - 1
      if (x, y) in pattern and (mirrored, y) not in pattern:
        errors += 1
      if (x, y) not in pattern and (mirrored, y) in pattern:
        errors += 1
      if errors > desired_errors:
        return False
  return errors == desired_errors

def is_mirrored_y(pattern: set[tuple[int, int]], max_x: int, max_y: int,
                  y_mirror: int, desired_errors: int = 0) -> bool:
  min_y = max(0, 2 * y_mirror - max_y)
  max_y = min(max_y, 2 * y_mirror)
  errors = 0
  for x in range(max_x):
    for y in range(min_y, y_mirror):
      mirrored = 2 * y_mirror - y - 1
      if (x, y) in pattern and (x, mirrored) not in pattern:
        errors += 1
      if (x, y) not in pattern and (x, mirrored) in pattern:
        errors += 1
      if errors > desired_errors:
        return False
  return errors == desired_errors

def find_mirror_axis(pattern: set[tuple[int, int]], max_x: int, max_y: int,
                     desired_errors: int = 0) -> tuple[None, int]|tuple[int, None]:
  for possible_x_mirror in range(1, max_x):
    if is_mirrored_x(pattern, max_x, max_y, possible_x_mirror, desired_errors):
      return possible_x_mirror, None
  for possible_y_mirror in range(1, max_y):
    if is_mirrored_y(pattern, max_x, max_y, possible_y_mirror, desired_errors):
      return None, possible_y_mirror
  raise RuntimeError('No mirror axis found')

class Day13(Solver):

  def __init__(self):
    super().__init__(13)
    self.patterns: list[set[tuple[int, int]]] = []
    self.dimensions: list[tuple[int, int]] = []

  def presolve(self, input: str):
    patterns = input.rstrip().split('\n\n')
    for pattern in patterns:
      lines = pattern.splitlines()
      points: set[tuple[int, int]] = set()
      max_x = 0
      max_y = 0
      for y, line in enumerate(lines):
        max_y = max(max_y, y)
        for x, char in enumerate(line):
          max_x = max(max_x, x)
          if char == '#':
            points.add((x, y))
      self.patterns.append(points)
      self.dimensions.append((max_x + 1, max_y + 1))

  def solve_first_star(self) -> int:
    sum = 0
    for pattern, (max_x, max_y) in zip(self.patterns, self.dimensions, strict=True):
      mirror_x, mirror_y = find_mirror_axis(pattern, max_x, max_y)
      sum += (mirror_x or 0) + (mirror_y or 0) * 100
    return sum

  def solve_second_star(self) -> int:
    sum = 0
    for pattern, (max_x, max_y) in zip(self.patterns, self.dimensions, strict=True):
      mirror_x, mirror_y = find_mirror_axis(pattern, max_x, max_y, 1)
      sum += (mirror_x or 0) + (mirror_y or 0) * 100
    return sum

Python

Let me know if you have any questions or feedback!

import dataclasses
import functools

from .solver import Solver


class MatchState:
  pass

@dataclasses.dataclass
class NotMatching(MatchState):
  pass

@dataclasses.dataclass
class Matching(MatchState):
  current_length: int
  desired_length: int

@functools.cache
def _match_one_template(template: str, groups: tuple[int, ...]) -> int:
  if not groups:
    if '#' in template:
      return 0
    else:
      return 1
  state: MatchState = NotMatching()
  remaining_groups: list[int] = list(groups)
  options_in_other_branches: int = 0
  for i in range(len(template)):
    match (state, template[i]):
      case (NotMatching(), '.'):
        pass
      case (NotMatching(), '?'):
        options_in_other_branches += _match_one_template(template[i+1:], tuple(remaining_groups))
        if not remaining_groups:
          return options_in_other_branches
        group, *remaining_groups = remaining_groups
        state = Matching(1, group)
      case (NotMatching(), '#'):
        if not remaining_groups:
          return options_in_other_branches
        group, *remaining_groups = remaining_groups
        state = Matching(1, group)
      case (Matching(current_length, desired_length), '.') if current_length == desired_length:
        state = NotMatching()
      case (Matching(current_length, desired_length), '.') if current_length < desired_length:
        return options_in_other_branches
      case (Matching(current_length, desired_length), '?') if current_length == desired_length:
        state = NotMatching()
      case (Matching(current_length, desired_length), '?') if current_length < desired_length:
        state = Matching(current_length + 1, desired_length)
      case (Matching(current_length, desired_length), '#') if current_length < desired_length:
        state = Matching(current_length + 1, desired_length)
      case (Matching(current_length, desired_length), '#') if current_length == desired_length:
        return options_in_other_branches
      case _:
        raise RuntimeError(f'unexpected {state=} with {template=} position {i} and {remaining_groups=}')
  match state, remaining_groups:
    case NotMatching(), []:
      return options_in_other_branches + 1
    case Matching(current, desired), [] if current == desired:
      return options_in_other_branches + 1
    case (NotMatching(), _) | (Matching(_, _), _):
      return options_in_other_branches
  raise RuntimeError(f'unexpected {state=} with {template=} at end of template and {remaining_groups=}')


def _unfold(template: str, groups: tuple[int, ...]) -> tuple[str, tuple[int, ...]]:
  return '?'.join([template] * 5), groups * 5


class Day12(Solver):

  def __init__(self):
    super().__init__(12)
    self.input: list[tuple[str, tuple[int]]] = []

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    for line in lines:
      template, groups = line.split(' ')
      self.input.append((template, tuple(int(group) for group in groups.split(','))))

  def solve_first_star(self) -> int:
    return sum(_match_one_template(template, groups) for template, groups in self.input)

  def solve_second_star(self) -> int:
    return sum(_match_one_template(*_unfold(template, groups)) for template, groups in self.input)

Python

from .solver import Solver


class Day11(Solver):

  def __init__(self):
    super().__init__(11)
    self.galaxies: list = []
    self.blank_x: set[int] = set()
    self.blank_y: set[int] = set()

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    self.galaxies = []
    max_x = 0
    max_y = 0
    for y, line in enumerate(lines):
      for x, c in enumerate(line):
        if c == '#':
          self.galaxies.append((x, y))
        max_x = max(max_x, x)
      max_y = max(max_y, y)
    self.blank_x = set(range(max_x + 1)) - {x for x, _ in self.galaxies}
    self.blank_y = set(range(max_y + 1)) - {y for _, y in self.galaxies}

  def solve(self, expansion_factor: int) -> int:
    galaxies = list(self.galaxies)
    total = 0
    for i in range(len(galaxies)):
      for j in range(i + 1, len(galaxies)):
        sx, sy = galaxies[i]
        dx, dy = galaxies[j]
        if sx > dx:
          sx, dx = dx, sx
        if sy > dy:
          sy, dy = dy, sy
        dist = sum((dx - sx, dy - sy,
            max(0, expansion_factor - 1) * len([x for x in self.blank_x if sx < x < dx]),
            max(0, expansion_factor - 1) * len([y for y in self.blank_y if sy < y < dy])))
        total += dist
    return total

  def solve_first_star(self):
    return self.solve(2)

  def solve_second_star(self):
    return self.solve(1000000)

Python

from .solver import Solver

_EXITS_MAP = {
  '|': ((0, -1), (0, 1)),
  '-': ((-1, 0), (1, 0)),
  'L': ((1, 0), (0, -1)),
  'J': ((-1, 0), (0, -1)),
  '7': ((-1, 0), (0, 1)),
  'F': ((1, 0), (0, 1)),
  '.': (),
  'S': (),
}

class Day10(Solver):

  def __init__(self):
    super().__init__(10)
    self.maze: dict[tuple[int, int], str] = {}
    self.start: tuple[int, int] = (0, 0)
    self.dists: dict[tuple[int, int], int] = {}

  def _pipe_has_exit(self, x: int, y: int, di: int, dj: int, inverse: bool = False) -> bool:
    if inverse:
      di, dj = -di, -dj
    return (di, dj) in _EXITS_MAP[self.maze[(x, y)]]

  def presolve(self, input: str):
    self.maze: dict[tuple[int, int], str] = {}
    self.start: tuple[int, int] = (0, 0)
    for y, line in enumerate(input.rstrip().split('\n')):
      for x, c in enumerate(line):
        self.maze[(x, y)] = c
        if c == 'S':
          self.start = (x, y)
    next_pos: list[tuple[int, int]] = []
    directions_from_start = []
    for di, dj in ((0, -1), (1, 0), (0, 1), (-1, 0)):
      x, y = self.start[0] + di, self.start[1] + dj
      if (x, y) not in self.maze:
        continue
      if not self._pipe_has_exit(x, y, di, dj, inverse=True):
        continue
      next_pos.append((x, y))
      directions_from_start.append((di, dj))
    self.maze[self.start] = [c for c, dmap in _EXITS_MAP.items()
                              if set(directions_from_start) == set(dmap)][0]
    dists: dict[tuple[int, int], int] = {}
    cur_dist = 0
    while True:
      cur_dist += 1
      new_next_pos = []
      for x, y in next_pos:
        if (x, y) in dists:
          continue
        dists[(x, y)] = cur_dist
        for di, dj in ((0, -1), (1, 0), (0, 1), (-1, 0)):
          nx, ny = x + di, y + dj
          if (nx, ny) not in self.maze:
            continue
          if not self._pipe_has_exit(x, y, di, dj):
            continue
          new_next_pos.append((nx, ny))
      if not new_next_pos:
        break
      next_pos = new_next_pos
    self.dists = dists

  def solve_first_star(self) -> int:
    return max(self.dists.values())

  def solve_second_star(self) -> int:
    area = 0
    for y in range(max(y for _, y in self.dists.keys()) + 1):
      internal = False
      previous_wall = False
      wall_start_symbol = None
      for x in range(max(x for x, _ in self.dists.keys()) + 1):
        is_wall = (x, y) == self.start or (x, y) in self.dists
        wall_continues = is_wall
        pipe_type = self.maze[(x, y)]
        if is_wall and pipe_type == '|':
          internal = not internal
          wall_continues = False
        elif is_wall and not previous_wall and pipe_type in 'FL':
          wall_start_symbol = pipe_type
        elif is_wall and not previous_wall:
          raise RuntimeError(f'expecting wall F or L at {x}, {y}, got {pipe_type}')
        elif is_wall and previous_wall and pipe_type == 'J':
          wall_continues = False
          if wall_start_symbol == 'F':
            internal = not internal
        elif is_wall and previous_wall and pipe_type == '7':
          wall_continues = False
          if wall_start_symbol == 'L':
            internal = not internal
        elif not is_wall and previous_wall:
          raise RuntimeError(f'expecting wall J or 7 at {x}, {y}, got {pipe_type}')
        if internal and not is_wall:
          area += 1
        previous_wall = wall_continues
    return area

Python

from .solver import Solver

class Day09(Solver):

  def __init__(self):
    super().__init__(9)
    self.numbers: list[list[int]] = []

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    self.numbers = [[int(n) for n in line.split(' ')] for line in lines]
    for line in self.numbers:
      stack = [line]
      while not all(x == 0 for x in stack[-1]):
        diff = [stack[-1][i+1] - stack[-1][i] for i in range(len(stack[-1]) - 1)]
        stack.append(diff)
      stack.reverse()
      stack[0].append(0)
      stack[0].insert(0, 0)
      for i in range(1, len(stack)):
        stack[i].append(stack[i-1][-1] + stack[i][-1])
        stack[i].insert(0, stack[i][0] - stack[i-1][0])

  def solve_first_star(self) -> int:
    return sum(line[-1] for line in self.numbers)

  def solve_second_star(self) -> int:
    return sum(line[0] for line in self.numbers)

Python

import itertools
import math
import re

from .solver import Solver

class Day08(Solver):

  def __init__(self):
    super().__init__(8)
    self.instructions: str = ''
    self.nodes: dict[str, tuple[str, str]] = {}

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    self.instructions = lines[0]
    for line in lines[2:]:
      g = re.fullmatch(r'(\w+) = \((\w+), (\w+)\)', line)
      assert g, f"line {line} doesn't match expected format"
      target, left, right = g.groups()
      self.nodes[target] = (left, right)

  def solve_first_star(self) -> int:
    instructions = itertools.cycle(self.instructions)
    cur = 'AAA'
    counter = 0
    while cur != 'ZZZ':
      instruction = next(instructions)
      if instruction == 'L':
        cur = self.nodes[cur][0]
      elif instruction == 'R':
        cur = self.nodes[cur][1]
      else:
        raise RuntimeError(f'Unexpected instruction: {instruction}')
      counter += 1
    return counter

  def solve_second_star(self) -> int:
    start_nodes: list[str] = [node for node in self.nodes if node.endswith('A')]
    end_nodes: set[str] = set(node for node in self.nodes if node.endswith('Z'))
    loop_offsets: dict[str, int] = {}
    loop_sizes: dict[str, int] = {}
    destination_offset_in_loops: dict[str, list[int]] = {}
    for node in start_nodes:
      cur = node
      path: list[tuple[int, str]] = [(0, cur)]
      for instruction_offset, instruction in itertools.cycle(enumerate(self.instructions)):
        next_node = self.nodes[cur][0] if instruction == 'L' else self.nodes[cur][1]
        next_state = ((instruction_offset + 1) % len(self.instructions), next_node)
        if next_state in path:
          loop_offsets[node] = path.index(next_state)
          loop_sizes[node] = len(path) - loop_offsets[node]
          destination_offset_in_loops[node] = [i for i, [_, n] in enumerate(path) if n in end_nodes]
          break
        path.append(next_state)
        cur = next_node
    return math.lcm(*loop_sizes.values())

Python

import collections

from .solver import Solver

_FIVE_OF_A_KIND  = 0x100000
_FOUR_OF_A_KIND  = 0x010000
_FULL_HOUSE      = 0x001000
_THREE_OF_A_KIND = 0x000100
_TWO_PAIR        = 0x000010
_ONE_PAIR        = 0x000001

_CARD_ORDER            = '23456789TJQKA'
_CARD_ORDER_WITH_JOKER = 'J23456789TQKA'

def evaluate_hand(hand: str, joker: bool = False) -> int:
  card_counts = collections.defaultdict(int)
  score = 0
  for card in hand:
    card_counts[card] += 1
  joker_count = 0
  if joker:
    joker_count = card_counts['J']
    del card_counts['J']
  counts = sorted(card_counts.values(), reverse=True)
  top_non_joker_count = counts[0] if counts else 0
  if top_non_joker_count + joker_count == 5:
    score |= _FIVE_OF_A_KIND
  elif top_non_joker_count + joker_count == 4:
    score |= _FOUR_OF_A_KIND
  elif top_non_joker_count + joker_count == 3:
    match counts, joker_count:
      case [3, 2], 0:
        score |= _FULL_HOUSE
      case [3, 1, 1], 0:
        score |= _THREE_OF_A_KIND
      case [2, 2], 1:
        score |= _FULL_HOUSE
      case [2, 1, 1], 1:
        score |= _THREE_OF_A_KIND
      case [1, 1, 1], 2:
        score |= _THREE_OF_A_KIND
      case _:
        raise RuntimeError(f'Unexpected card counts: {counts} with {joker_count} jokers')
  elif top_non_joker_count + joker_count == 2:
    match counts, joker_count:
      case [2, 2, 1], 0:
        score |= _TWO_PAIR
      case [2, 1, 1, 1], 0:
        score |= _ONE_PAIR
      case [1, 1, 1, 1], 1:
        score |= _ONE_PAIR
      case _:
        raise RuntimeError(f'Unexpected card counts: {counts} with {joker_count} jokers')
  card_order = _CARD_ORDER_WITH_JOKER if joker else _CARD_ORDER
  for card in hand:
    card_value = card_order.index(card)
    score <<= 4
    score |= card_value
  return score

class Day07(Solver):

  def __init__(self):
    super().__init__(7)
    self.hands: list[tuple[str, str]] = []

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    self.hands = list(map(lambda line: line.split(' '), lines))

  def solve_first_star(self):
    hands = self.hands[:]
    hands.sort(key=lambda hand: evaluate_hand(hand[0]))
    total_score = 0
    for rank, [_, bid] in enumerate(hands):
      total_score += (rank + 1) * int(bid)
    return total_score

  def solve_second_star(self):
    hands = self.hands[:]
    hands.sort(key=lambda hand: evaluate_hand(hand[0], True))
    total_score = 0
    for rank, [_, bid] in enumerate(hands):
      total_score += (rank + 1) * int(bid)
    return total_score