JavaScriptで末尾の要素から逆算して配列Aから配列Bを求める正しいアルゴリズム

次のようなバイナリ配列（配列A）について考えてみましょう。

const arr = [1,0,1,1,1,1,0,1,1];

この配列をsumRight()という関数に渡すと、次のような出力配列（配列B）が得られます。

const output = [1,0,4,3,2,1,0,2,1];

関数の仕組み

配列arrの各要素は「0」または「1」のいずれかです。この関数は、配列arrの最後の要素から先頭に向かって後方へカウントしていきます。連続して「1」が現れるたびに出力側の値が増加し、1つ目の連続する「1」なら出力は「1」、2つ目なら「2」、3つ目なら「3」となります。一方、元の配列の要素が「0」だった場合は、出力配列でも対応する位置が「0」になります。

上記の例で言えば、末尾から見て「1」が2連続している部分は出力が「2」「1」となり、途中の「0」でカウントがリセットされた後、再び4連続の「1」が出力では「4」「3」「2」「1」と表現されているのが分かります。

reduceRight()メソッドによる実装

それでは、Array.prototype.reduceRight()メソッドを使ってこの関数を実装してみましょう。reduceRight()は通常のreduce()メソッドと同じように配列を単一の値へ畳み込みますが、左からではなく右（末尾）から処理を開始する点が異なります。

const arr = [1,0,1,1,1,1,0,1,1];
const sumRight = arr => {
    return arr.reduceRight((acc, val) => {
        const { prev, res } = acc;
        if(val === 0){
            return {
                prev: 0,
                res: res.concat(0)
            };
        };
        return {
            res: res.concat(val+prev),
            prev: prev+1
        };
    }, {
        prev: 0,
        res: []
    }).res.reverse();
};
console.log(sumRight(arr));

コードのポイント

• アキュムレータとして「直前までの連続カウント（prev）」と「結果配列（res）」の2つの値を保持します。
• 要素が「0」の場合はprevをリセットし、結果配列に0を追加します。
• 要素が「1」の場合は「val + prev」の値を結果に追加し、prevをインクリメントして連続回数を記録します。
• reduceRight()は右から左へ処理するため、結果は逆順になっています。最後にreverse()を呼び出して元の順序に戻します。

実行結果

コンソールには次のように出力されます。

[
    1, 0, 4, 3, 2,
    1, 0, 2, 1
]