CodeWars オススメ問題 #2

はじめに

個人的に好きなアルゴリズム学習サイト「CodeWars」の問題をシェア。

週1くらいのペースで、全10回を目指す予定。

CodeWarsはいいぞ！の紹介はこちら

CodeWarsの始め方はこちら

オススメ問題

例

「東西南北に移動する時、無駄な移動を省け」という問題です。

「無駄な移動」とは、「北に行って南に行く」等です。
ただし、「北に行って東に行って南に行く」は「無駄な移動」ではありません。

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

-> [West]

["NORTH", "WEST", "SOUTH", "EAST"]

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

難易度

分類は 5kyu です。
シンプルな解法のため、他の「複雑で例外を多く含む」5kyuと比べると簡単ですし、良問です。

オススメの回答

「評価が高い回答」の中から、学びの多い回答をピックアップしてご紹介。

解答の方向性（ヒント）

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

-> []

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

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

1 ではSOUTHとNORTHは隣り合っていませんが、最終的には削除されるべきです。
2 では同じ用に隣り合っていませんが、削除されるべきではありません。

この２つのケースが問題の最小単位だと思います。

オーソドックスな解法

https://www.codewars.com/kata/reviews/551075dcaacf809d25000248/groups/5516e513a5808bc4a2000074

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();
      else
        dirs.push(dir);
      return dirs;
    }, []);
}

スタック・LIFO（後入れ先出し）と呼ばれる手法です。

1. 新しいスタック（配列）を用意する
2. 入力配列の各要素を順に処理する
3. スタックが空でない場合、スタックの一番上の要素と現在の要素が反対方向（例：NORTHとSOUTH）であれば、スタックから要素を取り除く（つまり、ペアを消す）
4. 反対方向でない場合、現在の要素をスタックに追加する
5. 最終的にスタックに残った要素が、最適化された経路となる

具体的なアルゴリズムは以下

1. とりあえずdirs（direction: 方角 の略かつ複数形）配列に入れます
2. もしdir（現在扱っている方角）がdirsの最後と逆なら
   つまり、dirの逆方向（opposite[dir]）がdirsの最後（dirs[dirs.length - 1]）と等しいなら
3. dirsから削除する（popは最後の要素を削除するメソッド）

正規表現 & 短い解答

https://www.codewars.com/kata/reviews/551075dcaacf809d25000248/groups/5511603aaacf8071e400087f

function dirReduc(arr) {
  var str = arr.join(''), pattern = /NORTHSOUTH|EASTWEST|SOUTHNORTH|WESTEAST/;
  while (pattern.test(str)) str = str.replace(pattern,'');
  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, '');
  }
  
  const result = str.match(/(NORTH|SOUTH|EAST|WEST)/g);
  return result || [];
}

正規表現は考えたのですが、この解答は思いつかなかった・・・！

素晴らしい点を列挙します。

• while(pattern.test(str))と書くことで、forを使うよりも簡潔に書けている
• また、forで条件に関わる配列を操作するとバグが発生するが、この書き方であればバグは発生しない
• returnにおいても、matchを使用することで簡潔に書けている

どれも思いつきませんでした。非常にエレガントです。脱帽。

おわりに

以上、CodeWarsオススメ問題でした。