歡迎來到北極！你的任務是在給定範圍中找出所有無效 ID。

本文翻譯自英文原文。

Github: GCaggianese/AoC-2025/D2

• The C programming language

題目 第 2 天：Gift Shop

• 值以 II-FF 表示並用逗號分隔，其中 II 是起始範圍，FF 是結束範圍（兩者都包含）。

輸入結構

• 沒有前導 0
• II < FF
• II 和 FF 之間用 - 分隔
• 無效 ID：
  • 範圍中的重複模式
    • 例：11-22：$\forall x \in [11,22] \cap \mathbb{N}^+$， 很容易看出唯一重複成對的模式是 11 和 22。
    • 例：11-33：$\forall x \in [11,33] \cap \mathbb{N}^+$， 現在重複模式包含 33 [11, 22, 33]。
  • 奇數長度的數字永遠有效
    • 111 -> 3 位數 -> 不能拆成兩半（有效）
    • 22022 -> 5 位數 -> 同理（有效）

第一部分：偶數位數的回文型數字

• 方法是辨識出「無效 ID」就是可以表示為兩個相同部分的數字。
• 可以用公式產生： $\text{Invalid} = d \times (10^n + 1)$，其中：
  • n 是位數的一半
  • d 是 n 位數的基底數字

1. 背後的數學：

   • 對 2n 位數而言，要成為「無效」很簡單，只要 $\text{left-part} = \text{right-part}$。
   • 可表示成：$\text{number} = d \times 10^n + d$ $\text{number} = d(10^n + 1)$
   • 其中 d 是重複出現的 n 位數「基底」。

2. 依位數舉例：

   1. 2 位數（n=1）：

      • 這個情況很基本，就是 11 的倍數。

   2. 4 位數（n=2）：

      • 乘數：$10^2 + 1 = 101$
      • 合法 d 值：${10, 11, …, 99}$
      • 無效 ID：$1010, 1111, 1212, …, 9999$
      • 例：$1111 = 11 × 101$

   3. 6 位數（n=3）：

      • … 與 n=2 相同邏輯 …

   4. 8 位數（n=4）：

      • … 與 n=3 相同邏輯 …

   5. 10 位數（n=5）：

      • 乘數：$10^5 + 1 = 100001$
      • 合法 d 值：${10000, 10001, …, 99999}$
      • 例：$1188511885 = 11885 × 100001$

3. 偵測演算法：

   對任意 value：

   1. 計算位數： $\text{digits} = \lfloor \log_{10}(\text{value}) \rfloor + 1$
   2. 檢查是否為偶數： $\text{digits} \equiv 1 \pmod{2} \implies \text{valid (skip)}$
   3. 計算乘數： $M = 10^{n} + 1 \quad \text{where} \quad n = \frac{\text{digits}}{2}$
   4. 測試整除： $\text{value} \equiv 0 \pmod{M} \implies \text{invalid}$

4. 奇數位數永遠有效：

   • 任何奇數位數的數字都不能分成兩個部分。
   • 例：111、212、11011 都有 3 或 5 位數。
   • 沒有辦法把它們表示成 $d \times (10^n + 1)\quad \text{where}\ n = \frac{\text{digits}}{2}$
   • 因此，所有奇數位數的數字都有效。

5. 因此：

   • 不需要手動檢查每個位數。
   • 每個數字的時間複雜度：O(1)。

第二部分：多重重複

• 現在無效 ID 包含至少重複兩次的模式（不只是剛好兩次）。
• 例：111（1×3）、123123123（123×3）、1212121212（12×5）

1. 延伸公式：

對長度為 $p$、重複 $k$ 次的模式：

\[\text{number} = s \times \frac{10^{k \cdot p} - 1}{10^p - 1}\]

其中：

• $s$ 是基底模式（$p$ 位數）
• $k \geq 2$ 是重複次數
• 總位數：$d = k \times p$

1. 偵測演算法：

對一個有 $d$ 位數的數字：

1. 找出 $d$ 的所有因數（排除 $d$ 本身）：這些是可能的模式長度。
2. 對每個 $p < d$ 的因數 $p$：
   • 計算 $k = d / p$（重複次數）
   • 計算乘數：$M = \frac{10^d - 1}{10^p - 1}$
   • 檢查 $\text{value} \equiv 0 \pmod{M}$
   • 驗證模式恰好有 $p$ 位數（沒有前導 0）
   • 若兩者皆成立 -> 無效
3. 因此：
   • 找因數：$O(\sqrt{d})$，其中 $d = \lfloor \log_{10}(\text{value}) \rfloor + 1$

使用 C 的解法

我使用 C 和很棒的 nob.h 作為 no-build system 來建立解法。 如果想執行它，只要先 bootstrap nob.c，再執行 ./nob；它會編譯解法，之後可以用 ./build/AoC-2025_D2 執行。