ゆめみからの挑戦状第3弾のreduceを用いる解法

皆さんこんにちは。先日、~~大喜利大会~~ [ゆめみからの挑戦状](https://qiita.com/Yametaro/items/86cbd945b4faf44e8349) としてJavaScriptのクイズが出題され、とても盛り上がっていました。リンク先の記事では、自分の解答も面白解答として紹介していただきました。模範解答は `flatMap` を用いるものですが、筆者の解答では配列操作の定番のひとつとして `reduce` メソッドを使ってみました。

そこでの解法がやや難解なコードとなっていたので、解説記事を用意しました。

# 問題と解答

出題されたクイズの内容は以下の通りです（上述の記事から引用）。

```js
const array1 = [1, 2, 3, 4, 5, 6]
const array2 = array1./* ここに解答を書いてください */

console.log(array2)
// -> [1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6]
```

配列を指示通りに加工するコードを書いてねという問題ですね。

筆者が用意した解答は次の通りです。

```js
const array1 = [1, 2, 3, 4, 5, 6]
const array2 = array1.concat(array1, array1).reduce((a,b,c,d)=> 
  (d.push(...d.splice(Number(a%16n),1)),a >> 4n||d),4721443915042874085729n).slice(0, 15);

console.log(array2)
```

ツイートに収まるように短くしていることもあって、やや読みにくくなっています。ということで、この記事ではこのコードがどういう動作をするのか解説します。

# 解説

上のコードがやっていることを、分かりやすいコードに直すと次のようになります。

```js
const array1 = [1, 2, 3, 4, 5, 6];
const work = array1.concat(array1, array1);

const ops = [
  1, 6, 1, 5, 10,
  1, 4, 1, 3, 7,
  1, 6, 2, 3, 3,
  15, 15, 15,
];
for (const x of ops) {
  const tmp = work.splice(x, 1)[0];
  work.push(tmp);
}

const array2 = work.slice(0, 15);
console.log(array2);
```

つまり、`work`という配列を用意し、それに対して`splice`と`push`による破壊的操作を繰り返すことで目的の結果を用意しています。`splice`は、ここでは配列の途中（上のコードでは`x`番目）から要素を1つ抜き出すために用いています。抜き出した要素は、`push`で配列の後ろに付けています。

この2つの操作がセットで、「配列の途中の要素を1つ一番後ろに移動させる」という操作になります。ある種の並び替えですね。

上のコードはまず作業用の配列`work`は最初`[1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6]`という内容になっており、これに対して18回の並び替え操作を行うことで、`work`は`[1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 2, 4]`となります。後ろの3つは余りなので、`slice`で余計な部分を捨てて`array2`が完成します。

並び替え操作の具体的な内容は、筆者が丹精込めた手作業により`ops`として用意しました。この`[1, 6, 1, ……]`という配列は、まず1番目の要素を後ろに移し、次に6番目の要素を後ろに移し……という操作の列を表します。

## 並び替え手順を数値にエンコードする

上のコードでは並び替え手順が配列`ops`として定義されていますが、これはダサいしスペースも食うので圧縮します。

今回のような整数の列は、ひとつの整数にエンコードできます。`ops`の要素は1つ4ビットで表現できるので、ちょうど16進数で1要素1桁で表現できます。具体的には、`ops`は`0xfff3326173141a5161`として表現します。元の配列の要素が下の桁から順番に現れています。

このエンコードを用いて上のコードを書き換えると、次のようになります。圧縮された数値から元の命令列を取り出すには、このようにビット演算を用います。この数値は桁数が多いので、BigIntを用いて表現している点に注意してください。

```js
const array1 = [1, 2, 3, 4, 5, 6];
const work = array1.concat(array1, array1);

for (let ops = 0xfff3326173141a5161n; ops; ops >>= 4n) {
  const tmp = work.splice(Number(ops % 16n), 1)[0];
  work.push(tmp);
}

const array2 = work.slice(0, 15);
console.log(array2);
```

`splice`の引数はBigIntではなく数値を渡す必要があるので `Number(ops % 16n)`として数値に変換しています。この`Number`というのがコード内で目立ってしまってインパクトを失わせてしまうのが残念ですが、古い言語仕様においてプリミティブ型の間の暗黙の変換がもたらした混乱を反省してか、JavaScriptのBigIntは`Number`を用いて明確に変換しないとエラーが出る仕様となっているので仕方ありません。

## ループをreduceに変換する

今回のお題は`array1./* ここに解答を書いてください */`なので、for文でループするのは避けたいところです。`;`を使えばまあfor文を書いてもよいのですが、せっかくなので美しさのためにreduceを使うことにします。

元々の`ops`が18要素の配列になっていたのにお気付きでしょうか。また、`work`も18要素です。そのため、普通に`reduce`でループすればちょうどいいループ回数になります[^note_1]。ひとまず`reduce`を`forEach`みたいに使います。

[^note_1]: もっとも、`ops`の最後の3つの`15`は何もしないことを表すので、要素が18個になるまで`15`で埋めているだけですが。

```js
const array1 = [1, 2, 3, 4, 5, 6];
const work = array1.concat(array1, array1);

let ops = 0xfff3326173141a5161n;

work.reduce(() => {
  const tmp = work.splice(Number(ops % 16n), 1)[0];
  work.push(tmp);
  ops >>= 4n;
});

const array2 = work.slice(0, 15);
console.log(array2);
```

さらに、上のコードで`let`に入れていた`ops`を、`reduce`の中に保持してもらうことができることに気づきます。`reduce`はそもそも初期値を用意し、配列をループしながらその値を変換していく操作のために使えるものです。今回、`ops`がちょうど配列をループしながら変更されているので、この機構が使えます。

```js
const array1 = [1, 2, 3, 4, 5, 6];
const work = array1.concat(array1, array1);

work.reduce((ops) => {
  const tmp = work.splice(Number(ops % 16n), 1)[0];
  work.push(tmp);
  return ops >> 4n;
}, 0xfff3326173141a5161n);

const array2 = work.slice(0, 15);
console.log(array2);
```

最終形のコードに結構近づきましたね。

## メソッドチェーンの形にする

ここからは、メソッドチェーンの形に持っていくためにコードを少し直します。

まず、`reduce`と`slice`を繋げましょう。今のところ、`work.reduce`はBigIntを操作しながらループするため、最終的な返り値もBigIntとなります。そのため、このままでは`slice`に繋げられません。

実は、`ops >> 4n`を繰り返して`ops`の内容を削っていくと、ループ終了のタイミングでちょうど`0n`になります。そのため、`work.reduce`の返り値は`0n`となっています。

このことを利用して、ループ終了時に`reduce`の返り値がBigIntではなく配列になるようにすることで、`slice`と繋げることができます。次のコードのように、まだ`ops >> 4n`が正の値のときは次のループに備えてBigIntを返し、0になったら最後なので`work`を返すことで、次の`slice`に繋げられます。

```js
const array1 = [1, 2, 3, 4, 5, 6];
const work = array1.concat(array1, array1);

const array2 = work.reduce((ops) => {
  const tmp = work.splice(Number(ops % 16n), 1)[0];
  work.push(tmp);
  return ops >> 4n || work;
}, 0xfff3326173141a5161n).slice(0, 15);

console.log(array2);
```

このように`reduce`の記憶領域を2つの用途で使うのは、我ながら芸術点が高いところです。

次に、`concat`と`reduce`も繋げましょう。ここで難しいのは、`reduce`のコールバックの中で`work`に対して破壊的操作をするので、先に`work`を変数に入れておく必要があるということです。メソッドチェーンにすると、`work`にアクセスできなそうです。

と思いきや、`reduce`のコールバック関数は第4引数に`this`相当の配列を受け取ることができます。これを用いることで、`work`を事前に変数に入れておく必要がなくなります。

```js
const array1 = [1, 2, 3, 4, 5, 6];
const array2 = array1.concat(array1, array1).reduce((ops, _cur, _i, work) => {
  const tmp = work.splice(Number(ops % 16n), 1)[0];
  work.push(tmp);
  return ops >> 4n || work;
}, 0xfff3326173141a5161n).slice(0, 15);

console.log(array2);
```

これでクイズに沿った形のコードにできました。あとは、`tmp`を消したり、変数名を1文字にして分かりにくくしたりします。また、16進数で書かれたマジックナンバーは10進数に直して不思議さを向上させるのが常套手段です。

そうすると、冒頭のコードになります。

```js
const array1 = [1, 2, 3, 4, 5, 6]
const array2 = array1.concat(array1, array1).reduce((a,b,c,d)=> 
  (d.push(...d.splice(Number(a%16n),1)),a >> 4n||d),4721443915042874085729n).slice(0, 15);

console.log(array2)
```

## もっと改善できた点

上のコードは、よく見るとコンセプトを変えずに改善できる点がいくつかあります。一つは、このコードでは`reduce`のコールバック関数が`(a,b,c,d)=>( ... )`のように式を`( )`で囲む形になっています。これは中でコンマ演算子を使っているからです。しかし、`d.push`が今回常に1を返すことを利用すれば、次のようにすれば括弧を消すことができました。これは投稿する前に気づきたかった反省点です。

```js
const array1 = [1, 2, 3, 4, 5, 6]
const array2 = array1.concat(array1, array1).reduce((a,b,c,d)=> 
  d.push(...d.splice(Number(a%16n),1))&&a>>4n||d,4721443915042874085729n).slice(0, 15);

console.log(array2)
```

あとは、`.slice(0, 15)`ではなく`.slice(3)`になるように並び替えたほうが少しすっきりしたかもしれません。

そもそも`slice`が必要なのは、ベースとして`array1.concat(array1, array1)`という18要素の配列を用いている一方で、ゴールが15要素だからです。材料が18要素となっているのは、必要な数値をベタ書きせずに`array1`を材料にしたほうが美しいと感じたからです。

# まとめ

ということで、筆者が用意した解答を解説しました。材料を用意してから`sort()`するという解答は他でも見られましたが、材料はあくまで`array1`から調達しつつ、しかも`sort()`に頼らず手作業で並び替えるという点で独自性が出せたのではないかと思います。

## 没ネタ

他に次のような解法を検討しましたが、解答を作れなかったのでボツになりました。

- 決定的なシャッフルアルゴリズムを、マジックナンバーとして指定した回数だけ走らせると偶然目的の形になっている。
    - ツイートに入るほど単純できれいに混ざるアルゴリスムが意外と作れない上に、マジックナンバーを探索しても見つからなかったのでボツに。
- `array1.concat(array1,array1)`に対してmapし、適当な係数と`Math.cos`や`Math.sin`を交えた計算をするとなんと目的の配列になる。
    - 探索しても適当な係数が見つからなかったのでボツに。

これらがだめだったので、探索に頼らずに解答を作れる今回のものになりました。