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

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

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

問題と解答

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

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]

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

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

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)

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

解説

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

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を用いて表現している点に注意してください。

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でループすればちょうどいいループ回数になります¹。ひとまずreduceをforEachみたいに使います。

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がちょうど配列をループしながら変更されているので、この機構が使えます。

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に繋げられます。

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を事前に変数に入れておく必要がなくなります。

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進数に直して不思議さを向上させるのが常套手段です。

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

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を返すことを利用すれば、次のようにすれば括弧を消すことができました。これは投稿する前に気づきたかった反省点です。

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を交えた計算をするとなんと目的の配列になる。
  • 探索しても適当な係数が見つからなかったのでボツに。

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

1. もっとも、opsの最後の3つの15は何もしないことを表すので、要素が18個になるまで15で埋めているだけですが。 ↩