第28回高専プロコン競技部門に出場しました

第28回高専プロコン 競技部門に出場しました Shu Kakihana(4-mi)

結果

一回戦1位通過🤣(ｲｪｰｲ)

準決勝15位敗退😭(ｶﾅｼｲ)

今年の競技部門はどんなやつ(簡単に) • A4サイズくらいの木の板のわくが与えられる • わくにピースを埋める • ピースやわくの頂点情報などはQRコードによる ヒントとして使用できるが，減点される • 全てのピースを埋めれば100点，ヒントを使うと そこから減点される(形状情報: -10, 位置情報: -20) • 全てのピースを埋めることが出来なければ0点

開発する必要があるもの • • • パズルソルバ • その名の通りパズルを解くためのプログラム • C++で実装 GUI • 最終的にパズルを組むのは人間 • 人間にわかりやすいようにピースやわくを表示 • Javaで実装 QRコード読取機 • ヒントであるQRコードを使うため • C++で実装

パズルをプログラムで解く • どんなアプローチ? • わくの各頂点の角度に合うピースを探す • 埋める • ピースとわくをマージして次のわくとする を繰り返す • 普通の全探索だと状態数多すぎて死ぬ • いい感じの評価関数でビームサーチやれば割りと短時間 で解けそう(本番ではChokudaiSearchを使用)

パズルをプログラムで解く • 幾何パートやりたくない… • つよいC++ライブラリ，Boostで解決 • 図形のマージ，面積計算，交差判定とか諸々

枝刈り • わくにおいて任意の辺の長さが4グリッドより小さい辺 • 全てのピースの最小角より小さい角 が出たらそのノード以降の探索打ち切り

評価関数 • 評価関数 • 探索していく上で今の状態を評価し数値化 • 埋めた頂点に接する辺が一致していたら 評価を上げる評価 • フレームの凸包面積が小さければ評価を上げる

試しにサンプルでやってみる

だめだ〜〜〜〜〜😫😫😫😫

1回戦前日夜までこの状態

必死になってバグを探す • ピースを反転したときの座標が反時計回りになっていた • • boost::geometry::correct()で直す それでもうまくいかない • Boostの都合上，辺と辺で囲まれた角の角度を求める とき，一方の辺の座標を反転をしないといけなかっ たっぽい • 座標反転は自前で実装

Yeah~~~~~~👍 👍 👍 👍

10秒くらいで完全解が出てビビる • 完全解が出た瞬間はめっちゃ嬉しかった • ここから少しパラメータをいじったりして寝た

1回戦に臨む • 意外にいいところまでいけるかもと思いながら会場に 向う • 何故か1位を取れてしまう • ぼくら以外のチームは位置情報を使っていて減点されて いた

プログラム上で完全解は出なかった • 残りの部分は人力で埋められるレベルだった • なぜうまくいかなかったかわからなかった • • ホテルに帰って考察しているとpureが問題点を指摘 • 180°が出来てしまったときに探索が止まるっぽい なるほど〜と思いながら修正しようと思ったが 実装がわからなくなって結局あきらめて寝た

準決勝 • 案の定そのケースにぶち当たってデタラメな結果が帰っ てきた • 仕方がないので諦めてヒントを全部開け人力で埋めた • 15位

改善法 • 都立品川の解法的なのを盗み聞きすると • 90°がなるべく出ないようにすると割りと良い解が でるらしい • マルチスレッド化 • 最初にピースを置く場所を変えて複数のスレッドで 走らせればよかった

感想 • 解けると，楽しい • C++の理解が深まった • Boostは強い • 一人で全てを抱えるとしんどいのでタスクを振ろう • 競技部門やりたい人があまりいなさそうなので 興味ある人はぼくに話しかけてください