Sabot-le

Avènement du Code 2024 Jour 10

Partie 1

Brève terreur, puis excitation

Je parcours généralement une page avant de tout lire attentivement.

Aujourd'hui, j'ai vu :

• Une grille
• et à quoi ressemblaient des chemins

Et je craignais que ce soit un autre défi du chemin le plus court.

Puis je l'ai lu.

Et j'ai poussé un soupir de soulagement... au moins pour la première partie.

Je dois trouver tous les chemins valides.

C'est... je peux le faire !

Commencer à 0

Je dois trouver tous les 0 :

input = input
  .split('\n')
  .map(
    line => line.split('').map(char => +char)
  )
let zeros = []
for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        if (input[r][c] == 0) {
            zeros.push([r,c])
        }
    }
}

0s : trouvé !

Essayez de vous déplacer par incréments de 1

À partir de chaque 0, un chemin valide est composé de neuf étapes où chaque nombre est supérieur d'un au précédent, se terminant à 9.

Cela ressemble à un travail de récursion.

J'ai besoin d'un cas de base :

1. Le nombre actuel n'est pas exactement un supérieur au précédent
2. Le numéro actuel est le 9

Voici comment mon algorithme devrait fonctionner :

Input:
1. Originating number
2. Current coordinates

Get current number

If it is not exactly one greater than the originating number
  Return false
Else
  If it is 9
    Return the current coordinates
  If it is not 9
    Continue with the coordinates in each orthogonal direction

Après l'avoir écrit, la partie qui me manquait était le suivi du registre des coordonnées de fin valides.

J'ai eu du mal avec ça pendant un certain temps.

Je recevais constamment une erreur qui me faisait penser à tort que je ne pouvais pas transmettre un ensemble ou même un tableau.

Mais heureusement, j'ai simplement oublié de le transmettre aux autres appels de la fonction récursive.

Voici mon algorithme récursif fonctionnel :

let dirs = [[-1,0],[0,-1],[0,1],[1,0]]
function pathFinder(num, coord, memo) {
    let current = input[coord[0]][coord[1]]
    if (current - num !== 1) {
        return false
    } else if (current == 9) {
        memo.add(coord.join(','))
        return
    } else {
        dirs.forEach(dir => {
            if (
                coord[0] + dir[0] >= 0 &&
                coord[0] + dir[0] < input.length &&
                coord[1] + dir[1] >= 0 &&
                coord[1] + dir[1] < input[0].length
            ) {
                pathFinder(
                  current, 
                  [coord[0] + dir[0], coord[1] + dir[1]], 
                  memo
                )
            }
        })
    }
}

Comme je dois commencer par les coordonnées des 0, mon premier appel utilise -1 :

pathFinder(-1, zeroCoordinate, matches)

Enfin, pour obtenir le score correct, je parcourt chaque zéro, générant l'ensemble unique de 9 de destination, conserve et résume les tailles des ensembles :

let part1 = zeros.map(z => {
    let matches = new Set()
    pathFinder(-1, z, matches)
    return matches.size
}).reduce((a, c) =>  a + c)

Tests rapides, résultats rapides

Il a généré la bonne réponse pour le petit exemple de saisie.

Et pour un exemple de saisie plus large.

Et...

...pour ma contribution au puzzle !!!

Woohoo!!!

Avec quoi la partie 2 me mettra-t-elle au défi ?

Partie 2

Euh, ça semble trop facile

Est-il possible que la façon dont j'ai écrit mon algorithme dans la première partie signifie que cela ne nécessitera que quelques petites modifications pour obtenir la bonne réponse ?

Comptez-les tous !

En ce moment, j'ajoute chaque 9 valide à un ensemble.

Pour la partie 2, je pense qu'il me suffit d'incrémenter un compteur pour chaque 9 valide.

Ça vaut le coup d'essayer !

Changez Set en Array et voilà !

Bonne réponse pour l'exemple.

Réponse correcte pour ma réponse au puzzle.

Wow. Ouah. Waouh.

Au lendemain... qui risque d'être beaucoup plus difficile.

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!