Carian Ceres

Kedatangan Kod 2024 Hari 4

Bahagian 1

X menandakan titik (beratus-ratus?).

Saya terkejut sehingga kini tidak ada teka-teki carian perkataan literal seperti ini.

Nampaknya menakutkan, tetapi strategi saya ialah:

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

Menyemak strategi ini pada contoh menyebabkan saya percaya ia adalah pendekatan yang menang.

Sekarang untuk bahagian yang menarik: mengekodkan semua perkara ini dari awal!

Cari indeks setiap X dalam grid...akhirnya

Pertama, saya perlu menghuraikan input ke dalam tatasusunan aksara 2D:

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

Halangan yang sering saya hadapi dalam teka-teki grid ialah mengambil kira indeks di luar sempadan.

Jika saya bermula dari sel sempadan - atau sel berhampiran dengan sempadan - dan berjalan jauh ke arah ke tepi, akhirnya saya akan menemui baris atau lajur yang di luar sempadan.

Saya mempunyai dua strategi untuk menangani perkara ini:

1. Tambahkan semakan pada syarat saya untuk baris atau lajur yang tidak wujud
2. Pad grid dengan baris dan lajur yang mencukupi supaya tiada risiko untuk keluar dari sempadan

Untuk cabaran ini, saya memilih untuk #2.

Melapik grid saya dengan jidar tebal 3 sel kelihatan seperti ini:

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('.')
]

Grid contoh kini kelihatan seperti ini:

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

Kini saya bersedia untuk mengkatalogkan koordinat setiap X dalam grid empuk:

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])
    }
  }
}

Kejayaan: ia menemui kesemua 19 X dalam grid contoh!

Berjalan tiga langkah dalam lapan arah dari setiap X

Semua lapan koordinat relatif dikodkan sebagai tatasusunan 8 elemen:

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

Kini untuk algoritma utama:

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

Dan dalam 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);

Ia menjana jawapan yang betul untuk input contoh!

Apakah yang akan berlaku apabila saya menjalankannya pada input teka-teki saya??!!

Saya mendapat nombor: beberapa ribu 'XMAS

Adakah jawapan yang betul?

IALAH!!!

Woohooo!!!

Tak sabar nak tengok bahagian 2 yang ada...

Bahagian 2

Ohhh saya. Ini menjadi lebih rumit. Tetapi boleh dilakukan!

Dalam Bahagian 1 saya sedang mencari Xs.

Kini, saya sedang mencari Cik

Dalam Bahagian 1 saya merekodkan huruf dalam garis lurus untuk membuat perkataan.

Kini, saya sedang mencari empat konfigurasi frasa 5 sel:

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

Satu M boleh menjadi sebahagian daripada beberapa X-MAS.

Dengan menyemak setiap M, saya mungkin akan menghadapi beberapa kali.

Saya perlu membina Set() koordinat bertali untuk setiap perlawanan. Dengan cara itu, saya hanya mengambil kira contoh X-MAS sekali.

Tiba-tiba - cemerlang! - idea

Saya tidak akan menyemak setiap M.

Saya akan menyemak setiap A.

Dan saya akan menyemak empat sel yang bersebelahan menyerong, mengikut urutan jam.

Padanan X-MAS akan sesuai dengan salah satu daripada empat corak ini:

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

`

Fuh! Ini akan menjadi jauh lebih membosankan daripada idea asal saya.

Dan saya sepatutnya dapat menggunakan semula kebanyakan kod Bahagian 1 saya!

Salin-Tampal-Tweak

Mencari semua Seperti dalam grid:
js
biarkan As = [];
untuk (biar baris = 0; baris < grid.panjang; baris ) {
untuk (biar kol = 0; kol < grid[0].panjang; kol ) {
if (grid[row][col] == "A") {
As.push([baris, kol]);
}
}
}

Mewujudkan susunan koordinat relatif untuk diperiksa:
js
biar Adirs = [
[-1, -1],
[-1, 1],
[1, 1],
[1, -1],
];

Menambahkan jumlah perlawanan:
js
biarkan bahagian2 = As.reduce((total, coord) => {
biarkan mengikut arah jam = Adirs.map((dir) => {
biarkan [baris, kol] = koordinat;
biarkan [y, x] = dir;
kembalikan grid[baris y][col x];
});
jika (["MSSM", "MMSS", "SMMS", "SSMM"].termasuk(ikut arah jam.join(""))) {
jumlah ;
}
pulangan jumlah;
}, 0);

Ia menjana jawapan yang betul untuk input contoh!

Sekarang untuk menyemak input teka-teki saya...

Memang!!! Jawapan yang betul!!!

Saya sangat gembira kerana saya terfikir untuk menggunakan As dan bukannya Ms.

Menjimatkan saya berjam-jam menyelesaikan masalah sakit kepala, saya pasti.

Itu satu lagi teka-teki yang menyeronokkan dan boleh diakses!

Saya tertanya-tanya apa yang ada pada Hari 5.

Atas ialah kandungan terperinci Carian Ceres. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!