Can Jimmy escape the ghosts?

Question

It is Halloween and Jimmy (/o\) has gone into a mysterious neighborhood for trick-or-treating (ask himself why). Now some evil ghosts are chasing him. Can Jimmy escape the ghosts?

Challenge:

Input:

A board showing position of Jimmy, ghosts, solid objects and empty spaces.

An example 10x5 board, o is Jimmy (we needed a single character Jimmy), gs are ghosts, #s are solid objects and .s are empty spaces:

##########
......g...
#.o.......
#.....g...
##########

Output:

A truthy value if Jimmy can escape at least in one scenario, otherwise a falsy value.

How things work:

Ghosts and Jimmy can move one space each turn. There are 4 possible movements: left, right, up, down (no diagonal movements, no skipping).

On each turn, first ghosts move one space towards Jimmy. Ghosts always select the closest path to Jimmy, if two possible moves towards Jimmy have the same cost, the move going to left or right is chosen. Ghosts can go through solid objects, meaning at the end of a turn a ghost can be on same space as a solid object. Multiple ghosts can stay on same space too. This basically means all the ghosts on the same space will move exactly like each other after that point (they are all like a single ghost now).

After all ghosts have moved, if any of the ghosts ends up on the same space as Jimmy, Jimmy is caught and you have to try another scenario.

If Jimmy is not caught, he moves next. You have to decide on Jimmy's moves. Jimmy cannot go through solid objects. If Jimmy moves to a space with a ghost, he is caught. Jimmy cannot move into a space he has already visited. If Jimmy has no valid moves, consider him caught.

After Jimmy has moved, if he ends up on an empty border space (i.e. a space on the edge of the grid without a ghost on it), he has escaped.

If you can find at least one scenario where Jimmy can escape, output a truthy value. Also if the input position before doing any moves is already an escape position, it is valid and you should return truthy. If Jimmy is caught or out of valid moves in all possible scenarios, then return a falsy value.

Challenge rules:

• You can use any consistent characters that you like for Jimmy, ghosts, solid objects and empty spaces in the input. You cannot use same character for different types of items though.
• The input board is always a rectangle or square with a minimum size of 2x2 and a maximum size of 10x10.
• Input is flexible as long as you don't include anything more than initial board information (for example, you cannot include if the initial board is already an escape position or not). It can be a multi-line string, a list of strings, a 2d array or matrix of characters or numbers, etc. It can also be position of items, for example a (x, y) for Jimmy and two lists of (x, y)s for ghosts and solid objects. You can also pass board size as a separate input if you like. Basically any format and combinations of inputs that don't include more than the initial board information are allowed.
• Input is guaranteed to always have a single Jimmy.
• Input always has at least one ghost.
• Input always has at least one solid object.
• Input can never start in a position where more than one item is on same space.
• Input can start in a position which already is an escaped position for Jimmy (any input with Jimmy on a border space), you should return truthy for cases like this.

General rules:

• This is code-golf, so shortest answer in bytes for every language wins. Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (i.e. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test cases:

Truthy:

Jimmy can move left, up, left to escape:

##########
......g...
#.o.......
#.....g...
##########

Jimmy is already on a border space, this is an escape:

#.
og

If Jimmy moves only left or only right, he escapes:

#########
.........
....g....
...g.g...
....o....
...g.g...
....g....
.........

Jimmy has only two ways, one of them is an escape:

##########
#g.o.....#
########.#
#........#
#.########
#........#
########.#
#........#
#.########

Falsy:

Jimmy is caught by first move of any of the ghosts:

.....
..g..
.go..
.....
.....

Jimmy has no valid moves:

###.......
#o#......g
###.......

Jimmy will run out of valid moves before ghost can catch him:

#####.....
#o..#....g
#####.....

Remember, ghosts can go through solid objects:

g#.#
.#.#
.#.#
.#o#
.#.#
.#.#
g#.#

Oh poor Jimmy! It is a dead end...

##########
#...o....g
##########

Jimmy!!? How did you get there in the first place?

#.########
#g.......#
#....g...#
#......g.#
#..g.....#
#....g...#
#........#
#....g...#
#..g....o#
##########

Answer 1

Python 2, 236 235 227 212 bytes

def f((x,y),G,M,U=[]):
 R=1-(len(M[0])-1>x>0<y<len(M)-1);H=[(u+cmp(x,u),v+cmp(y,v)*(u==x))for u,v in G];d,e=0,1
 for _ in' '*4*(R<1>((x,y)in H)):J=z,w=x+d,y+e;d,e=-e,d;R|=M[w][z]>(J in U)<f(J,H,M,U+[J])
 return R

Try it online!

-15 bytes thx to Bubbler

As input, takes a tuple (x,y) as jimmy's initial position, a list G == [(g1x,g1y), ...] of initial ghost positions, and a list of lists M which is the 2-dimensional binary matrix where cells are 0 if they contain "an object" (i.e., #) and 1 otherwise.

Returns 1 for truthy, 0 for falsey.

Loosely speaking, the idea here is that we're going to depth-first recurse over down, left, up, right to seek a border cell. To start,

R=1-(len(M[0])-1>x>0<y<len(M)-1)

R is truthy if jimmy starts on a border cell. We could just return R if he does, but that would add an additional return. So in any case, we calculate where the ghosts would move to next.

H=[(u+cmp(x,u),v+cmp(y,v)*(u==x))for u,v in G]

cmp(a,b) returns the sign of a-b as -1,0,1; so this updates the ghosts positions with preference for horizontal movement if possible. Next,

for _ in' '*4*(R<1>((x,y)in H)):

executes a loop 4 times (' '*4 is shorter than range(4)). Note that if jimmy is on the boundary (not R<1) or a ghost has landed on jimmy (not 1>((x,y)in H), then we skip the for loop and so we return 1 if jimmy has escaped, or 0 if a ghost got him.

    J=z,w=x+d,y+e;d,e=-e,d

d,e is the offset to jimmy's next position, starting as 0,1; and each time through the loop, d,e=-e,d rotates us through the 4 possible orthogonal positions.

    R|=M[w][z]>(J in U)<f(J,H,M,U+[J])

R gets set to truthy if jimmy's next position J is not an on "object" (M[w][z]>0), AND we haven't visited this position before (1>(J in U)), AND via recursion, jimmy can escape starting at position J with ghosts at H (0<f(J,H,M,U+[J])).

Answer 2

Python 2, 199 bytes

def g(I,G,W,w,h):
 u,v=I.real,I.imag;R=1-(w-1>u>0<v<h-1);H=[z+cmp(u,z.real)+cmp(v,z.imag)*(u==z.real)*1jfor z in G]
 for d in(R<1>(I in H+W))*range(4):J=I+1j**d;R|=(J in W)<g(J,H,W+[I],w,h)
 return R

Try it online!

Rewrite of Chas Brown's solution using complex numbers.

All the coordinates are represented as a complex number x+y*1j. I is Jimmy's position, G is the list of ghosts and W is the list of walls. w and h are the width and height of the board, respectively.

The output values and the algorithm are the same as the linked solution.

Answer 3

Javascript (ES6), 208 bytes

Recursive, depth-first search. A breadth-first approach would be probably faster, but less golfy. Input: a multi line string, using 1 for ghosts, 4 for solid objects, 6 for Jimmy and 2 for empty space.

f=(s,l=-~s.search`
`,j=s.search(6),g=[...s],x=j%l)=>j<l|!g[j+l]|!x|x>l-3||(g[j]=6,![...g].some((a,i)=>a&1&&(g[--g[i],t=i%l,i+=t<x?1:t>x?-1:i<j?l:i>j?-l:0]|=1,i==j))&&[l,-l,1,-1].some(d=>2==g[d+=j]&&f(g,l,d)))

Less golfed

// using parameters with default values instead of declared variables

f = (s,  // input board (as a string at first call, then as an array)
     l = -~g.search('\n'), // line size +1, that is distance to next line
     // at first call it is calculated, for recursive calls is passed
     j = g.search(6), // position of jimmy in grid
     // at first call it is calculated, for recursive calls is passed
     grid = [...s], // modifiable copy of board (converted to char array)
     x = j % l, // x position of jimmy, always obtained from j
) =>
{
  // first, check if Jimmy is out
  if (j<l | !grid[j+l] | !x | x>l-3) // top,bottom,left,right border
  {
    return true
  }
  // move all ghosts and check if some ghost can take Jimmy
  // the loop is on a copy of grid, so I can safely modify grid during the loop
  var taken = [...grid].some( // check all ghosts
        (a,i) => a & 1 && ( // is it a ghost?
         --grid[i], // remove ghost from grid, as it will move
         t = i % l, // x position of ghost
         // move ghost towards Jimmy
         i += t < x 
           ? 1 
           : t > x 
             ? -1 
             : i < j 
               ? l 
               : i > j 
                 ? -l 
                 : 0,
         grid[i] |= 1, // put ghost on grid in its new position
         i == j // return true if it reached Jimmy
  )
  return !taken && // if taken return false immediately
  // else recurse
  [l,-l,1,-1].some( // try to move Jimmy in all directions
    d => (
      d+=j, 2==g[d] && f(grid, l, d))
    )
  )
}

Test

cases=['##########\n......g...\n#.o.......\n#.....g...\n##########\n'
,'#.\nog\n'
,'#########\n.........\n....g....\n...g.g...\n....o....\n...g.g...\n....g....\n.........\n'
,'##########\n#g.o.....#\n########.#\n#........#\n#.########\n#........#\n########.#\n#........#\n#.########\n'
,'.....\n..g..\n.go..\n.....\n.....'
,'###.......\n\#o#......g\n###.......\n'
,'#####.....\n#o..#....g\n#####.....\n'
,'g#.#\n.#.#\n\.#.#\n.#o#\n.#.#\n.#.#\ng#.#\n'
,'##########\n#...o....g\n##########\n'
,'#.########\n#g.......#\n#....g...#\n#......g.#\n#..g.....#\n#....g...#\n#........#\n#....g...#\n#..g....o#\n##########\n'
]


f=(s,l=-~s.search`
`,j=s.search(6),g=[...s],x=j%l)=>j<l|!g[j+l]|!x|x>l-3||(g[j]=6,![...g].some((a,i)=>a&1&&(g[--g[i],t=i%l,i+=t<x?1:t>x?-1:i<j?l:i>j?-l:0]|=1,i==j))&&[l,-l,1,-1].some(d=>2==g[d+=j]&&f(g,l,d)))


cases.forEach(x=> (
  console.log(x,
    f(x.replace(/#/g,4).replace(/\./g,2).replace(/o/,6).replace(/g/g,2|1)))
))

Answer 4

Jelly, 94 89 bytes

Ø.,U$;N$+®ŒṬ€×8+®ŒṬ¤+&7$Ç€Ẹ
&Ɱ8,2ŒṪ€Ḣ©_¥/Ṡ01¦Ạ¡€+ƲṪŒṬḤ+&13$ÑÇFṀ>8Ʋ?
|Ø.¦4Z$⁺FṀ=12ƲÇFṀ>8Ʋ?

Try it online!

A full program that takes an integer matrix as its argument, with 0 as space, 1 as wall, 2 as ghost and 8 as Jimmy. Returns 1 for escape and 0 for no escape.