CodeIQ：メビウスの亀
私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「メビウスの亀」（CodeIQ）を参照してください。
問題の概要
【概要】
右写真のようなメビウスの帯の上を、不思議な亀が歩いています。
亀の初期位置は「1a」のマスで「2a」の方を向いています。
亀はコマンドのとおりに進みます。コマンドは下表のとおりです：
コマンド 意味 R 90度右に向きます。 L 90度左に向きます。 B 紙の裏側に移動します。向きは変わりません。
たとえば、
「1a」の位置にいて「1b」の方を向いている
↓Bコマンド
「1E」の位置で「1D」の方を向いている
という具合です。1〜9 1〜9マス 進みます。紙のフチに到達したら、裏側に行きます。
たとえば、
1c→1d→1e→1A→1B→1C
という具合です。
最終的に到達するマスの名前を計算して下さい。
メビウスの帯は、片面が (1〜32)×(a〜e)、反対側の面が(1〜32)×(A〜E) となっている紙をメビウスの帯になるようにしたものです。
【入出力】
入力は
L9R9B9
のようになっています。
コマンドの列が区切り文字なしで並んでいます。
出力は、
19a
のような感じです。
最終的に到達するマスを答えて下さい。
【例】
入力 出力 L9R9B9 19a RRRB1 1D
【補足】
不正な入力に対処する必要はありません。
コマンドの長さは1以上 20 以下です。
私のプログラム
Rubyで解答しています。
#!/usr/bin/ruby
# 向きを変える
def turn(pos, dir, cmd)
ndir = nil
npos = nil
if cmd == "B"
side = {"f"=>"b", "b"=>"f"}
ndir = [-1*dir[0], dir[1]]
npos = [side[pos[0]], -1*(pos[1]-4), pos[2]]
elsif cmd == "L"
nldir = {
[1,0] => [0,-1], # 右から上
[0,-1] => [-1,0], # 上から左
[-1,0] => [0,1], # 左から下
[0,1] => [1,0], # 下から右
}
npos = pos
ndir = nldir[dir]
elsif cmd == "R"
nrdir = {
[1,0] => [0,1], # 右から下
[0,1] => [-1,0], # 下から左
[-1,0] => [0,-1], # 左から上
[0,-1] => [1,0], # 上から右
}
npos = pos
ndir = nrdir[dir]
end
return[npos, ndir]
end
# 進む
def move(pos, dir, cmd)
side = {"f"=>"b", "b"=>"f"}
s = pos[0]
x = pos[1] + dir[0] * cmd.to_i
y = pos[2] + dir[1] * cmd.to_i
if y < 0 then
y = 32 + y
s = side[s]
elsif y >= 32 then
y = y - 32
s = side[s]
end
if x < 0 then
x = 5 + x
s = side[s]
elsif x >= 5 then
x = x - 5
s = side[s]
end
return [[s, x, y], dir]
end
# 座標を文字列で返す
def getPos(pos)
base = pos[0] == "f" ? 0x61 : 0x41
return (pos[2]+1).to_s + (base+pos[1]).chr
end
# 上下：1-32の方向
# 左右：a-e, A-Eの方向
# 座標は0始まりの数値(上下：0-31、左右：0-4)で扱う
def solve(input)
pos = ["f", 0, 0] # 位置：表裏(f, b), x, y
dir = [0, 1] # 向き：x,y
input.chars{|c|
if c =~ /[0-9]/ then
pos,dir = move(pos, dir, c)
else
pos,dir = turn(pos, dir, c)
end
}
return getPos(pos)
end
# main
while line = gets
line.strip!
if line.empty? then next end
puts solve(line)
end
解説
マップ移動をトレースする問題です。
写真が微妙にピンボケ（というかピントが薄い）のでメビウスの輪がどこからどこに繋がっているかわかりづらいですが、それさえ把握できれば素直な実装でいけます。
考え方
最初に少し補足です。
マップは表は表裏次のような紙をメビウスの輪になるようにつなげたものです。
| 表 | 裏 | ||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
32aが1A、32eが1Eと繋がります。
この問題でややこしいのはコマンドBだけです。
それ以外の境界移動は、
32xから下に移動は1X（xはa〜e、XはA〜E）
32Xから下に移動は1x（xはa〜e、XはA〜E）
Yeから右に移動はYA（Yは1〜32）
Yaから左に移動はYE（Yは1〜32）
となります。
コマンドBの場合、
x座標がa↔︎E、b↔︎D、c↔︎C、d↔︎B、e↔︎Aとなりますが、y座標は変わらず、
進行方向がx座標方向の時は反転するが、y座標方向の時は変わらない、
ということになります。
これをプログラムで実装すればOKです。
main
入力値をsolve()に渡し、結果を印字します。
solve(input)
入力値を1文字ずつ解釈しながら現在地を更新し、最後の入力値を処理したところで結果を返します。
座標は表裏とx方向は0〜5、y方向は0〜32の数値で扱います。
変数posは現在地で[表裏,x座標,y座標]で管理します。表は"f"、裏は"b"としています。
dirは現在の進行方向で上[0,-1]、右[1,0]、下[0,1]、左[-1,0]としています。
76〜82行目でコマンドを1つずつ実行します。
数値の場合はmove()で移動し、文字の場合はturn()で向きと表裏の移動を行います。
最終的にposをgetPos()で文字列に変換して返します。
turn(pos, dir, cmd)
考え方に書いた通りの処理を行います。
引数posは[表裏,x座標,y座標]、dirは進行方向、cmdは"B","L","R"のどれかです。
cmdが"B"の場合、
表裏が入れ替わり、
x座標がa↔︎E、b↔︎D、c↔︎C、d↔︎B、e↔︎Aとなりますが、y座標は変わらず、
進行方向がx座標方向の時は反転するが、y座標方向の時は変わらない、
ということになるのでその変換を行います。
進行方向の反転はx方向の移動量に-1をかければOKです。y方向に移動している場合はx方向の移動要素は0なので-1をかけても問題ありません。
x座標は数値で表現しているので-1*(現在の値-4)で変換できます（例：現在b(座標1)の場合は-1*(1-4)=3でdの場所になり、別途表裏を管理しているのでDとなる）。
cmdが"L"か"R"の場合は進行方向を90度回転した値にし、posは変更せず返します。変換は定数で現在の進行方向をキー、次の進行方向を値とした連想配列で求めます。
コマンド処理後の位置と進行方向を返します。
move(pos, dir, cmd)
考え方に書いた通りの処理を行います。
引数posは[表裏,x座標,y座標]、dirは進行方向、cmdは"0"〜"9"のどれかです。
まず単純に現在の進行方向にしたがってcmdで指定されただけ進めます。
x座標、y座標共に計算していますが進行方向のx要素とy要素はいずれかが必ず0なので両方とも計算してしまって問題ありません。
あとは境界を超えた場合の処理で、
y座標が0未満になった場合は32+yにして表裏を反転、
y座標が32以上になった場合はy-32にして表裏を反転、
で計算できます。
x座標も同様に、
x座標が0未満になった場合は5+xにして表裏を反転、
y座標が5以上になった場合はx-5にして表裏を反転、
で計算できます。
進行方向はいじらないので返却値には不要なのですがturn()との対称性のためコマンド処理後の位置と進行方向を返します。
getPos(pos)
位置を文字列で返します。
y座標は0始まりを1始まりにするので+1します。
x座標は表側なら'a'の文字コードに座標、裏側なら'A'の文字コードに座標を加えて文字に変換します。
あとはこれを連結して返します。
雑感
Bの時に進行方向と座標がどうなるかさえつかめれば問題ないと思います。
というか、どういう紙をメビウスの輪にしたのかを把握するのに一番手間取ったような。