TIL: LIFO Solution and Regular Exprresion Techniques【CodeWars】

Overview ?

The challenge Directions Reduction ask you to find shortest route from array of directions.

Examples:

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;
    }, []);
}

This is a LIFO (Last-in-First-out) approach implemented using reduce.

Steps:

1. Declare an empty stack (dirs)
2. For each direction in the input array (plan), check if the last element of the stack (dirs) is the opposite of the current direction
3. If they are opposites, pop the last element from the stack (and skip current direction). Otherwise, push the current direction onto the stack.
4. Repeat this process until all directions have been processed.

---

Solutions 2: Regular Expression

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

Alternative Version:

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

Steps:

1. Join the input array (arr) into a single string so we can manipulate it using regular expressions.
2. Define a regular expression (pattern) that matches opposite direction pairs (e.g., 'NORTHSOUTH', 'EASTWEST').
3. Use the replace method in a loop to remove any direction pairs found by the regular expression.
4. After all pairs have been removed, use the match method to extract the remaining directions from the string and return them as an array.

---

Discussion and Insights ?

I believe the minimum case for this solution is as follows:

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

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

I prefer Solution 2, as it is concise and uses regular expressions in a clever way. Initially, I couldn't imagine solving it with regular expressions, but the use of join, match, while, replace, and test methods to eliminate pairs is impressive.

If you're curious about these solutions or want to explore more challenges, visit here.
Welcome to leave a comment below!

Thank you for reading ?

The above is the detailed content of TIL: LIFO Solution and Regular Exprresion Techniques【CodeWars】. For more information, please follow other related articles on the PHP Chinese website!