セレス検索

コード 2024 の出現 4 日目

パート 1

X は (数百?) のスポットをマークします。

これまでこのような文字通りの単語検索パズルがなかったのには驚きました。

気の遠くなるような気がしますが、私の戦略は次のとおりです。

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

この戦略を例で確認すると、これが勝利のアプローチであると確信できます。

ここからはエキサイティングな部分です。この全体を最初からコーディングします。

グリッド内の各 X のインデックスを見つけます...最終的には

まず、入力を文字の 2D 配列に解析する必要があります。

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

グリッド パズルでよく直面する障害は、範囲外のインデックスを考慮することです。

境界セル (または境界に近いセル) から開始して、端に向かう方向にずっと歩いていくと、最終的には境界外の行または列に遭遇することになります。

これに対処するための 2 つの戦略があります:

1. 存在しない行または列の条件にチェックを追加します
2. 範囲外になる危険がないように、グリッドに十分な行と列を埋め込みます

このチャレンジでは、#2 を選択します。

グリッドを 3 セルの太さの境界線でパディングすると次のようになります:

grid = grid.map(line => ['.','.','.',...line,'.','.','.'])
grid = [
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  ...grid,
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.')
]

グリッドの例は次のようになります:

................
................
................
...MMMSXXMASM...
...MSAMXMSMSA...
...AMXSXMAAMM...
...MSAMASMSMX...
...XMASAMXAMM...
...XXAMMXXAMA...
...SMSMSASXSS...
...SAXAMASAAA...
...MAMMMXMMMM...
...MXMXAXMASX...
................
................
................

これで、パッドされたグリッド内の各 X の座標をカタログ化する準備ができました。

let Xs = []
for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[0].length; col++) {
    if (grid[row][col] == "X") {
      Xs.push([row, col])
    }
  }
}

成功: 例のグリッドで 19 個の X がすべて見つかりました!

各 X から 8 方向に 3 歩歩きます。

8 つの相対座標はすべて、8 要素の配列としてコード化されます。

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

次にメインのアルゴリズムについて説明します:

For each X
  For each direction
    Create an array that starts with X
    Do 3 times
      Move one cell in this direction
      Add the value of that cell to the array
    Check whether the concatenation of all four values is "XMAS"
      If it is, increment a tally

JavaScript では:

Xs.reduce((total, coord) => {
  dirs.forEach((dir) => {
    let [row, col] = coord;
    let [y, x] = dir;
    let word = ["X"];
    for (let i = 0; i < 3; i++) {
      row += y;
      col += x;
      word.push(grid[row][col]);
    }
    if (word.join("") == "XMAS") {
      total++;
    }
  });
  return total;
}, 0);

入力例に対する正しい答えが生成されます!

パズル入力で実行すると何が起こるでしょうか??!!

数字を取得しました:数千の「XMAS」

それは正しい答えですか?

そうです!!!

うおおお!!!

パート 2 では何が行われるのか楽しみです...

パート 2

ああ、私の。これはもう少し複雑になりました。でも実行可能！

パート 1 では X を探していました。

今、私は

さんを探しています。

パート 1 では、文字を直線で記録して単語を作成しました。

今、5 セル フレーズの 4 つの構成を探しています。

M S   M M   S M   S S
 A     A     A     A
M S   S S   S M   M M

単一の M が複数の X-MAS の一部である可能性があります。

M ごとにチェックすると、複数回遭遇する可能性があります。

一致ごとに文字列化された座標の Set() を構築する必要があります。そうすれば、X-MAS インスタンスを一度だけ考慮することになります。

突然 - 素晴らしい！ - アイデア

すべての M をチェックするつもりはありません。

すべての A をチェックします。

そして、斜めに隣接する 4 つのセルを時計回りにチェックしていきます。

X-MAS マッチは次の 4 つのパターンのいずれかに当てはまります:

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

`

ふぅ！これは、私の当初のアイデアよりもはるかに面倒ではありません。

パート 1 のコードのほとんどを再利用できるはずです!

コピー、ペースト、微調整

グリッド内のすべての As を検索:
js
let As = [];
for (let row = 0; row for (letcol = 0;col if (grid[row][col] == "A") {
As.push([行, 列]);
}
}
}

チェックする相対座標の順序の確立:
js
let Adirs = [
[-1, -1],
[-1, 1]、
[1, 1]、
[1, -1],
];

一致の合計を合計します:
js
let part2 = As.reduce((total, coord) => {
時計回りに = Adirs.map((dir) => {
let [行、列] = coord;
let [y, x] = ディレクトリ;
グリッドを返す[行 y][列 x];
});
if (["MSSM", "MMSS", "SMMS", "SSMM"].includes(時計回り.join(""))) {
合計 ;
}
合計を返します;
}, 0);

入力例に対する正しい答えが生成されます!

次に、パズルの入力を確認します...

確かに!!!正解です!!!

Ms. の代わりに As を使用することに思い当たってとてもうれしく思います

トラブルシューティングに費やす何時間もの頭痛の種が節約できたと確信しています。

これも楽しくてわかりやすいパズルでした!

5 日目には何が待っているのでしょうか。

以上がセレス検索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。