# 使用 Python 開發輔助測資生成的套件
> 作者：沈宗叡（暴力又被TLE）
## 摘要
本專案旨在解決程式競賽出題過程中，測試資料（測資）生成流程繁瑣、可讀性低、難以維護與重現的痛點。傳統的測資生成腳本（Generator）常為一次性使用，缺乏通用架構，導致功能混雜、錯誤追蹤困難，且難以驗證測資是否能有效區分正確解與錯誤解。
為此，本專案以「分治」思維為核心，開發了一套輔助測資生成的 Python 套件。此套件將測資生成的複雜流程拆解為三個核心模組：**解決方案裝飾器 (`sol_dec`)**、**測資生成器引擎 (`subtask_gen`)** 與 **驗證器工廠 (`verifier`)**。
主要成果包含：
1. **流程模組化**：將 I/O 處理、隨機生成、邏輯驗證等功能解耦，大幅提升程式碼的可讀性與可維護性。
2. **可復現的隨機性**：隔離每個測資點的隨機種子，確保在偵錯或重生測資時，能夠精確復現特定狀態。
3. **自動化驗證機制**：使用者僅需定義各解法（如：AC, WA, TLE, RE）的預期結果，套件即可自動運行並驗證測資是否能有效鑑別不同解法，並提供明確的錯誤報告。
4. **強健的錯誤處理**：定義了清晰的例外（Exception）類別，如 `TestcaseInvalidError`，使生成過程中「無效的測資」與「未預期的程式錯誤」得以區分，並實現了自動重試機制。
最終，本專案成功開發出一套具備高可讀性、可維護性及強健性的測資生成輔助工具，並已實際應用於「APCS 模擬測驗」的出題流程中，有效提升了出題效率與測資品質。
---
## 零、心得
如果說，出題是在精心佈置一個大型犯罪現場，那麼過去的我，就是那個堅持手工雕刻每一把凶器、親自測試、精調每一滴血跡飛濺角度的變態殺手。每一次出題，都像重新造一組輪子，而且造出來通常還是方的。我的 Generator 是一坨坨巨大的義大利麵，`random`、`print` 和各種 `try-except` 攪和在一起，debug 時就像在麵裡挑出所有蔥花，堪稱一場災難。曾以為 `assert self` 是指確保官解的邏輯天衣無縫，但寫了幾次漏洞百出的測資後，我才驚覺，我尚連 Generator 都 `assert` 不了。
於是，這次自主學習，我決定從凶器工匠，升級為軍火工廠設計師。我不再滿足於單純地調用 `compile(random("idea"))`，而是要親手打造那個 `compiler`。
這個專案的核心，就是「分治」——不是演算法，而是把那個堆滿雜物的混沌工作坊，拆建成三條分工明確的自動化產線。`sol_dec.py` 就像一個精神時光屋，把任何解法扔進去，就能精準捕獲它的所有輸出與吶喊；`verifier.py` 則是那個冷酷無情的品管員，拿著 AC 的標準答案當作量尺，無情地對比每一個 WA、TLE 或 RE 的半成品；而 `subtask_gen.py` 是整座工廠的中央控制系統，它啟動產線、監控品管，一旦發現瑕疵品 `TestcaseInvalidError`，就面無表情地整組熔掉重來，直到產出完美的凶器為止。
當然，蓋工廠的過程從來不是一帆風順。我曾雄心勃勃地想搞個多進程加速，結果一頭撞上 Windows 這堵大牆。我想要的是 `fork`，它給我的卻是 `spawn`——沒有俐落的「叉子」，只有一堆必須小心翼翼「醃製」才能捧走的「卵」，開銷巨大又難以追蹤。那一刻我深刻體會到，理想與現實的差距，大概就是 `fork()` 和 `os.system('python script.py')` 的距離。最終，我學會了工程師最重要的美德之一：妥協，以及 `import someone_elses_hard_work`。感謝 `func_timeout`，我的品管員總算學會了看手錶。
從前，我害怕被兇手幹掉；後來，我享受成為兇手的樂趣；而現在，我迷上了設計那把能讓兇手無後顧之憂、盡情揮灑的完美兇刀。這趟旅程讓我明白，寫出一個堪用的工具，與寫出一個能在競賽中 AC 的解，是兩種截然不同的挑戰。它需要對架構的宏觀思考、對細節的偏執，以及在理想與現實間不斷權衡的智慧。我已不只 AC、WA、RE 了自己，我還把這個過程、這個專案，打包並 `import` 到了我的技能樹裡。
---
## 壹、緒論
### 一、開發動機
作為「APCS 模擬測驗團隊」出題組的一員，我在多次的命題歷程中深刻體會到，出題的真正難點往往不在於想出題目本身，而在於撰寫一個高品質的測資生成器（Generator）。
我的 [出題歷程心得](https://hackmd.io/@ericshen19555/how_i_made_p2_look_like_p5#心得) 中曾如此描述：
> 寫 Generator 的重點不在於 AC，而是先嘗試寫出 WA 或 TLE 卻很有機會 AC 的假解，再想辦法致其於死地。這簡直不只是在寫題、出題，而是在布置一個大型犯罪現場...而我就是那個精心布局的完美主義變態殺手。
這段經歷讓我意識到，一個好的 Generator 需要絞盡腦汁預判參賽者所有可能的錯誤，並生成強度足夠的測資來捕捉這些「假解」。
然而，回顧我早期的 Generator，充滿了許多問題：
- **架構混亂**：所有邏輯，包括隨機數生成、格式化輸出、假解驗證，全都混雜在一個巨大的腳本中，可讀性極低。
- **流程控制不易**：生成特定強度（例如，能卡掉 $O(N^2)$ 但放行 $O(N \log N)$）的測資時，常需手動調整參數並反覆測試，效率低下。
- **錯誤難以追蹤**：當生成出的測資不符合預期時，難以判斷是生成邏輯錯誤、隨機數不佳，還是假解驗證本身出錯。
- **可復現性差**：隨機狀態未被妥善管理，導致一旦生成出有問題的測資，很難重現當時的場景進行偵錯。
從 [滅台之作「大智慧學苑的朋友圈」](https://hackmd.io/@ericshen19555/how_i_made_p2_look_like_p5#%E5%88%9D%E8%A6%8B%E6%BB%85%E5%8F%B0%EF%BC%9A%E5%A4%A7%E6%99%BA%E6%85%A7%E5%AD%B8%E8%8B%91%E7%9A%84%E6%9C%8B%E5%8F%8B%E5%9C%88)中因 `set` 去重後忘記更新 `n` 值而導致測資出錯的慘痛教訓，到 [超噁實作題「All I want for Minecraft is CRAFT」](https://hackmd.io/@ericshen19555/how_i_made_p2_look_like_p5#%E8%B6%85%E5%99%81%E5%AF%A6%E4%BD%9C%EF%BC%9AAll-I-want-for-Minecraft-is-CRAFT) 中耗費半個禮拜撰寫 400 多行，卻沒有任何一個程式碼版本是可以獨立生成完整測資的 Generator。我逐漸意識到，這種「為每道題從零造輪子」的模式是不可持續的。
我決心將過去的經驗系統化，開發一個通用的、模組化的輔助套件。這個套件的目標是將繁瑣的背景工作（如 I/O 重新導向、解法計時、結果比對）全部封裝好，讓身為出題者的我，只需專注於「生成測資的邏輯」和「定義假解的行為」，從而根本性地提升出題效率與測資品質。
### 二、目的
本專案旨在開發一個 Python 套件，以達成以下預期效益：
1. **提升可讀性與可維護性**：透過模組化設計，將測資生成的流程拆分為獨立、可複用的組件，使程式碼結構清晰。
2. **建立標準化流程**：提供一個標準化的框架，引導出題者完成測資生成、解法驗證、答案產出等一系列步驟。
3. **強化測資驗證能力**：自動化驗證測資強度，確保其能有效區分 AC（正確）、WA（答案錯誤）、TLE（超時）、RE（執行時錯誤）等不同類型的解法。
4. **確保結果可復現**：獨立管理每個測資生成過程的隨機種子，方便偵錯與重現。
5. **完善錯誤回報機制**：設計明確的報錯系統，幫助使用者快速定位問題來源。
6. **封裝為專案**：將所有功能打包成一個易於安裝與使用的 Python 模組，方便推廣與協作。
### 三、範圍與限制
本專案的核心目標是建立一個**單進程**的測資生成與驗證框架。原先規劃的功能，如利用多進程平行生成測資以加速，以及生成特殊圖論結構的工具函式，因在開發過程中遭遇平台相容性（特別是 Windows 的多進程機制）等技術瓶頸，在權衡後決定暫緩。
因此，本專案的範圍專注於：
- **流程控制**：定義並實現生成與驗證的標準流程。
- **隨機性管理**：提供可復現的隨機數生成器。
- **解法驗證**：透過裝飾器與驗證工廠，比對不同解法的輸出與執行狀態。
- **錯誤處理**：建立穩固的例外處理機制。
目前套件尚未包含圖論等特定演算法領域的輔助工具，且未實現多進程加速功能。
---
## 貳、專案設計與實作
本專案遵循「分治 (Divide and Conquer)」的設計思維，將複雜的測資生成任務拆解為三個獨立但互相協作的模組。
### 一、核心架構
<!--
*(此處建議放置一張能說明三個模組如何協作的架構圖) - WIP*
-->
整個套件主要由以下三個 Python 檔案構成：
1. `sol_dec.py`：Solution 裝飾器，負責劫持與管理解法函式的標準輸入輸出。
2. `verifier.py`：verifier 工廠，負責根據預期結果，執行並比對各個解法的行為。
3. `subtask_gen.py`：Generator 引擎，是整個流程的協調者，負責調用生成器與驗證器，並處理重試與錯誤。
### 二、模組詳解
#### 1. `sol_dec.py` - 解決方案裝飾器 (`@override_io`)
程式競賽的解法通常從標準輸入（stdin）讀取資料，並將結果輸出至標準輸出（stdout）。為了在 Python 腳本中自動測試這些函式，我們需要一種方法來模擬這個過程。
`@override_io` 裝飾器正是為此而生。它在函式執行前，將 `sys.stdin` 和 `sys.stdout` 分別重新導向至一個記憶體中的字串流（`io.StringIO`）。
**主要功能：**
- **輸入注入**：將給定的 `testcase` 字串作為函式的標準輸入。
- **輸出捕獲**：捕獲函式所有打印到標準輸出的內容。
- **I/O 還原**：無論函式執行成功或發生錯誤，`finally` 區塊確保 `sys.stdin` 和 `sys.stdout` 都會被還原為原始狀態，避免影響後續操作。
- **回傳結果**：函式執行完畢後，回傳一個包含 `(函式回傳值, 從 stdout 捕獲的輸出字串)` 的 Tuple。
```python
# sol_dec.py (核心邏輯)
@wraps(solution)
def inner(*args, testcase: str | None = None, **kwargs) -> tuple[Any, str] | NoReturn:
# ...
try:
if testcase is not None:
sys.stdin = StringIO(testcase) # 重新導向 stdin
sys.stdout = StringIO() # 重新導向 stdout
ret = solution(*args, **kwargs)
output = sys.stdout.getvalue()
finally:
sys.stdin = sys.__stdin__ # 還原 stdin
sys.stdout = sys.__stdout__ # 還原 stdout
return ret, output
```
#### 2. `verifier.py` - 驗證器工廠 (`verifier_factory`)
驗證器的核心職責是：給定一份測資，它能否有效地「置假解於死地」，同時讓所有正確解通過？
`verifier_factory` 是一個高階函式，它接收一個 `expected` 設定檔和 `timeout` 時間限制，並回傳一個客製化的 `verifier` 函式。
**`expected` 設定檔格式：**
```python
# key 為測資編號，value 為一個字典，描述該測資點的預期結果
expected_config = {
0: { # 第 0 筆測資
AC: [ac_sol_1, ac_sol_2], # 預期 AC 的解法
WA: [wa_sol_1], # 預期 WA 的解法
TLE: [tle_sol], # 預期 TLE 的解法
ZeroDivisionError: [re_sol], # 預期產生特定錯誤的解法
}
}
```
**`verifier` 函式執行流程：**
1. **執行 AC 解**：首先執行第一個 AC 解法，取得標準答案 `reference_answer_output`。若此解法超時或產生錯誤，則此測資直接判定為無效。
2. **驗證其餘 AC 解**：執行所有其他的 AC 解法，確保它們的輸出與標準答案一致。
3. **驗證 WA 解**：執行所有 WA 解法，確保它們的輸出**不等於**標準答案。
4. **驗證 TLE/RE 解**：執行所有應產生 TLE 或其他 Exception 的解法，並捕捉其拋出的例外。驗證捕捉到的例外類型是否與預期相符。
5. **超時偵測**：所有解法的執行都被 `func_timeout` 套件包裹，若執行超過指定的 `timeout` 秒數，會拋出 `TimeLimitExceededError`。
如果任何一個步驟的驗證失敗（例如，應為 WA 的解法卻得到了 AC），`verifier` 會拋出 `TestcaseInvalidError`，表示這份測資是無效的。
#### 3. `subtask_gen.py` - 生成器引擎 (`generator_runner`)
這是串連起整個流程的核心。`generator_runner` 同樣是一個工廠函式，它接收使用者撰寫的 `generator` 函式和 `verifier` 函式，並回傳最終的 `runner` 函式。
**`runner` 函式執行流程：**
1. **初始化**：為本次生成建立一個可復現的隨機數生成器 `ReproducibleRandom`。
2. **生成**：呼叫使用者提供的 `generator(testcase_index, rnd)`，產生一份測資字串。
3. **驗證**：將生成的測資傳遞給 `verifier(testcase_index, testcase)` 進行驗證。
4. **處理結果**：
- **成功**：若 `verifier` 順利執行完畢並回傳標準答案，則 `runner` 回傳 `(測資, 標準答案)`，流程結束。
- **測資無效 (`TestcaseInvalidError`)**：若 `verifier` 拋出此錯誤，表示測資強度不足或不符預期。`runner` 會捕捉此錯誤，印出提示訊息，並**重新執行**步驟 1-3，直到成功或達到重試次數上限。
- **未知錯誤**：若過程中發生任何其他未預期的錯誤，`runner` 會將其包裝成 `GeneratorRuntimeError`，並附上當時的隨機種子狀態，方便使用者偵錯，然後中斷程式。
```python
# subtask_gen.py (核心邏輯)
def generator_runner(generator, verifier, retry_limit=-1):
def runner(testcase_index):
retry_count = 0
while retry_count != retry_limit:
rnd = ReproducibleRandom() # 每次重試都用新的隨機種子
try:
testcase = generator(testcase_index, rnd)
answer = verifier(testcase_index, testcase)
return testcase, answer # 成功，回傳結果
except TestcaseInvalidError as e:
# 測資無效，印出 log 並重試
print(f"[#{testcase_index}] Attempt {retry_count + 1}: TestcaseInvalidError (retrying)...")
retry_count += 1
except Exception as e:
# 未預期錯誤，打包錯誤資訊後拋出
raise GeneratorRuntimeError(...) from e
raise RuntimeError(f"Failed to generate a valid test case after {retry_limit} attempts.")
return runner
```
這個「生成-驗證-重試」的循環，是本套件自動化與強健性的關鍵。
---
## 參、成果與效益
本專案成功開發出一套功能完整的測資生成輔助套件。相較於過去手動、零散的開發方式，本套件帶來了顯著的效益。
### 一、實際應用與成果
在開發此套件後，我將其應用於「APCS 模擬測驗」後續題目的測資生成，例如[「小伊卡合成」](https://hackmd.io/@apcs-simulation-/rk0_Tz3Wxx)與[「Bob 的答案卡」](https://hackmd.io/@apcs-simulation-/SJQcOFrNel)等題目。實際應用展現了以下成果：
- **開發效率提升**：出題者只需專注於 `generator` 函式與 `expected` 設定檔的撰寫，其餘繁瑣工作皆由套件處理，大幅縮短了開發時間。
- **程式碼品質提升**：模組化的結構使得 Generator 的程式碼變得乾淨、易讀且易於維護。例如在「小伊卡合成」一題中，我可以輕易地為不同子題撰寫不同的生成邏輯，並在同一個驗證框架下進行測試。
- **測資強度保證**：自動化的驗證機制確保了每一筆最終生成的測資都確實能卡掉所有已知的假解，提升了測資的鑑別度。
- **偵錯能力強化**：當測資生成不如預期時，清晰的錯誤回報與可復現的隨機種子，讓我能快速定位並修復問題。
### 二、效益評估
| 評估項目 | 使用本套件前 | 使用本套件後 |
| :--- | :--- | :--- |
| **可讀性** | 低。所有邏輯混雜，難以理解。 | 高。功能模組化，職責分明。 |
| **可維護性** | 低。修改一處可能影響全局，難以擴充。 | 高。模組間低耦合，易於修改與擴充新功能。 |
| **開發效率** | 慢。大量重複工作，需手動驗證。 | 快。專注核心邏輯，驗證流程自動化。 |
| **測資品質** | 不穩定。可能因疏忽而產生瑕疵測資。 | 穩定。自動化驗證確保測資強度與正確性。 |
| **可復現性** | 差。隨機狀態混亂，難以偵錯。 | 好。隨機種子隔離，可精確重現生成過程。 |
---
## 肆、遭遇困難與解決方案
在開發過程中，我遇到了許多預期之外的挑戰，這些挑戰讓我對軟體工程的複雜性有了更深刻的認識。
### 一、TLE 偵測與 Windows 多進程的「雷」
- **預期**：為了實現 TLE（Time Limit Exceeded）偵測，我計畫在父進程中計時，並在一個獨立的子進程中執行解法程式。
- **實際**：Windows 的多進程模型（`spawn`）與類 Unix 系統（`fork`）截然不同。`spawn` 會建立一個全新的 Python 解譯器，這帶來了幾個問題：
1. **序列化 (`pickle`) 限制**：所有傳遞給子進程的對象都必須是「可序列化的 (picklable)」。這對複雜的物件或閉包（closure）造成了極大限制。
2. **初始化開銷**：每次生成子進程都有巨大的效能開銷。
3. **錯誤追蹤困難**：子進程中的錯誤難以被父進程捕獲與追蹤。
- **折衷方案**：在多次嘗試失敗後，我意識到從頭打造跨平台的多進程計時器超出了本次自主學習的範圍。因此，我決定明智地「借鑑」別人的解決方案，引入了成熟的第三方套件 [`func_timeout`](https://pypi.org/project/func-timeout/)。它透過多線程與信號機制，提供了一個簡單易用的函式裝飾器 `@func_set_timeout` 來實現計時功能。
- **衍生問題**：`func_timeout` 拋出的 `FunctionTimedOut` 例外繼承自 `BaseException` 而非 `Exception`，這意味著普通的 `except Exception:` 無法捕捉它，需要在例外處理上特別注意。
### 二、放棄的功能：多進程加速與動態參數輸入
- **多進程加速**：基於上述在 Windows 遇到的困難，原訂平行生成多筆測資以加速的功能，最終宣告放棄。
- **動態參數輸入**：我曾嘗試使用 `inspect` 模組來動態偵測解法函式需要哪些參數（例如 `testcase_index`），並自動傳入。然而，這個功能與 `func_timeout` 裝飾器疊加使用時，發生了無法解釋的衝突。在權衡後，為了保證核心功能的穩定，我選擇放棄這個錦上添花的功能。
### 三、專案管理與開發習慣的挑戰
- **版本控制**：專案初期我遲遲未安裝與使用 Git，導致版本管理混亂，這是一個嚴重的壞習慣。在嘗試實作動態參數傳入、並最終放棄後，因為缺乏版本控制而沒有可靠的 rollback 手段，只能依靠編輯器內建的檔案歷史功能，並人工比對、確認正確版本，非常不穩定、效率低下且容易出錯。
- **環境管理**：Python 的套件環境一度非常混亂，後來花費時間學習並使用了虛擬環境來解決。
- **命名與風格**：變數如何命名、Type Hints 如何標註、Docstring 的格式、註解的風格等冗雜的「小問題」，實際上耗費了大量思考時間，但也讓我體會到程式碼風格一致性的重要性。
- **模組化設計的掙扎**：專案中花費最多時間的，其實是思考「**哪個功能應該放在哪個模組**」，即模組的劃分與功能定位。例如，循環 `import` 的問題就迫使我重新思考模組間的依賴關係。
---
## 伍、結論與未來展望
### 一、學習與反思
這次自主學習專案不僅僅是完成了一個軟體，更是一趟深刻的學習之旅。我學到的不僅是 Python 語法，更是軟體工程的思維模式：
1. **專案架構與模組劃分**：學會了如何將一個大問題拆解成多個小而美的組件，並思考它們之間的介面與依賴，這是本次最大的收穫。
2. **理想與現實的權衡**：深刻體會到，一個好的工程師需要在「理想的完美實現」與「現實的技術限制、時間成本」之間做出妥協與取捨。放棄多進程就是一個血淋淋的例子。
3. **Work–Right–Fast**：先讓功能可以運作（Work），再確保它正確無誤（Right），最後才去思考如何優化效能（Fast）。這個開發哲學能有效避免過早優化帶來的問題。
4. **例外處理與錯誤追蹤**：理解到強健的錯誤處理是軟體品質的基石。一個好的程式不只要能處理正常情況，更要能優雅地應對各種異常。
5. **與 AI 協作**：在開發過程中，我大量使用 ChatGPT 進行討論、偵錯、尋找解決方案。這段經歷讓我學會如何提出精準的問題，並與 AI 建立起高效的「革命情感」。
### 二、未來展望
這個專案仍有很大的進步空間，未來我希望能朝以下方向繼續努力：
1. **完善多進程/多線程支持**：重新研究並實現一個穩健的、跨平台的平行化方案，以加速大量測資的生成。
2. **擴充工具函式庫**：加入更多針對特定領域的輔助功能，例如原先規劃的「圖論相關」工具，可以生成特殊圖（如完全圖、鏈、菊花圖）或計算圖的資訊。
3. **打包並發布至 PyPI**：將套件正式打包，並發布到 Python 套件索引 (PyPI) 上，讓更多程式競賽出題者能夠方便地安裝與使用，並收集社群的回饋。
4. **建立更完整的文檔**：撰寫更詳盡的使用教學、API 參考與範例，降低新使用者的上手門檻。
5. **持續優化與重構**：隨著使用經驗的累積，持續對現有程式碼進行重構，使其更有效率、更具彈性。
總之，這次自主學習讓我從一個單純的「解題者」，蛻變為一個初步具備「工具開發者」思維的學生。這段從 0 到 1 的經歷，遠比單純解出幾道難題，帶給我更多成長與啟發。
---
## 陸、附件
本專案的 Gitub 連結：[https://github.com/ericshen19555/generator_helper](https://github.com/ericshen19555/generator_helper)
<a href="https://github.com/ericshen19555/generator_helper">
<img src="https://hackmd.io/_uploads/B1RH9zM8xe.png" alt="Image" width="50%"/>
<a/>
自主學習報告影片：[https://youtu.be/JzHINSIwNVc](https://youtu.be/JzHINSIwNVc)
<a href="https://youtu.be/JzHINSIwNVc">
<img src="https://hackmd.io/_uploads/BJ6Cw1tIlx.png" alt="Image" width="50%"/>
<a/>
Sign in with Wallet
Connect another wallet