Recherche Cérès

Avènement du Code 2024 Jour 4

Partie 1

X marque les (centaines ?) de points

Je suis surpris qu'il n'y ait pas eu de puzzle de recherche de mots littéraux comme celui-ci jusqu'à présent.

Cela semble intimidant, mais ma stratégie sera :

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

Vérifier cette stratégie sur l'exemple m'amène à croire que c'est une approche gagnante.

Maintenant, passons à la partie passionnante : coder tout cela à partir de zéro !

Trouver l'index de chaque X dans une grille...éventuellement

Tout d'abord, je dois analyser l'entrée dans un tableau 2D de caractères :

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

Un obstacle auquel je suis souvent confronté dans les puzzles de grille est la prise en compte des indices hors limites.

Si je pars d'une cellule frontalière - ou d'une cellule proche de la frontière - et que je marche si loin dans une direction vers le bord, je vais éventuellement rencontrer une ligne ou une colonne hors limites.

J'ai deux stratégies pour gérer cela :

1. Ajouter des vérifications à mes conditions pour les lignes ou colonnes inexistantes
2. Remplissez la grille avec suffisamment de lignes et de colonnes pour qu'il n'y ait aucun risque de sortir des limites

Pour ce challenge, j'opte pour le #2.

Le remplissage de ma grille avec une bordure épaisse de 3 cellules ressemble à ceci :

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

La grille d'exemple ressemble désormais à ceci :

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

Maintenant, je suis prêt à cataloguer les coordonnées de chaque X dans la grille rembourrée :

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

Succès : il a trouvé les 19 X dans la grille d'exemple !

Faire trois pas dans huit directions à partir de chaque X

Les huit coordonnées relatives sont codées sous forme d'un tableau à 8 éléments :

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

Maintenant, l'algorithme principal :

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

Et en 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);

Il génère la bonne réponse pour l'exemple de saisie !

Que se passera-t-il lorsque je l'exécuterai sur mon entrée de puzzle ??!!

Je reçois un numéro : quelques milliers de "XMAS"

Est-ce la bonne réponse ?

C'EST !!!

Woohooo!!!

J'ai hâte de voir ce que la deuxième partie nous réserve...

Partie 2

Ohhh mon Dieu. Cela est devenu un peu plus compliqué. Mais faisable !

Dans la première partie, je cherchais des X.

Maintenant, je cherche Mme

Dans la première partie, j'ai enregistré des lettres en ligne droite pour former un mot.

Maintenant, je recherche quatre configurations d'une phrase à 5 cellules :

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

Un seul M pourrait faire partie de plusieurs X-MAS.

En cochant chaque M, je suis susceptible d'en rencontrer plusieurs plusieurs fois.

Je devrai créer un Set() de coordonnées stringifiées pour chaque correspondance. De cette façon, je ne prends en compte qu'une seule fois une instance X-MAS.

Tout à coup – génial ! - idée

Je ne vais pas vérifier tous les M.

Je vérifierai chaque A.

Et je vérifierai les quatre cellules adjacentes en diagonale, dans le sens des aiguilles d'une montre.

Les matchs X-MAS correspondront à l'un de ces quatre modèles :

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

`

Ouf ! Ce sera beaucoup moins fastidieux que mon idée originale.

Et je devrais pouvoir réutiliser la plupart de mon code de la partie 1 !

Copier-Coller-Ajuster

Trouver tous les A dans la grille :
js
soit As = [];
pour (soit ligne = 0; ligne < grille.longueur; ligne) {
pour (soit col = 0; col < grille[0].length; col ) {
if (grid[row][col] == "A") {
As.push([ligne, col]);
>
>
>

Établissement de l'ordre des coordonnées relatives à vérifier :
js
laissez Adirs = [
[-1, -1],
[-1, 1],
[1, 1],
[1, -1],
];

Comptabiliser le décompte des matchs :
js
let part2 = As.reduce((total, coord) => {
laissez dans le sens des aiguilles d'une montre = Adirs.map((dir) => {
let [row, col] = coord;
laissez [y, x] = dir;
return grille[ligne y][col x];
});
if (["MSSM", "MMSS", "SMMS", "SSMM"].includes(clock.join(""))) {
total ;
>
retourner le total ;
}, 0);

Il génère la bonne réponse pour l'exemple de saisie !

Maintenant, je vais vérifier ma contribution au puzzle...

En effet !!! La bonne réponse !!!

Je suis tellement contente d'avoir eu l'idée d'utiliser le As au lieu du Ms.

M'a épargné des heures de casse-tête de dépannage, j'en suis sûr.

C'était un autre puzzle amusant et accessible !

Je me demande ce que le jour 5 nous réserve.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!