サイトアイコン FITSブログ

paiza Cランク相当問題「検索履歴」をワンライナ―で解く

※こちらは paiza の中でも解答コードを公開可能なレベルアップ問題集 https://paiza.jp/works/mondai
というコーナー内での解答コード掲載です。

paiza にコードの公開可能な「レベルアップ問題集」というコーナーがあったので、試しに解いてみることにしました。今回解いたのはCランク相当である「検索履歴」という問題です。

検索ワードの履歴とは次のようにつくられます。
検索ワード W が以前に入力されたことがある場合:
  履歴中の W を削除する。
  履歴の先頭に W を追加する。
検索ワード W が以前に入力されたことがない場合:
  履歴の先頭に W を追加する。
検索ワード W が N 個与えられるので、N 個の検索ワードが与えられた後の履歴を表示するプログラムを書いてください。

https://paiza.jp/works/mondai/skillcheck_archive/search_history?language_uid=javascript

これを、上記の説明文に書かれている処理内容にできるだけ忠実にコーディングすると、このようになると思います。

    // 検索履歴格納用の配列を確保
    history = [];
    lines.slice(1).forEach(word => {
        hit = history.indexOf(word);
        if (hit != -1) {
            // 単語がすでに検索履歴に含まれるなら削除
            history.splice(hit, 1);
        }
        // 検索履歴の先頭に単語を追加
        history.unshift(word);
    });
    // 出力
    console.log(history.join("\n"));

さらに、reduce のアキュムレータ機能を使えば history のようなワーク配列を確保する必要もなくなるので次のように書けます。

    console.log(lines.slice(1).reduce((a, b) => {
        hit = a.indexOf(b);
        if (hit != -1) {
            a.splice(hit, 1);
        }
        a.unshift(b);
        return a;
    }, []).join("\n"));

また、履歴に重複する単語が出てきた際に、一度 unshift したものを、indexOf で存在確認して splice で取り除くのは非効率ですね。なので、unshift する条件を、「重複があった場合は一番最後に登場する単語」=「現在のインデックス以降のソース配列に含まれない場合」とします。

    console.log(lines.slice(1).reduce((a, b, idx, arr) => {
        // reducer の idx と arr(ソース配列)を利用して
        // 現在のインデックス以降の配列 slice(idx + 1) に対して存在確認
        if (arr.slice(idx + 1).indexOf(b) == -1) {
            a.unshift(b);
        }
        return a;
    }, []).join("\n"));

ここまでくれば、三項演算子や配列のスプレッド構文などを使い、ワンライナーで書けます。※スプレッド構文は巨大な配列を展開するとランタイムエラーとなるので、処理速度の最適化が求められる問題では慎重に使用しましょう

// a.unshift(b) は値を返さないのでスプレッド構文 [b, ...a] で先頭への追加を実現
console.log(lines.slice(1).reduce((a, b, idx, arr) => arr.slice(idx + 1).indexOf(b) == -1 ? [b, ...a] : a, []).join("\n"));

また、ちょっと考え方を変えると、今回の出力は、ほぼ入力配列を reverse したものと言えそうです。ただし、重複があった場合は配列インデックスの大きいほう(後出の方)を残して reverse しなければいけません。これを filter で実現し、ワンライナーで書くと、下記のようなコードになると思います。

console.log(lines.slice(1).filter((l, idx, arr) => arr.slice(idx+1).indexOf(l) == -1).reverse().join("\n"));

ここまでくると可読性が低すぎるということでチーム内レビューでも指摘されると思いますが、考える分には楽しいですね。レベルアップ問題は解答を話し合ったり公開することが認められているので、普通はワンライナーでやらないであろう問題を、チームであーでもないこーでもないと話し合ってワンライナー化してみるのも、三項演算子や reducer への理解が含まるので面白いかもしれません。

モバイルバージョンを終了