Pythonで解く歩行ロボットのシミュレーション問題：最大ユークリッド距離を求めるアルゴリズム

無限に広がるグリッド上に、原点 (0, 0) からスタートして北向きに立っているロボットがあるとします。このロボットは、次の3種類のコマンドを受け取ることができます。

1. -2：左に90度回転する
2. -1：右に90度回転する
3. 1〜9：指定された数だけ前方へ移動する

また、グリッド上には障害物となるマスが存在します。障害物の位置は配列 obstacles で与えられ、i番目の障害物は座標 (obstacles[i][0], obstacles[i][1]) にあるとします。ロボットが障害物のあるマスに進もうとした場合、そのマスには入れず、直前のマスにとどまります。

このとき、ロボットが原点から取りうる最大のユークリッド距離の2乗を求めるのがこの問題の目的です。

入力例

たとえば、commands = [4, -1, 4, -2, 4]、obstacles = [[2, 4]] という入力の場合、出力は 65 になります。これは、ロボットが (1, 4) で障害物に阻まれて停止し、左に向きを変えて (1, 8) へ進むためです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 方向ごとの移動オフセットを定義します：position_offset = [(0, 1), (1, 0), (0, -1), (-1, 0)]（北・東・南・西の順）
• 現在位置 x、y、向いている方向 direction、最大距離 max_distance をすべて 0 で初期化します
• 各コマンドに対して以下を処理します：
  • コマンドが -2 の場合：direction = (direction - 1) % 4 で左回転
  • コマンドが -1 の場合：direction = (direction + 1) % 4 で右回転
  • それ以外の場合：現在の方向に応じたオフセット (x_off, y_off) を取得し、コマンドの値が 0 になるまで1マスずつ前進します。ただし、次のマスが障害物なら移動せず、残りのステップも破棄されます
• 毎ステップ、x² + y² を計算し、max_distance を更新していきます
• 最終的に max_distance を返します

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def robotSim(self, commands, obstacles):
        position_offset = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        obstacles = set(map(tuple, obstacles))
        x, y, direction, max_distance = 0, 0, 0, 0
        for command in commands:
            if command == -2:
                direction = (direction - 1) % 4
            elif command == -1:
                direction = (direction + 1) % 4
            else:
                x_off, y_off = position_offset[direction]
                while command:
                    if (x + x_off, y + y_off) not in obstacles:
                        x += x_off
                        y += y_off
                    command -= 1
                max_distance = max(max_distance, x**2 + y**2)
        return max_distance

ob = Solution()
print(ob.robotSim([4,-1,4,-2,4],[[2,4]]))

実行結果

入力：

[4,-1,4,-2,4],[[2,4]]

出力：

65

ポイントのまとめ

• 障害物の判定を高速化するため、obstacles リストをセット（set）に変換しています。これにより、各マスの存在確認が O(1) で行えます
• 方向の管理はモジュロ演算（% 4）を使うことで、北→東→南→西の循環をシンプルに表現できます
• ユークリッド距離そのものではなく距離の2乗を求めることで、平方根の計算を避け、浮動小数点誤差も回避できます

このアルゴリズムの計算量は、全コマンドの移動ステップ数の合計に比例する O(N + K)（Nはコマンド数、Kは総移動距離）となり、非常に効率的です。