加里凡特衛兵

代碼來臨 2024 年第 6 天

第 1 部分

一個非常熟悉的謎題

• 二維網格
• 到處都有障礙
• 追蹤路徑
• 計算造訪過的獨特圖塊

讓我們開始吧！

一次一步

解析網格：

let grid = input.split('\n').map(el => el.split(''))

辨識守衛的起始位置並將其替換為空圖塊：

let guard = null;
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

建立一個物件來追蹤守衛目前的旋轉：

let facing = [
  [-1,0],
  [0,1],
  [1,0],
  [0,-1]
]

• 守衛開始面向北，因此後續移動需要存取較小索引的行
• 遇到每個障礙物，警衛必須右轉
• 這將使她面朝東方，因此後續移動需要訪問更大指數的列
• 每次下一個單元格成為障礙物時，我的演算法都會從清單中拉出第一個項目並將其移到後面

追蹤存取的儲存格：

let visited = new Set()

每次移動時，我都會嘗試將字串化座標新增到此 Set() 中。

移動守衛：

while (true) {
  visited.add(guard.join(","));
  let next = [guard[0] + facing[0][0], guard[1] + facing[0][1]];
  if (
    next[0] >= 0 &&
    next[0] < grid.length &&
    next[1] >= 0 &&
    next[1] < grid[0].length
  ) {
    if (grid[next[0]][next[1]] == ".") {
      guard = next;
      console.log(guard);
    } else if (grid[next[0]][next[1]] == "#") {
      let oldDirection = facing.shift();
      facing.push(oldDirection);
    }
  } else {
    break;
  }
}

解釋：

Keep going until manually broken out of
  Add the current coordinate to the tracked list
  Record the next location to visit
  If it is within the grid
    If it is empty cell
      Move the guard
    Else If it is an obstacle
      Rotate the guard
  Else
    Break out of the loop

演算法成功為範例輸入產生了 41 個已訪問儲存格清單！

它會為我的拼圖輸入產生正確的答案嗎？

是的！ ！ ！

太棒了。

進入第二部！

第2部分

我有點預見到了這一點，並且很害怕它

老兄，檢查每個可能的選項以獲得一個有效的謎題。

閱讀時我最大的問題是：

• 如何辨識守衛何時進入循環？

但我想我知道：

• 我會追蹤朝向以及座標
• 如果清單包含下一個新增的副本，則循環即將開始

是時候讓事情變得更複雜了！

循環遍歷每個單元格以找到所有循環

首先，我想產生一個包含 . 的所有單元格的列表，不包括守衛的起始單元格：

let empties = [];
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == ".") {
      empties.push([r, c]);
    }
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

然後，使用reduce 來迭代每個.在網格中，複製網格和原始防護位置，在reduce內移動大量原始代碼，擴展while循環以包含跟踪坐標和具有當前狀態實例的旋轉列表的條件：

let part2 = empties.reduce((count, coord) => {
    let guardCopy = guard.slice()
    let gridCopy = grid.map(row => row.slice())
    gridCopy[coord[0]][coord[1]] = "#"
    let facing = [
        [-1,0],
        [0,1],
        [1,0],
        [0,-1]
      ]
    let visited = new Set()
    while (true) {
        let stamp = guardCopy.join(',') + facing[0].join(',')
        if (visited.has(stamp)) {
            count++
            break;
        } else {
            visited.add(stamp);
            let next = [guardCopy[0] + facing[0][0], guardCopy[1] + facing[0][1]]
            if (
              next[0] >= 0 &&
              next[0] < gridCopy.length &&
              next[1] >= 0 &&
              next[1] < gridCopy[0].length
            ) {
              if (gridCopy[next[0]][next[1]] == ".") {
                guardCopy = next;
              } else if (gridCopy[next[0]][next[1]] == "#") {
                let oldDirection = facing.shift();
                facing.push(oldDirection);
              }
            } else {
              break;
            }
        }
    }
    return count
}, 0)

很多。

但是它有效！至少在範例輸入上。

它對我有用嗎？ ？ ？

嗯...運行了 30 秒。

但是...它產生了答案！

這是...

正確答案!!!

嗚呼！ ！ ！

第 1 部分很容易。第 2 部分是一個艱難但受歡迎的規模提升。

袋子裡還有兩顆金星！

進入第 7 天。

以上是加里凡特衛兵的詳細內容。更多資訊請關注PHP中文網其他相關文章！