diff options
-rw-r--r-- | walking_robot_simulation.c | 100 | ||||
-rw-r--r-- | walking_robot_simulation.py | 50 |
2 files changed, 150 insertions, 0 deletions
diff --git a/walking_robot_simulation.c b/walking_robot_simulation.c new file mode 100644 index 0000000..8b2304d --- /dev/null +++ b/walking_robot_simulation.c @@ -0,0 +1,100 @@ +// 874. Walking Robot Simulation +#include "leetcode.h" + +/* + * a robot on an infinite xy plane starts at point '(0, 0)' facing north. the + * robot can receive a sequence of these three possible types of 'commands': -2 + * turn left 90 degree, -1 turn right 90 degrees, '1 <= k <= 9' move forward 'k' + * units, one unit at a time. some of the grid squares are 'obstacles'. the i'th + * obstacle is at grid point 'obstacles[i] = (xi, yi)'. if the robot runs into + * an obstacle, then it will instead stay in its current location and move on to + * the next command. return the maximum euclidean distance that the robot ever + * gets from the origin squared. + */ + +enum directions { NORTH, EAST, SOUTH, WEST, INVALID }; + +inline int change_direction(int old, int turn) { + switch (old) { + case NORTH: + return turn == -2 ? WEST : EAST; + case EAST: + return turn == -2 ? NORTH : SOUTH; + case SOUTH: + return turn == -2 ? EAST : WEST; + case WEST: + return turn == -2 ? SOUTH : NORTH; + default: + break; + } + return INVALID; +} + +inline void move_forward(int *pos, int dir, int steps) { + switch (dir) { + case NORTH: + pos[1] += steps; + break; + case EAST: + pos[0] += steps; + break; + case SOUTH: + pos[1] -= steps; + break; + case WEST: + pos[0] -= steps; + break; + default: + break; + } +} + +int robotSim(int *commands, int commandsSize, int **obstacles, + int obstaclesSize, int *obstaclesColSize) { + int pos[2] = {0, 0}, dir = NORTH, max_dist = 0; + for (int i = 0; i < commandsSize; i++) { + if (commands[i] == -2 || commands[i] == -1) + dir = change_direction(dir, commands[i]); + else { + int steps = commands[i], curr_dist = 0; + for (int j = 0; j < obstaclesSize; j++) { + if (dir == NORTH || dir == SOUTH) { + int obst_dist = (int)abs(obstacles[j][1] - pos[1]); + if ((obstacles[j][0] == pos[0]) && + ((dir == NORTH && obstacles[j][1] > pos[1]) || + (dir == SOUTH && obstacles[j][1] < pos[1])) && + (obst_dist <= steps)) { + steps = obst_dist - 1; + break; + } + } else { + int obst_dist = (int)abs(obstacles[j][0] - pos[0]); + if ((obstacles[j][1] == pos[1]) && + ((dir == EAST && obstacles[j][0] > pos[0]) || + (dir == WEST && obstacles[j][0] < pos[0])) && + (obst_dist <= steps)) { + steps = obst_dist - 1; + break; + } + } + } + move_forward(pos, dir, steps); + curr_dist = (pos[0] * pos[0]) + (pos[1] * pos[1]); + if (curr_dist > max_dist) + max_dist = curr_dist; + } + } + return max_dist; +} + +int main() { + int c1[] = {4, -1, 3}, o1[1][0] = {{}}, ocs1[] = {1}; + int c2[] = {4, -1, 4, -2, 4}, o2[1][2] = {{2, 4}}, ocs2[] = {1}; + int c3[] = {6, -1, -1, 6}, o3[1][0] = {{}}, ocs3[] = {1}; + printf("%d\n", robotSim(c1, ARRAY_SIZE(c1), (int **)o1, ARRAY_SIZE(o1), + ocs1)); // expect: 25 + printf("%d\n", robotSim(c2, ARRAY_SIZE(c2), (int **)o2, ARRAY_SIZE(o2), + ocs2)); // expect: 65 + printf("%d\n", robotSim(c3, ARRAY_SIZE(c3), (int **)o3, ARRAY_SIZE(o3), + ocs3)); // expect: 36 +} diff --git a/walking_robot_simulation.py b/walking_robot_simulation.py new file mode 100644 index 0000000..6114aa5 --- /dev/null +++ b/walking_robot_simulation.py @@ -0,0 +1,50 @@ +# 874. Walking Robot Simulation + +""" +a robot on an infinite xy plane starts at point '(0, 0)' facing north. the +robot can receive a sequence of these three possible types of 'commands': -2 +turn left 90 degree, -1 turn right 90 degrees, '1 <= k <= 9' move forward 'k' +units, one unit at a time. some of the grid squares are 'obstacles'. the i'th +obstacle is at grid point 'obstacles[i] = (xi, yi)'. if the robot runs into +an obstacle, then it will instead stay in its current location and move on to +the next command. return the maximum euclidean distance that the robot ever +gets from the origin squared. +""" + + +class Solution(object): + def robotSim(self, commands, obstacles): + """ + :type commands: List[int] + :type obstacles: List[List[int]] + :rtype: int + """ + i, j, max_dist, dir = 0, 0, 0, 0 + move, obstacles = ( + [ + (0, 1), + (-1, 0), + (0, -1), + (1, 0), + ], + set(map(tuple, obstacles)), + ) + for c in commands: + if c == -2: + dir = (dir + 1) % 4 + elif c == -1: + dir = (dir - 1) % 4 + else: + x, y = move[dir] + while c and (i + x, j + y) not in obstacles: + i += x + j += y + max_dist = max(max_dist, i**2 + j**2) + return max_dist + + +if __name__ == "__main__": + obj = Solution() + print(obj.robotSim(commands=[4, -1, 3], obstacles=[])) + print(obj.robotSim(commands=[4, -1, 4, -2, 4], obstacles=[[2, 4]])) + print(obj.robotSim(commands=[6, -1, -1, 6], obstacles=[])) |