soy-curd's blog

The blog is written about maebashi or sake or beer or program. [https://twitter.com/soycurd1]

JavaScriptでforの二重ループからforを一個削除する方法

プログラマのためのコードパズル」を読んでいたところ、かなり始めのほうに、for文の二重ループから forを一個削除することによりプログラムを短くするコードゴルフの技法が載っていた。 しかし、簡単な説明のみで式変形され、すぐには理解できなかったので、 理解しがてらその方法を紹介していく。

まずは以下のような二重ループがあったとする。

function solve() {
  for (var a = 0; a < 10; a++) {
    for (var b = 0; b < 10; b++) {
      if (a * b === 81) {
        console.log("solve!");
      }
    }
  }
}

solve()

このとき、変数aとbがそれぞれ0から9までインクリメントされ、a*b9*9=81となる場合が発生するので、"solve!"というログを見ることができるだろう。

これをfor一個で書く方法として以下のようなものがある。

function solve() {
for(a=0,b=-1;a<10;b<9||(b=-1,a++))b++,a*b==81&&console.log("solve!")
}
solve()

確かにコードからはforが一個消えている。しかし、消えた分のforの処理はどこで行われているのだろう?

これではわからないので、まずは読みやすくフォーマットしてみる。

function solve() {
  for (var a = 0, b = -1; a < 10; b < 9 || (b = -1, a++)) {
    b++;
    if (a * b == 81) {
      console.log("solve!");
    }
    // ※
  }
}

forの加算式の、b < 9 || (b = -1, a++)が目につくと思う。 ここで、※の部分にconsole.log(a, b)を仕込んでaとbがどのように増えるか見てみる。

0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 0
1 1
1 2
.
.
.

普通にforを二重にした場合と同じように、内側のループの変数がインクリメントされ、 その後外側のループの変数がインクリメントされている。

インクリメントしている部分はb++の箇所だ。

それでは、なぜこの箇所でaのループが一回しか回っていないのにもかかわらず、b++が10回も実行されるのだろうか...?

ここで、b < 9 || (b = -1, a++)をもう一度見てみる。これはfor文の加算式ではあるけれど、もっと重要な点がある。それは、a++b < 9の場合は実行されないという点だ。

つまり、このfor文は変数aについてだけのループではない。bが9より小さい場合はbのループを回し、そうでない場合にaのループを回す役目があるのだった。

(b = -1, a++)を式(x), b++を式(y)として、 logの結果にコメントをつけてみると、

0 0  // b == -1 < 9なので式(x)は実行されない。式(y)のみ実行でb == 0になる
0 1  // b == 0 < 9なので式(x)は実行されない。式(y)のみ実行でb == 1になる
0 2  // 上記と同様...
0 3  // 上記と同様...
0 4  // 上記と同様...
0 5  // 上記と同様...
0 6  // 上記と同様...
0 7  // 上記と同様...
0 8  // 上記と同様...
0 9  // 上記と同様...
1 0  // b == 9 < 9ではないので式(x)が実行。aがインクリメントされ1, bが-1になる。さらに式(y)が実行されb == 0になる。
1 1
1 2
.
.
.

ということだとわかる。ひとつひとつ処理を追ってみて、ようやく仕組みを理解できた。

コードゴルフでは、forの([初期化式]; [条件式]; [加算式])の部分で、式で可能なあらゆることをするようなので、そのあたりを注意して本のほうを読み進めていきたい。