# I like to move it move it

King Julian needs to get through the jungle, but he's feeling lazy. He wants a computer to be able to calculate a route through the jungle for him.

Using STDIN get a map of the jungle for the computer to crack. It will follow the following format:

01001E
010110
000P00
1100J1
S00111


The way the jungle map works is:

0 is ground that Julian can move along.

1 is dense impassable jungle.

P is an area with predators in it, that you must avoid at all costs.

J is relatively thick jungle. Julian's minions can break through one of these before tiring.

S is where Julian starts. It can be anywhere on the map.

E is where Julian wants to go; the end of the path. It also can be anywhere on the map, just like any other tile.

Every character is a tile on the map. Line breaks indicate a new row of tiles. If STDIN in your language does not support line breaks, the line break must be replaced by a space to signify a new row.

To move between the tiles, you must output a string using STDOUT containing the following special characters:

F - Forward

B - Backward

L - Rotate Julian left (90 degrees anticlockwise)

R - Rotate Julian right (90 degrees clockwise)

M - Minions destroy a J tile 1 tile forward from Julian, if there is one (M just clears out the tile, you still have to move onto it)

A possible output would be:

RFFLFRFMFLFRFLFF


Which solves the map above.

Notes:

• If your program outputs a solution which hits predators, game over.

• If you hit impassable jungle, you just bounce back to where you were before you ran into dense jungle, facing the same way. (Toward the jungle)

• Julian starts facing upwards. (^ That way ^)

• The output doesn't have to be the fastest solution, FFF and FBFBFBFBFBFFF are the same. However, outputting the fastest possible solution gives a -10% byte count bonus.

• If a map is invalid, STDOUT 'Invalid map.' (That includes if the map is unsolvable)

• A map cannot have rows or columns of different lengths; that makes it invalid.

#Language name, *n* bytes

code

Explanation (optional)


This is , so the shortest code in bytes wins.

• Your solution example has Julian walking straight into a predator. Something like RFFLFRFMFLFRFLFF should work instead. – Emigna Nov 23 '15 at 7:33
• @Emigna, Oops. I got mixed up between thick jungle and a predator's lair... – Oliver Nov 23 '15 at 8:04
• Does a P tile really add something different from a 1 tile? I can't really imagine a plausible solution that treats them any differently. – user7486 Nov 23 '15 at 14:34
• @dan1111 The P tile kills Julian when he travels over it. The 1 tile Julian can't pass through, but if Julian hits it he doesn't die, he just bounces back. – Oliver Nov 23 '15 at 21:02
• @Tobsta, yes, I understand. But does that make a difference? It seems like any successful solution would just avoid 1 and P tiles. – user7486 Nov 23 '15 at 21:51

# Groovy, 656 bytes

That was too long...

i={println"Invalid map."
System.exit(1)}
m=[]
while(r!=''){m<<r
o=m.size()
m.each{if(it.size()!=o)i()}
f=*4
m.eachWithIndex{l,n->s=l.indexOf('S')
e=l.indexOf('E')
if(s!=-1){f=s;f=n}
if(e!=-1){f=e;f=n}}
v=[]
t={x,y,d->if(d.contains([x,y])|y>=m.size()|x>=o|x<0|y<0)return
a=m[y][x]
def p=d+[[x,y]]
if(a=='E')v=p
if(a=='J'|a=='0'|a=='S'){t(x-1,y,p)
t(x+1,y,p)
t(x,y+1,p)
t(x,y-1,p)}}
t(f,f,[])
if(!v)i()
o=0
p=''
v.inject{t,s->
c=m[s][s]
k=[t-s,t-s]
z=[[0,1]:0,[1,0]:1,[0,-1]:2,[-1,0]:3][k]
p+=((((o-z)==0)?'':(z>0?'R':'L'))+(c=='J'?'M':'')+'F')
o=z
s}
println p


Output for the maze:

RFFLFRFMFLFRFLFF


Ungolfed:

invalid = {
println "Invalid map."
System.exit(1)
}
map = """01001E
010110
000P00
1110J1
S00111""".split('\n')

//map = [""]// TODO remove this, this is type checking only
//map.remove(0)
//while (line != '') {
//    map << line.replace('P','1')
//}

size = map.size()
map.each {if(it.size() != size) invalid()}

startAndEnd = [0,0,0,0]
map.eachWithIndex {it, idx -> s=it.indexOf('S');e=it.indexOf('E');
if(s!=-1){ startAndEnd=s; startAndEnd=idx}
if(e!=-1){ startAndEnd=e; startAndEnd=idx}}

def validPath = []

testMove = {x, y, visited ->// visited is an array of x y pairs that we have already visited in this tree
if (visited.contains([x,y]) || y>=map.size() || x>=size || x<0 || y<0)
return;

def valueAtPos = map[y][x]
def newPath = visited + [[x,y]]

if (valueAtPos == 'E') validPath = newPath
if ((valueAtPos == 'J' || valueAtPos == '0' || valueAtPos == 'S') && !validPath) {
testMove(x-1, y, newPath)
testMove(x+1, y, newPath)
testMove(x, y+1, newPath)
testMove(x, y-1, newPath)
}
}
if (!validPath) invalid()
testMove(startAndEnd,startAndEnd, [])

println validPath

orintation = 0
path = ''
validPath.inject {first, second ->
def chr = map[second][second]
def sub = [first-second,first-second]
println "acc:$first, second:$second"
def newOrin = [[0,1]:0, [1,0]:1, [0,-1]:2, [-1,0]:3][sub]
path += ((((orintation - newOrin)==0)?'':(newOrin>0?'R':'L')) + (chr=='J'?'M':'') + 'F')
orintation = newOrin
second
}
println "path: \$path"


I will try this again in python soon to see if I can shorten it further.