読者です 読者をやめる 読者になる 読者になる

オフラインリアルタイムどう書く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まとまりとして扱えるので複素数が実は便利なのです。

f:id:ange1:20170405170808p:plain

複素数で扱うもう1つのメリットは、回転の取り扱いやすさです。回転というのは一種の線形変換として扱え、しかも特定の変換結果から全体像をすぐにつかむことができます。

f:id:ange1:20170405173945p:plain

今回は、上の図のように、x+yi → xi+y(-1+1i) という変換になっています。
※画像では見易い位置を回転中心としていますが、実際は原点に相当する a のマスが中心です。

さて、実例として#21 のパターンを見てみます。

これは、反時計に4/6回転すると、問題にあるDのパターンと一致します。そして、一番下 ( 虚部が最小 ) から見ると、それぞれのマスの相対位置は -1+1i, 1i, 2i ( 虚部を実部より優先した昇順 ) ということで、検出することができます。

f:id:ange1:20170405193201p:plain

ということで、通常版、全パターン版のRuby実装です。なお、全パターンに対応する場合も、この相対位置の組をデータとして網羅するだけで済むので、拡張は非常に簡単です。

もうちょっと修正

さて。会場では修正しきれなかったのですが、若干不満が残っています。それは、

  • 位置をソートする時に、虚部優先にしているので比較処理がスッキリしない
  • ソートした配列を一回変数に保存している
  • 回転の計算で、実部・虚部を .real, .imag として取り出しているのが生々しい

ということでここいらへんを書き直したのが次の実装です。

それぞれ

  • 実部優先にして、.rect ( 実部・虚部の配列を返すメソッド ) だけで比較
  • 先頭からの相対位置ではなく、ソート順での直前のマスとの差分で形状を判断
  • なるべく複素数での計算で頑張る

としています。

終わりに

次の開催案内が出ました。5月初めはGW真っ只中になるため、次回E14は6月です。

なお、今回の色々な方の実装例は、オフラインリアルタイムどう書くE13 の問題 - Qiitaに紹介されています。