2025 day 1, ugly, lazy.

Co-authored-by: Mikael CAPELLE <mikael.capelle@thalesaleniaspace.com>
Co-authored-by: Mikaël Capelle <capelle.mikael@gmail.com>
Reviewed-on: #3

.drone.yml

@@ -0,0 +1,12 @@
+---
+kind: pipeline
+type: docker
+name: default
+
+steps:
+  - name: tests
+    image: python:3.10-slim
+    commands:
+      - pip install poetry
+      - poetry install
+      - poetry run poe lint

.gitignore

@@ -1 +1,7 @@
+# python / VS Code
 venv
+__pycache__
+.ruff_cache
+.vscode
+build
+files

2021/day1.py

@@ -1,14 +0,0 @@
-import sys
-
-lines = sys.stdin.read().splitlines()
-
-values = [int(line) for line in lines]
-
-# part 1
-answer_1 = sum(v2 > v1 for v1, v2 in zip(values[:-1], values[1:]))
-print(f"answer 1 is {answer_1}")
-
-# part 2
-runnings = [sum(values[i : i + 3]) for i in range(len(values) - 2)]
-answer_2 = sum(v2 > v1 for v1, v2 in zip(runnings[:-1], runnings[1:]))
-print(f"answer 2 is {answer_2}")

2021/day10.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day11.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day12.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day13.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day14.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day15.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day16.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day17.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day18.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day19.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day2.py

@@ -1,40 +0,0 @@
-import sys
-from math import prod
-from typing import Literal, cast
-
-lines = sys.stdin.read().splitlines()
-
-commands = [
-    (cast(Literal["forward", "up", "down"], (p := line.split())[0]), int(p[1]))
-    for line in lines
-]
-
-
-def depth_and_position(use_aim: bool):
-    aim, pos, depth = 0, 0, 0
-    for command, value in commands:
-        d_depth = 0
-        match command:
-            case "forward":
-                pos += value
-                depth += value * aim
-            case "up":
-                d_depth = -value
-            case "down":
-                d_depth = value
-
-        if use_aim:
-            aim += d_depth
-        else:
-            depth += value
-
-    return depth, pos
-
-
-# part 1
-answer_1 = prod(depth_and_position(False))
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = prod(depth_and_position(True))
-print(f"answer 2 is {answer_2}")

2021/day20.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day21.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day22.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day23.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day24.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day25.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2021/day3.py

@@ -1,39 +0,0 @@
-import sys
-from collections import Counter
-from typing import Literal
-
-
-def generator_rating(
-    values: list[str], most_common: bool, default: Literal["0", "1"]
-) -> str:
-    index = 0
-    most_common_idx = 0 if most_common else 1
-
-    while len(values) > 1:
-        cnt = Counter(value[index] for value in values)
-        bit = cnt.most_common(2)[most_common_idx][0]
-        if cnt["0"] == cnt["1"]:
-            bit = default
-        values = [value for value in values if value[index] == bit]
-        index += 1
-
-    return values[0]
-
-
-lines = sys.stdin.read().splitlines()
-
-
-# part 1
-most_and_least_common = [
-    tuple(Counter(line[col] for line in lines).most_common(2)[m][0] for m in range(2))
-    for col in range(len(lines[0]))
-]
-gamma_rate = int("".join(most for most, _ in most_and_least_common), base=2)
-epsilon_rate = int("".join(least for _, least in most_and_least_common), base=2)
-print(f"answer 1 is {gamma_rate * epsilon_rate}")
-
-# part 2
-oxygen_generator_rating = int(generator_rating(lines, True, "1"), base=2)
-co2_scrubber_rating = int(generator_rating(lines, False, "0"), base=2)
-answer_2 = oxygen_generator_rating * co2_scrubber_rating
-print(f"answer 2 is {answer_2}")

2021/day4.py

@@ -1,45 +0,0 @@
-import sys
-
-import numpy as np
-
-lines = sys.stdin.read().splitlines()
-
-numbers = [int(c) for c in lines[0].split(",")]
-
-boards = np.asarray(
-    [
-        [[int(c) for c in line.split()] for line in lines[start : start + 5]]
-        for start in range(2, len(lines), 6)
-    ]
-)
-
-# (round, score) for each board (-1 when not found)
-winning_rounds: list[tuple[int, int]] = [(-1, -1) for _ in range(len(boards))]
-marked = np.zeros_like(boards, dtype=bool)
-
-for round, number in enumerate(numbers):
-    # mark boards
-    marked[boards == number] = True
-
-    # check each board for winning
-    for index in range(len(boards)):
-        if winning_rounds[index][0] > 0:
-            continue
-
-        if np.any(np.all(marked[index], axis=0) | np.all(marked[index], axis=1)):
-            winning_rounds[index] = (
-                round,
-                number * int(np.sum(boards[index][~marked[index]])),
-            )
-
-    # all boards are winning - break
-    if np.all(marked.all(axis=1) | marked.all(axis=2)):
-        break
-
-# part 1
-(_, score) = min(winning_rounds, key=lambda w: w[0])
-print(f"answer 1 is {score}")
-
-# part 2
-(_, score) = max(winning_rounds, key=lambda w: w[0])
-print(f"answer 2 is {score}")

2021/day5.py

@@ -1,48 +0,0 @@
-import sys
-
-import numpy as np
-
-lines: list[str] = sys.stdin.read().splitlines()
-
-sections: list[tuple[tuple[int, int], tuple[int, int]]] = [
-    (
-        (
-            int(line.split(" -> ")[0].split(",")[0]),
-            int(line.split(" -> ")[0].split(",")[1]),
-        ),
-        (
-            int(line.split(" -> ")[1].split(",")[0]),
-            int(line.split(" -> ")[1].split(",")[1]),
-        ),
-    )
-    for line in lines
-]
-
-np_sections = np.array(sections).reshape(-1, 4)
-
-x_min, x_max, y_min, y_max = (
-    min(np_sections[:, 0].min(), np_sections[:, 2].min()),
-    max(np_sections[:, 0].max(), np_sections[:, 2].max()),
-    min(np_sections[:, 1].min(), np_sections[:, 3].min()),
-    max(np_sections[:, 1].max(), np_sections[:, 3].max()),
-)
-
-counts_1 = np.zeros((y_max + 1, x_max + 1), dtype=int)
-counts_2 = counts_1.copy()
-
-for (x1, y1), (x2, y2) in sections:
-    x_rng = range(x1, x2 + 1, 1) if x2 >= x1 else range(x1, x2 - 1, -1)
-    y_rng = range(y1, y2 + 1, 1) if y2 >= y1 else range(y1, y2 - 1, -1)
-
-    if x1 == x2 or y1 == y2:
-        counts_1[list(y_rng), list(x_rng)] += 1
-        counts_2[list(y_rng), list(x_rng)] += 1
-    elif abs(x2 - x1) == abs(y2 - y1):
-        for i, j in zip(y_rng, x_rng):
-            counts_2[i, j] += 1
-
-answer_1 = (counts_1 >= 2).sum()
-print(f"answer 1 is {answer_1}")
-
-answer_2 = (counts_2 >= 2).sum()
-print(f"answer 2 is {answer_2}")

2021/day6.py

@@ -1,21 +0,0 @@
-import sys
-
-values = [int(c) for c in sys.stdin.read().strip().split(",")]
-
-days = 256
-lanterns = {day: 0 for day in range(days)}
-for value in values:
-    for day in range(value, days, 7):
-        lanterns[day] += 1
-
-for day in range(days):
-    for day2 in range(day + 9, days, 7):
-        lanterns[day2] += lanterns[day]
-
-# part 1
-answer_1 = sum(v for k, v in lanterns.items() if k < 80) + len(values)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = sum(lanterns.values()) + len(values)
-print(f"answer 2 is {answer_2}")

2021/day7.py

@@ -1,21 +0,0 @@
-import sys
-
-import numpy as np
-
-positions = np.asarray([int(c) for c in sys.stdin.read().strip().split(",")])
-
-min_position, max_position = positions.min(), positions.max()
-
-# part 1
-answer_1 = min(
-    np.sum(np.abs(positions - position))
-    for position in range(min_position, max_position + 1)
-)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = min(
-    np.sum(abs(positions - position) * (abs(positions - position) + 1) // 2)
-    for position in range(min_position, max_position + 1)
-)
-print(f"answer 2 is {answer_2}")

2021/day8.py

@@ -1,87 +0,0 @@
-import itertools
-import os
-import sys
-
-VERBOSE = os.getenv("AOC_VERBOSE") == "True"
-
-digits = {
-    "abcefg": 0,
-    "cf": 1,
-    "acdeg": 2,
-    "acdfg": 3,
-    "bcdf": 4,
-    "abdfg": 5,
-    "abdefg": 6,
-    "acf": 7,
-    "abcdefg": 8,
-    "abcdfg": 9,
-}
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-lengths = {len(k) for k, v in digits.items() if v in (1, 4, 7, 8)}
-answer_1 = sum(
-    len(p) in lengths for line in lines for p in line.split("|")[1].strip().split()
-)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-values: list[int] = []
-
-for line in lines:
-    parts = line.split("|")
-    broken_digits = sorted(parts[0].strip().split(), key=len)
-
-    per_length = {
-        k: list(v)
-        for k, v in itertools.groupby(sorted(broken_digits, key=len), key=len)
-    }
-
-    # a can be found immediately
-    a = next(u for u in per_length[3][0] if u not in per_length[2][0])
-
-    # c and f have only two possible values corresponding to the single entry of
-    # length 2
-    cf = list(per_length[2][0])
-
-    # the only digit of length 4 contains bcdf, so we can deduce bd by removing cf
-    bd = [u for u in per_length[4][0] if u not in cf]
-
-    # the 3 digits of length 5 have a, d and g in common
-    adg = [u for u in per_length[5][0] if all(u in pe for pe in per_length[5][1:])]
-
-    # we can remove a
-    dg = [u for u in adg if u != a]
-
-    # we can deduce d and g
-    d = next(u for u in dg if u in bd)
-    g = next(u for u in dg if u != d)
-
-    # then b
-    b = next(u for u in bd if u != d)
-
-    # f is in the three 6-length digits, while c is only in 2
-    f = next(u for u in cf if all(u in p for p in per_length[6]))
-
-    # c is not f
-    c = next(u for u in cf if u != f)
-
-    # e is the last one
-    e = next(u for u in "abcdefg" if u not in {a, b, c, d, f, g})
-
-    mapping = dict(zip((a, b, c, d, e, f, g), "abcdefg"))
-
-    value = 0
-    for number in parts[1].strip().split():
-        digit = "".join(sorted(mapping[c] for c in number))
-        value = 10 * value + digits[digit]
-
-    if VERBOSE:
-        print(value)
-
-    values.append(value)
-
-
-answer_2 = sum(values)
-print(f"answer 2 is {answer_2}")

2021/day9.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2022/day1.py

@@ -1,7 +0,0 @@
-import sys
-
-blocks = sys.stdin.read().split("\n\n")
-values = sorted(sum(map(int, block.split())) for block in blocks)
-
-print(f"answer 1 is {values[-1]}")
-print(f"answer 2 is {sum(values[-3:])}")

2022/day10.py

@@ -1,38 +0,0 @@
-import sys
-
-lines = sys.stdin.read().splitlines()
-
-cycle = 1
-x = 1
-
-values = {cycle: x}
-
-for line in lines:
-    cycle += 1
-
-    if line == "noop":
-        pass
-    else:
-        r = int(line.split()[1])
-
-        values[cycle] = x
-
-        cycle += 1
-        x += r
-
-    values[cycle] = x
-
-answer_1 = sum(c * values[c] for c in range(20, max(values.keys()) + 1, 40))
-print(f"answer 1 is {answer_1}")
-
-
-for i in range(6):
-    for j in range(40):
-        v = values[1 + i * 40 + j]
-
-        if j >= v - 1 and j <= v + 1:
-            print("#", end="")
-        else:
-            print(".", end="")
-
-    print()

2022/day12.py

@@ -1,160 +0,0 @@
-import heapq
-import sys
-from typing import Callable, Iterator, TypeVar
-
-Node = TypeVar("Node")
-
-
-def dijkstra(
-    start: Node,
-    neighbors: Callable[[Node], Iterator[Node]],
-    cost: Callable[[Node, Node], float],
-) -> tuple[dict[Node, float], dict[Node, Node]]:
-    """
-    Compute shortest paths from one node to all reachable ones.
-
-    Args:
-        start: Starting node.
-        neighbors: Function returning the neighbors of a node.
-        cost: Function to compute the cost of an edge.
-
-    Returns:
-        A tuple (lengths, parents) where lengths is a mapping from Node to distance
-        (from the starting node) and parents a mapping from parents Node (in the
-        shortest path). If keyset of lengths and parents is the same. If a Node is not
-        in the mapping, it cannot be reached from the starting node.
-    """
-
-    queue: list[tuple[float, Node]] = []
-
-    visited: set[Node] = set()
-    lengths: dict[Node, float] = {start: 0}
-    parents: dict[Node, Node] = {}
-
-    heapq.heappush(queue, (0, start))
-
-    while queue:
-        length, current = heapq.heappop(queue)
-
-        if current in visited:
-            continue
-
-        visited.add(current)
-
-        for neighbor in neighbors(current):
-            if neighbor in visited:
-                continue
-
-            neighbor_cost = length + cost(current, neighbor)
-
-            if neighbor_cost < lengths.get(neighbor, float("inf")):
-                lengths[neighbor] = neighbor_cost
-                parents[neighbor] = current
-
-                heapq.heappush(queue, (neighbor_cost, neighbor))
-
-    return lengths, parents
-
-
-def make_path(parents: dict[Node, Node], start: Node, end: Node) -> list[Node] | None:
-    if end not in parents:
-        return None
-
-    path: list[Node] = [end]
-
-    while path[-1] is not start:
-        path.append(parents[path[-1]])
-
-    return list(reversed(path))
-
-
-def print_path(path: list[tuple[int, int]], n_rows: int, n_cols: int) -> None:
-    end = path[-1]
-
-    graph = [["." for _c in range(n_cols)] for _r in range(n_rows)]
-    graph[end[0]][end[1]] = "E"
-
-    for i in range(0, len(path) - 1):
-        cr, cc = path[i]
-        nr, nc = path[i + 1]
-
-        if cr == nr and nc == cc - 1:
-            graph[cr][cc] = "<"
-        elif cr == nr and nc == cc + 1:
-            graph[cr][cc] = ">"
-        elif cr == nr - 1 and nc == cc:
-            graph[cr][cc] = "v"
-        elif cr == nr + 1 and nc == cc:
-            graph[cr][cc] = "^"
-        else:
-            assert False, "{} -> {} infeasible".format(path[i], path[i + 1])
-
-    print("\n".join("".join(row) for row in graph))
-
-
-def neighbors(
-    grid: list[list[int]], node: tuple[int, int], up: bool
-) -> Iterator[tuple[int, int]]:
-    n_rows = len(grid)
-    n_cols = len(grid[0])
-
-    c_row, c_col = node
-    for n_row, n_col in (
-        (c_row - 1, c_col),
-        (c_row + 1, c_col),
-        (c_row, c_col - 1),
-        (c_row, c_col + 1),
-    ):
-        if not (n_row >= 0 and n_row < n_rows and n_col >= 0 and n_col < n_cols):
-            continue
-
-        if up and grid[n_row][n_col] > grid[c_row][c_col] + 1:
-            continue
-        elif not up and grid[n_row][n_col] < grid[c_row][c_col] - 1:
-            continue
-
-        yield n_row, n_col
-
-
-# === main code ===
-
-lines = sys.stdin.read().splitlines()
-
-grid = [[ord(cell) - ord("a") for cell in line] for line in lines]
-
-start: tuple[int, int]
-end: tuple[int, int]
-
-# for part 2
-start_s: list[tuple[int, int]] = []
-
-for i_row, row in enumerate(grid):
-    for i_col, col in enumerate(row):
-        if chr(col + ord("a")) == "S":
-            start = (i_row, i_col)
-            start_s.append(start)
-        elif chr(col + ord("a")) == "E":
-            end = (i_row, i_col)
-        elif col == 0:
-            start_s.append((i_row, i_col))
-
-# fix values
-grid[start[0]][start[1]] = 0
-grid[end[0]][end[1]] = ord("z") - ord("a")
-
-
-lengths_1, parents_1 = dijkstra(
-    start=start, neighbors=lambda n: neighbors(grid, n, True), cost=lambda lhs, rhs: 1
-)
-path_1 = make_path(parents_1, start, end)
-assert path_1 is not None
-
-print_path(path_1, n_rows=len(grid), n_cols=len(grid[0]))
-
-print(f"answer 1 is {lengths_1[end] - 1}")
-
-lengths_2, parents_2 = dijkstra(
-    start=end, neighbors=lambda n: neighbors(grid, n, False), cost=lambda lhs, rhs: 1
-)
-answer_2 = min(lengths_2.get(start, float("inf")) for start in start_s)
-print(f"answer 2 is {answer_2}")

2022/day14.py

@@ -1,140 +0,0 @@
-import sys
-from enum import Enum, auto
-from typing import Callable, cast
-
-
-class Cell(Enum):
-    AIR = auto()
-    ROCK = auto()
-    SAND = auto()
-
-    def __str__(self) -> str:
-        return {Cell.AIR: ".", Cell.ROCK: "#", Cell.SAND: "O"}[self]
-
-
-def print_blocks(blocks: dict[tuple[int, int], Cell]):
-    """
-    Print the given set of blocks on a grid.
-
-    Args:
-        blocks: Set of blocks to print.
-    """
-    x_min, y_min, x_max, y_max = (
-        min(x for x, _ in blocks),
-        0,
-        max(x for x, _ in blocks),
-        max(y for _, y in blocks),
-    )
-
-    for y in range(y_min, y_max + 1):
-        print(
-            "".join(str(blocks.get((x, y), Cell.AIR)) for x in range(x_min, x_max + 1))
-        )
-
-
-def flow(
-    blocks: dict[tuple[int, int], Cell],
-    stop_fn: Callable[[int, int], bool],
-    fill_fn: Callable[[int, int], Cell],
-) -> dict[tuple[int, int], Cell]:
-    """
-    Flow sands onto the given set of blocks
-
-    Args:
-        blocks: Blocks containing ROCK position. Modified in-place.
-        stop_fn: Function called with the last (assumed) position of a grain of
-            sand BEFORE adding it to blocks. If the function returns True, the grain
-            is added and a new one is flowed, otherwise, the whole procedure stops
-            and the function returns (without adding the final grain).
-        fill_fn: Function called when the target position of a grain (during the
-            flowing process) is missing from blocks.
-
-    Returns:
-        The input blocks.
-    """
-
-    y_max = max(y for _, y in blocks)
-
-    while True:
-        x, y = 500, 0
-
-        while y <= y_max:
-            moved = False
-            for cx, cy in ((x, y + 1), (x - 1, y + 1), (x + 1, y + 1)):
-                if (cx, cy) not in blocks and fill_fn(cx, cy) == Cell.AIR:
-                    x, y = cx, cy
-                    moved = True
-                elif blocks[cx, cy] == Cell.AIR:
-                    x, y = cx, cy
-                    moved = True
-
-                if moved:
-                    break
-
-            if not moved:
-                break
-
-        if stop_fn(x, y):
-            break
-
-        blocks[x, y] = Cell.SAND
-
-    return blocks
-
-
-# === inputs ===
-
-lines = sys.stdin.read().splitlines()
-
-paths: list[list[tuple[int, int]]] = []
-for line in lines:
-    parts = line.split(" -> ")
-    paths.append(
-        [
-            cast(tuple[int, int], tuple(int(c.strip()) for c in part.split(",")))
-            for part in parts
-        ]
-    )
-
-
-blocks: dict[tuple[int, int], Cell] = {}
-for path in paths:
-    for start, end in zip(path[:-1], path[1:]):
-        x_start = min(start[0], end[0])
-        x_end = max(start[0], end[0]) + 1
-        y_start = min(start[1], end[1])
-        y_end = max(start[1], end[1]) + 1
-
-        for x in range(x_start, x_end):
-            for y in range(y_start, y_end):
-                blocks[x, y] = Cell.ROCK
-
-print_blocks(blocks)
-print()
-
-x_min, y_min, x_max, y_max = (
-    min(x for x, _ in blocks),
-    0,
-    max(x for x, _ in blocks),
-    max(y for _, y in blocks),
-)
-
-# === part 1 ===
-
-blocks_1 = flow(
-    blocks.copy(), stop_fn=lambda x, y: y > y_max, fill_fn=lambda x, y: Cell.AIR
-)
-print_blocks(blocks_1)
-print(f"answer 1 is {sum(v == Cell.SAND for v in blocks_1.values())}")
-print()
-
-# === part 2 ===
-
-blocks_2 = flow(
-    blocks.copy(),
-    stop_fn=lambda x, y: x == 500 and y == 0,
-    fill_fn=lambda x, y: Cell.AIR if y < y_max + 2 else Cell.ROCK,
-)
-blocks_2[500, 0] = Cell.SAND
-print_blocks(blocks_2)
-print(f"answer 2 is {sum(v == Cell.SAND for v in blocks_2.values())}")

2022/day15.py

@@ -1,87 +0,0 @@
-import sys
-
-import numpy as np
-import parse
-
-
-def part1(sensor_to_beacon: dict[tuple[int, int], tuple[int, int]], row: int) -> int:
-    no_beacons_row_l: list[np.ndarray] = []
-
-    for (sx, sy), (bx, by) in sensor_to_beacon.items():
-        d = abs(sx - bx) + abs(sy - by)  # closest
-
-        no_beacons_row_l.append(sx - np.arange(0, d - abs(sy - row) + 1))
-        no_beacons_row_l.append(sx + np.arange(0, d - abs(sy - row) + 1))
-
-    beacons_at_row = set(bx for (bx, by) in sensor_to_beacon.values() if by == row)
-    no_beacons_row = set(np.concatenate(no_beacons_row_l)).difference(beacons_at_row)
-
-    return len(no_beacons_row)
-
-
-def part2_intervals(
-    sensor_to_beacon: dict[tuple[int, int], tuple[int, int]], xy_max: int
-) -> tuple[int, int, int]:
-    from tqdm import trange
-
-    for y in trange(xy_max + 1):
-        its: list[tuple[int, int]] = []
-        for (sx, sy), (bx, by) in sensor_to_beacon.items():
-            d = abs(sx - bx) + abs(sy - by)
-            dx = d - abs(sy - y)
-
-            if dx >= 0:
-                its.append((max(0, sx - dx), min(sx + dx, xy_max)))
-
-        its = sorted(its)
-        _, e = its[0]
-
-        for si, ei in its[1:]:
-            if si > e + 1:
-                return si - 1, y, 4_000_000 * (si - 1) + y
-            if ei > e:
-                e = ei
-
-    return (0, 0, 0)
-
-
-def part2_cplex(
-    sensor_to_beacon: dict[tuple[int, int], tuple[int, int]], xy_max: int
-) -> tuple[int, int, int]:
-    from docplex.mp.model import Model
-
-    m = Model()
-
-    x, y = m.continuous_var_list(2, ub=xy_max, name=["x", "y"])
-
-    for (sx, sy), (bx, by) in sensor_to_beacon.items():
-        d = abs(sx - bx) + abs(sy - by)
-        m.add_constraint(m.abs(x - sx) + m.abs(y - sy) >= d + 1, ctname=f"ct_{sx}_{sy}")
-
-    m.set_objective("min", x + y)
-
-    s = m.solve()
-
-    vx = int(s.get_value(x))
-    vy = int(s.get_value(y))
-    return vx, vy, 4_000_000 * vx + vy
-
-
-lines = sys.stdin.read().splitlines()
-
-sensor_to_beacon: dict[tuple[int, int], tuple[int, int]] = {}
-
-for line in lines:
-    r = parse.parse(
-        "Sensor at x={sx}, y={sy}: closest beacon is at x={bx}, y={by}", line
-    )
-    sensor_to_beacon[int(r["sx"]), int(r["sy"])] = (int(r["bx"]), int(r["by"]))
-
-xy_max = 4_000_000 if max(sensor_to_beacon) > (1_000, 0) else 20
-row = 2_000_000 if max(sensor_to_beacon) > (1_000, 0) else 10
-
-print(f"answer 1 is {part1(sensor_to_beacon, row)}")
-
-# x, y, a2 = part2_cplex(sensor_to_beacon, xy_max)
-x, y, a2 = part2_intervals(sensor_to_beacon, xy_max)
-print(f"answer 2 is {a2} (x={x}, y={y})")

2022/day16.py

@@ -1,158 +0,0 @@
-from __future__ import annotations
-
-import heapq
-import itertools
-import re
-import sys
-from collections import defaultdict
-from typing import FrozenSet, NamedTuple
-
-from tqdm import tqdm
-
-
-class Pipe(NamedTuple):
-    name: str
-    flow: int
-    tunnels: list[str]
-
-    def __lt__(self, other: object) -> bool:
-        return isinstance(other, Pipe) and other.name < self.name
-
-    def __eq__(self, other: object) -> bool:
-        return isinstance(other, Pipe) and other.name == self.name
-
-    def __hash__(self) -> int:
-        return hash(self.name)
-
-    def __str__(self) -> str:
-        return self.name
-
-    def __repr__(self) -> str:
-        return self.name
-
-
-def breadth_first_search(pipes: dict[str, Pipe], pipe: Pipe) -> dict[Pipe, int]:
-    """
-    Runs a BFS from the given pipe and return the shortest distance (in term of hops)
-    to all other pipes.
-    """
-    queue = [(0, pipe_1)]
-    visited = set()
-    distances: dict[Pipe, int] = {}
-
-    while len(distances) < len(pipes):
-        distance, current = heapq.heappop(queue)
-
-        if current in visited:
-            continue
-
-        visited.add(current)
-        distances[current] = distance
-
-        for tunnel in current.tunnels:
-            heapq.heappush(queue, (distance + 1, pipes[tunnel]))
-
-    return distances
-
-
-def update_with_better(
-    node_at_times: dict[FrozenSet[Pipe], int], flow: int, flowing: FrozenSet[Pipe]
-) -> None:
-    node_at_times[flowing] = max(node_at_times[flowing], flow)
-
-
-def part_1(
-    start_pipe: Pipe,
-    max_time: int,
-    distances: dict[tuple[Pipe, Pipe], int],
-    relevant_pipes: FrozenSet[Pipe],
-):
-    node_at_times: dict[int, dict[Pipe, dict[FrozenSet[Pipe], int]]] = defaultdict(
-        lambda: defaultdict(lambda: defaultdict(lambda: 0))
-    )
-    node_at_times[0] = {start_pipe: {frozenset(): 0}}
-
-    for time in range(max_time):
-        for c_pipe, nodes in node_at_times[time].items():
-            for flowing, flow in nodes.items():
-                for target in relevant_pipes:
-                    distance = distances[c_pipe, target] + 1
-                    if time + distance >= max_time or target in flowing:
-                        continue
-
-                    update_with_better(
-                        node_at_times[time + distance][target],
-                        flow + sum(pipe.flow for pipe in flowing) * distance,
-                        flowing | {target},
-                    )
-
-                update_with_better(
-                    node_at_times[max_time][c_pipe],
-                    flow + sum(pipe.flow for pipe in flowing) * (max_time - time),
-                    flowing,
-                )
-
-    return max(
-        flow
-        for nodes_of_pipe in node_at_times[max_time].values()
-        for flow in nodes_of_pipe.values()
-    )
-
-
-def part_2(
-    start_pipe: Pipe,
-    max_time: int,
-    distances: dict[tuple[Pipe, Pipe], int],
-    relevant_pipes: FrozenSet[Pipe],
-):
-    def compute(pipes_for_me: FrozenSet[Pipe]) -> int:
-        return part_1(start_pipe, max_time, distances, pipes_for_me) + part_1(
-            start_pipe, max_time, distances, relevant_pipes - pipes_for_me
-        )
-
-    combs = [
-        frozenset(relevant_pipes_1)
-        for r in range(2, len(relevant_pipes) // 2 + 1)
-        for relevant_pipes_1 in itertools.combinations(relevant_pipes, r)
-    ]
-
-    return max(compute(comb) for comb in tqdm(combs))
-
-
-# === MAIN ===
-
-
-lines = sys.stdin.read().splitlines()
-
-
-pipes: dict[str, Pipe] = {}
-for line in lines:
-    r = re.match(
-        R"Valve ([A-Z]+) has flow rate=([0-9]+); tunnels? leads? to valves? (.+)",
-        line,
-    )
-    assert r
-
-    g = r.groups()
-
-    pipes[g[0]] = Pipe(g[0], int(g[1]), g[2].split(", "))
-
-# compute distances from one valve to any other
-distances: dict[tuple[Pipe, Pipe], int] = {}
-for pipe_1 in pipes.values():
-    distances.update(
-        {
-            (pipe_1, pipe_2): distance
-            for pipe_2, distance in breadth_first_search(pipes, pipe_1).items()
-        }
-    )
-
-# valves with flow
-relevant_pipes = frozenset(pipe for pipe in pipes.values() if pipe.flow > 0)
-
-
-# 1651, 1653
-print(part_1(pipes["AA"], 30, distances, relevant_pipes))
-
-# 1707, 2223
-print(part_2(pipes["AA"], 26, distances, relevant_pipes))

2022/day18.py

@@ -1,51 +0,0 @@
-import sys
-from typing import FrozenSet
-
-import numpy as np
-
-xyz = np.asarray(
-    [
-        tuple(int(x) for x in row.split(","))  # type: ignore
-        for row in sys.stdin.read().splitlines()
-    ]
-)
-
-xyz = xyz - xyz.min(axis=0) + 1
-
-cubes = np.zeros(xyz.max(axis=0) + 3, dtype=bool)
-cubes[xyz[:, 0], xyz[:, 1], xyz[:, 2]] = True
-
-n_dims = len(cubes.shape)
-
-faces = [(-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1)]
-
-answer_1 = sum(
-    1 for x, y, z in xyz for dx, dy, dz in faces if not cubes[x + dx, y + dy, z + dz]
-)
-print(f"answer 1 is {answer_1}")
-
-visited = np.zeros_like(cubes, dtype=bool)
-queue = [(0, 0, 0)]
-
-n_faces = 0
-while queue:
-    x, y, z = queue.pop(0)
-
-    if visited[x, y, z]:
-        continue
-
-    visited[x, y, z] = True
-
-    for dx, dy, dz in faces:
-        nx, ny, nz = x + dx, y + dy, z + dz
-        if not all(n >= 0 and n < cubes.shape[i] for i, n in enumerate((nx, ny, nz))):
-            continue
-
-        if visited[nx, ny, nz]:
-            continue
-
-        if cubes[nx, ny, nz]:
-            n_faces += 1
-        else:
-            queue.append((nx, ny, nz))
-print(f"answer 2 is {n_faces}")

2022/day22.py

@@ -1,223 +0,0 @@
-import re
-import sys
-from typing import Callable
-
-import numpy as np
-
-VOID, EMPTY, WALL = 0, 1, 2
-TILE_FROM_CHAR = {" ": VOID, ".": EMPTY, "#": WALL}
-
-SCORES = {"E": 0, "S": 1, "W": 2, "N": 3}
-
-
-board_map_s, direction_s = sys.stdin.read().split("\n\n")
-
-# board
-board_lines = board_map_s.splitlines()
-max_line = max(len(line) for line in board_lines)
-board = np.array(
-    [
-        [TILE_FROM_CHAR[c] for c in row] + [VOID] * (max_line - len(row))
-        for row in board_map_s.splitlines()
-    ]
-)
-
-directions = [
-    int(p1) if p2 else p1 for p1, p2 in re.findall(R"(([0-9])+|L|R)", direction_s)
-]
-
-
-# find on each row and column the first and last non-void
-row_first_non_void = np.argmax(board != VOID, axis=1)
-row_last_non_void = board.shape[1] - np.argmax(board[:, ::-1] != VOID, axis=1) - 1
-col_first_non_void = np.argmax(board != VOID, axis=0)
-col_last_non_void = board.shape[0] - np.argmax(board[::-1, :] != VOID, axis=0) - 1
-
-
-faces = np.zeros_like(board)
-size = np.gcd(board.shape[0], board.shape[1])
-for row in range(0, board.shape[0], size):
-    for col in range(row_first_non_void[row], row_last_non_void[row], size):
-        faces[row : row + size, col : col + size] = faces.max() + 1
-
-SIZE = np.gcd(*board.shape)
-
-# TODO: deduce this from the actual cube...
-faces_wrap: dict[int, dict[str, Callable[[int, int], tuple[int, int, str]]]]
-
-if board.shape == (12, 16):  # example
-    faces_wrap = {
-        1: {
-            "W": lambda y, x: (4, 4 + y, "S"),  # 3N
-            "N": lambda y, x: (4, 11 - x, "S"),  # 2N
-            "E": lambda y, x: (11 - y, 15, "W"),  # 6E
-        },
-        2: {
-            "W": lambda y, x: (11, 19 - y, "N"),  # 6S
-            "N": lambda y, x: (0, 11 - y, "S"),  # 1N
-            "S": lambda y, x: (11, 11 - x, "N"),  # 5S
-        },
-        3: {
-            "N": lambda y, x: (x - 4, 8, "E"),  # 1W
-            "S": lambda y, x: (15 - x, 8, "E"),  # 5W
-        },
-        4: {"E": lambda y, x: (8, 19 - y, "S")},  # 6N
-        5: {
-            "W": lambda y, x: (7, 15 - y, "N"),  # 3S
-            "S": lambda y, x: (7, 11 - x, "N"),  # 2S
-        },
-        6: {
-            "N": lambda y, x: (19 - x, 11, "W"),  # 4E
-            "E": lambda y, x: (11 - y, 11, "W"),  # 1E
-            "S": lambda y, x: (19 - x, 0, "E"),  # 2W
-        },
-    }
-
-else:
-    faces_wrap = {
-        1: {
-            "W": lambda y, x: (3 * SIZE - y - 1, 0, "E"),  # 4W
-            "N": lambda y, x: (2 * SIZE + x, 0, "E"),  # 6W
-        },
-        2: {
-            "N": lambda y, x: (4 * SIZE - 1, x - 2 * SIZE, "N"),  # 6S
-            "E": lambda y, x: (3 * SIZE - y - 1, 2 * SIZE - 1, "W"),  # 5E
-            "S": lambda y, x: (x - SIZE, 2 * SIZE - 1, "W"),  # 3E
-        },
-        3: {
-            "W": lambda y, x: (2 * SIZE, y - SIZE, "S"),  # 4N
-            "E": lambda y, x: (SIZE - 1, SIZE + y, "N"),  # 2S
-        },
-        4: {
-            "W": lambda y, x: (3 * SIZE - y - 1, SIZE, "E"),  # 1W
-            "N": lambda y, x: (SIZE + x, SIZE, "E"),  # 3W
-        },
-        5: {
-            "E": lambda y, x: (3 * SIZE - y - 1, 3 * SIZE - 1, "W"),  # 2E
-            "S": lambda y, x: (2 * SIZE + x, SIZE - 1, "W"),  # 6E
-        },
-        6: {
-            "W": lambda y, x: (0, y - 2 * SIZE, "S"),  # 1N
-            "E": lambda y, x: (3 * SIZE - 1, y - 2 * SIZE, "N"),  # 5S
-            "S": lambda y, x: (0, x + 2 * SIZE, "S"),  # 2N
-        },
-    }
-
-
-def wrap_part_1(y0: int, x0: int, r0: str) -> tuple[int, int, str]:
-    if r0 == "E":
-        return y0, row_first_non_void[y0], r0
-    elif r0 == "S":
-        return col_first_non_void[x0], x0, r0
-    elif r0 == "W":
-        return y0, row_last_non_void[y0], r0
-    elif r0 == "N":
-        return col_last_non_void[x0], x0, r0
-
-    assert False
-
-
-def wrap_part_2(y0: int, x0: int, r0: str) -> tuple[int, int, str]:
-    cube = faces[y0, x0]
-    assert r0 in faces_wrap[cube]
-    return faces_wrap[cube][r0](y0, x0)
-
-
-def run(wrap: Callable[[int, int, str], tuple[int, int, str]]) -> tuple[int, int, str]:
-    y0 = 0
-    x0 = np.where(board[0] == EMPTY)[0][0]
-    r0 = "E"
-
-    for direction in directions:
-        if isinstance(direction, int):
-            while direction > 0:
-                if r0 == "E":
-                    xi = np.where(board[y0, x0 + 1 : x0 + direction + 1] == WALL)[0]
-                    if len(xi):
-                        x0 = x0 + xi[0]
-                        direction = 0
-                    elif (
-                        x0 + direction < board.shape[1]
-                        and board[y0, x0 + direction] == EMPTY
-                    ):
-                        x0 = x0 + direction
-                        direction = 0
-                    else:
-                        y0_t, x0_t, r0_t = wrap(y0, x0, r0)
-                        if board[y0_t, x0_t] == WALL:
-                            x0 = row_last_non_void[y0]
-                            direction = 0
-                        else:
-                            direction = direction - (row_last_non_void[y0] - x0) - 1
-                            y0, x0, r0 = y0_t, x0_t, r0_t
-                elif r0 == "S":
-                    yi = np.where(board[y0 + 1 : y0 + direction + 1, x0] == WALL)[0]
-                    if len(yi):
-                        y0 = y0 + yi[0]
-                        direction = 0
-                    elif (
-                        y0 + direction < board.shape[0]
-                        and board[y0 + direction, x0] == EMPTY
-                    ):
-                        y0 = y0 + direction
-                        direction = 0
-                    else:
-                        y0_t, x0_t, r0_t = wrap(y0, x0, r0)
-                        if board[y0_t, x0_t] == WALL:
-                            y0 = col_last_non_void[x0]
-                            direction = 0
-                        else:
-                            direction = direction - (col_last_non_void[x0] - y0) - 1
-                            y0, x0, r0 = y0_t, x0_t, r0_t
-                elif r0 == "W":
-                    left = max(x0 - direction - 1, 0)
-                    xi = np.where(board[y0, left:x0] == WALL)[0]
-                    if len(xi):
-                        x0 = left + xi[-1] + 1
-                        direction = 0
-                    elif x0 - direction >= 0 and board[y0, x0 - direction] == EMPTY:
-                        x0 = x0 - direction
-                        direction = 0
-                    else:
-                        y0_t, x0_t, r0_t = wrap(y0, x0, r0)
-                        if board[y0_t, x0_t] == WALL:
-                            x0 = row_first_non_void[y0]
-                            direction = 0
-                        else:
-                            direction = direction - (x0 - row_first_non_void[y0]) - 1
-                            y0, x0, r0 = y0_t, x0_t, r0_t
-                elif r0 == "N":
-                    top = max(y0 - direction - 1, 0)
-                    yi = np.where(board[top:y0, x0] == WALL)[0]
-                    if len(yi):
-                        y0 = top + yi[-1] + 1
-                        direction = 0
-                    elif y0 - direction >= 0 and board[y0 - direction, x0] == EMPTY:
-                        y0 = y0 - direction
-                        direction = 0
-                    else:
-                        y0_t, x0_t, r0_t = wrap(y0, x0, r0)
-                        if board[y0_t, x0_t] == WALL:
-                            y0 = col_first_non_void[x0]
-                            direction = 0
-                        else:
-                            direction = direction - (y0 - col_first_non_void[x0]) - 1
-                            y0, x0, r0 = y0_t, x0_t, r0_t
-        else:
-            r0 = {
-                "E": {"L": "N", "R": "S"},
-                "N": {"L": "W", "R": "E"},
-                "W": {"L": "S", "R": "N"},
-                "S": {"L": "E", "R": "W"},
-            }[r0][direction]
-
-    return y0, x0, r0
-
-
-y1, x1, r1 = run(wrap_part_1)
-answer_1 = 1000 * (1 + y1) + 4 * (1 + x1) + SCORES[r1]
-print(f"answer 1 is {answer_1}")
-
-y2, x2, r2 = run(wrap_part_2)
-answer_2 = 1000 * (1 + y2) + 4 * (1 + x2) + SCORES[r2]
-print(f"answer 2 is {answer_2}")

2022/day24.py

@@ -1,98 +0,0 @@
-import heapq
-import math
-import sys
-from collections import defaultdict
-
-lines = sys.stdin.read().splitlines()
-
-winds = {
-    (i - 1, j - 1, lines[i][j])
-    for i in range(1, len(lines) - 1)
-    for j in range(1, len(lines[i]) - 1)
-    if lines[i][j] != "."
-}
-
-n_rows, n_cols = len(lines) - 2, len(lines[0]) - 2
-CYCLE = math.lcm(n_rows, n_cols)
-
-east_winds = [{j for j in range(n_cols) if (i, j, ">") in winds} for i in range(n_rows)]
-west_winds = [{j for j in range(n_cols) if (i, j, "<") in winds} for i in range(n_rows)]
-north_winds = [
-    {i for i in range(n_rows) if (i, j, "^") in winds} for j in range(n_cols)
-]
-south_winds = [
-    {i for i in range(n_rows) if (i, j, "v") in winds} for j in range(n_cols)
-]
-
-
-def run(start: tuple[int, int], start_cycle: int, end: tuple[int, int]):
-    def heuristic(y: int, x: int) -> int:
-        return abs(end[0] - y) + abs(end[1] - x)
-
-    # (distance + heuristic, distance, (start_pos, cycle))
-    queue = [(heuristic(start[0], start[1]), 0, ((start[0], start[1]), start_cycle))]
-    visited: set[tuple[tuple[int, int], int]] = set()
-    distances: dict[tuple[int, int], dict[int, int]] = defaultdict(lambda: {})
-
-    while queue:
-        _, distance, ((y, x), cycle) = heapq.heappop(queue)
-
-        if ((y, x), cycle) in visited:
-            continue
-
-        distances[y, x][cycle] = distance
-
-        visited.add(((y, x), cycle))
-
-        if (y, x) == (end[0], end[1]):
-            break
-
-        for dy, dx in (0, 0), (-1, 0), (1, 0), (0, -1), (0, 1):
-            ty = y + dy
-            tx = x + dx
-
-            n_cycle = (cycle + 1) % CYCLE
-
-            if (ty, tx) == end:
-                heapq.heappush(queue, (distance + 1, distance + 1, ((ty, tx), n_cycle)))
-                break
-
-            if ((ty, tx), n_cycle) in visited:
-                continue
-
-            if (ty, tx) != start and (ty < 0 or tx < 0 or ty >= n_rows or tx >= n_cols):
-                continue
-
-            if (ty, tx) != start:
-                if (ty - n_cycle) % n_rows in south_winds[tx]:
-                    continue
-                if (ty + n_cycle) % n_rows in north_winds[tx]:
-                    continue
-                if (tx + n_cycle) % n_cols in west_winds[ty]:
-                    continue
-                if (tx - n_cycle) % n_cols in east_winds[ty]:
-                    continue
-
-            heapq.heappush(
-                queue,
-                ((heuristic(ty, tx) + distance + 1, distance + 1, ((ty, tx), n_cycle))),
-            )
-
-    return distances, next(iter(distances[end].values()))
-
-
-start = (
-    -1,
-    next(j for j in range(1, len(lines[0]) - 1) if lines[0][j] == ".") - 1,
-)
-end = (
-    n_rows,
-    next(j for j in range(1, len(lines[-1]) - 1) if lines[-1][j] == ".") - 1,
-)
-
-distances_1, forward_1 = run(start, 0, end)
-print(f"answer 1 is {forward_1}")
-
-distances_2, return_1 = run(end, next(iter(distances_1[end].keys())), start)
-distances_3, forward_2 = run(start, next(iter(distances_2[start].keys())), end)
-print(f"answer 2 is {forward_1 + return_1 + forward_2}")

2022/day25.py

@@ -1,27 +0,0 @@
-import sys
-
-lines = sys.stdin.read().splitlines()
-
-coeffs = {"2": 2, "1": 1, "0": 0, "-": -1, "=": -2}
-
-
-def snafu2number(number: str) -> int:
-    value = 0
-    for c in number:
-        value *= 5
-        value += coeffs[c]
-    return value
-
-
-def number2snafu(number: int) -> str:
-    values = ["0", "1", "2", "=", "-"]
-    res = ""
-    while number > 0:
-        mod = number % 5
-        res = res + values[mod]
-        number = number // 5 + int(mod >= 3)
-    return "".join(reversed(res))
-
-
-answer_1 = number2snafu(sum(map(snafu2number, lines)))
-print(f"answer 1 is {answer_1}")

2022/day3.py

@@ -1,23 +0,0 @@
-import string
-import sys
-
-lines = [line.strip() for line in sys.stdin.readlines()]
-
-# extract content of each part
-parts = [(set(line[: len(line) // 2]), set(line[len(line) // 2 :])) for line in lines]
-
-# priorities
-priorities = {c: i + 1 for i, c in enumerate(string.ascii_letters)}
-
-# part 1
-part1 = sum(priorities[c] for p1, p2 in parts for c in p1.intersection(p2))
-print(f"answer 1 is {part1}")
-
-# part 2
-n_per_group = 3
-part2 = sum(
-    priorities[c]
-    for i in range(0, len(lines), n_per_group)
-    for c in set(lines[i]).intersection(*lines[i + 1 : i + n_per_group])
-)
-print(f"answer 2 is {part2}")

2022/day4.py

@@ -1,17 +0,0 @@
-import sys
-
-lines = [line.strip() for line in sys.stdin.readlines()]
-
-
-def make_range(value: str) -> set[int]:
-    parts = value.split("-")
-    return set(range(int(parts[0]), int(parts[1]) + 1))
-
-
-sections = [tuple(make_range(part) for part in line.split(",")) for line in lines]
-
-answer_1 = sum(s1.issubset(s2) or s2.issubset(s1) for s1, s2 in sections)
-print(f"answer 1 is {answer_1}")
-
-answer_2 = sum(bool(s1.intersection(s2)) for s1, s2 in sections)
-print(f"answer 1 is {answer_2}")

2022/day5.py

@@ -1,41 +0,0 @@
-import copy
-import sys
-
-blocks_s, moves_s = (part.splitlines() for part in sys.stdin.read().split("\n\n"))
-
-blocks: dict[str, list[str]] = {stack: [] for stack in blocks_s[-1].split()}
-
-# this codes assumes that the lines are regular, i.e., 4 characters per "crate" in the
-# form of '[X] ' (including the trailing space)
-#
-for block in blocks_s[-2::-1]:
-    for stack, index in zip(blocks, range(0, len(block), 4)):
-        crate = block[index + 1 : index + 2].strip()
-
-        if crate:
-            blocks[stack].append(crate)
-
-# part 1 - deep copy for part 2
-blocks_1 = copy.deepcopy(blocks)
-
-for move in moves_s:
-    _, count_s, _, from_, _, to_ = move.strip().split()
-
-    for _i in range(int(count_s)):
-        blocks_1[to_].append(blocks_1[from_].pop())
-
-# part 2
-blocks_2 = copy.deepcopy(blocks)
-
-for move in moves_s:
-    _, count_s, _, from_, _, to_ = move.strip().split()
-    count = int(count_s)
-
-    blocks_2[to_].extend(blocks_2[from_][-count:])
-    del blocks_2[from_][-count:]
-
-answer_1 = "".join(s[-1] for s in blocks_1.values())
-print(f"answer 1 is {answer_1}")
-
-answer_2 = "".join(s[-1] for s in blocks_2.values())
-print(f"answer 2 is {answer_2}")

2022/day6.py

@@ -1,15 +0,0 @@
-import sys
-
-
-def index_of_first_n_differents(data: str, n: int) -> int:
-    for i in range(len(data)):
-        if len(set(data[i : i + n])) == n:
-            return i + n
-    return -1
-
-
-data = sys.stdin.read().strip()
-
-
-print(f"answer 1 is {index_of_first_n_differents(data, 4)}")
-print(f"answer 2 is {index_of_first_n_differents(data, 14)}")

2022/day7.py

@@ -1,80 +0,0 @@
-import sys
-from pathlib import Path
-
-lines = sys.stdin.read().splitlines()
-
-# we are going to use Path to create path and go up/down in the file tree since it
-# implements everything we need
-#
-# we can use .resolve() to get normalized path, although this will add C:\ to all paths
-# on Windows but that is not an issue since only the sizes matter
-#
-
-# mapping from path to list of files or directories
-trees: dict[Path, list[Path]] = {}
-
-# mapping from paths to either size (for file) or -1 for directory
-sizes: dict[Path, int] = {}
-
-# first line must be a cd otherwise we have no idea where we are
-assert lines[0].startswith("$ cd")
-base_path = Path(lines[0].strip("$").split()[1]).resolve()
-cur_path = base_path
-
-trees[cur_path] = []
-sizes[cur_path] = -1
-
-for line in lines[1:]:
-    # command
-    if line.startswith("$"):
-        parts = line.strip("$").strip().split()
-        command = parts[0]
-
-        if command == "cd":
-            cur_path = cur_path.joinpath(parts[1]).resolve()
-
-            # just initialize the lis of files if not already done
-            if cur_path not in trees:
-                trees[cur_path] = []
-        else:
-            # nothing to do here
-            pass
-
-    # fill the current path
-    else:
-        parts = line.split()
-        name: str = parts[1]
-        if line.startswith("dir"):
-            size = -1
-        else:
-            size = int(parts[0])
-
-        path = cur_path.joinpath(name)
-        trees[cur_path].append(path)
-        sizes[path] = size
-
-
-def compute_size(path: Path) -> int:
-    size = sizes[path]
-
-    if size >= 0:
-        return size
-
-    return sum(compute_size(sub) for sub in trees[path])
-
-
-acc_sizes = {path: compute_size(path) for path in trees}
-
-# part 1
-answer_1 = sum(size for size in acc_sizes.values() if size <= 100_000)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-total_space = 70_000_000
-update_space = 30_000_000
-free_space = total_space - acc_sizes[base_path]
-
-to_free_space = update_space - free_space
-
-answer_2 = min(size for size in acc_sizes.values() if size >= to_free_space)
-print(f"answer 2 is {answer_2}")

2022/day8.py

@@ -1,53 +0,0 @@
-import sys
-
-import numpy as np
-from numpy.typing import NDArray
-
-lines = sys.stdin.read().splitlines()
-
-trees = np.array([[int(x) for x in row] for row in lines])
-
-# answer 1
-highest_trees = np.ones(trees.shape + (4,), dtype=int) * -1
-highest_trees[1:-1, 1:-1] = [
-    [
-        [
-            trees[:i, j].max(),
-            trees[i + 1 :, j].max(),
-            trees[i, :j].max(),
-            trees[i, j + 1 :].max(),
-        ]
-        for j in range(1, trees.shape[1] - 1)
-    ]
-    for i in range(1, trees.shape[0] - 1)
-]
-
-answer_1 = (highest_trees.min(axis=2) < trees).sum()
-print(f"answer 1 is {answer_1}")
-
-
-def viewing_distance(row_of_trees: NDArray[np.int_], value: int) -> int:
-    w = np.where(row_of_trees >= value)[0]
-
-    if not w.size:
-        return len(row_of_trees)
-
-    return w[0] + 1
-
-
-# answer 2
-v_distances = np.zeros(trees.shape + (4,), dtype=int)
-v_distances[1:-1, 1:-1, :] = [
-    [
-        [
-            viewing_distance(trees[i - 1 :: -1, j], trees[i, j]),
-            viewing_distance(trees[i, j - 1 :: -1], trees[i, j]),
-            viewing_distance(trees[i, j + 1 :], trees[i, j]),
-            viewing_distance(trees[i + 1 :, j], trees[i, j]),
-        ]
-        for j in range(1, trees.shape[1] - 1)
-    ]
-    for i in range(1, trees.shape[0] - 1)
-]
-answer_2 = np.prod(v_distances, axis=2).max()
-print(f"answer 2 is {answer_2}")

2023/day1.py

@@ -1,45 +0,0 @@
-import sys
-
-lines = sys.stdin.read().splitlines()
-
-lookups_1 = {str(d): d for d in range(1, 10)}
-lookups_2 = lookups_1 | {
-    d: i + 1
-    for i, d in enumerate(
-        (
-            "one",
-            "two",
-            "three",
-            "four",
-            "five",
-            "six",
-            "seven",
-            "eight",
-            "nine",
-        )
-    )
-}
-
-
-def find_values(lookups: dict[str, int]) -> list[int]:
-    values: list[int] = []
-
-    for line in filter(bool, lines):
-        first_digit = min(
-            lookups,
-            key=lambda lookup: index
-            if (index := line.find(lookup)) >= 0
-            else len(line),
-        )
-        last_digit = max(
-            lookups,
-            key=lambda lookup: index if (index := line.rfind(lookup)) >= 0 else -1,
-        )
-
-        values.append(10 * lookups[first_digit] + lookups[last_digit])
-
-    return values
-
-
-print(f"answer 1 is {sum(find_values(lookups_1))}")
-print(f"answer 2 is {sum(find_values(lookups_2))}")

2023/day10.py

@@ -1,100 +0,0 @@
-import os
-import sys
-from typing import Literal, cast
-
-VERBOSE = os.getenv("AOC_VERBOSE") == "True"
-
-Symbol = Literal["|", "-", "L", "J", "7", "F", ".", "S"]
-
-lines: list[list[Symbol]] = [
-    [cast(Symbol, symbol) for symbol in line] for line in sys.stdin.read().splitlines()
-]
-
-# find starting point
-si, sj = next(
-    (i, j)
-    for i in range(len(lines))
-    for j in range(len(lines[0]))
-    if lines[i][j] == "S"
-)
-
-# find one of the two outputs
-ni, nj = si, sj
-for ni, nj, chars in (
-    (si - 1, sj, "|7F"),
-    (si + 1, sj, "|LJ"),
-    (si, sj - 1, "-LF"),
-    (si, sj + 1, "-J7"),
-):
-    if lines[ni][nj] in chars:
-        break
-
-# part 1 - find the loop (re-used in part 2)
-loop = [(si, sj), (ni, nj)]
-while True:
-    pi, pj = loop[-2]
-    i, j = loop[-1]
-
-    sym = lines[i][j]
-
-    if sym == "|" and pi > i or sym in "JL" and pi == i:
-        i -= 1
-    elif sym == "|" and pi < i or sym in "7F" and pi == i:
-        i += 1
-    elif sym == "-" and pj > j or sym in "J7" and pj == j:
-        j -= 1
-    elif sym == "-" and pj < j or sym in "LF" and pj == j:
-        j += 1
-
-    if (i, j) == (si, sj):
-        break
-
-    loop.append((i, j))
-
-answer_1 = len(loop) // 2
-print(f"answer 1 is {answer_1}")
-
-# part 2
-
-# replace S by an appropriate character for the loop below
-di1, dj1 = loop[1][0] - loop[0][0], loop[1][1] - loop[0][1]
-di2, dj2 = loop[0][0] - loop[-1][0], loop[0][1] - loop[-1][1]
-mapping: dict[tuple[int, int], dict[tuple[int, int], Symbol]] = {
-    (0, 1): {(0, 1): "-", (-1, 0): "F", (1, 0): "L"},
-    (0, -1): {(0, -1): "-", (-1, 0): "7", (1, 0): "J"},
-    (1, 0): {(1, 0): "|", (0, 1): "7", (0, -1): "F"},
-    (-1, 0): {(-1, 0): "|", (0, -1): "L", (0, 1): "J"},
-}
-lines[si][sj] = mapping[di1, dj1][di2, dj2]
-
-# find the points inside the loop using an adaptation of ray casting for a discrete
-# grid (https://stackoverflow.com/a/218081/2666289)
-#
-# use a set for faster '... in loop' check
-#
-loop_s = set(loop)
-inside: set[tuple[int, int]] = set()
-for i in range(len(lines)):
-    cnt = 0
-    for j in range(len(lines[0])):
-        if (i, j) not in loop_s and cnt % 2 == 1:
-            inside.add((i, j))
-
-        if (i, j) in loop_s and lines[i][j] in "|LJ":
-            cnt += 1
-
-if VERBOSE:
-    for i in range(len(lines)):
-        for j in range(len(lines[0])):
-            if (i, j) == (si, sj):
-                print("\033[91mS\033[0m", end="")
-            elif (i, j) in loop:
-                print(lines[i][j], end="")
-            elif (i, j) in inside:
-                print("\033[92mI\033[0m", end="")
-            else:
-                print(".", end="")
-        print()
-
-answer_2 = len(inside)
-print(f"answer 2 is {answer_2}")

2023/day11.py

@@ -1,41 +0,0 @@
-import sys
-
-import numpy as np
-
-lines = sys.stdin.read().splitlines()
-
-data = np.array([[c == "#" for c in line] for line in lines])
-
-rows = {c for c in range(data.shape[0]) if not data[c, :].any()}
-columns = {c for c in range(data.shape[1]) if not data[:, c].any()}
-
-galaxies_y, galaxies_x = np.where(data)  # type: ignore
-
-
-def compute_total_distance(expansion: int) -> int:
-    distances: list[int] = []
-    for g1 in range(len(galaxies_y)):
-        x1, y1 = int(galaxies_x[g1]), int(galaxies_y[g1])
-        for g2 in range(g1 + 1, len(galaxies_y)):
-            x2, y2 = int(galaxies_x[g2]), int(galaxies_y[g2])
-
-            dx = sum(
-                1 + (expansion - 1) * (x in columns)
-                for x in range(min(x1, x2), max(x1, x2))
-            )
-            dy = sum(
-                1 + (expansion - 1) * (y in rows)
-                for y in range(min(y1, y2), max(y1, y2))
-            )
-
-            distances.append(dx + dy)
-    return sum(distances)
-
-
-# part 1
-answer_1 = compute_total_distance(2)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = compute_total_distance(1000000)
-print(f"answer 2 is {answer_2}")

2023/day13.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day14.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day15.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day16.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day17.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day18.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day19.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day2.py

@@ -1,43 +0,0 @@
-import math
-import sys
-from typing import Literal, TypeAlias, cast
-
-CubeType: TypeAlias = Literal["red", "blue", "green"]
-
-MAX_CUBES: dict[CubeType, int] = {"red": 12, "green": 13, "blue": 14}
-
-# parse games
-lines = sys.stdin.read().splitlines()
-games: dict[int, list[dict[CubeType, int]]] = {}
-for line in filter(bool, lines):
-    id_part, sets_part = line.split(":")
-
-    games[int(id_part.split(" ")[-1])] = [
-        {
-            cast(CubeType, s[1]): int(s[0])
-            for cube_draw in cube_set_s.strip().split(", ")
-            if (s := cube_draw.split(" "))
-        }
-        for cube_set_s in sets_part.strip().split(";")
-    ]
-
-# part 1
-answer_1 = sum(
-    id
-    for id, set_of_cubes in games.items()
-    if all(
-        n_cubes <= MAX_CUBES[cube]
-        for cube_set in set_of_cubes
-        for cube, n_cubes in cube_set.items()
-    )
-)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = sum(
-    math.prod(
-        max(cube_set.get(cube, 0) for cube_set in set_of_cubes) for cube in MAX_CUBES
-    )
-    for set_of_cubes in games.values()
-)
-print(f"answer 2 is {answer_2}")

2023/day20.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day21.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day22.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day23.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day24.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day25.py

@@ -1,13 +0,0 @@
-import sys
-from collections import defaultdict
-from dataclasses import dataclass
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-answer_1 = ...
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = ...
-print(f"answer 2 is {answer_2}")

2023/day3.py

@@ -1,53 +0,0 @@
-import string
-import sys
-from collections import defaultdict
-
-NOT_A_SYMBOL = "." + string.digits
-
-lines = sys.stdin.read().splitlines()
-
-values: list[int] = []
-gears: dict[tuple[int, int], list[int]] = defaultdict(list)
-
-for i, line in enumerate(lines):
-    j = 0
-    while j < len(line):
-        # skip everything until a digit is found (start of a number)
-        if line[j] not in string.digits:
-            j += 1
-            continue
-
-        # extract the range of the number and its value
-        k = j + 1
-        while k < len(line) and line[k] in string.digits:
-            k += 1
-
-        value = int(line[j:k])
-
-        # lookup around the number if there is a symbol - we go through the number
-        # itself but that should not matter since it only contains digits
-        found = False
-        for i2 in range(max(0, i - 1), min(i + 1, len(lines) - 1) + 1):
-            for j2 in range(max(0, j - 1), min(k, len(line) - 1) + 1):
-                assert i2 >= 0 and i2 < len(lines)
-                assert j2 >= 0 and j2 < len(line)
-
-                if lines[i2][j2] not in NOT_A_SYMBOL:
-                    found = True
-
-                    if lines[i2][j2] == "*":
-                        gears[i2, j2].append(value)
-
-        if found:
-            values.append(value)
-
-        # continue starting from the end of the number
-        j = k
-
-# part 1
-answer_1 = sum(values)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = sum(v1 * v2 for v1, v2 in filter(lambda vs: len(vs) == 2, gears.values()))
-print(f"answer 2 is {answer_2}")

2023/day4.py

@@ -1,41 +0,0 @@
-import sys
-from dataclasses import dataclass
-
-
-@dataclass(frozen=True)
-class Card:
-    id: int
-    numbers: list[int]
-    values: list[int]
-
-
-lines = sys.stdin.read().splitlines()
-
-cards: list[Card] = []
-for line in lines:
-    id_part, e_part = line.split(":")
-    numbers_s, values_s = e_part.split("|")
-    cards.append(
-        Card(
-            id=int(id_part.split()[1]),
-            numbers=[int(v.strip()) for v in numbers_s.strip().split()],
-            values=[int(v.strip()) for v in values_s.strip().split()],
-        )
-    )
-
-winnings = [sum(1 for n in card.values if n in card.numbers) for card in cards]
-
-# part 1
-answer_1 = sum(2 ** (winning - 1) for winning in winnings if winning > 0)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-card2cards = {i: list(range(i + 1, i + w + 1)) for i, w in enumerate(winnings)}
-card2values = {i: 0 for i in range(len(cards))}
-
-for i in range(len(cards)):
-    card2values[i] += 1
-    for j in card2cards[i]:
-        card2values[j] += card2values[i]
-
-print(f"answer 2 is {sum(card2values.values())}")

2023/day5.py

@@ -1,129 +0,0 @@
-import sys
-from typing import Sequence
-
-MAP_ORDER = [
-    "seed",
-    "soil",
-    "fertilizer",
-    "water",
-    "light",
-    "temperature",
-    "humidity",
-    "location",
-]
-
-lines = sys.stdin.read().splitlines()
-
-# mappings from one category to another, each list contains
-# ranges stored as (source, target, length), ordered by start and
-# completed to have no "hole"
-maps: dict[tuple[str, str], list[tuple[int, int, int]]] = {}
-
-# parsing
-index = 2
-while index < len(lines):
-    p1, _, p2 = lines[index].split()[0].split("-")
-
-    # extract the existing ranges from the file - we store as (source, target, length)
-    # whereas the file is in order (target, source, length)
-    index += 1
-    values: list[tuple[int, int, int]] = []
-    while index < len(lines) and lines[index]:
-        n1, n2, n3 = lines[index].split()
-        values.append((int(n2), int(n1), int(n3)))
-        index += 1
-
-    # sort by source value
-    values.sort()
-
-    # add a 'fake' interval starting at 0 if missing
-    if values[0][0] != 0:
-        values.insert(0, (0, 0, values[0][0]))
-
-    # fill gaps between intervals
-    for i in range(len(values) - 1):
-        next_start = values[i + 1][0]
-        end = values[i][0] + values[i][2]
-        if next_start != end:
-            values.insert(
-                i + 1,
-                (end, end, next_start - end),
-            )
-
-    # add an interval covering values up to at least 2**32 at the end
-    last_start, _, last_length = values[-1]
-    values.append((last_start + last_length, last_start + last_length, 2**32))
-
-    assert all(v1[0] + v1[2] == v2[0] for v1, v2 in zip(values[:-1], values[1:]))
-    assert values[0][0] == 0
-    assert values[-1][0] + values[-1][-1] >= 2**32
-
-    maps[p1, p2] = values
-    index += 1
-
-
-def find_range(
-    values: tuple[int, int], map: list[tuple[int, int, int]]
-) -> list[tuple[int, int]]:
-    """
-    Given an input range, use the given mapping to find the corresponding list of
-    ranges in the target domain.
-    """
-    r_start, r_length = values
-    ranges: list[tuple[int, int]] = []
-
-    # find index of the first and last intervals in map that overlaps the input
-    # interval
-    index_start, index_end = -1, -1
-
-    for index_start, (start, _, length) in enumerate(map):
-        if start <= r_start and start + length > r_start:
-            break
-
-    for index_end, (start, _, length) in enumerate(
-        map[index_start:], start=index_start
-    ):
-        if r_start + r_length >= start and r_start + r_length < start + length:
-            break
-
-    assert index_start >= 0 and index_end >= 0
-
-    # special case if one interval contains everything
-    if index_start == index_end:
-        start, target, length = map[index_start]
-        ranges.append((target + r_start - start, r_length))
-    else:
-        # add the start interval part
-        start, target, length = map[index_start]
-        ranges.append((target + r_start - start, start + length - r_start))
-
-        # add all intervals between the first and last (excluding both)
-        index = index_start + 1
-        while index < index_end:
-            start, target, length = map[index]
-            ranges.append((target, length))
-            index += 1
-
-        # add the last interval
-        start, target, length = map[index_end]
-        ranges.append((target, r_start + r_length - start))
-
-    return ranges
-
-
-def find_location_ranges(seeds: Sequence[tuple[int, int]]) -> Sequence[tuple[int, int]]:
-    for map1, map2 in zip(MAP_ORDER[:-1], MAP_ORDER[1:]):
-        seeds = [s2 for s1 in seeds for s2 in find_range(s1, maps[map1, map2])]
-    return seeds
-
-
-# part 1 - use find_range() with range of length 1
-seeds_p1 = [(int(s), 1) for s in lines[0].split(":")[1].strip().split()]
-answer_1 = min(start for start, _ in find_location_ranges(seeds_p1))
-print(f"answer 1 is {answer_1}")
-
-# # part 2
-parts = lines[0].split(":")[1].strip().split()
-seeds_p2 = [(int(s), int(e)) for s, e in zip(parts[::2], parts[1::2])]
-answer_2 = min(start for start, _ in find_location_ranges(seeds_p2))
-print(f"answer 2 is {answer_2}")

2023/day6.py

@@ -1,47 +0,0 @@
-import math
-import sys
-
-
-def extreme_times_to_beat(time: int, distance: int) -> tuple[int, int]:
-    # formula (T = total time, D = target distance)
-    # - speed(t) = t,
-    # - distance(t) = (T - t) * speed(t)
-    # - distance(t) > D
-    #   <=> (T - t) * t > D
-    #   <=> -t^2 + T * t - D >= 0
-
-    a, b, c = -1, time, -distance
-    d = b * b - 4 * a * c
-
-    t1 = math.ceil(-(b - math.sqrt(d)) / (2 * a))
-    t2 = math.floor(-(b + math.sqrt(d)) / (2 * a))
-
-    if (time - t1) * t1 == distance:
-        t1 += 1
-
-    if (time - t2) * t2 == distance:
-        t2 -= 1
-
-    return t1, t2
-
-
-lines = sys.stdin.read().splitlines()
-
-# part 1
-times = list(map(int, lines[0].split()[1:]))
-distances = list(map(int, lines[1].split()[1:]))
-answer_1 = math.prod(
-    t2 - t1 + 1
-    for t1, t2 in (
-        extreme_times_to_beat(time, distance)
-        for time, distance in zip(times, distances)
-    )
-)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-time = int(lines[0].split(":")[1].strip().replace(" ", ""))
-distance = int(lines[1].split(":")[1].strip().replace(" ", ""))
-t1, t2 = extreme_times_to_beat(time, distance)
-answer_2 = t2 - t1 + 1
-print(f"answer 2 is {answer_2}")

2023/day8.py

@@ -1,29 +0,0 @@
-import itertools
-import math
-import sys
-
-lines = sys.stdin.read().splitlines()
-
-sequence = lines[0]
-nodes = {
-    p[0]: {d: n for d, n in zip("LR", p[1].strip("()").split(", "))}
-    for line in lines[2:]
-    if (p := line.split(" = "))
-}
-
-
-def path(start: str):
-    path = [start]
-    it_seq = iter(itertools.cycle(sequence))
-    while not path[-1].endswith("Z"):
-        path.append(nodes[path[-1]][next(it_seq)])
-    return path
-
-
-# part 1
-answer_1 = len(path(next(node for node in nodes if node.endswith("A")))) - 1
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = math.lcm(*(len(path(node)) - 1 for node in nodes if node.endswith("A")))
-print(f"answer 2 is {answer_2}")

2023/day9.py

@@ -1,29 +0,0 @@
-import sys
-
-lines = sys.stdin.read().splitlines()
-
-data = [[int(c) for c in line.split()] for line in lines]
-
-right_values: list[int] = []
-left_values: list[int] = []
-for values in data:
-    diffs = [values]
-    while any(d != 0 for d in diffs[-1]):
-        diffs.append([rhs - lhs for lhs, rhs in zip(diffs[-1][:-1], diffs[-1][1:])])
-
-    rhs: list[int] = [0]
-    lhs: list[int] = [0]
-    for cx in range(len(diffs) - 1):
-        rhs.append(diffs[-cx - 2][-1] + rhs[cx])
-        lhs.append(diffs[-cx - 2][0] - lhs[cx])
-
-    right_values.append(rhs[-1])
-    left_values.append(lhs[-1])
-
-# part 1
-answer_1 = sum(right_values)
-print(f"answer 1 is {answer_1}")
-
-# part 2
-answer_2 = sum(left_values)
-print(f"answer 2 is {answer_2}")

README.md

@@ -1,7 +1,36 @@
-# Advent Of Code
+# Holt59 - Advent Of Code
 
-To run any script, you need to pipe the input:
+Installation (with [`poetry`](https://python-poetry.org/)):
 
 ```bash
-cat 2022/inputs/day2.txt | python 2022/day2.py
+poetry install
+```
+
+To run any day:
+
+```bash
+holt59-aoc $day
+```
+
+You can use `-v` / `--verbose` for extra outputs in some case, `-t` / `--test` to run
+the code on the test data (one of the test data if multiple are present) or even
+`-u XXX` / `--user XXX` to run the code on a specific input after putting the input
+file under `src/holt59/aoc/inputs/XXX/$year/$day`.
+
+Full usage:
+
+```bash
+usage: Holt59 Advent-Of-Code Runner [-h] [-v] [-t] [-u USER] [-i INPUT] [-y YEAR] day
+
+positional arguments:
+  day                   day to run
+
+options:
+  -h, --help            show this help message and exit
+  -v, --verbose         verbose mode
+  -t, --test            test mode
+  -u USER, --user USER  user input to use
+  -i INPUT, --input INPUT
+                        input to use (override user and test)
+  -y YEAR, --year YEAR  year to run
 ```

pyproject.toml

@@ -0,0 +1,52 @@
+[tool.poetry]
+name = "holt59-advent-of-code"
+version = "0.1.0"
+description = ""
+authors = ["Mikael CAPELLE <capelle.mikael@gmail.com>"]
+license = "MIT"
+readme = "README.md"
+packages = [{ include = "holt59", from = "src" }]
+
+[tool.poetry.dependencies]
+python = "^3.12"
+numpy = "^2.1.3"
+tqdm = "^4.67.1"
+parse = "^1.20.2"
+sympy = "^1.13.3"
+networkx = "^3.4.2"
+pillow = "^11.0.0"
+imageio = "^2.36.1"
+pygifsicle = "^1.1.0"
+opencv-python = "^4.10.0.84"
+
+[tool.poetry.group.dev.dependencies]
+pyright = "^1.1.389"
+ruff = "^0.8.1"
+poethepoet = "^0.31.1"
+ipykernel = "^6.29.5"
+networkx-stubs = "^0.0.1"
+types-networkx = "^3.4.2.20241115"
+
+[tool.poetry.group.cplex.dependencies]
+docplex = "^2.30.251"
+cplex = "^22.1.2.0"
+
+[tool.poetry.group.ortools.dependencies]
+ortools = "^9.11.4210"
+
+[tool.poetry.scripts]
+holt59-aoc = "holt59.aoc.__main__:main"
+
+[tool.poe.tasks]
+format-imports = "ruff check --select I src --fix"
+format-ruff = "ruff format src"
+format.sequence = ["format-imports", "format-ruff"]
+lint-ruff = "ruff check src"
+lint-ruff-format = "ruff format --check src"
+lint-pyright = "pyright src"
+lint.sequence = ["lint-ruff", "lint-ruff-format", "lint-pyright"]
+lint.ignore_fail = "return_non_zero"
+
+[build-system]
+requires = ["poetry-core"]
+build-backend = "poetry.core.masonry.api"

run.ps1

@@ -1,12 +0,0 @@
-param(
-    [switch]$Test,
-    [PSDefaultValue()]
-    [Parameter(Mandatory = $false)]
-    $Year = 2023,
-    [Parameter(Mandatory = $true, Position = 0)]
-    $Day)
-
-$folder = $Test ? "tests" : "inputs"
-
-$env:AOC_VERBOSE = $VerbosePreference -eq "Continue"
-Get-Content ".\$Year\$folder\day$Day.txt" | python ".\$Year\day$Day.py"

src/holt59/aoc/2015/day1.py

@@ -0,0 +1,12 @@
+from typing import Any, Iterator
+
+from ..base import BaseSolver
+
+
+class Solver(BaseSolver):
+    def solve(self, input: str) -> Iterator[Any]:
+        floor = 0
+        floors = [(floor := floor + (1 if c == "(" else -1)) for c in input]
+
+        yield floors[-1]
+        yield floors.index(-1)

src/holt59/aoc/2015/day10.py

@@ -0,0 +1,147 @@
+import itertools
+from typing import Any, Iterator
+
+from ..base import BaseSolver
+
+# see http://www.se16.info/js/lands2.htm for the explanation of 'atoms' (or elements)
+#
+# see also https://www.youtube.com/watch?v=ea7lJkEhytA (video link from AOC) and this
+# CodeGolf answer https://codegolf.stackexchange.com/a/8479/42148
+
+# fmt: off
+ATOMS: list[tuple[str, tuple[int, ...]]] = [
+    ("22", (0, )),  # 0
+    ("13112221133211322112211213322112", (71, 90, 0, 19, 2, )),  # 1
+    ("312211322212221121123222112", (1, )),  # 2
+    ("111312211312113221133211322112211213322112", (31, 19, 2, )),  # 3
+    ("1321132122211322212221121123222112", (3, )),  # 4
+    ("3113112211322112211213322112", (4, )),  # 5
+    ("111312212221121123222112", (5, )),  # 6
+    ("132112211213322112", (6, )),  # 7
+    ("31121123222112", (7, )),  # 8
+    ("111213322112", (8, )),  # 9
+    ("123222112", (9, )),  # 10
+    ("3113322112", (60, 10, )),  # 11
+    ("1113222112", (11, )),  # 12
+    ("1322112", (12, )),  # 13
+    ("311311222112", (66, 13, )),  # 14
+    ("1113122112", (14, )),  # 15
+    ("132112", (15, )),  # 16
+    ("3112", (16, )),  # 17
+    ("1112", (17, )),  # 18
+    ("12", (18, )),  # 19
+    ("3113112221133112", (66, 90, 0, 19, 26, )),  # 20
+    ("11131221131112", (20, )),  # 21
+    ("13211312", (21, )),  # 22
+    ("31132", (22, )),  # 23
+    ("111311222112", (23, 13, )),  # 24
+    ("13122112", (24, )),  # 25
+    ("32112", (25, )),  # 26
+    ("11133112", (29, 26, )),  # 27
+    ("131112", (27, )),  # 28
+    ("312", (28, )),  # 29
+    ("13221133122211332", (62, 19, 88, 0, 19, 29, )),  # 30
+    ("31131122211311122113222", (66, 30, )),  # 31
+    ("11131221131211322113322112", (31, 10, )),  # 32
+    ("13211321222113222112", (32, )),  # 33
+    ("3113112211322112", (33, )),  # 34
+    ("11131221222112", (34, )),  # 35
+    ("1321122112", (35, )),  # 36
+    ("3112112", (36, )),  # 37
+    ("1112133", (37, 91, )),  # 38
+    ("12322211331222113112211", (38, 0, 19, 42, )),  # 39
+    ("1113122113322113111221131221", (67, 39, )),  # 40
+    ("13211322211312113211", (40, )),  # 41
+    ("311322113212221", (41, )),  # 42
+    ("132211331222113112211", (62, 19, 42, )),  # 43
+    ("311311222113111221131221", (66, 43, )),  # 44
+    ("111312211312113211", (44, )),  # 45
+    ("132113212221", (45, )),  # 46
+    ("3113112211", (46, )),  # 47
+    ("11131221", (47, )),  # 48
+    ("13211", (48, )),  # 49
+    ("3112221", (60, 49, )),  # 50
+    ("1322113312211", (62, 19, 50, )),  # 51
+    ("311311222113111221", (66, 51, )),  # 52
+    ("11131221131211", (52, )),  # 53
+    ("13211321", (53, )),  # 54
+    ("311311", (54, )),  # 55
+    ("11131", (55, )),  # 56
+    ("1321133112", (56, 0, 19, 26, )),  # 57
+    ("31131112", (57, )),  # 58
+    ("111312", (58, )),  # 59
+    ("132", (59, )),  # 60
+    ("311332", (60, 19, 29, )),  # 61
+    ("1113222", (61, )),  # 62
+    ("13221133112", (62, 19, 26, )),  # 63
+    ("3113112221131112", (66, 63, )),  # 64
+    ("111312211312", (64, )),  # 65
+    ("1321132", (65, )),  # 66
+    ("311311222", (66, 60, )),  # 67
+    ("11131221133112", (67, 19, 26, )),  # 68
+    ("1321131112", (68, )),  # 69
+    ("311312", (69, )),  # 70
+    ("11132", (70, )),  # 71
+    ("13112221133211322112211213322113", (71, 90, 0, 19, 73, )),  # 72
+    ("312211322212221121123222113", (72, )),  # 73
+    ("111312211312113221133211322112211213322113", (31, 19, 73, )),  # 74
+    ("1321132122211322212221121123222113", (74, )),  # 75
+    ("3113112211322112211213322113", (75, )),  # 76
+    ("111312212221121123222113", (76, )),  # 77
+    ("132112211213322113", (77, )),  # 78
+    ("31121123222113", (78, )),  # 79
+    ("111213322113", (79, )),  # 80
+    ("123222113", (80, )),  # 81
+    ("3113322113", (60, 81, )),  # 82
+    ("1113222113", (82, )),  # 83
+    ("1322113", (83, )),  # 84
+    ("311311222113", (66, 84, )),  # 85
+    ("1113122113", (85, )),  # 86
+    ("132113", (86, )),  # 87
+    ("3113", (87, )),  # 88
+    ("1113", (88, )),  # 89
+    ("13", (89, )),  # 90
+    ("3", (90, )),  # 91
+]
+# fmt: on
+
+STARTERS = [
+    "1",
+    "11",
+    "21",
+    "1211",
+    "111221",
+    "312211",
+    "13112221",
+    "1113213211",
+    "31131211131221",
+]
+
+
+def look_and_say_length(s: str, n: int) -> int:
+    if n == 0:
+        return len(s)
+
+    if s in STARTERS:
+        return look_and_say_length(
+            "".join(f"{len(list(g))}{k}" for k, g in itertools.groupby(s)), n - 1
+        )
+
+    counts = {i: 0 for i in range(len(ATOMS))}
+    idx = next(i for i, (a, _) in enumerate(ATOMS) if s == a)
+    counts[idx] = 1
+
+    for _ in range(n):
+        c2 = {i: 0 for i in range(len(ATOMS))}
+        for i in counts:
+            for j in ATOMS[i][1]:
+                c2[j] += counts[i]
+        counts = c2
+
+    return sum(counts[i] * len(a[0]) for i, a in enumerate(ATOMS))
+
+
+class Solver(BaseSolver):
+    def solve(self, input: str) -> Iterator[Any] | None:
+        yield look_and_say_length(input, 40)
+        yield look_and_say_length(input, 50)

src/holt59/aoc/2015/day11.py

@@ -0,0 +1,49 @@
+import itertools
+from typing import Any, Iterator
+
+from ..base import BaseSolver
+
+
+def is_valid(p: str) -> bool:
+    if any(c in "iol" for c in p):
+        return False
+
+    if not any(
+        ord(a) + 1 == ord(b) and ord(b) + 1 == ord(c)
+        for a, b, c in zip(p, p[1:], p[2:])
+    ):
+        return False
+
+    if sum(len(list(g)) >= 2 for _, g in itertools.groupby(p)) < 2:
+        return False
+
+    return True
+
+
+assert not is_valid("hijklmmn")
+assert not is_valid("abbceffg")
+assert not is_valid("abbcegjk")
+assert is_valid("abcdffaa")
+assert is_valid("ghjaabcc")
+
+
+def increment(p: str) -> str:
+    if p[-1] == "z":
+        return increment(p[:-1]) + "a"
+    elif p[-1] in "iol":
+        return p[:-1] + chr(ord(p[-1]) + 2)
+    else:
+        return p[:-1] + chr(ord(p[-1]) + 1)
+
+
+def find_next_password(p: str) -> str:
+    while not is_valid(p):
+        p = increment(p)
+    return p
+
+
+class Solver(BaseSolver):
+    def solve(self, input: str) -> Iterator[Any]:
+        answer_1 = find_next_password(input)
+        yield answer_1
+        yield find_next_password(increment(answer_1))

src/holt59/aoc/2015/day12.py

@@ -0,0 +1,27 @@
+import json
+from typing import Any, Iterator, TypeAlias
+
+from ..base import BaseSolver
+
+JsonObject: TypeAlias = dict[str, "JsonObject"] | list["JsonObject"] | int | str
+
+
+def json_sum(value: JsonObject, ignore: str | None = None) -> int:
+    if isinstance(value, str):
+        return 0
+    elif isinstance(value, int):
+        return value
+    elif isinstance(value, list):
+        return sum(json_sum(v, ignore=ignore) for v in value)
+    elif ignore not in value.values():
+        return sum(json_sum(v, ignore=ignore) for v in value.values())
+    else:
+        return 0
+
+
+class Solver(BaseSolver):
+    def solve(self, input: str) -> Iterator[Any]:
+        data: JsonObject = json.loads(input)
+
+        yield json_sum(data)
+        yield json_sum(data, "red")

src/holt59/aoc/2015/day13.py

@@ -0,0 +1,40 @@
+import itertools
+from collections import defaultdict
+from typing import Any, Iterator, Literal, cast
+
+import parse  # type: ignore
+
+from ..base import BaseSolver
+
+
+def max_change_in_happiness(happiness: dict[str, dict[str, int]]) -> int:
+    guests = list(happiness)
+    return max(
+        sum(
+            happiness[o][d] + happiness[d][o]
+            for o, d in zip((guests[0],) + order, order + (guests[0],))
+        )
+        for order in map(tuple, itertools.permutations(guests[1:]))
+    )
+
+
+class Solver(BaseSolver):
+    def solve(self, input: str) -> Iterator[Any]:
+        lines = input.splitlines()
+
+        happiness: dict[str, dict[str, int]] = defaultdict(dict)
+        for line in lines:
+            u1, gain_or_loose, hap, u2 = cast(
+                tuple[str, Literal["gain", "lose"], int, str],
+                parse.parse(  # type: ignore
+                    "{} would {} {:d} happiness units by sitting next to {}.", line
+                ),
+            )
+            happiness[u1][u2] = hap if gain_or_loose == "gain" else -hap
+
+        yield max_change_in_happiness(happiness)
+        for guest in list(happiness):
+            happiness["me"][guest] = 0
+            happiness[guest]["me"] = 0
+
+        yield max_change_in_happiness(happiness)

src/holt59/aoc/2015/day14.py

@@ -0,0 +1,63 @@
+from dataclasses import dataclass
+from typing import Any, Iterator, Literal, cast
+
+import parse  # type: ignore
+
+from ..base import BaseSolver
+
+
+@dataclass(frozen=True)
+class Reindeer:
+    name: str
+    speed: int
+    fly_time: int
+    rest_time: int
+
+
+class Solver(BaseSolver):
+    def solve(self, input: str) -> Iterator[Any]:
+        lines = input.splitlines()
+
+        reindeers: list[Reindeer] = []
+        for line in lines:
+            reindeer, speed, speed_time, rest_time = cast(
+                tuple[str, int, int, int],
+                parse.parse(  # type: ignore
+                    "{} can fly {:d} km/s for {:d} seconds, "
+                    "but then must rest for {:d} seconds.",
+                    line,
+                ),
+            )
+            reindeers.append(
+                Reindeer(
+                    name=reindeer, speed=speed, fly_time=speed_time, rest_time=rest_time
+                )
+            )
+
+        target = 1000 if len(reindeers) <= 2 else 2503
+
+        states: dict[Reindeer, tuple[Literal["resting", "flying"], int]] = {
+            reindeer: ("resting", 0) for reindeer in reindeers
+        }
+        distances: dict[Reindeer, int] = {reindeer: 0 for reindeer in reindeers}
+        points: dict[Reindeer, int] = {reindeer: 0 for reindeer in reindeers}
+
+        for time in self.progress.wrap(range(target)):
+            for reindeer in reindeers:
+                if states[reindeer][0] == "flying":
+                    distances[reindeer] += reindeer.speed
+
+            top_distance = max(distances.values())
+            for reindeer in reindeers:
+                if distances[reindeer] == top_distance:
+                    points[reindeer] += 1
+
+            for reindeer in reindeers:
+                if states[reindeer][1] == time:
+                    if states[reindeer][0] == "resting":
+                        states[reindeer] = ("flying", time + reindeer.fly_time)
+                    else:
+                        states[reindeer] = ("resting", time + reindeer.rest_time)
+
+        yield max(distances.values())
+        yield max(points.values()) - 1