Advent of Code 2025 / Everybody Codes 2025

第四年在這裡貼 Advent of Code 心得了。今年開始 Eric 決定要減輕一點他自己的負擔，所以題目數量減少到 12 天，不過仍然還是在 12/1 開場，每天開題；也就是今年只會到 12/12 就結束了。

目前看起來這個年末的程式設計謎題傳統有其他人繼承了下來，像是去年就開始的 Everybody Codes 它是自十一月的第一個星期一開始，連續四週的週一至週五各開一題——開啟時間似乎是 UTC+1 的 24:00，換算台灣時間是隔天的早上七點；麻煩的是這個時間剛好卡到我上班只好在到公司時偷一點時間出來寫。他這邊的故事風格比較中世紀一點，並且以鴨子做為各種吉祥物和故事元素，算是很不一樣的風格。

於是今年為了幫這篇文章充點篇幅 (?!)，我也把 Everybody Codes 的題目心得寫在這裡。如果只要看 Advent of Code 的，點此連結跳到下面。(我有放防雷圖，應該是不必擔心這樣跳過去會被雷) 文章仍然押 12/1 發，也就是發出時 Everybody Codes 的心得已經寫好了。

以下 Everybody Codes 防雷圖。

Everybody Codes 2025

Quest 1: Whispers in the Shell (2025/11/3)

第一題果然是簡單的熱身題。讀字串陣列進來，然後照它說的動索引或動字串就行。輸入分析還是相對比較「麻煩」的部份，是個給新手練習輸入分析的題型。

Quest 2: From Complex to Clarity (2025/11/4)

這題其實是要我們算 Mandelbrot set。(第三題的故事部份也破了這個梗就是) 中間的計算基本上是為了讓參加者只用整數而做的，整體上其實等同於某個固定大小的定點數 (Part 1 是一位定點，Part 2/3 則是五位定點)；所以我直接拿 C++ 的 <complex> 來做計算了。

Quest 3: The Deepest Fit (2025/11/5)

這題考的是能不能得出「排序是答案」這個結論：數字本身形成了一個 DAG，而答案即是這個 DAG 的拓撲排序。在看出相同大小元素對序列選取的影響之後也能容易得到 Part 3 的答案是眾數的個數。

Quest 4: Teeth of the Wind (2025/11/6)

齒輪模擬題，關鍵在於齒輪的不變量：固定時間內轉過的齒數。Part 3 的大小齒輪只是把這個不變量乘上大小變化倍率而已。

Quest 5: Fishbone Order (2025/11/7)

第一個週末題，不過仍然只是相對繁瑣一點的操作而已；比較搞事的是把數字串下來的部份是字串連接而已。

Quest 6: Mentorship Matrix (2025/11/10)

配對問題，問所有小寫字母跟其左邊的大寫字母組合有幾種。顯然在掃過去時有紀錄下目前為止的大寫字母數量就能馬上得出每個小寫字母有多少大寫字母配對；Part 3 就只是加上 sliding window 而已。

Quest 7: Namegraph (2025/11/11)

開始出現 DP 題了。前兩個 part 只是檢查，Part 3 就要實際算出生成的數量了；這裡就是標準的 DP，每個名字都能由較短的名字加上規則來組合而成，而我們只需要最後一個字母即可求出下一個長度的數量，因此 DP 陣列紀錄的就是每個長度每個字尾的名字個數。

Quest 8: The Art of Connection (2025/11/12)

這題算是簡化版計算幾何吧？不是對任何點做計算而是限定範圍內的點與直線交叉計算。也因為有限定所以交叉判定就沒有那麼多花俏的計算直接判斷大小就好。

Part 3 倒是有個很有趣的做法：與其對每種切法判斷線有沒有被切，反過來去累計這條線會被哪些切法切斷；後者不需要判斷，因為只要在線的兩邊各選一點就會被切到了。

說起來，今年有好多題目有彩蛋輸入；這題的「編織網」實際畫出來是可以看到有框成一個騎士盔甲的圖案在。

Quest 9: Encoded in the Scales (2025/11/13)

這題的配對關係很有意思。一個 (父，母，子) 的三元組，子的每個元素都是由父或母中其中而來的；前兩段就是要判斷任三個元素是否形成這樣的父母子三元組。仔細細想就能推斷出：

所有元素，三人中至少要有兩人相同
但兩同一不同的三種狀況至多只能出現兩種 (如 AAC/ACA/CAA 就不行)

Part 3 進一步要我們建出家族樹，但卻只要我們答出家族樹的總大小；因此這裡可以偷點懶，使用併查集 (disjoint set) 把所有有關係的三人全部加在一起，然後只要求出每個 set 的大小即可。

Quest 10: Feast on the Board (2025/11/14)

Part 1 和 Part 2 都是很容易的模擬題，照著它的說明下去模擬即可。

Part 3 就是難關了。給定一個盤面，求出所有走法使得所有羊棋被龍棋給吃光的序列數目。這個部份我用的是 BFS+DP，使用 BFS 依序搜過所有步數的所有狀態，然後在狀態更新時進行 DP 計算遊戲至下一步的序列數目，加去下一步的格子裡。基本上就是把 DP 中的「計算順序」以 BFS 來決定這樣。

Quest 11: The Scout Duck Protocol (2025/11/17)

這題開始有趣了。題目描述了一個「隊形平衡」演算法，要我們求出給定隊形到平衡需要多少步。Part 1 模擬十步，Part 2 解決一個小型問題，然後 Part 3 是個超大型隊形，直接跑會跑不完的那種。這題的關鍵在於：Part 3 輸入只需要進行演算法的第二部份，而這部份是有能快速求出步數的捷徑的。

Quest 12: One Spark to Burn Them All (2025/11/18)

給定一個數字陣列，對某一點「引爆」會將其所有往數字較小的路徑上的所有點一起引爆。Part 1 引爆左上角，Part 2 引爆左上右下兩個角，Part 3 則是要選擇三點能引爆最多格的點，求總計引爆多少格。是個很標準的淹水/BFS 題。

這題同樣有彩蛋輸入：Part 3 輸入所引爆的圖案是這個站的吉祥物鴨子。

Quest 13: Unlocking the Mountain (2025/11/19)

題目描述了一個奇妙的轉盤：轉盤上的數字自頂點起，第一個向右擺，下一個向左擺，再下一個向右擺，以此類推。數字擺好後，求出轉動某個格數後轉盤的位置為何。Part 1 每次只擺一個數字，Part 2 會擺一個範圍數字，Part 3 則是範圍變成超級大。陷阱其實就只有 Part 3 這個超大範圍，要你不要傻傻的一個一個數字擺下去而已。

Quest 14: The Game of Light (2025/11/20)

細胞自動機題。這題的規則比較有趣的是它看的是斜角相鄰的個數，不過實作上相對沒什麼問題——直到 Part 3 要你從中找循環為止。好在模擬起點是全黑，這表示 34×34 的空間可以切成對稱的四分之一來做模擬，然後可以發現它每 4095 步就循環一次 (這個循環可以偵測全亮的狀態來確認)，所以要找出含特定中心樣式的步數就很容易了。

Quest 15: Definitely Not a Maze (2025/11/21)

確實不是迷宮啦，因為牆只有一條連續壁……不過看起來這條連續壁是逐漸往外繞的。題目要求從連續壁的頭直接走到尾，不過因為牆是這樣繞的關係，加上 Part 3 又是超大型連續壁，直接搜會狀態爆炸。這裡我用了座標壓縮 (又稱離散化) 的技巧，把整張地圖只留下牆跟牆的兩邊的座標，再丟去 A* 搜就搜出來了。

果然週末題都很有挑戰性……

Quest 16: Harmonics of Stone (2025/11/24)

給定指示序列，每個序列中的數字 n 表示在每第 n 格放一個石頭。Part 1 給定指示和總長度求出總石頭個數，Part 2 給定開頭求出指示，Part 3 則綜合起來，給定開頭求出給定量能放多長。

簡單想一想就能知道 Part 1 可以直接以總長度除以各指示間隔再求和，Part 2 則反過來，在第 N 格有這麼多石頭表示 N 的因數裡恰有這麼多個在指示當中，由此即可篩出有和沒有的指示。(當然這就假設沒有大於給定長度的指示，我們也無法知道有沒有)

Part 3 則很有意思。使用 Part 2 求出指示後，原本想說用個 LCM 看能不能找出循環簡化計算，結果作者放了好些大質數在裡面讓 LCM 直接翻車……。然後想說好吧，不然就二分搜一下看看，然後就想到這不就是標準的指數搜尋問題嗎?! 所謂指數搜尋，是指在一個右端無限的單調範圍內進行「二分」搜尋的演算法，由於第一步是依照指數成長的速度切段下來看要找的東西在不在裡面，故稱指數搜尋。因為切下來的段落是指數成長，若欲搜尋數在第 \(N\) 格，會需要 \(O(\log N)\) 次切到它；切下來的段落約有 \(N/2\) 個元素，進行標準二分搜也需要 \(O(\log N)\) 次，所以總計的時間就是 \(O(\log N)\)。

不過 Part 3 其實還有另解：由 Part 1，給定長度可以求出石頭數至多是長度乘上指示的倒數和，因此倒求時給定石頭數可以除以倒數和求得只低估少許的長度，再簡單的搜過去就能找出答案了。

Quest 17: Deadline-Driven Development (2025/11/25)

火山要爆發了！Part 1 和 2 熟悉火山岩漿的圓形範圍後，Part 3 要我們自一個起點開始，繞火山岩漿一圈回到原點，這當中不能讓火山岩漿的圓形範圍碰到走過的路線。

比較麻煩的是這個「繞火山岩漿一圈」這件事。我一開始的寫法是自火山口往左右拉橫線，搜尋時紀錄下這結果是走過哪半邊的橫線，然後去找各一邊的結果湊起來；不過後來看到另一個判定法是只拉半邊當作「換日線」，紀錄目前位置是從哪邊跨過「換日線」，然後就能以跨過某個方向一次的原點做為搜尋目標。

Quest 18: When Roots Remember (2025/11/26)

給定一些植物的「接線」，其結果會通過一條管線接到下一條植物上，求最終植物的結果——或是 Part 3 要你在一個給定 81 輸入的接線上求出最佳解。

這題這個接線方式其實很有類神經網路的味道：每個「植物節點」有輸入值，經過管線的加權和，到節點本身進行 (某個變形的) ReLU 整流後做為結果；但 Part 3 的最佳化並沒有一個目標值能讓我們做反向傳播。後來換了個思路，既然是在一個很高維度的空間做最佳化，那不如來寫模擬退火吧！不過這畢竟是我第一次在做這種最佳化題上寫模擬退火，有些細節並沒有那麼熟，加上這題的值空間有個很大的 0 谷，進入 0 谷就不容易跳出來，花了好些時間在處理這些地方。不過至少找到的最大值是正確的 (而且貌似不只一解，可能因為這些解的某些中間值不管怎麼調都是 0 的關係) 而且跑的夠快。

Quest 19: Flappy Quack (2025/11/27)

……標題和圖片根本就把這題破梗破光了 XD。不過意外的當數字很大的時候不好做，你不可能用類 BFS 的搜尋搜過去：首先顯然不可能在每一步決定拍不拍，然後就算化簡到只在管子處算，這地圖目標之深會幾乎把所有淺層的狀態給找過，當淺層狀態夠多時一樣會爆炸。

不過如果觀察到拍的次數決定了到目標時的高度，那我們就可以不用管拍的次數了：反正能通過的範圍裡最低的那個就是最少次數。然後就是逐個掃過去決定哪些格子到得了，一路推到最後的管子就行了。

Quest 20: Dream in Triangles (2025/11/28)

這題就是標準的三角座標題，不過 Part 3 地圖還會轉……然後就忘記原地跳也是一步。orz

會轉的地圖一般來說有兩種解法：一種是真的把地圖轉過去，一種是倒過來把自己轉去目標格。這題因為是三角格的關係，需要的計算都不是很簡單，都會需要想一下。我是因為採用了轉地圖的方式才會忘記原地跳這一步；如果是自己轉去目標格的話應該是不會漏的。

以下 Advent of Codes 的防雷。

Advent of Codes 2025

喔對了，Git repo 在這裡。今年我決定把一些東西升級成 C++20 了，例如尋徑函式庫的 State 類別條件的 concept 補了上去，這樣我要寫 State 時放個 static_assert 就能讓 clangd 幫我檢查是不是該實作的都寫了。

1. Secret Entrance

熱身題就是要有 off by one error 才能叫熱身 XD 倒是意外地和 Everybody 2025 的 Quest 1 有部份相同的元素在。(是什麼就不捏他了) 在寫 Part 2 的時候一直覺得怎麼左右不對稱很討厭，然後才發現對啊左右本來就不對稱：取餘的分界線是在 0 的左邊，所以往右轉時跨線是在踩 0 之前自然直接求，往左轉時跨線是在踩 0 之後所以才會差 1。

2. Gift Shop

果然這種問題就能看到兩種思考方式：一是掃過所有範圍看裡面數字是不是重覆字串，一是產生所有重覆字串再去看它們在不在範圍裡。考慮到這題的數字不會大到爆炸，在 9e15 上限之下重覆兩次的極限是七位數，也就是產生所有重覆字串頂多千萬出頭次，我就直接寫後者了。

3. Lobby

總之是找數字的子字串使結果最大。我的做法是遞迴，每次找出最大的數字最早出現在哪。如果它含其後的數字足夠取的話就取它加遞迴取後面，否則遞迴取前面加上它和所有後面的數字；理由是這個最大的數字出來一定最賺，越早出現也越賺，所以求出它最早可以在哪裡，剩下的就遞迴找即可。

然後看到另一個不太確定算不算等價的做法：自左而右，取目前左界 (自字串左界開始) 至末尾前 X 位中的最大值，這個 X 位要留到保證後面有足夠的位數取剩下的數字。例如 part 2 的取 12 個，則第一個字是字串開頭至倒數第 12 個中的最早最大值，第二個字是第一個字之後至倒數第 11 個中的最早最大值，依此類推。這個貪心做法的理由是，每個位置只能在演算法中給的範圍內取值，所以直接取最大值即是答案。我不太確定我的做法是不是跟這個一樣的原因是貪的東西不一樣：我貪最大數字的最早位置，這個做法貪每個位置可能範圍內的最大值。

4. Printing Department

這天是方格存取函式庫的勝利。直接把要的邏輯寫成程式碼，細節處理 (例如八鄰域或陣列存取出界判斷) 交給過去的我搞定。

說起來好像 part 2 的刪除是少數可以邊查邊刪的狀況，因為不會有該碰得到的因為刪掉後變成碰不到的狀況。不過我還是出於習慣把待刪的點先收集起來再刪掉就是了。

5. Cafeteria

沒什麼好說的，就是整數區間的操作和運算。是不是該是時候把去年寫一半的區間運算類別給建起來了……

6. Trash Compactor

Part 1 看起來是個很無辜的「存下所有東西，運算子最後再給你」的題目，所以為了這個簡單練習了一下 C++ 用 <algorithm> 要怎麼兜出這種東西——結論是還是很搞剛，C++ 果然不是做這種高階程式設計的語言——然後看到 Part 2 說「噢其實東西是像中文直書那樣由右到左由上到下，請再做一次」差點罵出來……

然後擺在我的函式庫裡的一個意料之外的函式派上用場了：上面 Everybody codes 某題提到旋轉盤面，我其實早就有寫好正方形的旋轉函數擺著了，vector<string> 丟進去就會回傳另一個 vector<string> 是轉好的結果，所以我就丟進去左轉然後就簡單了 XD。

7. Laboratories

難得有一題是方格題但不用拉方格函式庫出來的：這題的性質直接一列列處理就好，我雖然懶惰用了一個 vector<string> 先拉輸入進來，但實際上也只有 one-pass 處理過去，這是可以邊讀邊處理的題目。

然後果然 part 2 的結果感覺怪怪的，加上這題每次拆就是兩倍顯然會有狀況，所以原本順手寫的 32-bit 變數還是改了 64-bit，果不其然答案是會爆掉的……

說起來這兩題就是今年的週末題了。看來今年整體的難度偏簡單的樣子？（補記：結果魔王不是在這裡……）

8. Playground

Kruskal 演算法實作題。當然就會有 disjoint set 的實作了。(對，disjoint set 上面 Everybody Codes 預習過了 XD Everybody Codes 的 DC 群裡不少人在說還好今年有預習到)

然後好像我要先寫起來的資料結構又變多了……

9. Movie Theater

先講結論：豪華地翻車了。大概因為最近忙著當〇之戰士的關係。

總之是個偽裝成格子地圖的計算幾何題：Part 1 求任兩點為角落形成的矩形最大多大，這可以直接算過去所以沒什麼問題，但 Part 2 告訴我們「給你的是一個格點頂點且軸對齊的多邊形，現在重做一次 Part 1 但矩形限定要完全在這多邊形內」。「矩形限定完全在這多邊形內」其實是個很討厭的條件，這跟題目的格子地圖偽裝也有關係：首先，每個座標點不是代表點而是那一塊單位方形，因此理論上會有一些邊界狀況要處理，不過看起來這題給的數字夠「寬」所以不是問題，簡單的條件例如矩形內沒有其他點和矩形邊都在多邊形內這樣綜合起來也能過。

另外一個問題則是「多邊形內」的判定：因為這是軸對齊的多邊形，幾乎一定會是凹的，所以一些凸形才能用的方式 (如判斷點是否都在邊的同一側) 就不能用。我後來選擇的是卷繞數法，就是對每條邊去判斷掃過去對卷繞數貢獻多少求和起來 (角度用內積算，方向用「外積」的正負號決定)，如果不是零就是在裡面了。然後求出了一個過大的答案。實際印出來除錯才發現我連 (0,0) 都會判斷成在多邊形裡，那這一定哪裡有問題——最後終於查出問題確實在這裡沒錯：我在求內積跟外積時溢位了……明明 Part 1 求矩形面積時有記得用上 64-bit 變數的，結果這裡忘記了 Orz。

10. Factory

終於繼 2018 Day 23 之後再次卡題了。這次和上次不一樣，不是找不到做法，而是這題是整數線性規劃最佳化問題，要實作已有的演算法會花不小的功夫就是。

Part 1 只是基本的關燈題，由於每個按鈕只有按跟不按兩種，二進位搜過去就能求得答案；但 Part 2 給定的是按完後每個數字出現的總次數，而按鈕的數目跟數字的總數不一定一樣，因此這就成了線性規劃問題：以第一個範例為例，若六個按鈕分別按下\(a,b,c,d,e,f\)次，則這相當於下列的整數線性規劃問題：

\begin{array}{rl} \min & a+b+c+d+e+f\\ \text{s.t.} & e+f=3\\ & b+f=5\\ & c+d+e=4\\ & a+b+d=7\\ & a,b,c,d,e,f\geq0\\ & a,b,c,d,e,f\in\mathbb{Z} \end{array}

六個變數四個條件，雖然可以寫出「通解」例如

\begin{array}{c} (a,b,c,d,e,f)=(2-d+f,5-f,1-d+f,d,3-f,f)\\=(2,5,1,0,3,0)+d(-1,0,-1,1,0,0)+f(1,-1,1,-1,0,1) \end{array}

但要從這裡在保持變數非負的前提下去求出目標的極小值其實仍然不是很容易。(範例給的 \((a,b,c,d,e,f)=(1,3,0,3,1,2)\) 對應於上述通解中使 \(d=3,f=2\))

其他輸入的按鈕數目和數字種類數有多有少，範例的三台機器就各有不同：第一台六變數四條件，第二台五變數五條件，第三台四變數六條件；而給的條件也不一定是獨立的，例如第二台雖然五個按鈕，但按鈕 (2,3) 和按鈕 (0,4) 各一次可以被按鈕 (0,2,3,4) 一次取代，所以實質是四個獨立條件；第三台數字 1 和 2 的條件及 0 和 4 的條件都分別是重覆的，而按鈕 (0,1,2,3,4) = (0,3,4) + (1,2)，所以實質是三個獨立條件。這些都增加了「求通解再去最佳化」的複雜度。

而直接解線性規劃呢？我還需要一點時間來搞懂 Simplex algorithm 怎麼寫……然後就沒時間當〇之戰士了 (被拖走)

補記：在 reddit 上看到一篇文章的做法沒去解線性規劃，而是利用了每個按鈕頂多只會加結果加一次的性質 (即是線性規劃條件的係數都是 0 或 1) 去做拆解。我原本不是在這裡第一次看到這個做法 (這個發表的人有在那個開了 AoC 討論串的遊戲 DC 群裡先提過一次)，但他這樣細講之後說服了我這是個可行的做法。理論上類似的做法可能對係數有界的條件都能用，但搜尋的深度很快就爆炸了；用在只有 0, 1 的這題上可能是最容易理解的。

11. Reactor

在搞事的一題之後來了一個相對輕鬆的題目。這題是標準的在 DAG 上 DP 的題目，也就是做 DP 的順序即是 DAG 的拓撲排序；Part 1 的 DP 只有一個數字，但 Part 2 就要分別紀錄說有沒有走過指定的兩個點，每個點要記四個數字。

12. Christmas Tree Farm

Eric 你……

解法

你真的要看嗎？

你真的真的要看嗎？

OK，以下是解法

先把明顯可以做的做一做吧。

……？

做了嗎？

……

做就對了。