#Can Jimmy escape the ghosts?

Posted: Can Jimmy escape the ghosts?

Can Jimmy escape the ghosts?

Posted: Can Jimmy escape the ghosts?

code-golf grid decision-problem path-finding

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 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 caught 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# ########## 

Sandbox Questions

• Is the challenge clear? Any issues or mistakes?
• Do you consider the challenge too complicated for CGCC?
• Any improvement suggestions?
• Any tag suggestions?
• Anything else?

Posted: Can Jimmy escape the ghosts?

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

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.