Maze solving: Difference between revisions
Content added Content deleted
(Added Julia language) |
(Added Kotlin) |
||
Line 2,749: | Line 2,749: | ||
dist, path = dijkstra(graph) |
dist, path = dijkstra(graph) |
||
printpath(path, 6)</lang> |
printpath(path, 6)</lang> |
||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<lang scala>// Version 1.2.31 |
|||
import java.io.File |
|||
typealias Maze = List<CharArray> |
|||
/** |
|||
* Makes the maze half as wide (i. e. "+---+" becomes "+-+"), so that |
|||
* each cell in the maze is the same size horizontally as vertically. |
|||
* (Versus the expanded version, which looks better visually.) |
|||
* Also, converts each line of the maze from a String to a |
|||
* char[], because we'll want mutability when drawing the solution later. |
|||
*/ |
|||
fun decimateHorizontally(lines: List<String>): Maze { |
|||
val width = (lines[0].length + 1) / 2 |
|||
val c = List(lines.size) { CharArray(width) } |
|||
for (i in 0 until lines.size) { |
|||
for (j in 0 until width) c[i][j] = lines[i][j * 2] |
|||
} |
|||
return c |
|||
} |
|||
/** |
|||
* Given the maze, the x and y coordinates (which must be odd), |
|||
* and the direction we came from, return true if the maze is |
|||
* solvable, and draw the solution if so. |
|||
*/ |
|||
fun solveMazeRecursively(maze: Maze, x: Int, y: Int, d: Int): Boolean { |
|||
var ok = false |
|||
var i = 0 |
|||
while (i < 4 && !ok) { |
|||
if (i != d) { |
|||
// 0 = up, 1 = right, 2 = down, 3 = left |
|||
when(i) { |
|||
0 -> if (maze[y - 1][x] == ' ') ok = solveMazeRecursively (maze, x, y - 2, 2) |
|||
1 -> if (maze[y][x + 1] == ' ') ok = solveMazeRecursively (maze, x + 2, y, 3) |
|||
2 -> if (maze[y + 1][x] == ' ') ok = solveMazeRecursively (maze, x, y + 2, 0) |
|||
3 -> if (maze[y][x - 1] == ' ') ok = solveMazeRecursively (maze, x - 2, y, 1) |
|||
else -> {} |
|||
} |
|||
} |
|||
i++ |
|||
} |
|||
// check for end condition |
|||
if (x == 1 && y == 1) ok = true |
|||
// once we have found a solution, draw it as we unwind the recursion |
|||
if (ok) { |
|||
maze[y][x] = '*' |
|||
when (d) { |
|||
0 -> maze[y - 1][x] = '*' |
|||
1 -> maze[y][x + 1] = '*' |
|||
2 -> maze[y + 1][x] = '*' |
|||
3 -> maze[y][x - 1] = '*' |
|||
else -> {} |
|||
} |
|||
} |
|||
return ok |
|||
} |
|||
/** |
|||
* Solve the maze and draw the solution. For simplicity, |
|||
* assumes the starting point is the lower right, and the |
|||
* ending point is the upper left. |
|||
*/ |
|||
fun solveMaze(maze: Maze) = |
|||
solveMazeRecursively(maze, maze[0].size - 2, maze.size - 2, -1) |
|||
/** |
|||
* Opposite of decimateHorizontally(). Adds extra characters to make |
|||
* the maze "look right", and converts each line from char[] to |
|||
* String at the same time. |
|||
*/ |
|||
fun expandHorizontally(maze: Maze): Array<String> { |
|||
val tmp = CharArray(3) |
|||
val lines = Array<String>(maze.size) { "" } |
|||
for (i in 0 until maze.size) { |
|||
val sb = StringBuilder(maze[i].size * 2) |
|||
for (j in 0 until maze[i].size) { |
|||
if (j % 2 == 0) |
|||
sb.append(maze[i][j]) |
|||
else { |
|||
for (k in 0..2) tmp[k] = maze[i][j] |
|||
if (tmp[1] == '*') { |
|||
tmp[0] = ' ' |
|||
tmp[2] = ' ' |
|||
} |
|||
sb.append(tmp) |
|||
} |
|||
} |
|||
lines[i] = sb.toString() |
|||
} |
|||
return lines |
|||
} |
|||
/** |
|||
* Accepts a maze as generated by: |
|||
* http://rosettacode.org/wiki/Maze_generation#Kotlin |
|||
* in a file whose name is specified as a command-line argument. |
|||
*/ |
|||
fun main(args: Array<String>) { |
|||
if (args.size != 1) { |
|||
println("The maze file to be read should be passed as a single command line argument.") |
|||
return |
|||
} |
|||
val f = File(args[0]) |
|||
if (!f.exists()) { |
|||
println("Sorry ${args[0]} does not exist.") |
|||
return |
|||
} |
|||
val lines = f.readLines(Charsets.US_ASCII) |
|||
val maze = decimateHorizontally(lines) |
|||
solveMaze(maze) |
|||
val solvedLines = expandHorizontally(maze) |
|||
println(solvedLines.joinToString("\n")) |
|||
}</lang> |
|||
{{out}} |
|||
Maze (maze.txt) produced by the maze generation program: |
|||
<pre> |
|||
+---+---+---+---+---+---+---+---+ |
|||
| | | | |
|||
+---+---+ + + +---+ + + |
|||
| | | | | | | |
|||
+ + + +---+ + +---+ + |
|||
| | | | | | |
|||
+ + + + +---+---+---+ + |
|||
| | | | | | |
|||
+---+ + +---+---+---+ + + |
|||
| | | | | | |
|||
+ +---+ + +---+ + + + |
|||
| | | | | | |
|||
+ + +---+---+ +---+---+ + |
|||
| | | | | |
|||
+ +---+ + +---+ + +---+ |
|||
| | | | |
|||
+---+---+---+---+---+---+---+---+ |
|||
</pre> |
|||
Solution generated by this program when passed maze.txt - follow *'s from bottom right (start) to top left (finish): |
|||
<pre> |
|||
+---+---+---+---+---+---+---+---+ |
|||
| * * * * * | * * * * * | | |
|||
+---+---+ * + + * +---+ * + + |
|||
| | * | | * | | * * * | |
|||
+ + + * +---+ * + +---+ * + |
|||
| | | * | * * * | * | |
|||
+ + + * + * +---+---+---+ * + |
|||
| | | * | * * * * * * * | * | |
|||
+---+ + * +---+---+---+ * + * + |
|||
| | * | * * * * * | * | * | |
|||
+ +---+ * + * +---+ * + * + * + |
|||
| | * * * | * * * | * * * | * | |
|||
+ + * +---+---+ * +---+---+ * + |
|||
| * * * | * * * | * * * | * * * | |
|||
+ * +---+ * + * +---+ * + * +---+ |
|||
| * * * * * | * * * * * | * * * | |
|||
+---+---+---+---+---+---+---+---+ |
|||
</pre> |
|||
=={{header|Mathematica}}== |
=={{header|Mathematica}}== |