Réparation de pont

Avènement du Code 2024 Jour 7

Partie 1

Première récursion de l'année

C'est du moins comme ça que j'ai l'intention de gagner une étoile d'or aujourd'hui :

• Commencez par la liste complète
• Vérifiez l'addition et la multiplication
• Pour chaque résultat, continuez avec le reste de la liste
• Jusqu'à ce que j'aie dépassé ou égalé le total

La difficulté sera dans les détails.

Faisons ça !

Créer mon algorithme

Tout d'abord, je dois analyser chaque ligne en une liste de nombres :

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Le premier élément est le total souhaité.

Le reste sont les opérandes ordonnés de l'équation.

Je devrai en tenir compte dans ma fonction récursive.

Voici ma fonction récursive :

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

Et voici la réduction qui l'utilise :

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

Comme je l'espérais mais ne m'y attendais jamais, cela génère la bonne réponse pour l'exemple d'entrée !

Est-ce que le traitement de ma saisie de puzzle sera terminé ?

Et si oui, cela générera-t-il la bonne réponse ?

Honnêtement, je ne suis pas sûr...

C'EST FAIT !!!

Waouh !!!

Aussi excité que je sois, je crains que la prochaine partie ajoute plus d'opérateurs ou nécessite du CS avancé pour que la récursion ne soit plus une solution viable.

Partie 2

Totalement inattendu ! Et bien plus difficile

Comment vais-je faire ça ?

...

Quelques jours plus tard...

Un récapitulatif de mon processus de réflexion :

• Est-ce aussi simple que d'ajouter une troisième clause à ma condition de retour ? Non
• Ma fonction récursive de la partie 1 est-elle correctement configurée pour réussir ? Non
• Oh non, est-il même possible d'accumuler un montant résultant d'opérations antérieures ? Non
• Est-ce que je vais vraiment devoir aborder cela avec une nouvelle stratégie ? Ouais

Compte tenu de toutes les nouvelles variantes

Pour cette équation :

292: 11 6 16 20

Ce sont toutes les équations possibles étant donné les trois opérateurs :

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Peut-être que je peux créer une chaîne de chaque équation et l'évaluer manuellement dans ma fonction récursive.

Par exemple :
Je commence par une chaîne vide dans l'appel de fonction le plus externe :

""

À partir de là, je crée trois variantes en utilisant le numéro suivant :

"" + "+N"
"" + "*N"
"" + "N"

Hmm, mais cela ne fonctionnera pas pour le premier numéro.

Je dois démarrer mon premier appel de fonction avec le premier numéro, pas une chaîne vide :

"N"

Même chose à partir de là :

"N" + "+N"
"N" + "*N"
"N" + "N"

Ouais, ça devrait marcher.

À la fin, j'aurai ces exemples de variations, tous évaluables :

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Passer à : Je l'ai codé... et j'ai découvert un problème plus important

J'ai écrit du code qui génère avec succès toutes les variantes de l'équation.

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

• j'ai l'habitude de parcourir la liste des numéros
• La dernière clause ne se poursuit que si i est avant ou à l'avant-dernier index

La fonction obtient quatre valeurs :

1. Une copie de la liste des numéros, moins le total attendu
2. Le prochain indice
3. La chaîne d'équation avec l'une des trois chaînes concaténées
4. Le même numéro de test

J'appelle la fonction en utilisant presque la même signature que dans la partie 1 :

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

La différence réside dans ce que je passe comme arguments :

1. La liste sans le montant total attendu
2. Commencer à l'index 0
3. Une chaîne contenant le premier nombre
4. Le montant total attendu

Excellente nouvelle :

• Il génère toutes les variations d'équation

Mauvaise nouvelle :

• Il évalue toutes les équations en utilisant PEMDAS, et non de gauche à droite

J'aurais dû savoir mieux... que l'évaluateur JavaScript intégré utiliserait par défaut le bon ordre des opérations, et non de gauche à droite.

Cela met vraiment une clé encore plus grande dans mon algorithme :

• Je vais devoir décomposer chaque équation et l'évaluer partie par partie

Uggghhh.

Heureusement, je pense que je sais exactement comment faire ça.

Faire des calculs manuellement

J'ai besoin d'obtenir du JavaScript pour évaluer une équation comme celle-ci :

292: 11 6 16 20

Dans cet ordre :

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

J'aimerais diviser cette équation en plusieurs parties :

""

La seule façon pour moi de voir comment, c'est avec cette expression à triple chaîne :

"" + "+N"
"" + "*N"
"" + "N"

Je remplis chaque opérateur avec un espace blanc uniquement pour l'utiliser comme séparateur.

Un fait sur cette liste de parties d'équation :

• Il contiendra toujours une quantité impaire d'éléments égale ou supérieure à 3

Comment puis-je exploiter ce fait dans une boucle qui parcourt chaque paire opérande-opérateur-opérande ?

Voici mon idée :

• Supprimez les trois premiers éléments
• Rejoignez-les sous forme de chaîne et évaluez-la comme une expression mathématique
• Rattachez le résultat au début de la liste d'équations
• Répétez jusqu'à ce que la liste des équations soit vide

J'espère que ça marchera !

Mon simulateur de mathématiques de travail en JavaScript :

"N"

Excellente nouvelle :

• Il me montre les valeurs calculées attendues

Mauvaise nouvelle :

• Je n'obtiens toujours pas la bonne réponse pour une équation dans l'exemple d'entrée

L'exemple de réponse ne peut pas être faux... n'est-ce pas ??

La réponse que je continue de générer est environ 7k inférieure à la réponse attendue.

Cela me fait penser que mon algorithme n'identifie pas cette équation comme correcte :

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Dans l'explication de l'exemple de saisie, voici l'équation gagnante :

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

Mon algorithme évalue cette équation et génère ce résultat :

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

C'est parce que mon algorithme fonctionne comme ceci :

292: 11 6 16 20

Je ne vois pas comment cela pourrait être un autre numéro.

Alors... j'ai cherché sur Google.

Et j'ai trouvé ma réponse, qui se cachait en clair dans l'explication, comme toujours :

Tous les opérateurs sont toujours évalués de gauche à droite.

Je pré-concaténais les valeurs à chaque appel de fonction récursive.

Au lieu de cela, mon algorithme devrait faire ceci :

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Maintenant que je comprends ce qui est censé se produire, puis-je ajuster mon algorithme pour qu'il corresponde à ce comportement de traitement ?

De gauche à droite... pour de vrai cette fois

Heureusement, ajuster mon algorithme a été relativement simple.

J'ai ajouté une clause replaceAll() pour tenir compte de ||.

La nouvelle boucle while dans laquelle je traite tous les trois éléments ressemble à ceci :

""

Et j'ai ajusté le || de ma déclaration de retour. clause pour inclure ces caractères, au lieu de concaténer instantanément les deux nombres.

Tests et re-tests

J'ai exécuté l'algorithme sur l'exemple d'entrée.

Il enfin a généré la bonne réponse !!

Quel soulagement !!

Je me demande s'il va finir de fonctionner et générer la bonne réponse sur ma saisie de puzzle.

Appuyer sur courir...

...

...

J'ai une réponse !

C'est énorme, donc c'est probablement bon signe.

Est-ce la bonne réponse ?

...

Non. Trop haut.

Déception.

Est-ce qu'il me manque un cas limite ?

Ma condition pour une équation gagnante est simplement que le résultat mathématique traité soit égal au montant du test.

Mais que se passe-t-il si l'une des variantes d'équations permet à un sous-ensemble de nombres de générer une réponse correcte ?

Pour détecter et exclure ce scénario, j'ai mis à jour ma condition if pour inclure une clause supplémentaire :

"" + "+N"
"" + "*N"
"" + "N"

De cette façon, ce n'est que si tous les nombres sont traités et que le montant résultant est égal au numéro du test que l'équation sera comptée.

La grande question :

• Est-ce que cela change la réponse que j'obtiens ?

Appuyer à nouveau sur Exécuter...

...

Hmm, cela ressemble toujours à la même réponse.

Oh, attendez, il y a deux chiffres vers la fin qui sont différents !

Ma nouvelle réponse est exactement 80 de moins qu'avant.

Existe-t-il une équation avec 80 comme montant attendu ?

Oui !

"N"

Existe-t-il un moyen d'obtenir 80 sans utiliser tous les nombres ?

Oui !

"N" + "+N"
"N" + "*N"
"N" + "N"

Était-ce le seul cas limite que je devais exclure ?

Envoi de ma nouvelle réponse...

C'EST CORRECT !!!

Woohoo!!!

Je l'ai fait !!!

Ça. Était. Épuisant. Et exaltant. Et vraiment courir. Et un défi.

Et toutes les raisons pour lesquelles j'aime faire ces puzzles.

En avant le suivant !

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!