Skip to main content
3 of 4
deleted 8 characters in body; edited title
Jamal
  • 34.9k
  • 13
  • 133
  • 237

Groovy pathfinding algorithm

I have created a bit of path-finding code in response to this code golf question. Since this is one of my first large bits of code in Groovy that I have written, I would like to see how I could improve it.

def invalid() {
    println "Invalid map."
    System.exit(1)
}

def map =
        """01001E
010110
000P00
1100J1
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
//    line = reader.readLine()
//}

def size = map[0].size()
map.each { if (it.size() != size) invalid() }

def startLocation = [0, 0]
def endLocation = [0, 0]
map.eachWithIndex { it, idx ->
    def startIdx = it.indexOf('S')
    def endIdx = it.indexOf('E')
    
    if (startIdx != -1) {
        startLocation[0] = startIdx; startLocation[1] = idx
    }
    if (endIdx != -1) {
        endLocation[0] = endIdx; endLocation[1] = 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 >= map[0].size() || x < 0 || y < 0)
        return;

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

    if (chr == 'E') validPath = newPath
    if ('J0S'.contains(chr) && !validPath) {
        testMove(x - 1, y, newPath)
        testMove(x + 1, y, newPath)
        testMove(x, y + 1, newPath)
        testMove(x, y - 1, newPath)
    }
}
testMove(startLocation[0], startLocation[1], [])
if (!validPath) invalid()

println validPath

def orintation = 0
def path = ''
validPath.inject { first, second ->
    def chr = map[second[1]][second[0]]
    def sub = [first[0] - second[0], first[1] - second[1]]
    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"
J Atkin
  • 1.8k
  • 2
  • 13
  • 15