先月やってくれよ。

AppleStore、分割金利0%キャンペーンやってる‥。なんだよー、先月やってくれよ。
MacBookを買って運転資金が尽きたので札幌が終わるまでいろんなイベントに参加できないのだ。Ruby関西行きたいのに。

• Apple Store 分割金利0%キャンペーン

N-Queen

どういう問題なんだっけ？なんか遠い昔にRindaで書いたような気もするんだけど発掘できない。どっかにRubyスクリプトないかな。

(追記)発見した。

• http://www.druby.org/ilikeruby/rinda.html

書き直し

IPSJの課題に合うように書き直してみる。課題の都合により次の行に進めるかどうかを試すメソッドをわけた。

class NQueen
  def concat(board, row)
    board.each_with_index do |v, col|
      return nil if v == row
      return nil if (v - row).abs == board.size - col
    end
    board + [row]
  end

  def nq(size, board=[])
    found = 0
    size.times do |row|
      fwd = concat(board, row)
      next unless fwd
      return 1 if fwd.size == size
      found += nq(size, fwd)
    end
    found
  end
end

if __FILE__ == $0
  size = (ARGV.shift || '5').to_i
  puts NQueen.new.nq(size)
end

そして

端の二行を与えて解を数える。

  def nq2(size, r1, r2)
    board = concat([r1], r2)
    return 0 unless board
    nq(size, board)
  end

  def ipsj(size)
    found = 0
    size.times do |r1|
      size.times do |r2|
        found += nq2(size, r1, r2)
      end
    end
    found
  end

Rinda化

まずipsjメソッドの方。

require 'rinda/rinda'

DRb.start_service

size = (ARGV.shift || '5').to_i
ro = DRbObject.new_with_uri('druby://localhost:12345')
ts = Rinda::TupleSpaceProxy.new(ro)

size.times do |r1|
  size.times do |r2|
    ts.write([:nq, size, r1, r2])
  end
end

found = 0
size.times do |r1|
  size.times do |r2|
    tuple = ts.take([:nq_ans, size, r1, r2, nil])
    found += tuple[4]
  end
end
puts found

そして仕事をする方（nq2）。

require 'rinda/rinda'
require 'nq'

DRb.start_service

ro = DRbObject.new_with_uri('druby://localhost:12345')
ts = Rinda::TupleSpaceProxy.new(ro)

while true
  symbol, size, r1, r2 = ts.take([:nq, nil, nil, nil])
  found = NQueen.new.nq2(size, r1, r2)
  ts.write([:nq_ans, size, r1, r2, found])
end

どうでもいいけどTupleSpaceサーバ。

require 'rinda/tuplespace'

ts = Rinda::TupleSpace.new
DRb.start_service('druby://localhost:12345', ts)
DRb.thread.join

結果

お。エンジンの方の数を倍にすると実行時間も減るねえ。さすが2Coreだ。iBookじゃつまらなかったもんなあ。

real	0m2.840s
real	0m1.564s