12
1
Challenge
Given a grid size, obstacles' positions, player position and target position your task is to find a path for the player to get to the target and avoid the obstacles at the same time (if necessary).
Input
- N: Grid size
N x N
- P: Player's position
[playerposx, playerposy]
- T: Target's position
[targetposx, targetposy]
- O: Obstacles' positions
[[x1, y1], [x2, y2],...,[xn, yn]]
Output
Path: A path player can use to reach target [[x1, y1], [x2, y2],...,[xn, yn]]
Rules
- The point
[0,0]
is on the top-left corner of the grid. - Player's position will always be on the left side of the grid.
- Target's position will always be on the right side of the grid.
- The grid will always have at least one obstacle.
- You can assume that no obstacle overlaps player or target position.
- You don't necessarily need to find the min path.
- The player can only move left, right, top and bottom not diagonally.
- You can take the input in any convenient way.
- You can assume that a path for the player to get to target will always exist.
- Obviously, for each input multiple valid paths exist, choose one.
- Assume
N > 2
so the grid will be at least3 x 3
.
Examples
Input: 9
, [6, 0]
, [3, 8]
, [[0, 5], [2, 2], [6, 4], [8, 2], [8, 7]]
Possible Output: [[6, 0], [6, 1], [6, 2], [6, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [4, 8], [3, 8]]
Input: 6
, [1, 0]
, [3, 5]
, [[1, 2], [2, 5], [5, 1]]
Possible Output: [[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 5]]
Note
Notice that X
is for rows and Y
for cols. Don't confuse them with the coordinates in an image.
Edit
As @digEmAll pointed out, due to rules #2
and #3
, playerY = 0
and targetY = N-1
. So, if you want you can take as input only playerX
and and targetX
(if that makes your code shorter).
1"Player position will always be on left side and target on right side" : does this mean that player-y = 0 and target-y = N-1 ? If so, can we just accept the x-coordinate (one number) for player and target ? – digEmAll – 2018-09-01T09:23:06.780
1@digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this. – DimChtz – 2018-09-01T09:26:56.267
Related but easier. Related but harder. – user202729 – 2018-09-01T10:33:04.187
Does the path have to be from start to finish, or can it be in reverse order? – kamoroso94 – 2018-09-01T17:15:49.030
1@kamoroso94 Yes, start to target (finish) :) – DimChtz – 2018-09-01T17:24:16.547