-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day17.kt
80 lines (73 loc) · 2.83 KB
/
Day17.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
package com.github.ephemient.aoc2023
class Day17(input: String) {
private val input = input.lines().mapNotNull { it.filter(('1'..'9')::contains).ifEmpty { null } }
fun part1(): Int? = bfs(
ok = { true },
next = { direction, distance ->
if (distance < 3) listOf(direction - 1, direction + 1, direction) else listOf(direction - 1, direction + 1)
}
)
fun part2(): Int? = bfs(
ok = { it >= 4 },
next = { direction, distance ->
when {
distance < 4 -> listOf(direction)
distance < 10 -> listOf(direction - 1, direction + 1, direction)
else -> listOf(direction - 1, direction + 1)
}
},
)
private inline fun bfs(
ok: (distance: Int) -> Boolean,
next: (direction: Direction, distance: Int) -> Iterable<Direction>,
): Int? {
val start = State(0, 0, Direction.R, 0)
val costs = mutableMapOf(start to 0)
val queue = PriorityQueue<IndexedValue<State>>(compareBy { (cost, state) -> cost - state.y - state.x })
queue.add(IndexedValue(0, start))
while (!queue.isEmpty()) {
val (cost, state) = queue.remove()
if (state.y == input.lastIndex && state.x == input.last().lastIndex && ok(state.distance)) return cost
if (costs.getValue(state) < cost) continue
@Suppress("LoopWithTooManyJumpStatements")
for (direction in next(state.direction, state.distance)) {
val newState = state.move(direction)
if (newState.y !in input.indices || newState.x !in input[state.y].indices) continue
val newCost = cost + input[newState.y][newState.x].digitToInt()
if (costs.getOrElse(newState) { Int.MAX_VALUE } <= newCost) continue
costs[newState] = newCost
queue.add(IndexedValue(newCost, newState))
}
}
return null
}
private enum class Direction {
U, L, D, R;
operator fun plus(other: Int): Direction = entries[(ordinal + other).mod(entries.size)]
operator fun minus(other: Int): Direction = entries[(ordinal - other).mod(entries.size)]
}
private data class State(
val y: Int,
val x: Int,
val direction: Direction,
val distance: Int,
)
private fun State.move(direction: Direction): State {
val y = when (direction) {
Direction.U -> y - 1
Direction.D -> y + 1
else -> y
}
val x = when (direction) {
Direction.L -> x - 1
Direction.R -> x + 1
else -> x
}
return State(
y = y,
x = x,
direction = direction,
distance = if (direction == this.direction) distance + 1 else 1,
)
}
}