一年一度的 Advent of Code 又來了，應該不需要多說了吧。
這裡就來順便更新一下我的近況好了。最近工作上遇到了一些狀況，比較不怎麼有心力去做之前計畫好的事；去年這時說到的 AoC 相關的東西的收尾結果一丁半點都沒動還是卡在那裡，然後接下來有一個我想丟出來的東西會要趕快先搞定。因此就變成了連續兩年空轉的部落格……
11 月時倒是因為這樣跑去做了另一個人的算是熱身賽 (?) 的站叫 Everybody Codes (有他的參賽者貼去 Advent of Code reddit 版我才知道的)，照這站長的計畫好像未來應該都會在 11 月時出新題，而今年他的題目雖然有一點偏 (最後這兩週我沒引入我的 BFS／A* 函式庫的次數好像屈指可數)，不過確實算是滿用心在做的。期待未來有沒有更有趣的東西。
那麼照例文章押 12/1 發出，但接下來每天都會更新當天的題目心得；以及一直都有的 github repo 連結。
1. Historian Hysteria
星期日的第一天感覺不太能搞太奇怪的東西，所以果然還是只能在輸入上搞事。只是看起來交錯輸入這種事驅離 AI 的效果沒有去年的字串處理問題那麼好，今年好像有人 4 秒 + 5 秒上榜的樣子……
然後我對我竟然記得 C++ 有 transform_reduce 這個函數小小嚇了一跳。還不是一般版的 inner_product 喔，是那個可以平行化的版本。
2. Red-Nosed Reports
感覺又是個會被 AI 秒殺的一題。看起來今年 Eric 比較收斂了一點，去年前幾題 (特別是第一題) 搞成那樣可能他也嚇到了吧。而且今天開題時有約兩分鐘網站是掛點狀態的，我通個靈猜大概是被秒殺的 AI 給衝爆了吧。(補記：結果好像不是的樣子？有人說開題前十分鐘就掛了)
基本上沒什麼好說的就是刷過去檢查對不對就行了。然而我在 Part 2 因為稍微取了點巧而在要忽略第一個元素時不小心多比較了必定失敗的一次所以吃了個 WA。(嘆氣)
開題兩個半小時補記：結果到現在看到的四篇的 reddit 求救文都是過於相信前兩個數，用它們來決定要看遞增還是遞減，所以當拐人的是第一或第二個數時就被拐走了。
3. Mull It Over
這題根本就是開口大叫「去用 regex！」的題目 XD 連我這個自認為字串分析是我的強項的都覺得「啊就 regex 丟下去就好了」。只是 C++ 的 regex 稍微笨重了那麼一點點就是了。(那是 C++11 時代的產物所以有一點當時的「風格」在)
然後不知為何我忘了在 | 之後的 () 組不會重新從 1 計數，所以在想明明敘述抓到了怎麼抓不到指令……
補記：啊，差點忘記一件事：這題的輸入檔不只一行。我因為想到 regex 的.會因為設定不同可能會不去抓換行，所以在寫之前先 wc 了一下，然後看到它回報六行……XD 還好這就只是多加一個迴圈而已所以問題不大。
4. Ceres Search
差點忘了更新第四題。這題表面上是個很普通的找字遊戲 (我的實作上也確實很簡單)，不過邊界處理問題果然還是咬的大家不要不要的。Reddit 上這題的問題最大宗的有兩個，都是邊界問題：一個是把 2D 接成 1D 然後用跨 N 個字當做下一列的找法，另一個則是 python 的負索引。有些人有這個問題的還只有一個方向，因為他們輸入之後沒有去掉換行直接找，所以跨左右邊界的會踩到換行字元沒事，但 python 負索引跨上下邊界的就出事了。
我呢？兩年前寫好的二維陣列存取函式庫早就把邊界處理給做好了，所有通過那邊的存取全部會檢查邊界，超界的話會回傳一個固定的邊界字元；這相當於把輸入圍一圈絕對不會出現的字，然後就直接條件寫下去，超出邊界的查詢會被那一圈字擋下來肯定不會出問題。所以難得在這麼早的一題拿到了三位數的名次。
不過也是因為做了 Everybody Codes 讓我稍微延伸了這個二維存取函式庫，允許在有指定時把上下或左右給接起來。原本是那邊的 20-3 題要我在一個上下接起來的地圖上尋徑，然後想想這種存取好像有時會很有用所以簡單寫起來了。如果 AoC 這邊有碰到要接的可能就會推上來吧？
5. Print Queue
是個比起前幾天來說都相對直接的題目。於是順順的寫下去看到 part 2 要把它排好……唔嗯，看起來是個 std::sort()，那就用下去吧。通了回頭想想，咦這不就表示 part 1 可以用 std::is_sorted() 秒掉嗎？馬上改了一下果然簡潔好多。不過這似乎需要題目提供的順序是全序才行，照看起來好像是的樣子：我的輸入檔第一部份有 1176 行，是 49 個元素的全組合。
補記：原來輸入的這 49 元素全組合裡是有圈的……看了一下我的輸入，好像是所有人都是在 24 個之前 24 個之後，所以是一大圈的意思嗎？不過這樣一來，因為這個大圖有圈，要使輸入能有排序結果必須要給全組合，否則因為圈的關係完全不能推理。
6. Guard Gallivant
模擬題。不知為何我的 part 2 總是有奇怪的 bug，所以為此決定把一些之後要再加在二維陣列存取的東西給加進去了：一個是把「座標+方向」打包變成一個「移動物」，這個比較小一點；另一個則是讓我能用一個 ranged-based for 來把整張表走過一次，也就是這個陣列存取物件要把它變成類 container 了。因為很難會需要隨機存取所以它的 iterator 是 ForwardIterator，不過倒是塞了一個小功能是直接把 iterator 轉成座標。
回到題目。Part 1 的經過點其實就是給我們一個提示說，全部 17K 個點只有約三分之一的 5K 個點是要考慮的，不用全部都跑一次。在勉強送過之後我繼續研究這 part2 要怎麼改才好，東拉西拉最終定版的版本是：做跟 part 1 一樣的模擬，但在每一步後都試試看在警衛前面放障礙物，能放的話就先岔出一條世界線跑被這個障礙物擋住的狀況。原本是用 unordered_set 來找迴圈，不過後來我想到我不用找出在圈哪，只要找到有圈就好，那就能用龜兔賽跑演算法的簡單版來找圈了。最後我每次都會忘的 -O3 開下去果然不到二十分之一秒就收工了。
7. Bridge Repair
由左算到右一副看起來就是 DP 題的樣子。不過即使加了把中途結果太大的給丟掉的最佳化全部跑完還是要大概四秒的樣子。
說起來我稍微研究了一下數值範圍。能產生數字的大小顯然是加法 < 乘法 < 連接，所以只要全部連起來沒有爆那中途就不可能爆；原本我以為這題會有更大範圍會爆炸的數值，但看起來在 253 的硬上限之下題目也不能出太扯，試著掃了一下也發現題目給的數字連起來最多就 15 個，全連起來也都小於 1015 所以絕對不會有事。似乎這就只是要抓 (不小心) 用了 32-bit 的人而已的樣子。
一個有趣的不怎麼題外的題外話：Reddit 上有一個很令人？？？的錯法是：他們處理輸入後把每一行放到一個以目標數值為 key 的 hashmap 裡，然後就被偶然出現的不同行但有同樣目標數值的狀況給婊到了……照大家的回應看起來應該只有部份人的輸入有這種狀況，因為有看到回應說用這樣寫的程式用在回應者的輸入上是有正解的；但也沒有少到少數輸入，因為到我寫下這段文字為止 (開場約三個半小時) reddit 上有這個問題的人已經至少有四個了……
補記：然後有篇文章點出了我的盲點了：以這題這種限制式的狀況，從右到左算會比從左到右算效率來得好。由左到右只有超出範圍的狀況可以剪掉，但由右到左的話，加法跟原本一樣可以剪掉太小的，但乘法可以剪掉不能整除的，連接可以剪掉尾數不對的，這樣縮小嘗試的方式可以刪掉一堆不合的狀況。改了個右往左的版本甚至沒開最佳化都是瞬間出答案。
8. Resonant Collinearity
線性代數題 (大誤)。好啦其實沒有什麼太高大上的計算，不過就是個座標跟向量的加減運算問題而已。正好座標跟向量是我的二維陣列存取函式庫裡的基本計算類別，所以就直接拿來用了。（設計上有一個 Coord 類別存座標，Vector 類別存向量，然後有些加減型態的改變例如兩個 Coord 相減得 Vector，Coord 加 Vector 會變成另一個 Coord，所以 part 1 的兩點就是 c1+(c1-c2) 跟 c2+(c2-c1) 了)
不過初版程式碼的 part 2 因為算錯邊，所以原本只有算在兩個天線外面的座標點，結果也答對了？！這是不是代表題目的輸入沒有會算到中間的狀況，所以原本以為會需要的 gcd 計算其實是不必要的？！這是 Day 8 題的難度嗎？！？！
9. Disk Fragmenter
啊，磁碟重組程式。那已經是古老的回憶了呢 (遠目)
咳。於是今天也是模擬題。不過兩個模擬的方式適合的資料結構不太一樣：part 1 是區塊為單位所以是 id 的陣列，但 part2 是檔案為單位所以是〈id, 長度〉的鏈結串列比較適合。我大概可以想像今天的 reddit 會有什麼樣腥風血雨 (X) 的 bug 文章了。
……然後，前兩篇 Day 9 的求救文是被題目範例的一位數 id 給騙了，以為每一個區塊都只有一位數，所以 10 號以上不知道要不要做什麼處理……我是有心理準備會有怪問題啦，但這也太怪了點 Orz
算是不怎麼有關的：我今天把我的輸入函式庫也加入跟上面二維陣列存取函式庫一樣的 range based for 支援了。這樣就不用一個很彆扭的 lambda callback 寫邏輯，直接寫成普通的 for 迴圈即可。
10. Hoof It
很標準的尋徑題，而且因為尋徑長度固定是 10 所以甚至直接來也沒什麼問題。有些寫法的 part 2 應該會比 part 1 簡單，不過這兩部份到底哪一個真的「簡單」也很難說就是了。(然後 reddit 前五篇 Day 10 文就都是讀錯 part 1 但解了 part 2 的迷因 XD) 我本來 part 2 要想一下怎麼改的，結果改完發現其實可以寫在一起，所以就變成同時計算兩部份了。
11. Plutonian Pebbles
看到這種跟 look-and-say 有相似行為的東西應該要想到 part 2 會一次問更久之後……。不過也因為這樣，在 11 月熱身時寫起來的 cache 化函數派上用場了；當初設計這個 cache 化就是只要裡面擺函數，cache 的邏輯不用寫在函數裡，會用類似 Decorator pattern 的方式裝飾上去，為了 template 介面合理當初傷了不少腦筋 (後來因為不定參數模板很難寫，所以就只寫最多兩個參數的了；要更多參數的話再說)。好處就是今天要用時直接寫好邏輯，外面掛 cache 化就直接用了。
……是說，這題是不是跟三年前燈籠魚那題很像……？
12. Garden Groups
微妙的不知道要不要算做計算幾何的題目。題目是問由格子合成的多邊形的面積、周長和邊數。面積淹個水就好，周長在淹水的同時往外面看一看也行，問題是邊數。
正在我在想要不要跟去年一樣搬皮克出來的時候突然靈光一閃：我不要算邊數，我算角落數就好啦！於是事情就變得簡單起來了：只要檢查每一格的四個角是不是所在多邊形的角即可。詳細條件是，當我們在下圖中的左上角的 A 時，數滿足以下狀況的角落數：
AX AA
Y* AX左邊數往外彎的角，* 不判斷使對角連接的點算兩次；右邊數往內彎的角，三個 A 只讓這個 A 計入計數。這樣數過一邊之後就是總角落數，也就是總邊數了。
13. Claw Contraption
……一個純到不能再純的國一數學題。這題擺在這裡是要唬那些數學不耐症的人嗎 Orz 所以當然答案就是克拉瑪直接上了。Part 2 加的 1013 就只是在要解題者去找數學解而已。
什麼？輸入分析？前年早就寫了只讀數字的函數就用啦。
14. Restroom Redoubt
果然前一天輕鬆就是表示這個週末不會太好過。Part 1 是個很基本的模擬題，比較不一樣的就只是地圖是傳統(?)的拓撲甜甜圈地圖 (即是上下跟左右連通)，以及要算的分布是個類似「象限」的東西。
Part 2 就好玩了。Day 11 時 reddit 上有張迷因說當 part 2 題目越短就會越可怕，今天當然也不例外：它說這些機器人在跑的時候，偶爾會組成一個聖誕樹的形狀，問最快何時會出現？——問題是，到底那棵樹長怎樣？！我要怎麼在程式裡寫出「這裡有棵聖誕樹」這樣的條件？！？！
實在沒什麼點子只好隨便考慮一下：既然會組成一個圖形，那表示 (幾乎) 所有人的位置應該都在附近，這樣的話我只要把每對的距離和求出來找最小值，大概就會在附近。求每對的距離和這件事去年 Day 11 就做過了，用我在那裡提到的排序+線性時間做法可以很快掃完全部 101×103 個狀態。幸運地最小值所在的圖形真的出現了要求的聖誕樹所以那就是答案了。
15. Warehouse Woes
如標題所述，今天的題目是倉庫番模擬題。所以基本上沒什麼好說的就是跑下去就對了，是對是錯把中間過程印出來就會知道哪裡不對。
算是有點相關的題外話，我前陣子在噗浪上轉了篇影片在講一個沒什麼玩過解謎遊戲的玩家因為《Void Stranger》跳進了倉庫番遊戲的坑裡的心路歷程。今天的題目其實讓我想到另外兩個沒在那噗裡提到的倉庫番遊戲：《The Golem》和《Jelly is Sticky》。雖然今天的題目只有兩格大的方塊，但這個一次推動數個連在一起的方塊的概念確實不算少見就是了。
……喔對了，Eric 的惡趣味幽默果然很有趣：由於今年是十週年，今年的故事基本上是過去的精彩大回顧；然後今天的題目故事就正好回顧到三年前的燈籠魚，雖然題目裡有連過去不過實際要做的題目基本上無關。然而上面我也提到過 Day 11 的題目跟燈籠魚那題的 part 2 有異曲同工之妙，而且由於收斂狀態集的大小夠大1還不能用當年的超快解矩陣乘法來做，讓不少人看到提到燈籠魚就一股 PTSD 上來了 XD
16. Reindeer Maze
……怎麼有種我們又陷入地圖題迴圈的錯覺了。
Part 1 就是個很標準的單源最短路徑，但 Part 2 就麻煩了。理論上 Dijkstra 是有辦法紀錄路徑啦，但我懶……於是我的懶人 (X) 做法是在尋徑中紀錄過程中每一點的最短路徑長度，然後自最短路徑最長的往回找，對每一個有紀錄的點檢查是否它有後繼也在對應長度的紀錄中，如果沒有的話就把這一點拿掉。(也就是倒回來把「死路」給消掉就是了) 由於腦袋因為一些原因還是有點昏昏的，條件寫了好幾次才寫對，好在沒有吃到 WA 就是了。
17. Chronospatial Computer
去年沒出的抽象機器題出現了——結果輸入不是組合語言而是類似 intcode 的機器語言。原本以為之前寫的函式庫要上場了結果沒用到。Part 1 基本上就是跑下去就對了，但 part 2…好吧，看來又是一個要拆輸入的日子了。
補記：這天我的某篇回文拿到了個人 reddit 最高讚數了——那是在一篇告訴大家 JavaScript 做這題會有問題要用個方法閃的文章，我在下面解釋原因：因為 JavaScript 在做位元運算時會把數值轉成 32-bit 整數再做的關係。這一點我覺得是 Eric 的小失誤，不過 (1) 如這篇文章所說這是有辦法閃的 (最簡單的方法是 BigInt)，(2) 寫的方式對的話其實理論上讓它截斷到 32-bit 其實好像影響也不大的樣子。
18. RAM Run
很有趣的一題。Part 1 還只是一般的尋徑題而已，part 2 則就是繼續打掉地板問什麼時候不通了。連同我的做法，在 DC 群裡已經看到了四種不同解：
算是一個足夠有趣 (題目方面跟解法方面) 的題目。
補記：在 reddit 上看到了一個另解四：
19. Linen Layout
聽說這題是 MTG 梗題？因為題目中的五個顏色正好是白(W)、藍(U)、黑(B)、紅(R)、綠(G)，連順序跟代號都一模一樣。
總之這題是頗為普通的 DP 題，大概是那種教完 DP 之後的練習題那種程度。恰好今天題目中連到的 2023 Day 12 是那題一維數織，也是個結構類似的 DP 題。我則是在寫 part 1 時反正就順便所以把組合數也一起算出來了 (還提早發現組合數會溢位)，所以兩部份通關的間隔只有 92 秒，算是個人除了 Day 25 part 2 之外的紀錄了吧？
20. Race Condition
怎麼今年這邊也是一堆二維尋徑題…
不過說是尋徑，題目都告訴你路徑是一本道了，所以這題其實是要你把路徑收集起來再來做跳格運算。我在 part 1 時沒搞懂這一點，所以弄了一個帶作弊情形的狀態去跑尋徑，想當然爾在實際問題上就爆狀態數了；所以只好乖乖的把路徑求出來再來跳。part 2 改範圍時就只是把跳格的範圍改大一點而已。
其實 part 1 時還因為一個語意問題搞混我好一段時間：題目雖然說作弊持續 2 皮秒，但因為 2 皮秒後的所在位置要是路上，所以其實只能穿一格牆；我把 2 皮秒當成可以穿兩格牆所以實作的亂七八糟的…
值得一提的是，題目剛出時在 part 2 有個敘述是：
If cheat mode is active when the end position is reached, cheat mode ends automatically.
但這會造成一個邊界狀況是當作弊起終點和路線終點在同一水平或垂直線上時，會因為這條規則而取消直接走過去的那唯一路徑，所以會使計算出問題。Eric 表示說這是一個測試者給他的建議，不過因為在開題的數小時內暫時連絡不上對方無法確定當初的用意，所以他先把這句話拿掉了。理論上照現在能過 part 2 的人的做法的話，這句話應該要反過來說變成「在作弊狀態下無法到達終點」之類的吧。
補記：該測試者出面了 XD 看起來他也同意用和我上面提的類似的語句來改動，不過反正這一條是確定拿掉了沒錯。
21. Keypad Conundrum
看到題目的第一印象：這是 reYal 吧？！(然後 DC 群裡的另一個人說這個是 Press Ctrl )
總之就是個如同上面兩個遊戲一般操作的操作的操作模擬器。我一開始的思路其實整個卡住了，想著從 N 層的結果下去求 N+1 層的最小值，然後才光兩層而已可能性就開始爆炸了，更不用說 25 層。更麻煩的點在於兩個盤面都有不能移到的格子：數字盤 0 的左邊和方向盤上的左邊都不能移進去，再加上 A 鈕位置的不對稱性，幾乎沒有公式可以套。
吃了點東西腦子比較清楚之後才想通怎麼倒過來求；重點在於按下某層的一個按鈕需要所有它下面的層全部按 A，也就是我們的序列可以在這裡打斷，前面做完後下面所有層都在 A 所以所有接下來的移動也都是從 A 開始。於是我可以去求讓 N 層前方向鍵盤上自某按鈕起移到另一按鈕按下的此層最短步數，然後第 N+1 層前的就去列出他要在第 N 層的按法有多少，哪一個總長度是最短的記下來。也就是題目變成一次 25 格的大 DP 了。最後一層的數字鍵則一樣列出在其前一層有哪些按法，去求總長度最短就是答案了。
最終我通關時間是開題後四個半小時，但 part 2 的全球名次才快 2000 人…這題果然夠難。
22. Monkey Market
哎呀，那些大數猴子又回來了 XD 今天的題目，part 1 是擬隨機數模擬這個沒什麼好說的，但 part 2 變成看這些擬隨機數出的趨勢賣股票藏身處了。說實在話心情有點微妙的複雜：因為最近工作上在做的專案和這個有擦上了個那麼一點點關係。嘛總之，在產生價格後滑動求出最近四個變化量的組合，然後丟去一個陣列儲存說有沒有看過這個組合，有就把對應價格加進去，最後再掃一次全部的組合狀況找出總賣價的最大值。
不過在昨天這麼重量級的一題之後，今天則只是單純的大量模擬題，最後兩天難度或許可能繼續停在這個程度？
23. LAN Party
我猜錯了…果然有大炸彈在最後。
今天的題目很單純的給你一個圖。Part 1 只是求出所有的 K3 子圖，然後問這些子圖中有哪些包含某一群節點；part 2 就是大炸彈了：要你求這圖的最大團——沒錯，我們又有一題 NP-Complete 題目了。鑑於我腦子裡沒有記過有什麼演算法可以用，只好在維基百科上找一找，然後找到了 Bron-Kerbosch 演算法可以列出所有極大團。把有 pivot 的版本實作起來跑還算滿快的，它找到的極大團再去比較團的大小找最大的團輸出就行了。
24. Crossed Wires
我又猜錯了，但不得不說這題雖然也是重題，但重得很剛好。
Part 1 就是之前也出過的邏輯閘模擬題，但 part 2 就有趣了：它告訴我們這份輸入是個 N 位元的加法器線路 (事實上它是所謂的波紋進位加法器，基本上跟手算結構一樣的那一種)，但其中有四對輸出接錯了，要我們找出這四對。這是個把線路圖畫出來用眼睛看比用程式去找還容易的題目。而且這題出的很佛，接錯的點都只限定在單一個位元的全加器裡面，沒有跨位元的接錯點。(有的話還滿有可能會接成迴圈，那就麻煩了)
25. Code Chronicle
照例的 25 號題是簡單收尾題。為了首尾呼應 (？)，雖然簡單寫過去過了但還是改了一個用了 inner_product 的版本，個人感覺還算不賴。
全年總結等我今天下班吧。
註腳
- 有人用了點數學加上實際寫程式計算過，Day 11 這題的收斂集大小約有四千個數字，顯然模擬 75 輪用這種大到離譜的矩陣乘法來做是自找麻煩。 ↩︎