ガード・ガリバント

コード 2024 の出現 6 日目

パート 1

とてもおなじみのパズル

• 2D グリッド
• いたるところに障害物
• パスを追跡
• 訪問した固有のタイルを数える

それでは、始めましょう!

一度に一歩ずつ

グリッドの解析:

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 へ!

パート 2

こうなるのがなんとなくわかって、怖かった

古い、有効な 1 つのパズルについて考えられるすべての選択肢をチェックしてください。

読んでいるときの私の大きな疑問は次のとおりです:

• ガードがループに入ったことをどのように識別すればよいですか?

しかし、私は知っていると思います:

• 座標だけでなく向いている方向も追跡します
• リストに次に追加されるリストのコピーが含まれている場合、ループが開始されます

物事をさらに複雑にする時が来ました!

各セルをループしてすべてのループを見つける

まず、ガードの開始セルを除く、. を持つすべてのセルのリストを生成したいと思います。

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 は、大変ではありましたが、規模の拡大は歓迎すべきものでした。

バッグの中にさらに 2 つの金の星があります!

7 日目へ。

以上がガード・ガリバントの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。