Advent Of Code 2019, Day 15

最近看 Rust 好像還蠻紅的，想說不如趁著工作比較沒那麼忙的時候試著用它來做做看 Advent Of Code，這幾天做得還蠻起勁的… 這兩天被第 15 天的題目卡了超久，結果發現都是卡在一些其實想通了就會覺得很蠢的地方，想說不如紀錄一下。

Why Rust?

原本有想過與其學一個之前完全沒有碰過的語言，倒不如把一直以來學得零零落落的 Haskell 好好地用熟跟搞懂，但是 Cargo 做為一個包管理器實在是太好用了，相較之下 Haskell 的 stack 在之前使用的經驗上就比較麻煩，我到現在還是搞不懂什麼時候該 stack install 什麼時候不該。 (理論上貌似是根本就不該做這件事情，但是好像很多執行檔的官方安裝教學都是在使用這個指令？搞不懂…)

另外 Rust 比起 Haskell 這種純到不能再純的函數語言，在程式的自由度上我覺得還是高上不少，至少那些 C++ 裡面很常見的資料結構諸如 vector、 hash map 跟 hash set 之類的，在 Rust 裡面的用法其實也跟 C++ 裡的沒太大差別。反觀 Haskell 光是 map 要怎麼樣更新我到現在都還沒搞清楚過… 可能實際上沒那麼難？網路上我看過幾乎所有學會 Haskell 的人都說只要一旦能搞懂單子到底在幹嘛的時候，基本上就可以算是半通了，之後有空有心情的時候再看看吧。

Rust 實際上使用起來，我覺得最爽的點是在於它的編譯器丟出來的錯誤訊息，與其說是跟你講說哪裡做錯哪裡編不過，更像是跟你講說哪個地方的錯誤該用什麼方式修改。 Rust 當然也是有些東西 (e.g. 聰明指標那部分) 個人覺得設計得有點反人類，可能要真的很常用才會比較熟悉整套 Rust 語法的系統。但是 Rust 編譯器會跟你講說是哪一變數的 lifetime 不夠長、哪一行忘記 dereference、哪個變數在宣告的時候忘記加上 mut (Rust 所有的變數預設都是 immutable 的，需要加上 mut 才能夠在宣告之後去改動變數的值) 等等，其實只要照做就可以修掉那個錯誤。

最後就是 Rust 本質上是強型別語言，前幾個禮拜在狂刻 Python 的我重新碰到一個會幫我做 type checking 的語言真的是還蠻感動的。

Advent Of Code?

基本上就是一拯救聖誕老公公的解題遊戲，但他的 puzzle input 都不是有辦法用人肉 parse + 計算的類型，然後好像是亂數產生的，還算有趣。似乎是每年年底會舉行？

What’s in day 15?

在前幾天裡已經做了一台能夠讀取程式碼並做出相對應反應的電腦，能夠對送進來的程式碼做讀寫修改，同時也能吃外部送進來的輸入值，跟把值輸出到外部。

在這題裡面，我們要當一個二維平面上面的機器人，平面上會有牆壁擋路，而我們要想辦法走到一個事先不知道位置，只有抵達時才會知道位置的點。機器人一開始是待在 (0, 0)，可以朝北南西東四個方向前進。如果機器人想朝北前進，就要把 1 輸入進電腦裡，電腦會輸出 0 (前面是擋路的牆，不能走)，1 (前面沒有東西，可以前進到這格) 或是 2 (此移動後抵達終點)。想要朝南則是輸入 2，朝西是 3，朝東是 4。

第一小題是要算出從起點到終點至少會需要幾步路。

第二小題是要算從終點開始，要花多少時間才能把整個地圖上可以填的地方 (也就是不是牆壁的格子) 填滿：

(#：牆壁，*：終點，.：還沒被填過的格子，O：被填過的格子)

t=0:

##.##..#.
##....#..
#.#.*...#
...#.###.
.#.......

t=1:

##.##..#.
##..O.#..
#.#O*O..#
...#O###.
.#.......

t=2:

##.##..#.
##.OOO#..
#.#O*OO.#
...#O###.
.#..O....

t=3:

##.##O.#.
##OOOO#..
#.#O*OOO#
...#O###.
.#.OOO...

t=4:

##O##OO#.
##OOOO#O.
#.#O*OOO#
...#O###.
.#OOOOO..

t=5:

##O##OO#.
##OOOO#OO
#.#O*OOO#
..O#O###.
.#OOOOOO.

t=6:

##O##OO#O
##OOOO#OO
#.#O*OOO#
.OO#O###.
.#OOOOOOO

t=7:

##O##OO#O
##OOOO#OO
#O#O*OOO#
OOO#O###O
.#OOOOOOO

t=8:

##O##OO#O
##OOOO#OO
#O#O*OOO#
OOO#O###O
O#OOOOOOO

在這邊的話需要 8 個單位時間才能夠把整個地圖上所有能夠填的格子都填滿。

How to solve this damn thing?

第一題

我主要是在第一題的時候卡關，卡在一個很呆的點… 我一開始覺得只要用簡單的 BFS 去不停地看目前所知的格子之中，哪些格子可以走到相鄰的未探索的格子，這樣不停地去拓展 frontier，可以很快地就找到終點。但是我忘記要探索一個新的格子時，機器人必須先走到那個格子的旁邊才有辦法：(?：下個要探索的，#：牆壁，O：可以走的格子，*：機器人目前所在地，：機器人還不知道可以探索的格子)

grid:

   ?##O###
  #O#OO#OO
  #OOO#OO#
 #OO####O*
  #OOOOOO#

所以為了要探索左上角的 ?，機器人必須從右下角一路走到 ? 下方的格子，才能夠進行探索：機器人不能瞬間傳送，沒辦法在右下角遠端探測左上角待觀測的格子。

在我的實作裡面，機器人需要記下目前走過的地圖、當前的方向、現在所在的格子，以及下一個需要探索的格子。機器人會輸入自己目前的方向到電腦裡面，再根據電腦的回答來判斷是不是能夠前進到下一個格子裡面，如果可以的話就更新目前所在的格子為下一個格子。

接下來再算出周遭的格子哪一格可以被作為下一個可以前進的選項：如果周遭有還沒有探測過的格子，那就將它作為下一個格子，並算出從現在的格子走到下一個格子的方向是什麼。如果周遭的格子都探測過了，則選擇周遭格子內所需步數最少的格子作為下一個格子，另外因為我們不希望重複走過之前走過的路，所以把周遭格子之中不是下一個格子，但也不是牆壁的格子的步數設定為很大的數字 (1,000,000,000)。

fn get_next(&mut self) -> Coordinate {
    let c = self
        .current
        .neighbors()
        .into_iter()
        .filter(|c| !self.map.contains_key(c))
        .next();
    if let Some(result) = c {
        return result;
    }
    let result = self
        .current
        .neighbors()
        .into_iter()
        .filter(|c| self.map.get(c).unwrap().0 == Tile::Empty)
        .min_by(|x, y| self.get_cost(&x).unwrap().cmp(&self.get_cost(&y).unwrap()))
        .unwrap();
    for n in self.current.neighbors().iter() {
        if *n != result {
            let v = self.map.get_mut(n).unwrap();
            if (*v).0 == Tile::Empty {
                (*v).1 = 1_000_000_000;
            }
        }
    }
    result
}

Rust 好用的點我覺得就是那些 iterator 跟 map / filter methods，不然整天都在寫迴圈，一堆大括號看了就頭暈。

第二題

第二題反而可以用第一題我原先搞錯的做法來做，直接用 BFS 來探索還沒被填過的格子。

fn get_time(&self) -> Option<u64> {
    let os = self.oxygen_system?;
    let mut result = 0;
    let mut visited: HashSet<Coordinate> = HashSet::new();
    let mut frontier: Vec<Coordinate> = os
        .neighbors()
        .into_iter()
        .filter(|i| self.get_tile(i) == Some(Tile::Empty))
        .collect();
    visited.insert(os);

    while !frontier.is_empty() {
        let mut new_frontier = Vec::new();
        for c in frontier.into_iter() {
            visited.insert(c);
            let mut neighbors = c
                .neighbors()
                .into_iter()
                .filter(|i| self.get_tile(i) == Some(Tile::Empty) && !visited.contains(i))
                .collect();
            new_frontier.append(&mut neighbors);
        }
        frontier = new_frontier;
        result += 1;
    }
    Some(result)
}

Rust 沒有像 Python 裡的 None 或是 C / C++ 裡面的 NULL 之類的東西，而是用基本上跟 Haskell 的 Maybe 完全相同的 Option<> 來包住一個可能有也可能沒有值的變數。但 Rust 裡面的這種 functor (感覺上 Rust 的 functor 跟 iterator 好像是同一件事情？) 又跟 Haskell 裡面的 monad 感覺不太一樣，自己的感覺是 Rust 的型別反而比 Haskell 的再沒限制一點。

Codes

GitHub

用兩個機器人的 struct 應該是完全沒必要的，但實在是懶得 refactor 了…