/
Day12.kt
128 lines (105 loc) · 3.8 KB
/
Day12.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
package com.akikanellis.adventofcode.year2022
import com.akikanellis.adventofcode.year2022.utils.Point
object Day12 {
fun shortestPathSteps(input: String, ascending: Boolean): Int {
val squares = squares(input)
val startSquare = squares.single { if (ascending) it.startSquare else it.endSquare }
val shortestPath =
shortestPath(
ascending = ascending,
startSquare = startSquare
) { square -> if (ascending) square.endSquare else square.lowestElevation }
return shortestPath.size - 1
}
private fun squares(input: String): List<Square> {
val squaresGrid = input
.lines()
.filter { it.isNotBlank() }
.mapIndexed { rowIndex, row ->
row.mapIndexed { columnIndex, heightmapCharacter ->
Square(
position = Point(columnIndex, rowIndex),
heightmapCharacter = heightmapCharacter
)
}
}
val squares = squaresGrid.flatten()
for (square in squares) {
square.addNeighbours(
listOfNotNull(
squaresGrid[square.y].elementAtOrNull(square.x + 1),
squaresGrid[square.y].elementAtOrNull(square.x - 1),
squaresGrid.elementAtOrNull(square.y + 1)?.get(square.x),
squaresGrid.elementAtOrNull(square.y - 1)?.get(square.x)
)
)
}
return squares
}
private fun shortestPath(
ascending: Boolean,
startSquare: Square,
endSquareFound: (Square) -> Boolean
): List<Square> {
val endSquare = endSquare(ascending, startSquare, endSquareFound)
val shortestPath = mutableListOf<Square>()
var nextParentSquare: Square? = endSquare
while (nextParentSquare != null) {
shortestPath.add(0, nextParentSquare)
nextParentSquare = nextParentSquare.parent
}
return shortestPath
}
private fun endSquare(
ascending: Boolean,
startSquare: Square,
endSquareFound: (Square) -> Boolean
): Square {
val squaresToVisit = mutableListOf(startSquare)
while (squaresToVisit.isNotEmpty()) {
val square = squaresToVisit.removeFirst()
square.visit()
if (endSquareFound(square)) return square
square.accessibleNeighbours(ascending)
.filterNot { it.visited }
.forEach { neighbour ->
neighbour.visit()
neighbour.parent = square
squaresToVisit += neighbour
}
}
error("Could not find end square")
}
private data class Square(
val position: Point,
val heightmapCharacter: Char,
var visited: Boolean = false,
var parent: Square? = null
) {
val x = position.x
val y = position.y
val neighbours = mutableListOf<Square>()
val elevation = when (heightmapCharacter) {
'S' -> 'a'
'E' -> 'z'
else -> heightmapCharacter
}
val startSquare = heightmapCharacter == 'S'
val endSquare = heightmapCharacter == 'E'
val lowestElevation = elevation == 'a'
fun visit() {
visited = true
}
fun accessibleNeighbours(ascending: Boolean) = neighbours
.filter { neighbour ->
if (ascending) {
neighbour.elevation - elevation <= 1
} else {
elevation - neighbour.elevation <= 1
}
}
fun addNeighbours(neighbours: List<Square>) {
this.neighbours += neighbours
}
}
}