/
Day10.kt
135 lines (113 loc) · 4.13 KB
/
Day10.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
package y2023.day10
import AnsiColor
import AocPuzzle
import printColored
fun main() = Day10.runAll()
object Day10 : AocPuzzle<Int, Int>() {
override fun solve1(input: List<String>): Int {
val maze = Maze(input)
maze.printMaze()
val loop = maze.traverseMaze()
return loop.size / 2
}
override fun solve2(input: List<String>): Int {
val maze = Maze(input)
maze.printMaze()
val loop = maze.traverseMaze()
return (maze.maze.flatten() - loop).count { it.isInside(loop.toList()) }
}
private fun Maze.traverseMaze(): Set<Pipe> {
val result = mutableSetOf<Pipe>()
var mazeIt = start
while (result.add(mazeIt)) {
val lt = mazeIt.left(this)
val rt = mazeIt.right(this)
val up = mazeIt.up(this)
val dn = mazeIt.down(this)
mazeIt = when {
lt != null && lt !in result && mazeIt.isConnecting(lt) -> lt
rt != null && rt !in result && mazeIt.isConnecting(rt) -> rt
up != null && up !in result && mazeIt.isConnecting(up) -> up
dn != null && dn !in result && mazeIt.isConnecting(dn) -> dn
else -> break
}
}
return result
}
private fun Pipe.isInside(loop: List<Pipe>): Boolean {
// good old inside polygon check...
// based on pnpoly: https://wrfranklin.org/Research/Short_Notes/pnpoly.html
var isInside = false
for (i in loop.indices) {
val li = loop[i]
val lj = if (i == 0) loop.last() else loop[i-1]
if ((li.y > y) != (lj.y > y) && (x < (lj.x - li.x) * (y - li.y) / (lj.y - li.y) + li.x)) {
isInside = !isInside
}
}
return isInside
}
private fun Pipe.up(maze: Maze): Pipe? = maze[x, y-1]
private fun Pipe.down(maze: Maze): Pipe? = maze[x, y+1]
private fun Pipe.left(maze: Maze): Pipe? = maze[x-1, y]
private fun Pipe.right(maze: Maze): Pipe? = maze[x+1, y]
private fun Pipe.isConnecting(other: Pipe): Boolean = when {
x == other.x && y > other.y -> // other is up
shape in openUp && other.shape in openDn
y == other.y && x < other.x -> // other is right
shape in openRt && other.shape in openLt
x == other.x && y < other.y -> // other is down
shape in openDn && other.shape in openUp
y == other.y && x > other.x -> // other is left
shape in openLt && other.shape in openRt
else -> false
}
private fun Maze.printMaze() {
val loop = traverseMaze()
val loopPoly = loop.toList()
maze.forEach { row ->
print(" ")
row.forEach {
val fgColor = when {
it.shape == 'S' -> AnsiColor.BLACK
it in loop -> AnsiColor.BRIGHT_BLUE
it.isInside(loopPoly) -> AnsiColor.RED
else -> AnsiColor.BRIGHT_BLACK
}
val bgColor = if (it.shape == 'S') AnsiColor.BRIGHT_YELLOW else null
printColored("${charMap[it.shape] ?: it.shape}", fgColor, bgColor)
}
println()
}
}
private val openUp = setOf('|', 'J', 'L', 'S')
private val openDn = setOf('|', '7', 'F', 'S')
private val openLt = setOf('-', 'J', '7', 'S')
private val openRt = setOf('-', 'L', 'F', 'S')
private val charMap = mapOf(
'|' to '┃',
'-' to '━',
'J' to '┛',
'L' to '┗',
'F' to '┏',
'7' to '┓'
)
}
data class Pipe(val shape: Char, val x: Int, val y: Int)
class Maze(lines: List<String>) {
val maze: List<List<Pipe>> =
lines.mapIndexed { y, row ->
row.mapIndexed { x, c ->
Pipe(c, x, y)
}
}
val width = maze[0].size
val height = maze.size
val start: Pipe = maze.flatten().first { it.shape == 'S' }
operator fun get(x: Int, y: Int): Pipe? {
if (x !in 0 until width || y !in 0 until height) {
return null
}
return maze[y][x]
}
}