I think there are generally two improvements you can make:
- Leverage the GDK (probably what you're most interested in)
- 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.
