パスカルの三角形 ― 2006年06月07日 06時50分

「パスカルの三角形」(d.y.d.) より。とりあえず JavaScript で書いてみる。

function pascal(n) {
  var result = [1];
  n.times(function () {
    result.inject(function (prev, current, index) {
      result[index] = prev + current;
      return current;
    });
    result.push(1);
  });
  return result;
}

10 .times(function (n) {
  print(pascal(n));
});

/*
1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
1,5,10,10,5,1
1,6,15,20,15,6,1
1,7,21,35,35,21,7,1
1,8,28,56,70,56,28,8,1
1,9,36,84,126,126,84,36,9,1
*/

ヘルパ関数は以下のとおり。

Number.prototype.times = function (callback, thisObject) {
  for (var i = 0; i < this; i++)
    callback.call(thisObject, i);
  return this;
};

/* array.inject(callback);
 * array.inject(initial, callback [, thisObject [, omitInitial]]);
 */
Array.prototype.inject = function (initial, callback, thisObject, omitInitial) {
  var length = this.length;
  var result = initial;
  var i = 0;
  if (arguments.length == 1) {
    callback = arguments[0];
    omitInitial = true;
  }
  if (omitInitial)
    result = this[i++];
  for (; i < length; i++)
    result = callback.call(thisObject, result, this[i], i, this);
  return result;
};

prototype.js の Enumerable#inject は初期値を省略することができないが、ここでは Ruby に従って初期値を省略できるようにした。MochiKit の reduce は初期値を省略できる。

これを書いて inject って便利だな、でも代入を使っているあたり何か間違ってるような気が……と思っていたら「Game Scripting Memo - 続・パスカルの三角形」を見て目から鱗。なるほど、inject とはこういう風に使うものだったのか……。どうもこの境地には達し得なさそうな気がするのでせめてメモとして JavaScript に書き直してみる (動作未確認、要 prototype.js)。

print($R(1, 10).map(function (i) {
  return $R(1, i, true).inject([1], function (list) {
    return list.concat(0).inject([0, []], function (data, current) {
      return [current, data[1].concat(data[0] + current)];
    })[1];
  });
}).join("\n"));

by nanto_vi [JavaScript] [コメント(0)｜トラックバック(0)]

100 までの素数を列挙 in JavaScript ― 2006年06月17日 16時33分

「キミならどう書く 2.0 - ROUND 1 - ― Lightweight Language Ring」より。せっかくなので JavaScript 1.7 の新機能である Generator を使って書いてみる。

function countUp(n)
{
  n = n || 0;
  while (true)
    yield n++;
}

function filter(iterator, callback, thisObject)
{
  for (var i in iterator)
    if (callback.call(thisObject, i))
      yield i;
}

function takeWhile(iterator, callback, thisObject)
{
  var result = [];
  for (var i in iterator) {
    if (callback.call(thisObject, i))
      result.push(i);
    else
      break;
  }
  return result;
}

function prime()
{
  var primes = countUp(2);
  while (true) {
    let (n = primes.next()) {
      yield n;
      primes = filter(primes, function (i) { return i % n != 0; });
    }
  }
}

print(takeWhile(prime(), function (n) { return n < 100; }).join(" "));

だが、現時点では Generator が壊れている上、let 文 / let 式内で定義された関数の挙動がおかしいため、これはうまく動かない。そこで Generator を擬似的に実装、JavaScript 1.6 以下 / JScript でも動くように。

if (!this.StopIteration)
  this.StopIteration = { toString: function () { return "StopIteration"; } };

function countUp(n)
{
  n = n || 0;
  return { next: function () { return n++; } };
}

function filter(iterator, callback, thisObject)
{
  return {
    next: function () {
      while (true) {
        var i = iterator.next();
        if (callback.call(thisObject, i))
          return i;
      }
    }
  };
}

function takeWhile(iterator, callback, thisObject)
{
  var result = [];
  while (true) {
    try {
      var i = iterator.next();
      if (callback.call(thisObject, i))
        result.push(i);
      else
        break;
    } catch (e) {
      if (e == StopIteration)
        break;
      throw e;
    }
  }
  return result;
}

function prime()
{
  var primes = countUp(2);
  return {
    next: function () {
      var n = primes.next();
      primes = filter(primes, (function (n) {
        return function (i) { return i % n != 0; };
      })(n));
      return n;
    }
  };
}

print(takeWhile(prime(), function (n) { return n < 100; }).join(" "));
// 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

ある範囲から素数を抜き出すのではなく、ひたすら素数を生成し続けていくイメージ。速度は遅いけど。

ちなみに JScript 5.6 で試したら 949 番目の素数 7489 までは求められたが、それ以降は「実行時エラー: スタック領域が不足しています」となってしまった。

by nanto_vi [JavaScript] [コメント(0)｜トラックバック(0)]