12
\$\begingroup\$

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).

enter image description here


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).

\$\endgroup\$
  • 1
    \$\begingroup\$ "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 ? \$\endgroup\$ – digEmAll Sep 1 '18 at 9:23
  • 1
    \$\begingroup\$ @digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this. \$\endgroup\$ – DimChtz Sep 1 '18 at 9:26
  • \$\begingroup\$ Related but easier. Related but harder. \$\endgroup\$ – user202729 Sep 1 '18 at 10:33
  • \$\begingroup\$ Does the path have to be from start to finish, or can it be in reverse order? \$\endgroup\$ – kamoroso94 Sep 1 '18 at 17:15
  • 1
    \$\begingroup\$ @kamoroso94 Yes, start to target (finish) :) \$\endgroup\$ – DimChtz Sep 1 '18 at 17:24
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ +1 I like the way you print the output (not the typical boring list of lists) :) \$\endgroup\$ – DimChtz Sep 1 '18 at 14:10
  • \$\begingroup\$ @DimChtz: well thanks but... that's the helper function, the code-golf function just prints a list of coordinates x1 y1 x2 y2 ... xn yn :D \$\endgroup\$ – digEmAll Sep 1 '18 at 14:13
  • 1
    \$\begingroup\$ Yes, I know :P but still nice. \$\endgroup\$ – DimChtz Sep 1 '18 at 14:29
  • 1
    \$\begingroup\$ agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :) \$\endgroup\$ – JayCe Sep 2 '18 at 0:26
  • \$\begingroup\$ @JayCe: good idea, changed ! \$\endgroup\$ – digEmAll Sep 2 '18 at 8:43
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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]].

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! Nice first answer! \$\endgroup\$ – Arnauld Sep 5 '18 at 10:54
  • 1
    \$\begingroup\$ @Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^ \$\endgroup\$ – Delfad0r Sep 5 '18 at 10:58
  • 1
    \$\begingroup\$ Nice golf! You can save one byte by using an operator instead of a function: Try it online! \$\endgroup\$ – BMO Sep 5 '18 at 11:25
  • \$\begingroup\$ @BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of \$\endgroup\$ – Delfad0r Sep 5 '18 at 11:42
  • 1
    \$\begingroup\$ Btw. there is a section with tips for Haskell in particular where you can find this and many more tricks. Oh and there's always chat too: Of Monads and Men \$\endgroup\$ – BMO Sep 5 '18 at 11:46
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.