Oh no! There are a bunch of meteoroids on my way through the universe ... what am I and my space ship, the SP4C3, supposed to do?

I need to manoeuver my shuttle through these rocks or I am done for!

Write a program that guides my shuttle through a map of asteroids, using as few bytes as possible since I don't have much time left to type them into my navigation device.
And because this is code-golf, dammit.

You will receive map data as input, represented by either a 2-dimensional array of characters, or an aray of strings. on the map will represent empty space, which is free to travel on, while #, or any other printable ASCII character, represents rocks. Somewhere on the map there will be a character representing the ship and its current direction, either <, v, > or ^.

Your output will have to be a string of instructions that my ship has to take. This ship only knows 4 instructions: <, v, >, ^, which represent moving left, down, right and up, but the ship is not allowed to navigate out of map bounds.

The top-left coordinate of your map is (0|0), so going down the Y-axis increases your y coordinate, while going right on the X-axis increments your x coordinate.

Note that we, for the sake of simplicity, reduce space to a 2-dimensional ... well, space, here.

There is one last problem: Since my ship is already moving pretty fast, there is no way we can turn around (i.e. doing a 180° turn), so if the direction that the ship has to take is > (right) there is no way we can navigate < (left).

## Success

Your code is successful, if it is able to produce navigation data to get the ship to the other side of the map, based on the direction it is facing (i.e. the last x coordinate if the ship is facing > (right)), without crashing into terrain.

## Input

You can receive input in any reasonable format, as long it is able to contain the map data, including the ship coordinates. You may assume that the input is always layed out in a way that the ship is able to pass through the entire map without turning around.

## Output

You may directly output to stdout or return a string from a method, as you prefer. Note that your output may only contain directional characters (<, v, >, ^).

## Rules

• Standard loopholes are forbidden.
• This is , so the shortest code in bytes, in any language, wins.
• Only coding languages that were not created solely for this challenge may be used.

## Example Cases

Input:

####      #####     ##
##          ##    ##
####
>        ##     ####
######
#######   ###
#     #####   ########


Solved Input:

####      #####     ##
##          ##    ##
>>>>>>>v ####
>>>>>>>>^##    v####
#####  >>>>>>>>
######   ###
#      #####  ########


Output: >>>>>>>>^>>>>>>>vv>>>>>>>>

Input:

##      ###      #
#      ####     ###
>     ###      ###
###    #  ###     ###
#####    ####    ####
######       ##
####      #######  ##


Solved Input:

##      ###      #
#      ####     ###
>>>>>v###>>>>>v###
###  v #>^### v   ###
#####>>>^#### >>v####
######       ## >>>>>
####      #######  ##


Output: >>>>>vv>>>^>^>>>>>vv>>v>>>>>

Input:

##    v        #######
#   ##  ##### ##########
#     ###    ######
#  ###     ###     #
##   #  ##   ##
####   #           ####


Solved Input:

##    v        #######
#   ##v ##### ##########
# >>v ###    ######
#  ###v    ###     #
##   # v##   ##
####   #v          ####


Output: vv>>vvvv

Thanks to Kevin Cruijssen for this testcase!

Input:

##       #
>   ###  #
#####    #
###   ###
# # # # #
#


Solved Input:

## ^>>>> #
>>>>###v #
#####<<v #
### <v###
# #v# # #
#  v>>>>>


Output: >>>>^>>>>vv<<v<vv>>>>>

Note: There may be some cases where multiple solutions are possible. A solution will be correct as long as the ship reaches its destination without crashing.

Good luck!

## marked as duplicate by Shaggy, Toto, pajonk, Laikoni, GryphonAug 8 '17 at 11:16

• "You may assume that the input is always layed out in a way that the ship is able to pass through the entire map without turning around." Does this mean that it's guaranteed that < will never need to be used? – marinus Aug 8 '17 at 6:27