NetBeansとScalaで遊ぶ（遅延評価編）
忙しくてしばらく使っていなかったScalaとNetbeans、新しいバージョンを入れてみる。
Netbeansが6.8、Scalaは2.8.0.RC2、Scalaプラグインがnb-scala-6.8v1.1.0rc2b。
ScalaのIDEサポートは、もう十分使えますね。（Eclipseプラグインは知らんけど）
そして、すっかり忘れてしまったScalaの復習。
ブレークポイントからステップ実行して挙動の確認。（←こういう発想は関数型が身についていない証拠？）
Scalaの対話式実行環境よりこちらのほうがやりやすい。
遅延評価の確認で以下のコードをステップ実行
var foo = "foo" // (a) lazy val bar = foo // (b) lazy val baz = foo // (c) foo = "bar" // (d) println(bar) // (e) => "bar"が表示される foo = "baz" // (f) println(baz) // (g) => "baz"が表示される
最初の行のブレークポイントで停止(a)。
この時点で変数ウィンドウにfoo,bar,bazは登場しないが、謎のbitmap$0$1というIntRef型の変数が。
この時点でIntRefが参照しているintの値は0。
次行にステップオーバー。(b)
変数ウィンドウにfooが登場するかと思ったらfoo$1というObjectRef型の変数登場。
foo$1が参照しているのは文字列"foo"。
遅延評価される変数が束縛された変数は特別扱いらしい。
次行にステップオーバー。(c)
barは変数ウィンドウに登場しない。これは登場したらその時点で評価されてしまうので当然。
代わりにbar$lzy$1というObjectRef型の変数登場。参照先はnull。
(d)(e)とステップ実行して次に(f)に行くと思ったら(b)に戻ってしまった。
この行が評価されたよ、という意味なのか。そして再び(e)に戻る。
この時点でbar$lzy$1の参照先は文字列"bar"になっていた。
そして、bitmap$0$1の参照先のintの値が1に。
(g)を実行し終わった時には、bitmap$0$1の参照先のintの値は3になっていた。
bitmap$0$1は、各ビットを遅延評価変数が評価されたかのフラグとして使っているらしい。
では、64を超えた数の遅延評価変数と定義したらどうなるか・・。bitmap$1$1という変数が登場しました。
おまけ
上記の(a)の行と(b)の行を入れ替えてもNetBeans上でエラーになりません。
束縛元の定義が後でもいいという超遅延評価？
当然、コンパイルするとエラーになります。
バケツ問題
某プログラム勉強会で、お題が出たので解いてみる。
問題
水がいっぱい入ったバケツ一個と、空のバケツがいくつかあり、それぞれのバケツの容量は正確にわかっている。この状態から指定された容量を量りとる、最
小手数の手順を求めよ。
ただし
・バケツからバケツに水を移す操作を１手と数える。
・バケツからバケツに水を移す際は、注がれるバケツがいっぱいになるか、注ぐバケツが空になるまで行う。
・従って、水は一滴も漏れない。
例えば。バケツが4つ。10リットル,8リットル,3リットル。10リットルのバケツが満タンで、あとは空っぽ。ここから4リットル量りとりたい。
最小手数の手順は
10リットルのバケツから、3リットルのバケツに注ぐ
3リットルのバケツから、8リットルのバケツに注ぐ
10リットルのバケツから、3リットルのバケツに注ぐ
の3手（要するに、10リットルから3リットルを2回減じている）となる。
表示を短くするために、バケツに順に 0, 1, 2 と番号を振ると、
0→2, 2→1, 0→2
と、表示することができる。
最初の状態から、他のバケツに注いだ状態、さらに他のバケツに注いだ状態と遷移させて状態を評価、解が出たら停止すればよい。
ただし、状態Ａ→状態Ｂ→状態Ａとなると永久に終了しないので、過去に評価した状態は記憶しておき同じ状態を繰り返さないようにする。
あと、状態Ａ→状態Ｂ→状態Ｃと縦型探索をすると、状態Ａ→状態Ｃという最適解を見逃してしまうので横型探索をする。
def solve(target, buckets) done = {} # 評価済みの状態保持用 cur_fill = [["", [buckets.first] + [0] * (buckets.size - 1)]] # 現在の状態 while (!cur_fill.empty?) next_fill = [] # 生成された次の状態保存用 cur_fill.each do |record, fill| buckets.size.times do |i| next if fill[i] == 0 buckets.size.times do |j| next if i == j next if fill[j] == buckets[j] mv_vol = [fill[i], buckets[j] - fill[j]].min new_fill = fill.clone new_fill[i] -= mv_vol new_fill[j] += mv_vol next if done[new_fill] done[new_fill] = true new_record = record + " #{i}→#{j}" if new_fill[i] == target or new_fill[j] == target puts "#{new_record.chars.count('→')} 手 :#{new_record}" return end next_fill << [new_record, new_fill] end end end cur_fill = next_fill end puts "***解なし***" end val, *elem = ARGV.map(&:to_i) solve(val, elem)
同様のアルゴリズムのscala実装。
なぜかruby版より、かなり遅い。オブジェクトの生成回数が多いのがネックなのか。
object Bucket { import scala.collection.mutable.HashMap import scala.collection.mutable.Stack def main(args: Array[String]) { args.map(_.toInt).toList match { case x::xs => println(solve(x, xs)) case _ => println("argument error") } } case class Bucket(id:Int, size:Int, fill:Int) case class State(parent:State, buckets:List[Bucket]) { def key:List[Int] = buckets.sort((a,b) => a.id < b.id).map(_.fill) def record:String = { if (parent == null) return "" var dst, src = 0 var mv = parent.key.zip(key).zip(List.range(0,buckets.size)) for (((a, b),i) <- mv if a != b) yield { if (a > b) src = i else dst = i } parent.record + " " + src.toString + "->" +dst.toString } } def solve(ans:Int, buckets:List[Int]):String = { val done = new HashMap[List[Int], Boolean] var curStates = new Stack[State] var rootState = Array.fromFunction(i => new Bucket(i, buckets(i), if (i==0) buckets(0) else 0))(buckets.size).toList curStates.push(new State(null,rootState)) while (!curStates.isEmpty) { var nextStates = new Stack[State] for (cs <- curStates) yield { for (src <- cs.buckets if src.fill > 0; dst <- cs.buckets if dst.size > dst.fill && src != dst) yield { var mvVol = Math.min(src.fill, dst.size - dst.fill) var newSrc = new Bucket(src.id, src.size, src.fill - mvVol) var newDst = new Bucket(dst.id, dst.size, dst.fill + mvVol) var newState = new State(cs, newSrc::newDst::cs.buckets.filter((bc) => bc != src && bc != dst)) var key = newState.key if (!done.contains(key)) { done.put(key, true) if (newSrc.fill == ans || newDst.fill == ans) return newState.record nextStates.push(newState) } } } curStates = nextStates } "no answer" } }
切符問題
某プログラム勉強会で、お題が出たので解いてみる。
遠い昔に似た問題のソルバーを作ったことがある。
いくつかの正の整数と加算・減算・乗算 の3つの演算子（そして、括弧）を使って、ある別の正の整数を生成する方法を探し出すプログラムを書け。
例えば。{2,5,6,8}から10を生成する方法は、例えば (2+8)*(6-5) があるので、これを出力すればよい。
なお：
・解がない場合は、その旨を出力すること
・解が複数ある場合でも、ひとつだけ出力すればよい
・オーバーフローは考慮しなくてもよい
・不正な入力（負の数がある、など）への対処は不要
・括弧は無駄にたくさんついていてもよい。
・ヒント：再帰
「切符問題」といわれていたけれど、与えられた４つの数字を加減乗除して指定された数字にする、という問題。
切符に数字が４つ書かれていて、その数字を使ったのが起源だったようだが。
見かけた車のナンバーを加減乗除して10を作るのは、いい暇つぶし。
で、出題者が再帰での回答を期待しているようなので、あえて再帰をしない方法で。
require "mathn" class Ticket def initialize(val, elem) @val = val @elem = elem end def calc_rpn(rpn) stack = [] rpn.each do |e| stack.push e.class == Fixnum ? e : "(#{stack.pop}#{e}#{stack.pop})" end return nil unless stack.size == 1 val = eval(stack.first) rescue val = nil return nil unless val == @val return stack.first end def solve %w(+ - * /).map{|e| [e]*(@elem.size - 1)}.flatten.combination(@elem.size - 1).to_a.uniq.each do |e| (@elem + e).permutation do |rpn| if ans = calc_rpn(rpn) return ans end end end "解なし" end end val, *elem = ARGV.map(&:to_i) puts Ticket.new(val, elem).solve
与えられた数から、逆ポーランド記法のパターンを生成して指定された数になるかチェックしています。
かなり強引な方法で無駄が多いので、与える数の個数は４個が限界でしょうか。
普通に再帰を使うとこんな感じ。
require "mathn" class Ticket def initialize(val, elem) @val = val @elem = elem end def gen_exp(elem,&block) if elem.size == 1 yield elem.first else 0.upto(elem.size-2) do |i1| e1 = elem[i1] (i1+1).upto(elem.size-1) do |i2| e2 = elem[i2] elem_next = [] elem.each_with_index{|e,i| elem_next.push(e) unless i == i1 or i == i2} gen_exp(elem_next+["(#{e1}+#{e2})"],&block) gen_exp(elem_next+["(#{e1}-#{e2})"],&block) gen_exp(elem_next+["(#{e1}*#{e2})"],&block) gen_exp(elem_next+["(#{e1}/#{e2})"],&block) gen_exp(elem_next+["(#{e2}-#{e1})"],&block) gen_exp(elem_next+["(#{e2}/#{e1})"],&block) end end end end def solve gen_exp(@elem) do |exp| val = eval(exp) rescue val = nil return exp if val == @val end "解なし" end end val, *elem = ARGV.map(&:to_i) puts Ticket.new(val, elem).solve
ここで、出題をよく読むと「加減乗除」の「除」は使わなくて良いらしい。
有理数クラスが無いので見送っていたscalaの出番（scalaなら有理数クラスの実装も簡単なんだけれどね）。
object Ticket { import scala.collection.mutable.Stack def main(args: Array[String]) { args.map(_.toInt).toList match { case x::xs => if (!solve(x, xs, List())) println("No answer") case _ => println("Argument error") } } def calcRpn(rpn:List[Any]):Int = { var st = new Stack[Int] rpn.foreach { _ match { case "+" => st.push(st.pop+st.pop) case "-" => st.push(-st.pop+st.pop) case "*" => st.push(st.pop*st.pop) case n:Int => st.push(n) } } st.pop } def solve(ans:Int, nums:List[Int], pn:List[Any]):Boolean = { var c1, c2 = 0 pn.foreach {_ match{case n:Int => c1+=1; case _ => c2+=1}} if (nums.size == 0) { if (c1 == c2 + 1) { if (calcRpn(pn.reverse) == ans) { println(pn.reverse) return true } return false } } else { for (i <- 1 to nums.size) { var (n1,n2) = nums.splitAt(i) if (solve(ans, n1.take(n1.size-1):::n2, n1.last::pn)) return true } } if (c1 > c2 + 1) { List("+", "-", "*").foreach {op => if (solve(ans, nums, op::pn)) return true } } false } }
gemの更新
Windows環境にパッケージをgemでインストールしようとしたところ、gemのバージョン1.3.1以上じゃないと駄目だと叱られる。
の結果は1.1.1。ActiveScriptRubyでインストールされたもの。
> gem -v
で更新しようとすると、"Nothing to update"と言われる。
> gem update --system
ネットで調べると、gem本体は更新用パッケージで更新するようになったらしい。ということで更新用パッケージをインストール。
しかし、ここでもgemのバージョン1.3.1以上じゃないと駄目だと叱られる。その1.3.1以上を入れるためにやっているのに・・。
> gem install rubygems-update
しかたがないので、バージョン指定をする。
これで更新パッケージは無事インストール。
> gem install rubygems-update -v=1.3.1
でgemの更新。
> update_rubygems
の結果は1.3.1に。
> gem -v
gemは、もっと新しいバージョンがありそうだけれど今日はここまで。
ナップサック問題？
某プログラム勉強会で、お題が出たので解いてみる。
あなたは硬貨を何枚か持っており、ある金額を払いたい。
お釣りの金額が最小となるような硬貨の組み合わせと、その場合のおつりを計算せよ。
硬貨の価値はすべて正の整数、払いたい金額も正の整数で、オーバーフローは考慮しなくても良いとする。
最良の組み合わせが複数ある場合、そのうちひとつを出力すればよい。
問題を読んだ瞬間「ナップサック問題？」と思ったけれど微妙に違う。
しかし、「持っている硬貨の金額合計−払う金額」を超えない最大硬貨の組み合わせと考えるとナップサック問題になる。
ナップサック問題の解法はネットにいくらでもあるし楽勝楽勝。と思っていた・・が。
よく見かける動的計画法を使ったアルゴリズムは同じ硬貨を何枚でも使っていい場合のみ適用できるので、この問題では使えない。
その他は遺伝的アルゴリズムとか必ずしも最適解を出すとは限らないものばかり。さすがＮＰ困難の問題。
結局力技で解決。
コインの全ての組み合わせを生成してるので（多少枝狩りはしているが）コインの種類が多くなると遅くなる。
class Coins def initialize(total, coins) @total = total @coins = coins end def gen_sum(coins) if coins.size == 1 @used.push coins.first yield coins.first @used.pop yield 0 else car,*cdr = coins gen_sum(cdr) do |sum| next if sum > @sum_limit yield sum next if car + sum > @sum_limit @used.push car yield car + sum @used.pop end end end def solve @used = [] used_sv = nil min = @coins.first @sum_limit = @total + min - 1 gen_sum(@coins) do |sum| change = sum - @total next if change < 0 if change < min min = change used_sv = @used.clone end break if min == 0 end puts "金額 : %d, 支払い : %s, おつり : %d"%[@total, used_sv.sort.inspect, min] end end total, *coins = ARGV.map(&:to_i) Coins.new(total, coins.sort).solve
数学のお勉強
某プログラム勉強会で、お題が出たので解いてみる。
[問1]6面体のサイコロを3回振る。同じ目が一度も出ない確率を計算せよ。
6P3/63 = 5/9
簡単な確率問題。
3回の試行で同じ目が出ない組み合わせ(6P3)を、3回の試行の全ての可能性(63)で割る。
[問2]128bitの乱数を1兆個発生させる。同じ値が一度も出ない確率のおおよその値を求めよ。（必要なら、数学公式集などを利用する）
[問1]と同じやり方で解こうとすると死ねる。
乱数のとりえる値の数をn、試行回数をkとすると
nPk/nk
ここでは、n=2128,k=1012
まともに計算したら、どのくらいかかるのだろう？
で、回答
0.9999999999999985306320614736099829776071878571538233981958611321639300600254765538643653
方法は後述。
[問3]128bitの乱数を一日に10万回発生させる。同じ値が一度も出ない確率が99.9%を下回るのは約何日後か。
128bitの乱数のうち、既に発生した数の割合が0.1%を超える日をn日目とする。
100000 * n / 0.001 > 2128
n > 2128 / 108
n > 3402823669209384634633746074317
その前に人類が死滅しているのは確実ですな。
[問4]「N bit の乱数を何個発生させたら同じ値が一度も出ない確率が p % を下回るか」のおおよその値を計算するプログラムを書け。また、Nは32〜512 辺り、p は50%〜99.9999% 辺りを想定している。
わーい、やっとプログラムだ。まずk回の試行で同じ値が一度も出ない確率（n=2N）をp(k)とする。
p(k) = nPk/nk
ここで、分子と分母を別に計算するとDoubleの精度ではあっというまに指数部がオーバーフローしてしまう。
BigDecimal*1を使えばいいけれど遅い。
ここで
p(2) = (n - 1) / n
p(k) = p(k-1) * (n-(k-1)) / n
なので、kを増やしながら (n-(k-1)) / n をかけていって、指定された確率以下になるkを求めてみる。
def try_count1(bits, rate) n = 2 ** bits r = 1.0 k = 2 while(k < n) r *= (n-(k-1)).to_f/n break if r < rate k += 1 end k end
予想されたことではあるけれど、使い物になるのはbit数が40くらいまで。
ここで、k回目の試行で重複する確率を考えてみる。
2回目の試行で重複する確率は(1/n)
3回目の試行で重複する確率は(2/n)
…
k回目の試行で重複する確率は((k-1)/n)
k回目までで重複する確率は
(1/n) + (2/n) + .. (k-1)/n = k*(k-1)/(n*2)（等差数列の和）
はい、おかしいですね。
k回目の試行で重複する確率が((k-1)/n)になるのは、それまでの試行で重複が無かった場合だけなので厳密にはこの計算じゃ駄目なのだけれど、kに対してnが十分大きければ、この値で近似してもいいじゃん（ほんとか？）。
require "bigdecimal" def dup_rate(n, k) r = BigDecimal.new(k.to_s) r *= (k - 1) r /= (n*2) end def try_count2(bits, rate) rate /= 100 rate = 1.0 - rate n = 2 ** bits min_try = 1 max_try = n while(max_try > min_try + 1) try_cnt = (min_try + max_try) / 2 if dup_rate(n, try_cnt) < rate min_try = try_cnt else max_try = try_cnt end end max_try end
最初のプログラムと実行結果を比べてみる
N=40 p = 99.999%
try_count1: 4690
try_count2: 4690
N=40 p = 99%
try_count1: 148665
try_count2: 148292
N=40 p = 70%
try_count1: 885629
try_count2: 812224
N=40 p = 50%
try_count1: 1234605
try_count2: 1048577
まあ、使えるかな。
ということで、[問2]も
puts (1 - dup_rate(2**128,10**12))
で解いたのでした。
*1:scala(java)のBigDecimalは桁数が増えるとどんどん遅くなるけれど、RubyのBigDecimalは仮数部の精度を指定できるのでそんなに遅くならない。仮数部の精度はそんなに要らない用途には向いているかも。
エンコーディングは俺が決める
RubyのMechanize、使っている人はどのくらいいるのだろう？
少し前のruby-listに「MechanizeはRubyのキラーアプリになる云々。」という投稿があったけれど、そんなにニーズがあるのだろうか？自分は便利に使っているけれど・・。
そのMechanize、ページのエンコーディングを勝手に判断する。それが正しければ問題ないのだが・・。
だいたい、Mechanizeでウェブにアクセスするような人は対象のサイトのエンコーディングは当然知っている。
だからエンコーディングを指定させてくれ、と思うのだが、現時点ではその手段は無い。
将来的にはどうだろう。
とりあえず、自分はMechanizeをrequireした後に
class WWW::Mechanize::Page def initialize(uri=nil, response=nil, body=nil, code=nil, mech=nil) @encoding = 'Shift_JIS' body = Util.to_native_charset(body, @encoding) rescue body super(uri, response, body, code) @mech ||= mech raise Mechanize::ContentTypeError.new(response['content-type']) unless response['content-type'] =~ /^(text\/html)|(application\/xhtml\+xml)/i @parser = @links = @forms = @meta = @bases = @frames = @iframes = nil end end
