「メビウスの亀」問題解答(CodeIQ)
はじめに
CodeIQというところでプログラミング問題に挑戦しましたので、ネタバレです。
問題
今回は次のような問題でした。
- メビウスの輪状のマス目 ( メビウスの帯 ) の上で、文字列として入力されるコマンドに従って亀を歩かせる時、亀が最終的に到達するマスを求め、マスの名前を出力する。
- メビウスの帯は、幅5マス、長さ32マスの紙からメビウスの輪 ( 表裏を1回ひねって輪状にする ) として構成したものである。
- 各マスの名前は、座標に基づいて付けられており、紙の表面が
1～32+a～e、裏面が1～32+A～E( 例えば5Cや32e) である。メビウスの帯にする際に、1a,1b,1c,1d,1eのマスには、それぞれ32A,32B,32C,32D,32Eが連結される。 - 亀は、最初
1aの場所にいて2aの方を向いており ( 右手が縁、左手が1b)、英数字で表されるコマンドを先頭から1文字ずつ解釈し、各文字に応じて下の表のように進む。- なお、
Bコマンドに対しては
1aの位置で1bの方を向いている状態→1Eの位置で1Dの方を向いている
というような動きになる。 - 数字のコマンドで裏に回る場合、
1c→1d→1e→1A→1B→1C
というような動きをする。
- なお、
| コマンド | 意味 |
|---|---|
R |
その場で90°右に向きを変えるだけ |
L |
その場で90°左に向きを変えるだけ |
B |
紙の裏側に移動する。向きはそのまま |
1～9 |
今向いている方向に、その数字のマス分進む。途中で縁に到達したら裏に回る |
なお、問題に載っていたメビウスの帯の図は次のようなものでした。
解説
このメビウスの帯ですが、マスに重複を許せば、配置としては次の図のような2次元トーラス ( ドラクエのマップのように、上下・左右がループする構造 ) と見ることができます。
とすると、これは整数環×整数環の2次元の問題なので、複素数として扱うことができます。
しかし、一つだけ難点があります。それはBによる裏側への移動です。位置および向きの変換は次の図のようになるわけですが…。これをどう扱うかが悩みどころです。
で、どうしたか。この位置・向きの変換は、虚軸方向の反転と見ることができます。そこでマスに対応する複素数の格子を2×2単位にして、なおかつ虚部を1ずらしで奇数にして、複素共役で扱うことにしたのです。
ちょうど次のような様子になります。
これで全て出揃いました。結局、
- 実軸方向は mod 128 でループし、0,2,4,… を、マスの1,2,3,… に対応させる
- 虚軸方向は mod 20 でループし、1,3,5,… を、マスのa,b,c,… に対応させる
- 実部 64～126 では、a,b,c,… と A,B,C,… を入れ替える
- 移動は距離2ずつ行う
- 方向転換
LおよびRは、それぞれ向きの90°回転 ( ×i )、-90°回転 ( ×(-i) ) で処理する Bによる裏周りは、位置および向きを複素共役に変える
ということで提出版のコード(Ruby)が次になります。each_with_objectのループで、rに格納されている位置・向きをころころ変換していくという、非常に単純な実装になっています。
終わりに
鍋谷さんは、2次元格子・座標系の問題のバリエーションが多いのですが、複素数がここまではまると気持ちいい感じがしますね。tap-breakも使えて、Rubyらしいコードになったと思います。
