(ブログ名 '未定)

プログラミングとかのメモ帳

プロコンの反省を書き連ねるだけの雑記

プロコンの反省や経験など書き連ねただけの雑記
思いついつく度に追加します

やったこと

第27回プログラミングコンテスト競技部門に参加した
第27回 高専プロコン 競技部門 - Google 検索
公式サイトの競技内容を簡単に内容を説明すると、
1).パズルの欠片の画像を取り込むと、自動的に置き方を表示するプログラムを作成して下さい
2).パズルを人力で埋めて下さい(作成したプログラムを使えとは言っていない)
と言うものである。

いつ、何をやっていたか

予選資料作成(4〜5月頃)

 ピースの画像を頂点データに変換する役割、与えられた頂点データを用いてパズルを解く役割、解いたパズルを表示する役割の内、私はパズルを解く役割を担当することになった。
 この頃から、n-1解(職人の経験と勘により巨大なピースを一つ抜かして、職人の経験と勘によりピースを適当に埋める方式)の有効性について知っていて、プログラムする以上は唯一解を探す方式を取らなければならないと思っていた。
 当時は唯一解を出すためには、二角の和が180度となる場合を探す方式も、等しい長さの辺を探す方式も、特別な場合を考えた時に唯一解に至らなくなると考えていて、考えうる全てのパターンを試す必要があると考えていた。 そうなると、探索空間も膨大になるわけで、、、。(以下ドキュメントに記載予定) とにかく、このことを考えながら、後の空白の三ヶ月に突入することとなる

空白の三ヶ月(6〜9月中盤)

 この間には、夏休みを始め多くの休日が存在していたが、ほとんどコードを書けなかった。理由としては、時間を遊びに使ってしまったこと、まだ時間があると考えてしまったこと、とりあえず指を動かさなかったこと、問題を解く気にならなかった事にある。 根本的には、問題を解く気にならなかった事が原因だと思っている。
 先延ばし魔の威力は絶大なものだったと今でも反省している。
 

精神と時の部屋(9月終盤〜プロコン当日)

 結局、夏休みの最終盤までコードを書くことはせず、地獄の二週間が始まることとなった。ここまでに実装されていたのは、ピースの定義・当たり判定・座標をピースに変換する関数だけで、言ってしまえば、他の関数は実装されていなかった。

ピースの結合(プロコン二週間前〜プロコン一週間前ぐらい)

 まず取り掛かったのは、ピースの結合である。
 ピースの結合とは、ピースAのある点Anと、ピースBのある点Bmを、合わせることにより、新しいピースに変換する動作である。角度と裏表を付けたピースを2つ用意し、誤差範囲以下にある2つの点を原則一つの点にした後、角度が360度か180度になった点を排除する。このことにより実装した
 最も基礎的な部分であるが、考えた項目(辺の上にある点、点が辺に接触する場合、図形の中に図形を内包する場合など)が多く、結合の時に発生する全ての事象を考慮しようとし、多くの時間がかかり、思考に苦労した。

誤差と探索 (プロコン1週間前ぐらい〜プロコン4日前)

 この時から、パズルのピースとモニタを 二対一 でにらめっこすることとなる。
 画像を取り込む時に発生する誤差、それをプログラムすることは楽に出来た。ただ、誤差の調整と全探索は、両者は矛盾しているものだと思うこととなる。
 問題は、プログラムは、現実は異なるピースを誤差が原因で、同じピースであると判断すること、もしくは、本来は同じ座標にある点が誤差が原因で、合成されなくなることであった。 ピースの結合が狂うことの問題は、全探索しようとする時に発生し、誤差と全探索の間に発生する矛盾を考えていた。

手動動的計画法(プロコン4日前)

 大会まで残り4日になった中、私は、探索を動的計画法(当時は、ピース一つ一つの結合を小さな問題と考えていた)で書こうと思っていた。ただ、誤差を考えると、プログラムが書けなくなることも知っていたわけである。 そんな中、部活に参加してある声を聞くこととなる
>> 人力をサポートするプログラムを作れば?
 まぁ、こんな感じの声だったと思う。動的計画法・全探索・誤差・残りの時間・人力のサポート・自分の現状・・・そんな事を考えながら、お風呂から上がると、突然と指が動き始めた。私が手動動的計画法と名付けるアルゴリズムの設計が、微小な時間にて書き上げられたのである。
 
手動動的計画法は、誤差と全探索の矛盾を埋め合わせるために考えたアルゴリズムで、動的計画法で言う"小さな問題を解くこと":このプログラムで言う"確定されたピースの結合"は人間が行う。プログラムの機能は表面上、1)結合できるかもしれないピースを候補として表示する事と、2)人間が他にパターンが無いと判断したピースの候補を、コマンドライン上に打ち込ませること、3)そして内部的なピースの状態を更新することの3つである。

ここに画像を追加する予定

新たなる実装(プロコン3日前〜競技部門本戦中)

 新しいアイディアを考えてから、他の人の手を借りながら実装を始めた。そして、三日三晩の徹夜や、特急コーディング、そして、会場コーディングを経て、実装が終わることとなる。

戦いの終焉(プロコン競技部門終了〜数日後)

 結果として、プログラムはつまらない理由(ファイルシステムの違い)で動作しなかった。他のいかなるプログラムも人力に圧倒された事、もっと計画的にやっておけば良かったという反省・・・などと、残念な気持ちに支配されながら、今年のプロコンは終わった。

反省点

  • 大会前のデスマはするべきでない。そもそもやった時点で負けだと思うべき
  • チームメートとのコミュニケーションをもっと取っておけばよかった。
  • 緊張により、大会中にいつも通りのパフォーマンスを出せなかった。練習を予め積んでおけば、緊張はほぐされたと思う
  • 長期休業中にプロコンの準備ができると思わないほうがいい。可能なら、休業前に作るべき
  • 先延ばし魔の恐怖を味わう前に片付ける
  • 完全に動くと思われたプログラムが、つまらないミス(文字コードの互換性)で動作しなかった。練習を予め積んでおけば、問題に対処できたと思う。
  • もっと他の高専生達と交流したかった(ただし運営側のシステムにも問題がある。)
  • 計画性がなかった。もっと早い時期から書いていたら、徹夜も軽いものになっただろうし、練習の時間もとれ、プログラムの質が上がっただろう
  • モチベーションの維持が出来なかった(運営にも問題がある気がするが...。)やる気さえあれば、計画無視で急速にプロジェクトが進むと思った。

成果物

二回戦開始直前に作り終えたプログラム。
本番では、Windowsとのファイルシステムの違いにより、データを読み込めなかったと言う悲劇が発生した。
簡単にシステム概要を説明すると、
ピース毎の頂点座標を入力すると、ピース(枠を含む)に変換し、合体出来るピースの候補を探索・表示してくれる。
そこで、どのピースを合体したか?コマンドラインから入力することで、ピースの数がどんどん減っていく仕組み
f:id:ikemaki:20161014193441p:plain

ソースコードはこちら
github.com

微修正やドキュメント整備は後日やります。
アルゴリズムの詳細なども追加する予定

その他