2010-12-02[n年前へ]
■数学(コーディング)パズル、大好き!?
ここのところ、数学パズル||コーディング・パズルにハマっています。きっかけは、国際情報オリンピック(International Olympiad in Informatics)の予選問題にもなったことがあるという「入門レベルの問題」で、「200個以内の長方形の上左および右下座標(32bit floatで表現できるような実数)が与えられる。長方形は相互に重なりが許されるとき、与えられた長方形群により覆われた部分の面積を求めるコードを書け。今すぐ書け。あっ、実行時間が2秒を越えるようなコードはダメだかんね」というお題でした。
あなたなら、このお題に対して、どんなコードを書くでしょう?VisualBasicでも、Perlでも、C++でも、Lispでも・・・、自分の言葉で問題を書き綴り・解き明かす「数学(コーディング)パズル」はっても楽しくスリリングなことなのだろう、と思います。きっと、それは固くなりがちな頭を柔らかくし、何らかの瞬発力を与えてくれるものであるような気がします。
ちなみに、そのお題を与えられたとき、適当にRubyで書いたコードが下のものになります。あなたなら、どんなコードを書きますか?
def makeRect(n) data=[] n.times{ data<<[rand(),rand(),rand(),rand()] } return data end def makeMesh(rects) xg=[] yg=[] rects.each do |xt,xb,yt,yb| xg<<xt<<xb yg<<yt<<xb end xg.sort! yg.sort! mesh=[] (xg.length-1).times do |x| (yg.length-1).times do |y| cx=(xg[x]+xg[x+1])/2 cy=(yg[y]+yg[y+1])/2 area=(xg[x+1]-xg[x])*(yg[y+1]-yg[y]) mesh<<[cx,cy,area] if area>0 end end return mesh end rects=makeRect(200) mesh=makeMesh(rects) area=0 mesh.each do |x,y,a| rects.each do |xt,xb,yt,yb| if xt<x&&x<xb&&yt<y&&y<yb area+=a break end end end puts area
■Powered
by yagm.net