119 lines
3.7 KiB
Text
119 lines
3.7 KiB
Text
import "os" for Process
|
|
import "./ioutil" for File, FileUtil
|
|
|
|
/*
|
|
* 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
|
|
* character list, because we'll want mutability when drawing the solution later.
|
|
*/
|
|
var decimateHorizontally = Fn.new { |lines|
|
|
var width = ((lines[0].count + 1)/2).floor
|
|
var c = List.filled(lines.count, null)
|
|
for (i in 0...lines.count) {
|
|
c[i] = List.filled(width, null)
|
|
for (j in 0...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.
|
|
*/
|
|
var solveMazeRecursively // recursive function
|
|
solveMazeRecursively = Fn.new { |maze, x, y, d|
|
|
var ok = false
|
|
var i = 0
|
|
while (i < 4 && !ok) {
|
|
if (i != d) {
|
|
// 0 = up, 1 = right, 2 = down, 3 = left
|
|
if (i == 0) {
|
|
if (maze[y - 1][x] == " ") ok = solveMazeRecursively.call(maze, x, y - 2, 2)
|
|
} else if (i == 1) {
|
|
if (maze[y][x + 1] == " ") ok = solveMazeRecursively.call(maze, x + 2, y, 3)
|
|
} else if (i == 2) {
|
|
if (maze[y + 1][x] == " ") ok = solveMazeRecursively.call(maze, x, y + 2, 0)
|
|
} else if (i == 3) {
|
|
if (maze[y][x - 1] == " ") ok = solveMazeRecursively.call(maze, x - 2, y, 1)
|
|
}
|
|
}
|
|
i = i + 1
|
|
}
|
|
|
|
// 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] = "*"
|
|
if (d == 0) {
|
|
maze[y - 1][x] = "*"
|
|
} else if (d == 1) {
|
|
maze[y][x + 1] = "*"
|
|
} else if (d == 2) {
|
|
maze[y + 1][x] = "*"
|
|
} else if (d == 3) {
|
|
maze[y][x - 1] = "*"
|
|
}
|
|
}
|
|
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.
|
|
*/
|
|
var solveMaze = Fn.new { |maze|
|
|
solveMazeRecursively.call(maze, maze[0].count - 2, maze.count - 2, -1)
|
|
}
|
|
|
|
/*
|
|
* Opposite of decimateHorizontally(). Adds extra characters to make
|
|
* the maze "look right", and converts each line from a char list to a
|
|
* string at the same time.
|
|
*/
|
|
var expandHorizontally = Fn.new { |maze|
|
|
var tmp = List.filled(3, " ")
|
|
var lines = List.filled(maze.count, null)
|
|
for (i in 0...maze.count) {
|
|
var sb = ""
|
|
for (j in 0...maze[i].count) {
|
|
if (j % 2 == 0) {
|
|
sb = sb + maze[i][j]
|
|
} else {
|
|
for (k in 0..2) tmp[k] = maze[i][j]
|
|
if (tmp[1] == "*") {
|
|
tmp[0] = " "
|
|
tmp[2] = " "
|
|
}
|
|
sb = sb + tmp.join()
|
|
}
|
|
}
|
|
lines[i] = sb
|
|
}
|
|
return lines
|
|
}
|
|
|
|
/*
|
|
* Accepts a maze as generated by:
|
|
* http://rosettacode.org/wiki/Maze_generation#Wren
|
|
* in a file whose name is specified as a command-line argument.
|
|
*/
|
|
var args = Process.arguments
|
|
if (args.count != 1) {
|
|
System.print("The maze file to be read should be passed as a single command line argument.")
|
|
return
|
|
}
|
|
if (!File.exists(args[0])) {
|
|
System.print("Sorry %(args[0]) does not exist.")
|
|
return
|
|
}
|
|
var lines = FileUtil.readLines(args[0]).where { |l| l != "" }.toList
|
|
var maze = decimateHorizontally.call(lines)
|
|
solveMaze.call(maze)
|
|
var solvedLines = expandHorizontally.call(maze)
|
|
System.print(solvedLines.join("\n"))
|