-
Notifications
You must be signed in to change notification settings - Fork 5.7k
/
maze.kt
223 lines (197 loc) · 5.32 KB
/
maze.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
/**
* Let's Walk Through a Maze.
*
* Imagine there is a maze whose walls are the big 'O' letters.
* Now, I stand where a big 'I' stands and some cool prize lies
* somewhere marked with a '$' sign. Like this:
*
* OOOOOOOOOOOOOOOOO
* O O
* O$ O O
* OOOOO O
* O O
* O OOOOOOOOOOOOOO
* O O I O
* O O
* OOOOOOOOOOOOOOOOO
*
* I want to get the prize, and this program helps me do so as soon
* as I possibly can by finding a shortest path through the maze.
*/
import java.util.*
/**
* This function looks for a path from max.start to maze.end through
* free space (a path does not go through walls). One can move only
* straightly up, down, left or right, no diagonal moves allowed.
*/
fun findPath(maze : Maze) : List<Pair<Int, Int>>? {
val previous = HashMap<Pair<Int, Int>, Pair<Int, Int>>
val queue = LinkedList<Pair<Int, Int>>
val visited = HashSet<Pair<Int, Int>>
queue.offer(maze.start)
visited.add(maze.start)
while (!queue.isEmpty()) {
val cell = queue.poll()
if (cell == maze.end) break
for (newCell in maze.neighbors(cell._1, cell._2)) {
if (newCell in visited) continue
previous[newCell] = cell
queue.offer(newCell)
visited.add(cell)
}
}
if (previous[maze.end] == null) return null
val path = ArrayList<Pair<Int, Int>>()
var current = previous[maze.end]
while (current != maze.start) {
path.add(0, current)
current = previous[current]
}
return path
}
/**
* Find neighbors of the (i, j) cell that are not walls
*/
fun Maze.neighbors(i : Int, j : Int) : List<Pair<Int, Int>> {
val result = ArrayList<Pair<Int, Int>>
addIfFree(i - 1, j, result)
addIfFree(i, j - 1, result)
addIfFree(i + 1, j, result)
addIfFree(i, j + 1, result)
return result
}
fun Maze.addIfFree(i : Int, j : Int, result : List<Pair<Int, Int>>) {
if (i !in 0..height-1) return
if (j !in 0..width-1) return
if (walls[i][j]) return
result.add(Pair(i, j))
}
/**
* A data class that represents a maze
*/
class Maze(
// Number or columns
val width : Int,
// Number of rows
val height : Int,
// true for a wall, false for free space
val walls : Array<out Array<out Boolean>>,
// The starting point (must not be a wall)
val start : Pair<Int, Int>,
// The target point (must not be a wall)
val end : Pair<Int, Int>
) {
}
/** A few maze examples here */
fun main(args : Array<String>) {
printMaze("I $")
printMaze("I O $")
printMaze("""
O $
O
O
O
O I
""")
printMaze("""
OOOOOOOOOOO
O $ O
OOOOOOO OOO
O O
OOOOO OOOOO
O O
O OOOOOOOOO
O OO
OOOOOO IO
""")
printMaze("""
OOOOOOOOOOOOOOOOO
O O
O$ O O
OOOOO O
O O
O OOOOOOOOOOOOOO
O O I O
O O
OOOOOOOOOOOOOOOOO
""")
}
// UTILITIES
fun printMaze(str : String) {
val maze = makeMaze(str)
println("Maze:")
val path = findPath(maze)
for (i in 0..maze.height - 1) {
for (j in 0..maze.width - 1) {
val cell = Pair(i, j)
print(
if (maze.walls[i][j]) "O"
else if (cell == maze.start) "I"
else if (cell == maze.end) "$"
else if (path != null && path.contains(cell)) "~"
else " "
)
}
println("")
}
println("Result: " + if (path == null) "No path" else "Path found")
println("")
}
/**
* A maze is encoded in the string s: the big 'O' letters are walls.
* I stand where a big 'I' stands and the prize is marked with
* a '$' sign.
*
* Example:
*
* OOOOOOOOOOOOOOOOO
* O O
* O$ O O
* OOOOO O
* O O
* O OOOOOOOOOOOOOO
* O O I O
* O O
* OOOOOOOOOOOOOOOOO
*/
fun makeMaze(s : String) : Maze {
val lines = s.split("\n")!!
val w = max<String?>(lines.toList(), comparator<String?> {o1, o2 ->
val l1 : Int = o1?.size ?: 0
val l2 = o2?.size ?: 0
l1 - l2
})!!
val data = Array<Array<Boolean>>(lines.size) {Array<Boolean>(w.size) {false}}
var start : Pair<Int, Int>? = null
var end : Pair<Int, Int>? = null
for (line in lines.indices) {
for (x in lines[line].indices) {
val c = lines[line]!![x]
data[line][x] = c == 'O'
when (c) {
'I' -> start = Pair(line, x)
'$' -> end = Pair(line, x)
else -> {}
}
}
}
if (start == null) {
throw IllegalArgumentException("No starting point in the maze (should be indicated with 'I')")
}
if (end == null) {
throw IllegalArgumentException("No goal point in the maze (should be indicated with a '$' sign)")
}
return Maze(w.size, lines.size, data, start!!, end!!)
}
// An excerpt from the Standard Library
val String?.indices : IntRange get() = IntRange(0, this!!.size)
fun <K, V> Map<K, V>.set(k : K, v : V) { put(k, v) }
fun comparator<T> (f : (T, T) -> Int) : Comparator<T> = object : Comparator<T> {
override fun compare(o1 : T, o2 : T) : Int = f(o1, o2)
override fun equals(p : Any?) : Boolean = false
}
fun <T, C: Collection<T>> Array<T>.to(result: C) : C {
for (elem in this)
result.add(elem)
return result
}