オフラインリアルタイムどう書くE13参加しました
はじめに
2017/4/1開催の「オフラインリアルタイムどう書くE13」に参加しましたので、そのレポートです。
どんな感じ?
前回から導入された卓球台で、席順を決める卓球の勝負が行われるようになりました。嘘です。が、久しぶりにプレイできて丁度体を暖めることが できました。まあ、とはいえ…ガチ勢の球は流石に厳しかった。
今回は人数が少なく、出題者の鍋谷さん含め6名、解けたのは3名、難易度は高目でした。問題としては条件を絞った通常版と無制限の全条件版の2種類がありましたが、40～50分の時点でなんとか組めました。
問題
問題は六角形のテトロミノでした。概要は次の通りです。
- a～z の英字が割り振られたヘクス ( 6角形のマス目 ) の内、4マス ( 相異なる4文字の英字 ) が指定される
- その4マスが形作るテトロミノ ( 連結する4マスによる図形 ) の形状を、指定の英大文字で返す
- 回転・平行移動により重なるテトロミノは同じ形状と見做す。ただし反転 ( 線対称移動 ) は除く
- 問題の条件は2種類、通常版は特定のテトロミノに当てはまらない形状は全て - と判定する。全条件版は全てのテトロミノの形状が網羅されており、テトロミノを構成しない場合のみ - とする
詳細は上のリンクからご覧ください。
解説
会場での実装
基本方針としては素直かと思います
- 4つのマスを座標で表す
- 6通り回転させつつ、一致する形状がないか調べる
- 形状を見る場合は、ある基準で座標をソートして、その中でとった基準との差分を見る ( 平行移動に対応 )
さて、座標の取り方ですが、次の図のように、60°の角度で2本の軸を設け、xy平面ではなく複素平面を構成しています。最近のマイブームとでもいいますか、2次元データを1まとまりとして扱えるので複素数が実は便利なのです。
複素数で扱うもう1つのメリットは、回転の取り扱いやすさです。回転というのは一種の線形変換として扱え、しかも特定の変換結果から全体像をすぐにつかむことができます。
今回は、上の図のように、x+yi → xi+y(-1+1i) という変換になっています。
※画像では見易い位置を回転中心としていますが、実際は原点に相当する a のマスが中心です。
さて、実例として#21 のパターンを見てみます。
これは、反時計に4/6回転すると、問題にあるDのパターンと一致します。そして、一番下 ( 虚部が最小 ) から見ると、それぞれのマスの相対位置は -1+1i, 1i, 2i ( 虚部を実部より優先した昇順 ) ということで、検出することができます。
ということで、通常版、全パターン版のRuby実装です。なお、全パターンに対応する場合も、この相対位置の組をデータとして網羅するだけで済むので、拡張は非常に簡単です。
もうちょっと修正
さて。会場では修正しきれなかったのですが、若干不満が残っています。それは、
- 位置をソートする時に、虚部優先にしているので比較処理がスッキリしない
- ソートした配列を一回変数に保存している
- 回転の計算で、実部・虚部を .real, .imag として取り出しているのが生々しい
ということでここいらへんを書き直したのが次の実装です。
それぞれ
- 実部優先にして、.rect ( 実部・虚部の配列を返すメソッド ) だけで比較
- 先頭からの相対位置ではなく、ソート順での直前のマスとの差分で形状を判断
- なるべく複素数での計算で頑張る
としています。
終わりに
次の開催案内が出ました。5月初めはGW真っ只中になるため、次回E14は6月です。
なお、今回の色々な方の実装例は、オフラインリアルタイムどう書くE13 の問題 - Qiitaに紹介されています。
