TIL : Solution LIFO et techniques d'expression régulière【CodeWars】

Aperçu ?

Le défi Directions Reduction vous demande de trouver l'itinéraire le plus court à partir d'un un tableau de directions.

Exemples :

Input
-> Output
["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
-> ["WEST"]
/* 
Because moving "NORTH" and "SOUTH", or "EAST" and "WEST", is unnecessary.
*/

/* 
Case: omit the first "NORTH"-"SOUTH" pair 
["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
-> ["SOUTH", "EAST", "WEST", "NORTH", "WEST"]

Case: omit the "EAST"-"WEST" pair 
-> ["SOUTH", "NORTH", "WEST"]

Case: omit the "NORTH"-"SOUTH" pair 
-> ["WEST"]
*/

// this case cannot be reduced:
["NORTH", "WEST", "SOUTH", "EAST"]
-> ["NORTH", "WEST", "SOUTH", "EAST"]

---

Solutions 1 : LIFO

function dirReduc(plan) {
  var opposite = {
    'NORTH': 'SOUTH', 'EAST': 'WEST', 'SOUTH': 'NORTH', 'WEST': 'EAST'};
  return plan.reduce(function(dirs, dir){
      if (dirs[dirs.length - 1] === opposite[dir])
        dirs.pop(); // Remove last direction if it's the opposite
      else
        dirs.push(dir); // Otherwise, add current direction to the stack
      return dirs;
    }, []);
}

Il s'agit d'une approche LIFO (Last-in-First-out) mise en œuvre à l'aide de la réduction.

Mesures:

1. Déclarer une pile vide (répertoires)
2. Pour chaque direction du tableau d'entrée (plan), vérifiez si le dernier élément de la pile (dirs) est à l'opposé de la direction actuelle
3. S'ils sont opposés, retirez le dernier élément de la pile (et ignorez la direction actuelle). Sinon, poussez la direction actuelle sur la pile.
4. Répétez ce processus jusqu'à ce que toutes les instructions aient été traitées.

---

Solutions 2 : expression régulière

function dirReduce(arr) {
  let str = arr.join(''), pattern = /NORTHSOUTH|EASTWEST|SOUTHNORTH|WESTEAST/;
  while (pattern.test(str)) str = str.replace(pattern,''); // Remove pairs while they exist
  return str.match(/(NORTH|SOUTH|EAST|WEST)/g)||[];
}

Version alternative :

function dirReduc(arr) {
  const pattern = /NORTHSOUTH|EASTWEST|SOUTHNORTH|WESTEAST/;
  let str = arr.join('');

  while (pattern.test(str)) {
    str = str.replace(pattern, ''); // Remove pairs while they exist
  }

  const result = str.match(/(NORTH|SOUTH|EAST|WEST)/g);
  return result || [];
}

Mesures:

1. Rejoignez le tableau d'entrée (arr) en une seule chaîne afin que nous puissions le manipuler à l'aide d'expressions régulières.
2. Définissez une expression régulière (modèle) qui correspond à des paires de directions opposées (par exemple, « NORD-SUD », « EST-OUEST »).
3. Utilisez la méthode replace dans une boucle pour supprimer toutes les paires de directions trouvées par l'expression régulière.
4. Une fois toutes les paires supprimées, utilisez la méthode match pour extraire les directions restantes de la chaîne et les renvoyer sous forme de tableau.

---

Discussion et idées ?

Je crois que le cas minimum pour cette solution est le suivant :

1. ["SOUTH", "EAST", "WEST", "NORTH"]
-> []

2. ["NORTH", "WEST", "SOUTH", "EAST"]
-> ["NORTH", "WEST", "SOUTH", "EAST"]

Je préfère la solution 2, car elle est concise et utilise les expressions régulières de manière intelligente. Au départ, je ne pouvais pas imaginer le résoudre avec des expressions régulières, mais l'utilisation des méthodes join, match, while, replace et test pour éliminer les paires est impressionnante.

Si vous êtes curieux de connaître ces solutions ou si vous souhaitez explorer d'autres défis, visitez ici.
N'hésitez pas à laisser un commentaire ci-dessous !

Merci d'avoir lu ?

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!