DEV Community

kohki_takatama
kohki_takatama

Posted on

TIL: LIFO Solution and Regular Exprresion Techniques【CodeWars】

#javascript #codewars #algorithms #todayilearned

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"]
Enter fullscreen mode Exit fullscreen mode

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; }, []); }
Enter fullscreen mode Exit fullscreen mode

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)||[]; }
Enter fullscreen mode Exit fullscreen mode

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 || []; }
Enter fullscreen mode Exit fullscreen mode

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"]
Enter fullscreen mode Exit fullscreen mode

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 🙌

Top comments (0)