<p>A robot on an infinite XY-plane starts at point <code>(0, 0)</code> facing north. The robot receives an array of integers <code>commands</code>, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:</p>

<ul>
	<li><code>-2</code>: Turn left <code>90</code> degrees.</li>
	<li><code>-1</code>: Turn right <code>90</code> degrees.</li>
	<li><code>1 &lt;= k &lt;= 9</code>: Move forward <code>k</code> units, one unit at a time.</li>
</ul>

<p>Some of the grid squares are <code>obstacles</code>. The <code>i<sup>th</sup></code> obstacle is at grid point <code>obstacles[i] = (x<sub>i</sub>, y<sub>i</sub>)</code>. If the robot runs into an obstacle, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.</p>

<p>Return the <strong>maximum squared Euclidean distance</strong> that the robot reaches at any point in its path (i.e. if the distance is <code>5</code>, return <code>25</code>).</p>

<p><strong>Note:</strong></p>

<ul>
	<li>There can be an obstacle at <code>(0, 0)</code>. If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to <code>(0, 0)</code> due to the obstacle.</li>
	<li>North means +Y direction.</li>
	<li>East means +X direction.</li>
	<li>South means -Y direction.</li>
	<li>West means -X direction.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [4,-1,3], obstacles = []</span></p>

<p><strong>Output:</strong> <span class="example-io">25</span></p>

<p><strong>Explanation: </strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 4 units to <code>(0, 4)</code>.</li>
	<li>Turn right.</li>
	<li>Move east 3 units to <code>(3, 4)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(3, 4)</code>, which squared is <code>3<sup>2</sup> + 4<sup>2 </sup>= 25</code> units away.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [4,-1,4,-2,4], obstacles = [[2,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">65</span></p>

<p><strong>Explanation:</strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 4 units to <code>(0, 4)</code>.</li>
	<li>Turn right.</li>
	<li>Move east 1 unit and get blocked by the obstacle at <code>(2, 4)</code>, robot is at <code>(1, 4)</code>.</li>
	<li>Turn left.</li>
	<li>Move north 4 units to <code>(1, 8)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(1, 8)</code>, which squared is <code>1<sup>2</sup> + 8<sup>2</sup> = 65</code> units away.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [6,-1,-1,6], obstacles = [[0,0]]</span></p>

<p><strong>Output:</strong> <span class="example-io">36</span></p>

<p><strong>Explanation:</strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 6 units to <code>(0, 6)</code>.</li>
	<li>Turn right.</li>
	<li>Turn right.</li>
	<li>Move south 5 units and get blocked by the obstacle at <code>(0,0)</code>, robot is at <code>(0, 1)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(0, 6)</code>, which squared is <code>6<sup>2</sup> = 36</code> units away.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= commands.length &lt;= 10<sup>4</sup></code></li>
	<li><code>commands[i]</code> is either <code>-2</code>, <code>-1</code>, or an integer in the range <code>[1, 9]</code>.</li>
	<li><code>0 &lt;= obstacles.length &lt;= 10<sup>4</sup></code></li>
	<li><code>-3 * 10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 3 * 10<sup>4</sup></code></li>
	<li>The answer is guaranteed to be less than <code>2<sup>31</sup></code>.</li>
</ul>

#include <span>
#include <array>
#include <vector>
#include <unordered_set>
using namespace std;

/*
The code will run faster with ios::sync_with_stdio(0).
However, this should not be used in production code and interactive problems.
In this particular problem, it is ok to apply ios::sync_with_stdio(0).

Many of the top-ranked C++ solutions for time on leetcode apply this trick,
so, for a fairer assessment of the time percentile of my code
you could outcomment the lambda expression below for a faster run.
*/

/*
const static auto speedup = [] {
    ios::sync_with_stdio(0);
    return nullptr;
}();
*/

class Solution {

    static const int TURN_RIGHT = -1;
    static const int TURN_LEFT = -2;
    static const int SUPPLEMENT_TO_PRIME_NUMBER = 29; 

    static constexpr array<int, 2> NORTH{ 0, 1 };
    static constexpr array<int, 2> EAST{ 1, 0 };
    static constexpr array<int, 2> SOUTH{ 0, -1 };
    static constexpr array<int, 2> WEST{ -1, 0 };
    static constexpr array<int, 2> RANGE_OF_COORDINATES{ -3 * 10000, 3 * 10000 };

    static constexpr array< array<int, 2>, 4> DIRECTIONS{ NORTH, EAST, SOUTH, WEST };

public:
    int robotSim(const vector<int>& commands, const vector<vector<int>>& obstacles) const {
        unordered_set<int> quickAccessToHashObstacles = createQuickAccessToHashObstacles(obstacles);

        int indexDirection = 0;
        array<int, 2> currentCoordinates = { 0, 0 };
        int maxSquaredEuclideanDistance = 0;

        for (const auto& command : commands) {
            if (command == TURN_LEFT || command == TURN_RIGHT) {
                indexDirection = calculateNewIndexDirection(command, indexDirection);
                continue;
            }

            for (int step = 1; step <= command; ++step) {
                int nextX = currentCoordinates[0] + DIRECTIONS[indexDirection][0];
                int nextY = currentCoordinates[1] + DIRECTIONS[indexDirection][1];

                if (quickAccessToHashObstacles.contains(calculateHashCoordinates(nextX, nextY))) {
                    break;
                }

                currentCoordinates[0] = nextX;
                currentCoordinates[1] = nextY;
                int currentDistanceFromStart = calculateDistanceFromStart(currentCoordinates);

                if (maxSquaredEuclideanDistance < currentDistanceFromStart) {
                    maxSquaredEuclideanDistance = currentDistanceFromStart;
                }
            }
        }

        return maxSquaredEuclideanDistance;
    }

private:
    int calculateNewIndexDirection(int turn, int indexDirection) const {
        if (turn == TURN_RIGHT) {
            return (indexDirection + 1) % DIRECTIONS.size();
        }
        else if (turn == TURN_LEFT) {
            return (indexDirection + DIRECTIONS.size() - 1) % DIRECTIONS.size();
        }
        return indexDirection;
    }

    int calculateDistanceFromStart(span <const int> currentCoordinates) const {
        return currentCoordinates[0] * currentCoordinates[0] + currentCoordinates[1] * currentCoordinates[1];
    }

    unordered_set<int> createQuickAccessToHashObstacles(span<const vector<int>> obstacles)const {
        unordered_set<int> quickAccessToHashObstacles;
        for (const auto& coordinates : obstacles) {
            quickAccessToHashObstacles.insert(calculateHashCoordinates(coordinates[0], coordinates[1]));
        }
        return quickAccessToHashObstacles;
    }

    int calculateHashCoordinates(int x, int y) const {
        return x + y * (2 * RANGE_OF_COORDINATES[1] + SUPPLEMENT_TO_PRIME_NUMBER);
    }
};
36286