👌

Kickstart2020 RoundB: Robot Path Decoding

2021/05/29に公開

Python

stack

kickstart

tech

問題

新しい惑星を探索するRoverの移動プログラム（移動方向の指定）が与えられた時、Roverの最終位置を求めるというのが問題。Roverの移動プログラムは、以下の4つの移動方向を示す文字として表される。

N: １ユニット分北へ移動
S: １ユニット分南へ移動
E: １ユニット分東へ移動
W: 1ユニット分西へ移動

Roverの位置は $10^9$ 行x $10^9$ 列のグリッドで与えられ、初期位置は $\left(1,1\right)$ 。また、グリッドは円環で、 $10^9$ 行目から１ユニット分南へ移動した時の位置は $1$ 行目に戻り、１行目から１ユニット分東へ移動した時の位置は $10^9$ 行目になる。列の場合も同様。

移動プログラムは $X\left(Y\right)$ のような記述も可能で、例えば以下のように解釈する（ $2\leq X \leq 9$ )。

2(NWE): NWEを2回繰り返し = NWENWE
3(S2(E)): Eを2回繰り返し、SEEを3回繰り返し = SEESEESEE
EEEE4(N)2(SS): Nを4回繰り返し、SSを2回繰り返し = EEEENNNNSSSS

アルゴリズムと実装

基本的な考え方は、移動プログラムを逐次解釈していくだけなのですが、移動方向文字と繰り返し回数、開閉ブラケットで以下のように処理を行います。

繰り返し回数（23456789）の場合は、繰り返し回数用のスタック(Xs)にpush
移動方向文字と開ブラケットの場合は、row方向及びcol方向移動量を保持するスタックにpush
- ただし、S及びEの場合は1、N及びWの場合は-1をpush
- update(row_moves, col_moves, c)で処理
閉ブラケットの場合は、開ブラケット以降の移動方向に対して繰り返しを適用した値を計算し、row及びcolのスタックにpush
- update(moves, X)で処理

最後は、rowとcolのスタックに記録されている移動量を合計し、 $10^9$ の剰余計算とスタート位置オフセットを加えて出力するという処理になります。
計算量について。移動プログラム長をNとする。まず、N回のforループで、各ループで実施するpushやpopは $O(1)$ で計算できます。ただし、繰り返しを計算するときのpopのwhile繰り返しが移動プログラム長の繰り返しになることがあり、各文字は多くて2回走査される。また最後のsumの計算は $O(N)$ となるので、全体では $O(N)$ となる。移動量のスタック領域が必要なので、space complexityも $O(N）$ となる。
Test set1と2がPassedでしたが、もう少し最適化できそうな気がします。

def push(col_moves, row_moves, c):
    if c == '(':
        col_moves.append(c)
        row_moves.append(c)
    elif c == 'E' or c == 'W':
        move = 1 if c == 'E' else -1
        col_moves.append(move)
    elif c == 'N' or c == 'S':
        move = -1 if c == 'N' else 1
        row_moves.append(move)
    return col_moves, row_moves

def update(moves, X):
    i = len(moves) - 1
    move = 0
    while i >= 0 and moves[i] != '(':
        move += moves.pop()
        i -= 1
    moves.pop()
    moves.append(move * X)
    return moves

T = int(input())
for t in range(1, T + 1):
    program = input()
    col_moves = []
    row_moves = []
    Xs = []
    for c in program:
        if c == ')':
            X = Xs.pop()
            col_moves = update(col_moves, X)
            row_moves = update(row_moves, X)                
        elif c in ['(', 'N', 'S', 'E', 'W']:
            col_moves, row_moves = push(col_moves, row_moves, c)
        elif c in '23456789':
            Xs.append(int(c))
    col_end = 1 + sum(col_moves) % 10**9
    row_end = 1 + sum(row_moves) % 10**9
    print('Case #{}: {} {}'.format(t, col_end, row_end))

問題

アルゴリズムと実装

Discussion