# 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)
//while (line != '') {
//    map << line
//}

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"  ## 1 Answer I think there are generally two improvements you can make: 1. Leverage the GDK (probably what you're most interested in) 2. Refactor the code to make it testable. First, here's the code: def map = """01001E 010110 000P00 1100J1 S00111""".split('\n') def path = findPath(map) println "path:$path"

assert path == 'RFFLFRFMFLFRFLFF'

def findPath(map) {
/**
* Validate the map.
*/
map.with {
def size = getAt(0).size()
def invalidRows = it.findAll { row -> row.size() != size }

if(invalidRows) throw new IllegalArgumentException("The map $it contains the following invalid rows:$invalidRows")

it.join().split('').countBy { it }.with { counts ->
if(counts.S > 1) throw new IllegalArgumentException("The map $it contains multiple start positions.") if(counts.E > 1) throw new IllegalArgumentException("The map$it contains multiple end positions.")
if(!counts.S) throw new IllegalArgumentException("The map $it is missing the start position.") if(!counts.E) throw new IllegalArgumentException("The map$it is missing the end position.")
}
}

/**
* Get the start and end locations.
*/
def (startLocation, endLocation) = { markers ->
def locations = markers.clone()

map.eachWithIndex { it, y ->
markers
.collectEntries { marker -> [(marker): it.indexOf(marker)] }
.each { marker, x ->
def index = locations.indexOf(marker)

if(x != -1) locations[index] = [x: x, y: y]
}
}

return locations
}(['S', 'E'])

/**
* Find the valid path, if possible.
*/
def validPath = testMove(startLocation.x, startLocation.y, map, [])
if (!validPath) throw new IllegalArgumentException("The map $map does not contain a valid path.") /** * Generate the path in the output format. */ def path = validPath.collate(2, 1, false).with { def orintation = 0 def builder = new StringBuilder() it.each { pair -> def first = pair[0] def second = pair[1] 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] builder.append ((((orintation - newOrin) == 0) ? '' : (newOrin > 0 ? 'R' : 'L')) + (chr == 'J' ? 'M' : '') + 'F') orintation = newOrin } builder.toString() } } def testMove(x, y, map, 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]] def ret if (chr == 'E') return newPath if ('J0S'.contains(chr)) { def locations = [ [x: x - 1, y: y], [x: x + 1, y: y], [x: x, y: y + 1], [x: x, y: y - 1] ] for(location in locations) { ret = testMove(location.x, location.y, map, newPath) if(ret) return ret } } }  # Leverage the GDK Early in the script, you have a size variable which is used to ensure all of the rows in the map are of the same length. The size variable is not used elsewhere. So to limit its scope, you can refactor the validation using Object.with(Closure): map.with { def size = getAt(0).size() def invalidRows = it.findAll { row -> row.size() != size } if(invalidRows) throw new IllegalArgumentException("The map$it contains the following invalid rows: $invalidRows") ... }  In addition, you can validate that the map contains only one start and end position. map.with { ... it.join().split('').countBy { it }.with { counts -> if(counts.S > 1) throw new IllegalArgumentException("The map$it contains multiple start positions.")
if(counts.E > 1) throw new IllegalArgumentException("The map $it contains multiple end positions.") if(!counts.S) throw new IllegalArgumentException("The map$it is missing the start position.")
if(!counts.E) throw new IllegalArgumentException("The map \$it is missing the end position.")
}
}


You can assign the startLocation and endLocation directly, without an initial value which is then overwritten, like this:

def (startLocation, endLocation) = { markers ->
def locations = markers.clone()

map.eachWithIndex { it, y ->
markers
.collectEntries { marker -> [(marker): it.indexOf(marker)] }
.each { marker, x ->
def index = locations.indexOf(marker)

if(x != -1) locations[index] = [x: x, y: y]
}
}

return locations
}(['S', 'E'])


This has the additional benefit of not having side-effects.

Another improvement is to change the location Lists to Maps so that instead of startLocation[0] you can do startLocation.x. This improves readability.

To build the path String, I think using Collection.collate(size, step, keepRemainder) is better suited than Collection.inject(Closure) because it helps clarify the code's intent. inject() can be used on the output of collate(), but that would have been more trouble than it's worth due to the need to keep multiple things in context (accumulator). So I used Object.with(Closure) instead.

def path = validPath.collate(2, 1, false).with {
def orintation = 0
def builder = new StringBuilder()

it.each { pair ->
def first = pair[0]
def second = pair[1]
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]

builder.append ((((orintation - newOrin) == 0) ? '' : (newOrin > 0 ? 'R' : 'L')) + (chr == 'J' ? 'M' : '') + 'F')
orintation = newOrin
}

builder.toString()
}


In addition, since in the JVM String is immutable, String concatenation can create temporary objects which the JVM must then dispose of. It's typically better to use StringBuilder.

# Testability

To make the code testable, meaning that it can be executed via a method call and the output can be validated, I placed most of the code into the findPath() method. As a consequence, I converted the testMove closure into a method.

I know the challenge states If a map is invalid, STDOUT 'Invalid map.' (That includes if the map is unsolvable). However, I disagree with using the same error message for multiple problems. That's one reason I replaced these messages with insightful exceptions. The other reason is to keep the Groovy Console from exiting.

• Fantastic answer! Thanks for taking the time to write this out. As it happens you were right. This being originally for a code golf challenge I was/am less worried about testing than just writing somewhat idiomatic groovy code. Again, thanks much! – J Atkin Dec 4 '15 at 22:41
• In the map.with closure you define invalidRows = it.findAll { row -> row.size() != size }. Would this be an appropriate time to use find? Such as invalidRow = it.find { row -> row.size() != size } – J Atkin Dec 4 '15 at 23:14
• Initially I used find, but later changed it to findAll so that all of the erroneous rows can be shown in the exception message. But, that's assuming that the length of the first row is always correct. So, find may be the better choice. – Emmanuel Rosa Dec 4 '15 at 23:19