Galivant de garde

Avènement du Code 2024 Jour 6

Partie 1

Un genre de puzzle très familier

• Grille 2D
• Obstacles partout
• Suivre un chemin
• Comptez les tuiles uniques visitées

Allons-y !

Un pas à la fois

Analyse de la grille :

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

Identifier l'emplacement de départ du garde et le remplacer par une tuile vide :

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] = ".";
    }
  }
}

Création d'un objet pour suivre la rotation actuelle du garde :

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

• La garde commence face au nord, donc les mouvements ultérieurs nécessitent de visiter des rangées d'indices inférieurs
• A chaque obstacle, le gardien doit tourner à droite
• Cela la ferait face à l'est, donc les mouvements ultérieurs nécessitent de visiter des colonnes d'indices plus élevés
• Chaque fois que la cellule suivante constitue un obstacle, mon algorithme extraira le premier élément de la liste et le déplacera vers l'arrière

Suivi des cellules visitées :

let visited = new Set()

À chaque mouvement, je tenterai d'ajouter les coordonnées stringifiées à ce Set().

Déplacer le garde :

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;
  }
}

Une explication :

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

Cet algorithme génère avec succès une liste de cellules visitées de 41 pour l'exemple d'entrée !

Est-ce que cela générera la bonne réponse pour mon puzzle ?

Oui !!!

Génial.

Passons à la partie 2 !

Partie 2

J'ai un peu vu ça venir et je le redoutais

Le vieux, cochez toutes les options possibles pour en trouver un valide.

Ma grande question en lisant est :

• Comment puis-je identifier le moment où le garde entre dans une boucle ?

Mais je pense que je sais :

• Je suivrai la direction d'orientation ainsi que les coordonnées
• Si la liste comprend une copie de la suivante ajoutée, alors une boucle est sur le point de commencer

Il est temps de rendre les choses beaucoup plus compliquées !

Parcourir chaque cellule pour trouver toutes les boucles

Tout d'abord, je souhaite générer une liste de toutes les cellules avec un ., à l'exclusion de la cellule de départ du gardien :

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] = ".";
    }
  }
}

Ensuite, utilisez une réduction pour parcourir chaque fichier . dans la grille, en copiant la grille et la position de garde d'origine, en déplaçant une grande partie du code d'origine à l'intérieur de la réduction, en élargissant la boucle while pour inclure une condition pour les coordonnées suivies et la liste de rotation ayant une instance de l'état actuel :

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)

C'est beaucoup.

Mais ça marche ! Au moins sur l'exemple d'entrée.

Est-ce que ça fonctionnera sur le mien, cependant ???

Eh bien... il a fallu 30 secondes pour courir.

Mais... cela a généré une réponse !

Et c'est le...

BONNE RÉPONSE!!!

Woohoo!!!

La première partie était un jeu d’enfant. Et la deuxième partie a été une montée en puissance difficile mais bienvenue.

Deux étoiles d'or supplémentaires dans le sac !

Au jour 7.

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!