Get me out of here

Question

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

1. The point [0,0] is on the top-left corner of the grid.
2. Player's position will always be on the left side of the grid.
3. Target's position will always be on the right side of the grid.
4. The grid will always have at least one obstacle.
5. You can assume that no obstacle overlaps player or target position.
6. You don't necessarily need to find the min path.
7. The player can only move left, right, top and bottom not diagonally.
8. You can take the input in any convenient way.
9. You can assume that a path for the player to get to target will always exist.
10. Obviously, for each input multiple valid paths exist, choose one.
11. Assume N > 2 so the grid will be at least 3 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).

Answer 1

JavaScript (ES6), 135 bytes

Takes input as (width, [target_x, target_y], obstacles)(source_x, source_y), where obstacles is an array of strings in "X,Y" format.

Returns an array of strings in "X,Y" format.

(n,t,o)=>g=(x,y,p=[],P=[...p,v=x+','+y])=>v==t?P:~x&~y&&x<n&y<n&[...o,...p].indexOf(v)<0&&[0,-1,0,1].some((d,i)=>r=g(x+d,y-~-i%2,P))&&r

Try it online!

Commented

(n, t, o) =>              // n = width of maze, t[] = target coordinates, o[] = obstacles
  g = (                   // g() = recursive search function taking:
    x, y,                 //   (x, y) = current coordinates of the player
    p = [],               //   p[] = path (a list of visited coordinates, initially empty)
    P = [                 //   P[] = new path made of:
      ...p,               //     all previous entries in p
      v = x + ',' + y     //     the current coordinates coerced to a string v = "x,y"
    ]                     //
  ) =>                    //
    v == t ?              // if v is equal to the target coordinates:
      P                   //   stop recursion and return P
    :                     // else:
      ~x & ~y             //   if neither x nor y is equal to -1
      && x < n & y < n    //   and both x and y are less than n
      & [...o, ...p]      //   and neither the list of obstacles nor the path
        .indexOf(v) < 0   //   contains a position equal to the current one:
      && [0, -1, 0, 1]    //     iterate on all 4 possible directions
        .some((d, i) =>   //     for each of them:
          r = g(          //       do a recursive call with:
            x + d,        //         the updated x
            y - ~-i % 2,  //         the updated y
            P             //         the new path
          )               //       end of recursive call
        ) && r            //     if a solution was found, return it

Answer 2

R, 227 bytes

function(N,P,G,O){M=diag(N+2)*0
M[O+2]=1
b=c(1,N+2)
M[row(M)%in%b|col(M)%in%b]=1
H=function(V,L){if(all(V==G+2))stop(cat(L))
M[t(V)]=2
M<<-M
for(i in 0:3){C=V+(-1)^(i%/%2)*(0:1+i)%%2
if(!M[t(C)])H(C,c(L,C-2))}}
try(H(P+2,P),T)}

Try it online!

Not really short, and definitely not giving the shortest path (e.g. check the first example).
It basically performs a recursive depth-first search and stops as soon as the target has been reached, printing the path.

Thanks to JayCe for the improvement in output formatting

Answer 3

Python 2, 151 149 bytes

N,s,e,o=input()
P=[[s]]
for p in P:x,y=k=p[-1];k==e>exit(p);P+=[p+[[x+a,y+b]]for a,b in((0,1),(0,-1),(1,0),(-1,0))if([x+a,y+b]in o)==0<=x+a<N>y+b>-1]

Try it online!

Answer 4

Haskell, 133 131 130 bytes

• -1 byte thanks to BWO

(n!p)o=head.(>>=filter(elem p)).iterate(\q->[u:v|v@([x,y]:_)<-q,u<-[id,map(+1)]<*>[[x-1,y],[x,y-1]],all(/=u)o,x`div`n+y`div`n==0])

Try it online! (with a few testcases)

A function ! taking as input

• n :: Int size of the grid
• p :: [Int] player's position as a list [xp, yp]
• o :: [[Int]] obstacles position as a list [[x1, y1], [x2, y2], ...]
• t :: [[[Int]]] (implicit) target's position as a list [[[xt, yt]]] (triple list just for convenience)

and returning a valid path as a list [[xp, yp], [x1, y1], ..., [xt, yt]].

As a bonus, it finds (one of) the shortest path(s) and it works for any player's and target's position. On the other hand, it's very inefficient (but the examples provided run in a reasonable amount of time).

Explanation

(n ! p) o =                                                         -- function !, taking n, p, o and t (implicit by point-free style) as input
    head .                                                          -- take the first element of
    (>>= filter (elem p)) .                                         -- for each list, take only paths containing p and concatenate the results
    iterate (                                                       -- iterate the following function (on t) and collect the results in a list
        \q ->                                                       -- the function that takes a list of paths q...
            [u : v |                                                -- ... and returns the list of paths (u : v) such that:
                v@([x, y] : _) <- q,                                -- * v is an element of q (i.e. a path); also let [x, y] be the first cell of v
                u <- [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]],   -- * u is one of the neighbouring cells of [x, y]
                all (/= u) o,                                       -- * u is not an obstacle
                x `div` n + y `div` n == 0                          -- * [x, y] is inside the grid
            ]
    )

This function performs a recursive BFS via iterate, starting from the target and reaching the player's starting position. Paths of length \$k\$ are obtained by prepending appropriate cells to valid paths of length \$k-1\$, starting with the only valid path of length 1, that is the path [[xt, yt]].

The apparently obscure expression [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]] is just a "golfy" (-1 byte) version of [[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]].

Answer 5

APL (Dyalog Unicode), ⁷⁹ 75 bytes

{⍺←0j¯1⋄n p t o←⍵⋄p=t:p⋄p,(-∘p∇⊣@1∘⍵)⊃s/⍨{~∨/¯1n∊9 11○⍵}¨s←o~⍨p+⍺×0j1*3⌽⍳4}

Try it online!

^{-4 bytes by refactoring c thanks to @Adám.}

---

APL (Dyalog Unicode), 79 bytes

{⍺←0j¯1⋄n p t o←⍵⋄p=t:p⋄c←⊃s/⍨{~∨/¯1 n∊9 11○⍵}¨s←o~⍨p+⍺×0j1*3⌽⍳4⋄p,(c-p)∇c@1⊢⍵}

Try it online!

Takes a 4-element array N P T O as input, where N is an integer and the coordinates are represented as complex numbers.

Interprets a complex number x + yi (XjY in APL's notation) as the position (x, y), where (0, 0) is at the bottom left of the board and x and y directions are right and upwards respectively. Uses the right-hand-touching algorithm in this view, which works because both the start and the target are adjacent to the outer wall (and the minimal path is not required). The path may have multiple copies of the same coordinates when it encounters a dead end. To ensure that the player is touching the right-hand wall at start, the direction is initialized to the downwards direction -i.

Ungolfed with comments

f←{
  ⍺←0j¯1
  d←⍺                ⍝ direction, default down
  n p t o←⍵          ⍝ decompose the inputs
  p=t:p              ⍝ player = target: reached the goal
  turn←0j1*¯1 0 1 2  ⍝ turns to try out, right turn first
  steps←o~⍨p+d×turn  ⍝ possible steps from current position
  chosen←⊃steps/⍨{~∨/¯1 n∊9 11○⍵}¨steps  ⍝ the free spot with highest precedence
  d2←chosen-p        ⍝ keep track of the previous step
  p,d2∇n chosen t o  ⍝ move one step and recurse
}

Answer 6

Retina 0.8.2, 229 bytes

.
$&$&
@@
s@
##
.#
{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u
+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)
.(.)
$1

Try it online! Not sure whether the I/O format qualifies. Explanation:

.
$&$&

Duplicate each cell. The left copy is used as a temporary working area.

@@
s@

Mark the start of the maze as visited.

##
.#

Mark the end of the maze as being empty.

{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u

While available working cells exist, point them to adjacent previously visited cells.

+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)

Trace the path from the exit to the start using the working cells as a guide.

.(.)
$1

Delete the working cells.

Answer 7

JavaScript, 450 bytes

Takes input as (n, {playerx, playery}, {targetx, targety}, [{obstaclex, obstacley}]). Returns an array of {hopx, hopy}.

j=o=>JSON.stringify(o);l=a=>a.length;c=(a,o)=>{let i=l(a);while(i>0){i--;if(j(a[i])==j(o)){return 1;}}return 0;}h=(p,t,o)=>{if(p.y<t.y&&!c(o,{x:p.x,y:p.y+1})){return{x:p.x,y:p.y+1};}if(p.y>t.y&&!c(o,{x:p.x,y:p.y-1})){return{x:p.x,y:p.y-1};}if(p.x<t.x&&!c(o,{x:p.x+1,y:p.y})){return{x:p.x+1,y:p.y};}if(p.x>t.x&&!c(o,{x:p.x-1,y:p.y})){return{x:p.x-1,y:p.y};}return t;}w=(n,p,t,o)=>{let r=[];r.push(p);while(j(p)!==j(t)){p=h(p,t,o);r.push(p);}return r;}

Here is an unobfuscated version on my mess:

// defining some Array's function for proper comparaisons
json = (object) => { return JSON.stringify(object) };
length = (array) => { return array.length; }
contains = (array, object) => {
    let i = length(array);
    while (i > 0) {
    i--;
        if (json(array[i]) == json(object)) { return true; }
    }
    return false;
}
//return next found hop
getNextHop = (player, target, obstacles) => {
    //uggly serie of conditions
    //check where do we have to go and if there is an obstacle there
    if(player.y<target.y && !contains(obstacles, [x:player.x, y:player.y+1])) { return [x:player.x, y:player.y+1]; }
    if(player.y>target.y && !contains(obstacles, [x:player.x, y:player.y-1])) { return [x:player.x, y:player.y-1]; }
    if(player.x<target.x && !contains(obstacles, [x:player.x+1, y:player.y])) { return [x:player.x+1, y:player.y]; }
    if(player.x>target.x && !contains(obstacles, [x:player.x-1, y:player.y])) { return [x:player.x-1, y:player.y]; }
    return target;
}
//return found path
getPath = (gridsize, player, target, obstacles) => {
    let path = [];
    path.push(player);
    //while player is not on target
    while(json(player)!=json(target)) {
        player = getNextHop(player, target, obstacles); //gridsize is never used as player and target are in the grid boundaries
        path.push(player);
    }
    return path;
}