オフラインリアルタイムどう書くE09参加しました

はじめに

2016/10/30開催の「オフラインリアルタイムどう書くE09」に参加しましたので、そのレポートです。

どんな感じ?

日曜開催だったためか参加者はかなり少なく…、まあ初参加の方もいなかったので自己紹介は割愛で。進行は早かったですね。

さて、今回は鍋谷さん出題の回でした。取り敢えず問題を見た瞬間、「どうすりゃいいのコレ…」という感じでしたが、何とか整理して残り10分で一発で通しました。バグってたら間違いなく時間足りなくなっていたところなのでホッとしました。

問題

問題は五角形の世界でした。概要は次の通りです。

  • 五角形のマスで満たされたフィールドを入力の指示に従って進む。
  • 途中で通ったことのあるマスに再びついた場合は、そこまでに何マス進んだか、ついた場所は何マス目に通った場所かをカンマ区切りの文字列を返す。
  • 重複して通るマスがない場合は、- を返す。
  • 入力の指示は、向いている方向へ1進む ( その後向きを反転 )、向きを変えるといったのものから構成されます。

詳細は上のリンクからご覧ください。なお、フィールドに一切番号等IDを振っていないのは、座標設定等で変に固定観念を与えたくなかったからだそうです。

解説

実装1

ということで、図を見て座標の設定どうするんだと途方に暮れたわけですが。5角形4つをペアにして6角形のユニットが作れることから、そのユニットの座標と、ユニット内の位置とで各5角形を識別することにしました。

f:id:ange1:20161203140046p:plain

そして、5角形の各辺にも、反時計まわりで0~4のIDを割り振ると、移動後の位置・向きの関係が次の図のように整備できます。

f:id:ange1:20161203140426p:plain

ということで、それに従って座標を遷移させるように実装したのが、会場で組んだ実装です。

コードの最初で定義している X がその遷移のテーブルで、はっきりいってここを整備するのに20~30分かけてます。ここが全てと言えます。

実装2

ところで。今回私のように、五角形4つをまとめて1ユニットとする考えをした人が多かったのですが、2つで1ユニットにするという考え方も出てきました。五角形をひしゃげさせて長方形とみなし、2つまとめて正方形を作るということです。丁度次の図のようになります。

f:id:ange1:20161203141439p:plain

4つをまとめる時と違って、縦向き2つ組、横向き2つ組という2種類のユニットができることにはなりますが、こちらの方がよりすっきりしていると言えます。出題者の鍋谷さんも、これをイメージして問題を作り出したそうで。

そうすると、これを利用してより簡潔な実装が可能になります。

どういうことかというと、全ての長方形 ( 五角形をひしゃげさせたもの ) は、向きが違うだけで全て対等な存在ですから、ある向きに動いた時の位置・向きの変化は相対的に整理することができるということです。これが相対性理論ですね! ( 違います )

具体的には次の図のようになります。

f:id:ange1:20161203142020p:plain

長方形毎に、ベースとなるベクトル ( 対になっている長方形から逃げる方向 ) を基準とし、先ほどの実装と同じように、進む向きに 0~4 のIDを振った場合、座標の変化 と、ベースベクトルの変化 ( ユニット内の位置に相当 )が、ベースベクトルをどれだけの角度回転させた向きになるか、で整理できるのです。
※図中のオレンジが座標変化、青がベースベクトル変化を表します。

まとめると次のようになります。

  • 方向0 … 進んだ後の向き 0、座標変化なし、ベースベクトルは180°回転
  • 方向1 … 進んだ後の向き 2、ベースベクトル-90°の向きに移動、ベースベクトルは+90°回転
  • 方向2 … 進んだ後の向き 1、ベースベクトルの向きに移動、ベースベクトルは-90°回転
  • 方向3 … 進んだ後の向き 4、ベースベクトルの向きに移動、ベースベクトルは+90°回転
  • 方向4 … 進んだ後の向き 3、ベースベクトル+90°の向きに移動、ベースベクトルは-90°回転

では、プログラム上でこの回転はどう扱えば良いのでしょう…?

ベクトル・行列ライブラリで回転行列を計算しても良いのですが、もっとお手軽なものがあります。それは複素数です。理系の方であれば、高校で複素平面って習ってますよね。いや、私は習ってないんですが…。
複素数の演算により、+90°の回転は×i等の掛け算により向きを、それに移動方向を示す複素数の足し算で2次元の座標の変化を、それぞれまとめて管理することができます。

ということで、複素数の計算を使った実装は次のようになります。コード中の ip という変数が、上で言うベースベクトルを管理するものです。Rubyの場合、計算結果に小数が絡まない限り、整数係数の複素数のまま計算できるというのも良いところです。

終わりに

記事書きかけのまま随分経ってしまいましたが、次回開催後だとマヌケなので、なんとか仕上げました。というか、もう今日の夕方からですし。
次回は残念ながら所用で行けませんが、オンラインで参加したいと思います。