16
\$\begingroup\$

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.

Your answer should somewhat follow this format:

#Language name, *n* bytes

    code

Explanation (optional)

This is , so the shortest code in bytes wins.

| improve this question | | | | |
\$\endgroup\$
  • \$\begingroup\$ Your solution example has Julian walking straight into a predator. Something like RFFLFRFMFLFRFLFF should work instead. \$\endgroup\$ – Emigna Nov 23 '15 at 7:33
  • \$\begingroup\$ @Emigna, Oops. I got mixed up between thick jungle and a predator's lair... \$\endgroup\$ – Oliver Nov 23 '15 at 8:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – user7486 Nov 23 '15 at 14:34
  • \$\begingroup\$ @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. \$\endgroup\$ – Oliver Nov 23 '15 at 21:02
  • 1
    \$\begingroup\$ @Tobsta, yes, I understand. But does that make a difference? It seems like any successful solution would just avoid 1 and P tiles. \$\endgroup\$ – user7486 Nov 23 '15 at 21:51
1
\$\begingroup\$

Groovy, 656 bytes

That was too long...

i={println"Invalid map."
System.exit(1)}
m=[]
q=System.in.newReader()
r=q.readLine()
while(r!=''){m<<r
r=q.readLine()}
o=m[0].size()
m.each{if(it.size()!=o)i()}
f=[0]*4
m.eachWithIndex{l,n->s=l.indexOf('S')
e=l.indexOf('E')
if(s!=-1){f[0]=s;f[1]=n}
if(e!=-1){f[2]=e;f[3]=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[0],f[1],[])
if(!v)i()
o=0
p=''
v.inject{t,s->
c=m[s[1]][s[0]]
k=[t[0]-s[0],t[1]-s[1]]
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)
//reader = System.in.newReader()
//line = reader.readLine()
//while (line != '') {
//    map << line.replace('P','1')
//    line = reader.readLine()
//}

size = map[0].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[0]=s; startAndEnd[1]=idx}
    if(e!=-1){ startAndEnd[2]=e; startAndEnd[3]=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[0],startAndEnd[1], [])

println validPath

orintation = 0
path = ''
validPath.inject {first, second ->
    def chr = map[second[1]][second[0]]
    def sub = [first[0]-second[0],first[1]-second[1]]
    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.

| improve this answer | | | | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.