二进制咸鱼的自我救赎

Advent of Code 2025 完赛记录

2025-12-31 #python

连续几年都参加了 AOC，但是没有一年能完赛，今年终于完成了比赛。今年的题目不会很难，而且题量缩减，再加上大模型也能给一点思路（其实用大模型写代码的话估计可以秒杀很多题目，但是我没有这么用），所以还是能做完的。这篇文章主要讲一下里面用到了一些算法的地方。

Day5 Part2

题目可以理解为找出给定的所有区间内的整数。而且也给了提示区间是有重复的，所以我们遍历所有区间，来不断的合并重复的区间，并删除原本的区间，直到没有线段可以合并，说明合并完成。假设两个区间分别 (start, end) 和 (a_start, a_end)，判断在 x 轴上重合可以用 max(start, a_start) <= min(end, a_end) 这个公式来判断。

def solve_p2(lines: list[str]):
    ranges: list[tuple[int, ...]] = []
    cnt = 0
    for line in lines:
        if line == "":
            break
        ranges.append(tuple(int(t) for t in line.split("-")))
    while True:
        merge_deleted = set()
        merged = set()
        for i in range(len(ranges)):
            start, end = ranges[i]
            if ranges[i] in merge_deleted:
                # 线段已经被删除了，无需判断
                continue
            for j in range(i + 1, len(ranges)):
                a_start, a_end = ranges[j]
                if ranges[j] in merge_deleted:
                    continue
                if max(start, a_start) <= min(end, a_end):
                    # 线段重合
                    merged.add((min(start, a_start), max(end, a_end)))
                    merge_deleted.add(ranges[i])
                    merge_deleted.add(ranges[j])
        if not merged:
            # 没有可以合并的线段，退出循环
            break
        # 计算合并后的线段
        ranges = list((set(ranges) - merge_deleted) | merged)
    for start, end in ranges:
        cnt += end - start + 1
    print(cnt)

Day8 Part2

Part1 题目为在连接 1000 条边之后，找出边的长度最大的 3 颗树。可以转换为使用并查集来推导出森林，然后再遍历森林找出最大的树。

Part2 题目为找出最小生成树。在 Part1 已经有并查集的情况下，使用克鲁斯卡尔算法计算，即可解决。

class UnionFind[T]:
    # https://zhuanlan.zhihu.com/p/666225895, 这个 Python 实现是错的...
    # https://blog.csdn.net/WZHao000/article/details/142529658
    def __init__(self, nodes: list[T]):
        self.father: dict[T, T] = dict((i, i) for i in nodes)

    def find(self, node: T):
        if self.father[node] == node:
            return node
        self.father[node] = self.find(self.father[node])
        return self.father[node]

    def union(self, node_x: T, node_y: T):
        root_x = self.find(node_x)
        root_y = self.find(node_y)
        if root_x != root_y:
            self.father[root_x] = root_y

    def __str__(self) -> str:
        return str(self.father)


def kruskal(pos_lst: list[Point], dis_lst: list[tuple[Point, Point, float]]):
    uf = UnionFind(pos_lst)
    edge_cnt = 0
    for p1, p2, dis in dis_lst:
        p1_parent, p2_parent = uf.find(p1), uf.find(p2)
        if p1_parent == p2_parent:
            continue
        uf.union(p1_parent, p2_parent)
        edge_cnt += 1
        if edge_cnt == len(pos_lst) - 1:
            print(p1[0] * p2[0])
            break

Day9 Part2

这是两个多边形是否相交问题的简化版本，一个多边形和一个矩形是否相交。可以检查 4 个点是否在多边形内，再检查边是否在多边形内，即可解决。但是我偷懒了，使用了 "shapely" 库来解决。

TODO: 对比 shapely 的结果来写出手动检查的版本

from multiprocessing import Pool
from itertools import combinations

from shapely.geometry import Polygon, box


def rect_in_poly(p1, p2, poly: Polygon):
    x_min, x_max = min(p1[0], p2[0]), max(p1[0], p2[0])
    y_min, y_max = min(p1[1], p2[1]), max(p1[1], p2[1])
    rect = box(x_min, y_min, x_max, y_max)
    if poly.contains(rect):
        return (abs(p1[0] - p2[0]) + 1) * (abs(p1[1] - p2[1]) + 1)
    else:
        return 0


def solve(lines: list[str]):
    points = [tuple(map(int, i.split(","))) for i in lines]
    poly = Polygon(points)
    with Pool(processes=8) as pool:
        size_lst = pool.starmap(
            rect_in_poly, ((p1, p2, poly) for p1, p2 in combinations(points, 2))
        )
    print(max(size_lst))

Day10 Part2

这个是通过 z3-solver 的 Optimize 来解决的，我特意看了一下 reddit 上的解答，发现大家都在用 SMT 来解决的，所以我就学习了一个老哥的做法。

其实有看到头铁的老哥，通过求算矩阵方程+暴力循环找最优解的

# https://github.com/nitekat1124/advent-of-code-2025/blob/main/solutions/day10.py
from z3 import Int, Sum, Optimize, sat


def solve(lines: list[str]):
    total = 0
    for line in lines:
        light, *remain = line.split(" ")
        *ops, joltage = remain
        ops = [tuple(map(int, i[1:-1].split(","))) for i in ops]
        joltage = [int(i) for i in joltage[1:-1].split(",")]
        optimizer = Optimize()  #  z3 魔法，小子
        ops_cnt = [Int(str(i)) for i in ops]
        # 每个按钮点击次数 >= 0
        for cnt in ops_cnt:
            optimizer.add(cnt >= 0)
        # 遍历按钮看一下当前 jol 是否被按钮影响到
        # 如果影响到就计数
        for jol_idx, jol in enumerate(joltage):
            touched = []
            for op_idx, op in enumerate(ops):
                if jol_idx in op:
                    touched.append(ops_cnt[op_idx])
            optimizer.add(Sum(touched) == jol)
        optimizer.minimize(Sum(ops_cnt))
        if optimizer.check() == sat:
            model = optimizer.model()
            total += sum(model[c].as_long() for c in ops_cnt)  # type: ignore
        else:
            print("What?")
            exit()
    print(total)

Day11 Part2

这个题目是找到图中几个点之间有多少条路线，通过 DFS + 缓存会在求解第一条路线的时候卡住，问了一下 Deepseek, 他给出了使用拓扑排序 + 动态规划可以很快的解决。有一种可能经过的路线为 "dac" => "fft"，但是在我的数据中，这个路线没有联通的可能性，所以直接忽略了。

def dfs_cached(node: str, end: str, graph: dict[str, list[str]], cache: dict[str, int]):
    if node == end:
        return 1
    if cnt := cache.get(node):
        return cnt
    cnt = 0
    for dec in graph.get(node, []):
        cnt += dfs_cached(dec, end, graph, cache)
    cache[node] = cnt
    return cnt


def count_paths_in_dag(graph: dict[str, list[str]], start: str, end: str):
    # 初始化入度
    indeg = defaultdict(int)
    for ancs in graph.values():
        for anc in ancs:
            indeg[anc] += 1

    # 拓扑排序
    q = deque(i for i in graph.keys() if indeg[i] == 0)
    topo = []
    while q:
        u = q.popleft()
        topo.append(u)
        for v in graph.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    # DP计数
    dp = defaultdict(int)
    dp[start] = 1
    for u in topo:
        for v in graph.get(u, []):
            dp[v] += dp[u]  # 对于每一个节点，更新他的邻居

    return dp[end]


def solve(lines: list[str]):
    graph: dict[str, list[str]] = {}
    for line in lines:
        node, remain = line.split(": ")
        decs = remain.split(" ")
        graph[node] = decs
    # dac_fft = dfs_cached("dac", "fft", graph, {})
    svr_fft = count_paths_in_dag(graph, "svr", "fft")
    print(svr_fft)
    fft_dac = dfs_cached("fft", "dac", graph, {})
    print(fft_dac)
    dac_out = dfs_cached("dac", "out", graph, {})
    print(dac_out)
    print(svr_fft * fft_dac * dac_out)

Day12 Part1

题目是一个很复杂的问题，是不规则多边形填充到矩形问题，可以通过回溯法 + 剪枝来实现，但是题目作者特意优化数据，导致直接计算不规则多边形的面积是否大于矩形就可以解决了，让大家过了个好年（好圣诞节）。

总结

虽然题目难度不大，但是还是重新复习了不少东西。

Refs

• https://www.reddit.com/r/adventofcode