「照這個速度，我們就沒有時間把花環掛到餐廳了！」

本文翻譯自英文原文。

Github: GCaggianese/AoC-2025/D5

• GNU’s Programming and Extension Language

題目：第 5 天：Cafeteria

第一部分

問題

給定一個輸入檔，內容包含：

• 格式為 start-end 的範圍（例如 3-5、10-14）
• 要檢查的個別數字

計算有多少個個別數字落在任何已定義範圍內（包含端點）。

演算法

1. 將所有範圍解析成 (start, end) 配對列表。
2. 對每個個別數字：
   1. 檢查它是否落在任何範圍內：start ≤ n ≤ end。
   2. 如果是，增加計數器。
3. 回傳最終計數。

實作筆記（GNU Guile Scheme）

1. 失敗的方法

   1. 布林向量

      • 想法： 建立以數字為索引的向量，將範圍標記為 #t。
      • 問題： 輸入包含最高到 10^14 的數字，需要不可能的 RAM 量。
      • 結論： 小測資可行，但真實輸入會災難性爆炸。

   2. Hash table

      • 想法： 將範圍展開成 hash table entries，以便 O(1) 查詢。
      • 問題： 展開 1-1000000000 這樣的範圍會建立數十億筆 entries。
      • 結果： 永遠沒有跑完。
      • 結論： 記憶體膨脹加上效能災難。

2. 最終解法：範圍檢查

   • 方法： 將範圍存成配對，直接檢查包含關係。
   • 複雜度：
     • 空間：O(R)，R = 範圍數量（約 1000）
     • 時間：O(V × R)，V = 要檢查的值（約 200）
   • 執行時間： 幾乎瞬間（<1s）
   • 關鍵洞察： 不要展開範圍，直接檢查 membership。

   為問題選對資料結構。過早展開是所有記憶體問題的根源。

第二部分

問題

• 計算所有已定義範圍中有多少唯一數字（展開後但不重複）。

• 不包含個別數字。

解法

1. 將所有範圍解析為 (start, end) 配對（和第一部分相同）。
2. 依起始位置排序範圍。
3. 合併重疊與相鄰的區間：
   • 如果 next.start ≤ current.end + 1：合併成一個範圍。
   • 否則：保留為分離範圍。
4. 計算合併後範圍中的數字數量。
   • 加總所有計數。

實作：區間合併

• 方法： 不展開範圍 -> 合併重疊區間並計數。
• 複雜度：
  • 空間：O(R)，R = 範圍數量
  • 時間：排序 O(R log R) + 合併 O(R) = O(R log R)
• 重點： [1, 1000000000] 只用 2 個數字就能表示十億個值。

數學表示 » 實體展開。關鍵是儲存抽象。

程式碼

;; See aoc2025-d5.scm for full implementation