Get me out of here

Clash Royale CLAN TAG#URR8PPP

up vote
12
down vote

favorite

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

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

code-golf grid path-finding

share|improve this question

edited Sep 3 at 9:06

asked Sep 1 at 7:41

DimChtz

601111

• 
  
  
  

  
  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
  Sep 1 at 9:23
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this.
  – DimChtz
  Sep 1 at 9:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related but easier. Related but harder.
  – user202729
  Sep 1 at 10:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the path have to be from start to finish, or can it be in reverse order?
  – kamoroso94
  Sep 1 at 17:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @kamoroso94 Yes, start to target (finish) :)
  – DimChtz
  Sep 1 at 17:24
  

  
  
  
  

add a comment | 

up vote
12
down vote

favorite

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

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

code-golf grid path-finding

share|improve this question

edited Sep 3 at 9:06

asked Sep 1 at 7:41

DimChtz

601111

• 
  
  
  

  
  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
  Sep 1 at 9:23
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this.
  – DimChtz
  Sep 1 at 9:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related but easier. Related but harder.
  – user202729
  Sep 1 at 10:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the path have to be from start to finish, or can it be in reverse order?
  – kamoroso94
  Sep 1 at 17:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @kamoroso94 Yes, start to target (finish) :)
  – DimChtz
  Sep 1 at 17:24
  

  
  
  
  

add a comment | 

up vote
12
down vote

favorite

1

up vote
12
down vote

favorite

1

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

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

code-golf grid path-finding

share|improve this question

edited Sep 3 at 9:06

asked Sep 1 at 7:41

DimChtz

601111

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

code-golf grid path-finding

share|improve this question

edited Sep 3 at 9:06

asked Sep 1 at 7:41

DimChtz

601111

share|improve this question

share|improve this question

edited Sep 3 at 9:06

edited Sep 3 at 9:06

edited Sep 3 at 9:06

asked Sep 1 at 7:41

DimChtz

601111

asked Sep 1 at 7:41

DimChtz

601111

asked Sep 1 at 7:41

DimChtz

601111

601111

• 
  
  
  

  
  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
  Sep 1 at 9:23
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this.
  – DimChtz
  Sep 1 at 9:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related but easier. Related but harder.
  – user202729
  Sep 1 at 10:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the path have to be from start to finish, or can it be in reverse order?
  – kamoroso94
  Sep 1 at 17:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @kamoroso94 Yes, start to target (finish) :)
  – DimChtz
  Sep 1 at 17:24
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  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
  Sep 1 at 9:23
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this.
  – DimChtz
  Sep 1 at 9:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related but easier. Related but harder.
  – user202729
  Sep 1 at 10:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does the path have to be from start to finish, or can it be in reverse order?
  – kamoroso94
  Sep 1 at 17:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @kamoroso94 Yes, start to target (finish) :)
  – DimChtz
  Sep 1 at 17:24
  

  
  
  
  

1

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
Sep 1 at 9:23

"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
Sep 1 at 9:23

1

1

@digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this.
– DimChtz
Sep 1 at 9:26

@digEmAll Good point. Honestly, I didn't think of this and yes you can I will edit this.
– DimChtz
Sep 1 at 9:26

Related but easier. Related but harder.
– user202729
Sep 1 at 10:33

Related but easier. Related but harder.
– user202729
Sep 1 at 10:33

Does the path have to be from start to finish, or can it be in reverse order?
– kamoroso94
Sep 1 at 17:15

Does the path have to be from start to finish, or can it be in reverse order?
– kamoroso94
Sep 1 at 17:15

1

1

@kamoroso94 Yes, start to target (finish) :)
– DimChtz
Sep 1 at 17:24

@kamoroso94 Yes, start to target (finish) :)
– DimChtz
Sep 1 at 17:24

add a comment | 

6 Answers
6

active

oldest

votes

up vote
5
down vote

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

share|improve this answer

edited Sep 1 at 15:04

answered Sep 1 at 10:06

Arnauld

63.6k580268

add a comment | 

up vote
5
down vote

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

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

share|improve this answer

edited Sep 2 at 8:42

answered Sep 1 at 14:08

digEmAll

1,73147

• 
  
  
  

  
  

  
  
  
  
  
  

  
  +1 I like the way you print the output (not the typical boring list of lists) :)
  – DimChtz
  Sep 1 at 14:10
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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
  – digEmAll
  Sep 1 at 14:13
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Yes, I know :P but still nice.
  – DimChtz
  Sep 1 at 14:29
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :)
  – JayCe
  Sep 2 at 0:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JayCe: good idea, changed !
  – digEmAll
  Sep 2 at 8:43
  

  
  
  
  

add a comment | 

up vote
4
down vote

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!

share|improve this answer

edited Sep 1 at 17:33

answered Sep 1 at 9:04

ovs

17.3k21056

add a comment | 

up vote
2
down vote

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

share|improve this answer

edited Sep 5 at 11:46

answered Sep 4 at 15:11

Delfad0r

914

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Welcome to PPCG! Nice first answer!
  – Arnauld
  Sep 5 at 10:54
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^
  – Delfad0r
  Sep 5 at 10:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nice golf! You can save one byte by using an operator instead of a function: Try it online!
  – BWO
  Sep 5 at 11:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of
  – Delfad0r
  Sep 5 at 11:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  – BWO
  Sep 5 at 11:46
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

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.

share|improve this answer

answered Sep 1 at 23:40

Neil

75.1k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Rule #8: You can take the input in any convenient way. Yes, it qualifies :)
  – DimChtz
  Sep 1 at 23:42
  

  
  
  
  

add a comment | 

up vote
1
down vote

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))returnx:p.x,y:p.y+1;if(p.y>t.y&&!c(o,x:p.x,y:p.y-1))returnx:p.x,y:p.y-1;if(p.x<t.x&&!c(o,x:p.x+1,y:p.y))returnx:p.x+1,y:p.y;if(p.x>t.x&&!c(o,x:p.x-1,y:p.y))returnx: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;

share|improve this answer

answered Sep 2 at 11:53

MinerBigWhale

111

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f171550%2fget-me-out-of-here%23new-answer', 'question_page');

);

Post as a guest

Name Email

6 Answers
6

active

oldest

votes

6 Answers
6

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
5
down vote

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

share|improve this answer

edited Sep 1 at 15:04

answered Sep 1 at 10:06

Arnauld

63.6k580268

add a comment | 

up vote
5
down vote

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

share|improve this answer

edited Sep 1 at 15:04

answered Sep 1 at 10:06

Arnauld

63.6k580268

add a comment | 

up vote
5
down vote

up vote
5
down vote

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

share|improve this answer

edited Sep 1 at 15:04

answered Sep 1 at 10:06

Arnauld

63.6k580268

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

share|improve this answer

edited Sep 1 at 15:04

answered Sep 1 at 10:06

Arnauld

63.6k580268

share|improve this answer

share|improve this answer

edited Sep 1 at 15:04

edited Sep 1 at 15:04

edited Sep 1 at 15:04

answered Sep 1 at 10:06

Arnauld

63.6k580268

answered Sep 1 at 10:06

Arnauld

63.6k580268

answered Sep 1 at 10:06

Arnauld

63.6k580268

63.6k580268

add a comment | 

add a comment | 

up vote
5
down vote

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

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

share|improve this answer

edited Sep 2 at 8:42

answered Sep 1 at 14:08

digEmAll

1,73147

• 
  
  
  

  
  

  
  
  
  
  
  

  
  +1 I like the way you print the output (not the typical boring list of lists) :)
  – DimChtz
  Sep 1 at 14:10
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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
  – digEmAll
  Sep 1 at 14:13
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Yes, I know :P but still nice.
  – DimChtz
  Sep 1 at 14:29
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :)
  – JayCe
  Sep 2 at 0:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JayCe: good idea, changed !
  – digEmAll
  Sep 2 at 8:43
  

  
  
  
  

add a comment | 

up vote
5
down vote

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

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

share|improve this answer

edited Sep 2 at 8:42

answered Sep 1 at 14:08

digEmAll

1,73147

• 
  
  
  

  
  

  
  
  
  
  
  

  
  +1 I like the way you print the output (not the typical boring list of lists) :)
  – DimChtz
  Sep 1 at 14:10
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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
  – digEmAll
  Sep 1 at 14:13
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Yes, I know :P but still nice.
  – DimChtz
  Sep 1 at 14:29
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :)
  – JayCe
  Sep 2 at 0:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JayCe: good idea, changed !
  – digEmAll
  Sep 2 at 8:43
  

  
  
  
  

add a comment | 

up vote
5
down vote

up vote
5
down vote

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

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

share|improve this answer

edited Sep 2 at 8:42

answered Sep 1 at 14:08

digEmAll

1,73147

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

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

share|improve this answer

edited Sep 2 at 8:42

answered Sep 1 at 14:08

digEmAll

1,73147

share|improve this answer

share|improve this answer

edited Sep 2 at 8:42

edited Sep 2 at 8:42

edited Sep 2 at 8:42

answered Sep 1 at 14:08

digEmAll

1,73147

answered Sep 1 at 14:08

digEmAll

1,73147

answered Sep 1 at 14:08

digEmAll

1,73147

1,73147

• 
  
  
  

  
  

  
  
  
  
  
  

  
  +1 I like the way you print the output (not the typical boring list of lists) :)
  – DimChtz
  Sep 1 at 14:10
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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
  – digEmAll
  Sep 1 at 14:13
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Yes, I know :P but still nice.
  – DimChtz
  Sep 1 at 14:29
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :)
  – JayCe
  Sep 2 at 0:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JayCe: good idea, changed !
  – digEmAll
  Sep 2 at 8:43
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  +1 I like the way you print the output (not the typical boring list of lists) :)
  – DimChtz
  Sep 1 at 14:10
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @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
  – digEmAll
  Sep 1 at 14:13
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Yes, I know :P but still nice.
  – DimChtz
  Sep 1 at 14:29
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :)
  – JayCe
  Sep 2 at 0:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JayCe: good idea, changed !
  – digEmAll
  Sep 2 at 8:43
  

  
  
  
  

+1 I like the way you print the output (not the typical boring list of lists) :)
– DimChtz
Sep 1 at 14:10

+1 I like the way you print the output (not the typical boring list of lists) :)
– DimChtz
Sep 1 at 14:10

@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
– digEmAll
Sep 1 at 14:13

@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
– digEmAll
Sep 1 at 14:13

1

1

Yes, I know :P but still nice.
– DimChtz
Sep 1 at 14:29

Yes, I know :P but still nice.
– DimChtz
Sep 1 at 14:29

1

1

agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :)
– JayCe
Sep 2 at 0:26

agree with @DimChtz... and I think it looks even better if you write(t(mx),1,N) instead of printing :)
– JayCe
Sep 2 at 0:26

@JayCe: good idea, changed !
– digEmAll
Sep 2 at 8:43

@JayCe: good idea, changed !
– digEmAll
Sep 2 at 8:43

add a comment | 

up vote
4
down vote

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!

share|improve this answer

edited Sep 1 at 17:33

answered Sep 1 at 9:04

ovs

17.3k21056

add a comment | 

up vote
4
down vote

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!

share|improve this answer

edited Sep 1 at 17:33

answered Sep 1 at 9:04

ovs

17.3k21056

add a comment | 

up vote
4
down vote

up vote
4
down vote

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!

share|improve this answer

edited Sep 1 at 17:33

answered Sep 1 at 9:04

ovs

17.3k21056

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!

share|improve this answer

edited Sep 1 at 17:33

answered Sep 1 at 9:04

ovs

17.3k21056

share|improve this answer

share|improve this answer

edited Sep 1 at 17:33

edited Sep 1 at 17:33

edited Sep 1 at 17:33

answered Sep 1 at 9:04

ovs

17.3k21056

answered Sep 1 at 9:04

ovs

17.3k21056

answered Sep 1 at 9:04

ovs

17.3k21056

17.3k21056

add a comment | 

add a comment | 

up vote
2
down vote

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

share|improve this answer

edited Sep 5 at 11:46

answered Sep 4 at 15:11

Delfad0r

914

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Welcome to PPCG! Nice first answer!
  – Arnauld
  Sep 5 at 10:54
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^
  – Delfad0r
  Sep 5 at 10:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nice golf! You can save one byte by using an operator instead of a function: Try it online!
  – BWO
  Sep 5 at 11:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of
  – Delfad0r
  Sep 5 at 11:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  – BWO
  Sep 5 at 11:46
  
  

  
  
  
  

add a comment | 

up vote
2
down vote

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

share|improve this answer

edited Sep 5 at 11:46

answered Sep 4 at 15:11

Delfad0r

914

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Welcome to PPCG! Nice first answer!
  – Arnauld
  Sep 5 at 10:54
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^
  – Delfad0r
  Sep 5 at 10:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nice golf! You can save one byte by using an operator instead of a function: Try it online!
  – BWO
  Sep 5 at 11:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of
  – Delfad0r
  Sep 5 at 11:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  – BWO
  Sep 5 at 11:46
  
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

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

share|improve this answer

edited Sep 5 at 11:46

answered Sep 4 at 15:11

Delfad0r

914

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

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

share|improve this answer

edited Sep 5 at 11:46

answered Sep 4 at 15:11

Delfad0r

914

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this answer

share|improve this answer

edited Sep 5 at 11:46

edited Sep 5 at 11:46

edited Sep 5 at 11:46

answered Sep 4 at 15:11

Delfad0r

914

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered Sep 4 at 15:11

Delfad0r

914

answered Sep 4 at 15:11

Delfad0r

914

914

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

New contributor

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

Delfad0r is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Welcome to PPCG! Nice first answer!
  – Arnauld
  Sep 5 at 10:54
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^
  – Delfad0r
  Sep 5 at 10:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nice golf! You can save one byte by using an operator instead of a function: Try it online!
  – BWO
  Sep 5 at 11:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of
  – Delfad0r
  Sep 5 at 11:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  – BWO
  Sep 5 at 11:46
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Welcome to PPCG! Nice first answer!
  – Arnauld
  Sep 5 at 10:54
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^
  – Delfad0r
  Sep 5 at 10:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Nice golf! You can save one byte by using an operator instead of a function: Try it online!
  – BWO
  Sep 5 at 11:25
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of
  – Delfad0r
  Sep 5 at 11:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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
  – BWO
  Sep 5 at 11:46
  
  

  
  
  
  

2

2

Welcome to PPCG! Nice first answer!
– Arnauld
Sep 5 at 10:54

Welcome to PPCG! Nice first answer!
– Arnauld
Sep 5 at 10:54

1

1

@Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^
– Delfad0r
Sep 5 at 10:58

@Arnauld Thanks! I actually spent several hours trying to squeeze a few bytes out of my solution just to beat your 135 ^^
– Delfad0r
Sep 5 at 10:58

1

1

Nice golf! You can save one byte by using an operator instead of a function: Try it online!
– BWO
Sep 5 at 11:25

Nice golf! You can save one byte by using an operator instead of a function: Try it online!
– BWO
Sep 5 at 11:25

@BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of
– Delfad0r
Sep 5 at 11:42

@BWO Thanks for the tip. I'm new here, so there are many tricks I've never heard of
– Delfad0r
Sep 5 at 11:42

1

1

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
– BWO
Sep 5 at 11:46

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
– BWO
Sep 5 at 11:46

add a comment | 

up vote
1
down vote

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.

share|improve this answer

answered Sep 1 at 23:40

Neil

75.1k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Rule #8: You can take the input in any convenient way. Yes, it qualifies :)
  – DimChtz
  Sep 1 at 23:42
  

  
  
  
  

add a comment | 

up vote
1
down vote

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.

share|improve this answer

answered Sep 1 at 23:40

Neil

75.1k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Rule #8: You can take the input in any convenient way. Yes, it qualifies :)
  – DimChtz
  Sep 1 at 23:42
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

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.

share|improve this answer

answered Sep 1 at 23:40

Neil

75.1k744170

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.

share|improve this answer

answered Sep 1 at 23:40

Neil

75.1k744170

share|improve this answer

share|improve this answer

answered Sep 1 at 23:40

Neil

75.1k744170

answered Sep 1 at 23:40

Neil

75.1k744170

answered Sep 1 at 23:40

Neil

75.1k744170

75.1k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Rule #8: You can take the input in any convenient way. Yes, it qualifies :)
  – DimChtz
  Sep 1 at 23:42
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Rule #8: You can take the input in any convenient way. Yes, it qualifies :)
  – DimChtz
  Sep 1 at 23:42
  

  
  
  
  

Rule #8: You can take the input in any convenient way. Yes, it qualifies :)
– DimChtz
Sep 1 at 23:42

Rule #8: You can take the input in any convenient way. Yes, it qualifies :)
– DimChtz
Sep 1 at 23:42

add a comment | 

up vote
1
down vote

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))returnx:p.x,y:p.y+1;if(p.y>t.y&&!c(o,x:p.x,y:p.y-1))returnx:p.x,y:p.y-1;if(p.x<t.x&&!c(o,x:p.x+1,y:p.y))returnx:p.x+1,y:p.y;if(p.x>t.x&&!c(o,x:p.x-1,y:p.y))returnx: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;

share|improve this answer

answered Sep 2 at 11:53

MinerBigWhale

111

add a comment | 

up vote
1
down vote

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))returnx:p.x,y:p.y+1;if(p.y>t.y&&!c(o,x:p.x,y:p.y-1))returnx:p.x,y:p.y-1;if(p.x<t.x&&!c(o,x:p.x+1,y:p.y))returnx:p.x+1,y:p.y;if(p.x>t.x&&!c(o,x:p.x-1,y:p.y))returnx: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;

share|improve this answer

answered Sep 2 at 11:53

MinerBigWhale

111

add a comment | 

up vote
1
down vote

up vote
1
down vote

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))returnx:p.x,y:p.y+1;if(p.y>t.y&&!c(o,x:p.x,y:p.y-1))returnx:p.x,y:p.y-1;if(p.x<t.x&&!c(o,x:p.x+1,y:p.y))returnx:p.x+1,y:p.y;if(p.x>t.x&&!c(o,x:p.x-1,y:p.y))returnx: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;

share|improve this answer

answered Sep 2 at 11:53

MinerBigWhale

111

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))returnx:p.x,y:p.y+1;if(p.y>t.y&&!c(o,x:p.x,y:p.y-1))returnx:p.x,y:p.y-1;if(p.x<t.x&&!c(o,x:p.x+1,y:p.y))returnx:p.x+1,y:p.y;if(p.x>t.x&&!c(o,x:p.x-1,y:p.y))returnx: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;

share|improve this answer

answered Sep 2 at 11:53

MinerBigWhale

111

share|improve this answer

share|improve this answer

answered Sep 2 at 11:53

MinerBigWhale

111

answered Sep 2 at 11:53

MinerBigWhale

111

answered Sep 2 at 11:53

MinerBigWhale

111

111

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f171550%2fget-me-out-of-here%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email