You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
100 lines
3.4 KiB
100 lines
3.4 KiB
import java.io.File
|
|
import kotlin.math.min
|
|
|
|
data class Coordinate ( val x: Int, val y: Int )
|
|
|
|
fun main() {
|
|
var y = 0
|
|
var x = 0
|
|
var start = Coordinate(0,0)
|
|
var end = Coordinate(0,0)
|
|
val grid: HashMap<Coordinate, Char> = hashMapOf()
|
|
for (line in File("b.input").readLines()) {
|
|
x = 0
|
|
line.chars().forEach {
|
|
val c = when(Char(it)) {
|
|
'S' -> { start = Coordinate(x,y); 'a' }
|
|
'E' -> { end = Coordinate(x,y); 'z' }
|
|
else -> Char(it)
|
|
}
|
|
grid.put(Coordinate(x,y), c)
|
|
x++
|
|
}
|
|
y++
|
|
}
|
|
|
|
println("start point is $start, end point is $end")
|
|
val neighbors: Map<Coordinate, Set<Coordinate>> =
|
|
grid.keys.map {s ->
|
|
Pair(s,
|
|
neighbors(s).filter {e ->
|
|
grid.containsKey(e) && close(grid.get(s)!!, grid.get(e)!!)
|
|
}.toSet())
|
|
}.toMap()
|
|
|
|
val distances: MutableMap<Coordinate, Int> = mutableMapOf(start to 0)
|
|
var nodesToVisit: MutableSet<Coordinate> = mutableSetOf(start)
|
|
val visited: MutableSet<Coordinate> = mutableSetOf()
|
|
while (nodesToVisit.isNotEmpty()) {
|
|
for (currentNode in nodesToVisit.toMutableSet()) {
|
|
println("visiting $currentNode and examining itss neighbors, ${neighbors[currentNode]}")
|
|
nodesToVisit.remove(currentNode)
|
|
|
|
for (neighbor in neighbors[currentNode]!!) {
|
|
distances.put(neighbor, min(
|
|
distances[neighbor] ?: Int.MAX_VALUE,
|
|
(distances[currentNode] ?: (Int.MAX_VALUE - 100)) + 1
|
|
)
|
|
)
|
|
if (!(neighbor in visited)) {
|
|
nodesToVisit.add(neighbor)
|
|
}
|
|
}
|
|
|
|
visited.add(currentNode)
|
|
}
|
|
}
|
|
println("distance from S to end point is ${distances[end]}")
|
|
|
|
var minimum = Int.MAX_VALUE
|
|
for (startPoint in grid.keys.filter {grid[it] == 'a'}) {
|
|
|
|
val distances: MutableMap<Coordinate, Int> = mutableMapOf(startPoint to 0)
|
|
var nodesToVisit: MutableSet<Coordinate> = mutableSetOf(startPoint)
|
|
val visited: MutableSet<Coordinate> = mutableSetOf()
|
|
while (nodesToVisit.isNotEmpty()) {
|
|
for (currentNode in nodesToVisit.toMutableSet()) {
|
|
//println("visiting $currentNode and examining itss neighbors, ${neighbors[currentNode]}")
|
|
nodesToVisit.remove(currentNode)
|
|
|
|
for (neighbor in neighbors[currentNode]!!) {
|
|
distances.put(
|
|
neighbor, min(
|
|
distances[neighbor] ?: Int.MAX_VALUE,
|
|
(distances[currentNode] ?: (Int.MAX_VALUE - 100)) + 1
|
|
)
|
|
)
|
|
if (!(neighbor in visited)) {
|
|
nodesToVisit.add(neighbor)
|
|
}
|
|
}
|
|
|
|
visited.add(currentNode)
|
|
}
|
|
}
|
|
minimum = min(distances[end]?: Int.MAX_VALUE, minimum)
|
|
}
|
|
println("smallest distance across any starting point was $minimum")
|
|
}
|
|
|
|
fun neighbors(r: Coordinate): Set<Coordinate>{
|
|
val left = Coordinate(r.x-1, r.y)
|
|
val right = Coordinate(r.x+1, r.y)
|
|
val up = Coordinate(r.x, r.y-1)
|
|
val down = Coordinate(r.x, r.y+1)
|
|
return setOf(left, right, up, down)
|
|
}
|
|
|
|
fun close(a: Char, b: Char): Boolean {
|
|
return b <= a.inc()
|
|
} |