TIL: LIFO解法と正規表現テクニック【CodeWars】

概要 ？

ルート短縮チャレンジでは、一連のルートから最短ルートを見つけることが求められます。

例:

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"]

---

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

これは、reduce を使用して実装された LIFO (後入れ先出し) アプローチです。

手順:

1. 空のスタック (ディレクトリ) を宣言します
2. 入力配列 (plan) の各方向について、スタック (dirs) の最後の要素が現在の方向の逆かどうかを確認します
3. それらが反対の場合、スタックから最後の要素をポップします (そして現在の方向をスキップします)。それ以外の場合は、現在の方向をスタックにプッシュします。
4. すべての方向が処理されるまでこのプロセスを繰り返します。

---

解決策 2: 正規表現

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

代替バージョン:

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

手順:

1. 正規表現を使用して操作できるように、入力配列 (arr) を 1 つの文字列に結合します。
2. 逆方向のペアに一致する正規表現 (パターン) を定義する (例: 「北南」、「東西」)。
3. 正規表現で見つかった方向ペアを削除するには、ループ内で replace メソッドを使用します。
4. すべてのペアが削除されたら、match メソッドを使用して文字列から残りの方向を抽出し、配列として返します。

---

ディスカッションと洞察 ?

この解決策の最小ケースは次のとおりだと思います:

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

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

解決策 2 は簡潔で、正規表現を賢く使用しているため、私は解決策 2 を好みます。最初は正規表現で解決するなんて想像もできませんでしたが、join、match、while、replace、test メソッドを使ってペアを排除するのは印象的です。

これらのソリューションに興味がある場合、またはさらに多くの課題を検討したい場合は、ここにアクセスしてください。
以下にコメントを残すことを歓迎します!

読んでいただきありがとうございます?

以上がTIL: LIFO解法と正規表現テクニック【CodeWars】の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。