paiza Aランクレベルアップ問題の「へび」をpython3で解いてみた

自分のスキルをチェックできるというpaizaランクなるものを知り、力試しと勉強にとやってみました。
Aランクの問題はいきなり取り掛かるにはちょっと難しそう…ということでまずは例題にチャレンジしました。
使った問題はこのページの「へび」です。
https://paiza.jp/works/mondai/a_rank_level_up_problems/problem_index?language_uid=python3

与えられた大きさのマップの中で時間経過とともにルールに従って蛇が移動し、移動ができなくなるまでに通った軌跡を出力せよ、という問題です。

このページでは、解法のヒントとなる問題を順に解いていけば、それらの要素を包括した最終問題(「へび」)を解けるようになるという風に設計されています。が最初の問題を解いたところで面倒くさくなってしまい、最終問題に移動しました。そのため手順はめちゃくちゃかもしれません。

大まかな作成手順の設定

・最初の入力行で読む必要のある行数が全てわかるので、先に全部の情報得るためにすべての入力データを整理し、マップとしてまとめる。
・同じ座標を２回踏んだり、マップ外に出ると終了になる。位置を座標でx、yのように管理し、一度通った座標はすべて記録しておく必要がある。
・方向転換の設定が大変そうなので、方向転換の関数を定義してまとめて扱えるようにしよう

最初の情報の取り込み

#入力データの取得
import sys
F = sys.stdin
N = F.readline()

#取得したデータを個別の数値に変換
firstline = N.strip("\n").split(" ")
firstlist = [int(n) for n in firstline]

#マップサイズ、初期座標、転回回数、転回時刻の取得
ylen = firstlist[0] - 1
xlen = firstlist[1] - 1
#マップの座標はゼロを含むので１引いておく必要がある
Y = firstlist[2]
X = firstlist[3]
rotatenum = firstlist[4]
tizu = []
rotatetime = []
rotatedir = []

最初の行からわかる情報を整理し、必要な基礎情報を集めました。

方向転換の関数をつくる

最初の設定で蛇は北を向いているとのことですが、転回のたびに左右どちらかに向きを変えて進みます。東西南北の移動を座標に反映させるための関数を作りました。

#方向転換せず直進するとき
def norotation(dir, Y, X):
    if dir == 'N':
        newY = Y - 1
        newX = X
        newdir = 'N'
    elif dir == 'E':
        newY = Y
        newX = X + 1
        newdir = 'E'

    elif dir == 'W':
        newY = Y
        newX = X - 1
        newdir = 'W'

    elif dir == 'S':
        newY = Y + 1
        newX = X
        newdir = 'S'
    return newY, newX, newdir

#方向転換するとき
def rotation(dir, changedir, Y, X ):
    if dir == 'N':
        if changedir == 'R':
            newdir = 'E'
            newY = Y
            newX = X + 1
        else:
            newdir = 'W'
            newY = Y
            newX = X - 1

    elif dir == 'E':
        if changedir == 'R':
            newdir = 'S'
            newY = Y + 1
            newX = X
        else:
            newdir = 'N'
            newY = Y - 1
            newX = X

    elif dir == 'W':
        if changedir == 'R':
            newdir = 'N'
            newY = Y - 1
            newX = X
        else:
            newdir = 'S'
            newY = Y + 1
            newX = X

    elif dir == 'S':
        if changedir == 'R':
            newdir = 'W'
            newY = Y
            newX = X - 1
        else:
            newdir = 'E'
            newY = Y
            newX = X + 1
    return newY, newX, newdir

マップ作成

ここで初期設定の方角(北)も入れていますが、これは問題文の設定のとおりです。
マップは'.'(移動可)と'#'(移動不可の障害物)でできています。
マップ用に用意した空のリストに、一行ずつマップを表す文字列を入れました。
リストのインデックスがY座標、要素である文字列の順番がX座標ということになります。

#マップ取得
dir = 'N'
for i in range(ylen + 1):
    N = F.readline()
    N2 = N.strip("\n")
    tizu.append(N2)

初期位置の設定

蛇が通った場所は*で示すルールです。
初期座標、つまり最初に蛇がいる位置を変更しておきます。
文字列はそのまま位置を指定して文字を書き換え、ということができないと思うので、
いったん文字列を一文字ずつのリストに変更してから書き換えたい場所を変更し、
もう一度つなげて文字列に戻したもので該当するインデックスYの要素を更新します。

#最初にへびがいる座標を'*'に変える
tizu[Y]
newline = tizu[Y]
mojilist = list(newline)
mojilist[X] = '*'
changedline = ''.join(mojilist)
tizu[Y] = changedline

転回時刻と方向の取得

どの時刻に左右どちらに移動するかの情報を取得します。
0~99までの100の時刻の中で、以下のリストに入ってくる時刻のみ転回し、それ以外は直進です。

for i in range(rotatenum):
    N = F.readline()
    N3 =N.strip("\n").split(" ")
    rotatetime.append(int(N3[0]))
    rotatedir.append(N3[1])

実際の移動マップを作成する

これまで準備した情報を使って、実際に0から99までの時刻で蛇を移動させてマッピングします。

for time in range(100):
#転回時刻ではないときの移動
    if time not in rotatetime:
#現在の座標取得
        tizuline = tizu[Y]
        tizupoint = tizuline[X]
#直進後に向いている方角と移動後の座標を取得
        c = norotation(dir, Y, X)
        newY = c[0]
        newX = c[1]
        newdir = c[2]
#蛇がマップ外に出たら終了
        if newX > xlen:
            break
        elif newX < 0:
            break
        elif newY > ylen:
            break
        elif newY < 0:
            break
        else:
            pass
        newline = tizu[newY]
        mojilist = list(newline)
        newpoint = mojilist[newX]
#障害物(#)か自分の通った場所に当たったら終了、そうでなければマップを更新して次のループへ
        if newpoint == '#':
            break
        elif newpoint == '*':
            break
        else:
            mojilist[newX] = '*'
            changedline = ''.join(mojilist)
            tizu[newY] = changedline
            #地図をへびの通った印をつけて更新
        Y = newY
        X = newX
        dir = newdir
#転回時刻の移動
    elif time in rotatetime:
#現在の座標取得
        timeindex = rotatetime.index(time)
        changedir = rotatedir[timeindex]
        tizuline = tizu[Y]
        tizupoint = tizuline[X]
#転回させて、転回度に向いている方角と移動後の座標を取得
        c = rotation(dir, changedir, Y, X)
        newY = c[0]
        newX = c[1]
        newdir = c[2]
#蛇がマップ外に出たら終了
        if newX > xlen:
            break
        elif newX < 0:
            break
        elif newY > ylen:
            break
        elif newY < 0:
            break
        else:
            pass
        newline = tizu[newY]
        mojilist = list(newline)
        newpoint = mojilist[newX]
#障害物(#)か自分の通った場所に当たったら終了、そうでなければマップを更新して次のループへ
        if newpoint == '#':
            break
        elif newpoint == '*':
            break
        else:
            mojilist[newX] = '*'
            changedline = ''.join(mojilist)
            tizu[newY] = changedline
            #地図をへびの通った印をつけて更新
        Y = newY
        X = newX
        dir = newdir

終了後のマップを出力

蛇の移動経路を反映したマップを出力します。

for t in range(len(tizu)):
    print(tizu[t])

個人的にミスの原因となった難しかったポイント

座標や時刻など、多くの数値が初期データとして渡されますが、
「0を含むか含まないか」を間違えて1ズレてしまい、移動距離が一つ足りないとか、最後の移動時刻を取り漏らす等のミスを頻発させてしまいました。これは作成しているうちにごっちゃになってしまいがちなので注意が必要だと感じました。