ICFPC2008感想
7/12(土) AM 4:00 - 7/15(火) AM 4:00まではICFP Programming Contest 2008に参加していました。「ICFPコンテストて何？」てむきの方とかはk.inabaさんによる紹介とか読むといいんじゃないかなと思います。一応簡単に説明すると、参加資格、使用プログラミング言語も定めず世界中から参加人を募る毎年開催のプログラミング祭みたいなもんです。
k.inabaさんの紹介にもありますが、2006年と2007年の主催者が用意したシステムの気合の入りっぷりが尋常じゃなく、おもしろすぎることあたりからも割と評判が広まったような印象がありますけど気のせいかもしれません。
というわけで今年。そういやハチロク世代とかだと参加する人多いのかなーと思って適当に「集まらないか？」的なこと書いたりしたのですが、まあ適当過ぎて集まりませんでした。というわけで個人で非常に気楽にダラダラと参加していました。好成績とかそういうのを意識すらしてない怠けた参加態度だったんですが、これはこれでけっこう楽しかったです。
1日目
まず問題文を読み解くところが難関です。難関なのでこれだけで1日目をだいたい終えたような記憶があります。まず今年の問題はでっかい岩とかクレーターとか、襲いかかってくる火星人がいたりする火星の地にて探査機を基地にたどりつくよう走らせるというものなんですが、ここまで読み解くのにもずいぶん時間がかかった。あとTCP/IPソケット通信をする云々書いてあったけどその辺さっぱりわからなかったので慌てて調べたり。でもRubyのTCPSocketあたりとか特に難しくもなさそうだったので自然とRubyで書き初めました。たぶんこの日は
#!/usr/bin/env ruby require 'socket' port = ARGV[1].to_i host = ARGV[0] rounds = 5 sock = TCPSocket.open(host, port) sock.setsockopt(Socket::IPPROTO_TCP, Socket::TCP_NODELAY, 1) $/ = ';' count = 0 sock.each_line do |line| puts line case line[0] when ?I when ?T when ?B when ?S when ?C when ?K when ?E if (count += 1) == rounds sock.close exit end end end sock.close
こういう正真正銘何もしない(探査機を動かさない)プログラムを書いて試しにサブミットしたあたりまでで終えてた気がします。
2日目
しばらくは
#!/usr/bin/env ruby require 'socket' port = ARGV[1].to_i host = ARGV[0] sock = TCPSocket.open(host, port) sock.setsockopt(Socket::IPPROTO_TCP, Socket::TCP_NODELAY, 1) while op=$stdin.gets sock.write(op.chomp+';') end sock.close
みたいなプログラム書いて、ジョイパッドとJoyToKey使って手動で探査機走らせて遊んだりしていました。だいたいこの遊びが2日目にした作業の半分くらいのような……
もう半分は障害物を完全無視して基地へと進むようにしました。頭左右に振りながらヨタヨタしながらも一応基地へと進むことに感動したりしてました。
この後にLiveCD上で書いてたソースコードを紛失したりしましたが、たいして書いてなかったので被害は小さかったです。この時点でもプログラムはたぶんこんな感じ。
#!/usr/bin/env ruby require 'socket' port = ARGV[1].to_i host = ARGV[0] rounds = ARGV[2] ? ARGV[2].to_i : 5 sock = TCPSocket.open(host, port) sock.setsockopt(Socket::IPPROTO_TCP, Socket::TCP_NODELAY, 1) $/ = ';' init = sock.gets dx, dy, time_limit, min_sensor, max_sensor, max_speed, max_turn, max_hard_turn = init.scan(/-?[\d\.]+/).map!{|f|f.to_f} count = 0 sock.each_line do |line| puts line case line[0] when ?T time, ctrl, x, y, dir, speed = line[1..-1].scan(/[^\s]+/) if time=='0' sock.write('a;a;') else x = x.to_f y = y.to_f dir = dir.to_f pos_dir = Math.atan2(y, x)*180/Math::PI if (pos_dir > 0 && pos_dir-180 < dir && dir < pos_dir) || (pos_dir < 0 && (dir < pos_dir || pos_dir+180 < dir)) sock.write('r;') else sock.write('l;') end end when ?B when ?S when ?C when ?K when ?E if (count += 1) == rounds sock.close exit end end end sock.close
3日目
2日目のプログラムの時点で、運が良ければ基地にたどりつくようになってたので割と満足していたのですが、さすがに障害物避けようとする努力の影すら無いのはなー、と思いちょっとごちゃごちゃ書き足しました。Tメッセージを読んで、だいたい探査機の向いてる方向ある障害物のうち、一番近いものを避けようとする感じです。左の方にあったら右に向いて、右の方にあったら左を向く、という。障害物の半径も読んでないので、当たるときは普通に当たります。あとなんか正面から障害物に突っ込むことあるので普通にダメダメだと思う。火星人はあんまし当たらないので完全無視。
まあ、なんとなく2日目よりは良くなってるのかなあと思えるような思えないような。最終提出のプログラムはこんなの。ひどいので誰の参考にもならないと思います。ruby知らない人に「rubyのプログラムは汚ないなあ」と思われないように言っておきますと、処理を全部mainの中に書いてるCプログラムみたいなもんです。
#!/usr/bin/env ruby require 'socket' class AngleRange DIR_R = 1 DIR_L = 2 DIR_RL = 3 def initialize(base, range) @base = base @range = range end def include?(dir, rl) in_flag = 0 if @base - @range <= -180 if dir <= @base || 360 + @base - @range <= dir in_flag |= DIR_R elsif @base < dir && dir < @base + @range in_flag |= DIR_L end elsif @base + @range >= 180 if @base - @range <= dir && dir <= @base in_flag |= DIR_R elsif dir <= -360 + @base + @range || @base <= dir in_flag |= DIR_L end elsif @base - @range < dir && dir < @base in_flag |= DIR_R elsif @base < dir && dir < @base + @range in_flag |= DIR_L end rl&in_flag != 0 end end def nearest(objs, x, y, dir, range) near_dir = nil near_dis = Float::MAX near_obj = nil objs.each{|c| rx = c[0]-x ry = c[1]-y rdis = rx**2+ry**2 cdir = Math.atan2(ry, rx)*180/Math::PI if range.include?(cdir, AngleRange::DIR_RL) && rdis < near_dis near_dir = cdir near_dis = rdis end } near_dir end counter = 0 port = ARGV[1].to_i host = ARGV[0] rounds = ARGV[2] ? ARGV[2].to_i : 5 $/ = ';' sock = TCPSocket.open(host, port) sock.setsockopt(Socket::IPPROTO_TCP, Socket::TCP_NODELAY, 1) init = sock.gets dx, dy, time_limit, min_sensor, max_sensor, max_speed, max_turn, max_hard_turn = init.scan(/-?[\d\.]+/).map!{|f|f.to_f} count = 0 aa = false sock.each_line do |line| #puts line case line[0] when ?T time, ctrl, x, y, dir, speed = line[1..-1].scan(/[^\s]+/) if time=='0' sock.write('a;a;') aa = true else x = x.to_f y = y.to_f dir = dir.to_f pos_dir = Math.atan2(y,x)*180/Math::PI acc = ctrl[0] turn = ctrl[1] dis = x**2 + y**2 if dis > 1000 sock.write('a') aa = true elsif aa aa = false sock.write('b') end craters_dir = 0 boulders_dir = 0 if line.scan(/h/).length == 0 craters = line.scan(/c (-?[\d\.]+) (-?[\d\.]+) (-?[\d\.]+)/) range = AngleRange.new(dir, 20.0) if craters.length > 0 craters.map!{|c|c.map!{|f|f.to_f}} near_dir = nearest(craters, x, y, dir, range) if near_dir if range.include?(near_dir, AngleRange::DIR_R) craters_dir += 1 elsif range.include?(near_dir, AngleRange::DIR_L) craters_dir -= 1 end end else boulders = line.scan(/b (-?[\d\.]+) (-?[\d\.]+) (-?[\d\.]+)/) range = AngleRange.new(dir, 10.0) if boulders.length > 0 boulders.map!{|c|c.map!{|f|f.to_f}} near_dir = nearest(boulders, x, y, dir, range) if near_dir if range.include?(near_dir, AngleRange::DIR_R) boulders_dir += 1 elsif range.include?(near_dir, AngleRange::DIR_L) boulders_dir -= 1 end end end end end if craters_dir > 0 sock.write('l') elsif craters_dir < 0 sock.write('r') elsif boulders_dir > 0 sock.write('l') elsif boulders_dir < 0 sock.write('r') else range = AngleRange.new(pos_dir, 180) if range.include?(dir, AngleRange::DIR_R) if turn != ?r && turn != ?R sock.write('r') end else if turn != ?l && turn != ?L sock.write('l') end end end sock.write(';') end when ?B when ?S when ?C when ?K when ?E if (count += 1) == rounds exit end end sock.flush end sock.close
言いたかったこと。
見てわかるように、やってることのショボさは尋常じゃないです。でも最初に問題文読んだとき「こんなの俺程度じゃどうしようもないじゃん……」という印象ほどじゃあなかったなと。なんだかんだとダラダラ書いて、動いてるプログラム見てりゃ結構楽しいんですよ。ICFPCはプログラミングスキルそんな高くない人でも割と楽しめましたよ、というのが言いたかったことです。どっとはらい。
