-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day21.kt
116 lines (106 loc) · 4.6 KB
/
Day21.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
package com.github.ephemient.aoc2023
class Day21(input: String) {
private val grid = input.lines().filter { it.isNotEmpty() }
private val size = grid.size
init {
require(size % 2 != 0)
require(grid.all { it.length == size })
require(grid.first().all { it != '#' })
require(grid.all { it.first() != '#' && it.last() != '#' })
require(grid.last().all { it != '#' })
}
private val start = grid.withIndex().firstNotNullOf { (y, line) ->
val x = line.indexOf('S')
if (x >= 0) IntPair(y, x) else null
}
private fun makeBlock(initial: Iterable<IndexedValue<IntPair>>): IntArray {
val queue = PriorityQueue<IndexedValue<IntPair>>(compareBy { it.index })
val block = IntArray(size * size) { -1 }
for (value in initial) queue.add(value)
while (!queue.isEmpty()) {
val (step, point) = queue.remove()
val existing = block[point]
if (existing in 0..step) continue
check(existing < 0)
block[point] = step
for (next in point.neighbors()) {
val candidate = block[next]
if (candidate < 0) {
queue.add(IndexedValue(step + 1, next))
} else {
check(candidate in step - 1..step + 1) { "$point=$step $next=$candidate" }
}
}
}
return block
}
fun part1(n: Int = 64): Int = makeBlock(listOf(IndexedValue(0, start))).count { it in 0..n && it xor n and 1 == 0 }
@Suppress("CyclomaticComplexMethod")
fun part2(n: Int = 26501365): Long {
val origin = makeBlock(listOf(IndexedValue(0, start)))
var acc = origin.count { it in 0..n && it xor n and 1 == 0 }.toLong()
for (quadrant in 0..<4) {
val signY = quadrant and 1 == 0
val signX = quadrant and 2 == 0
val block = makeBlock(
listOf(
IndexedValue(
origin[if (signY) 0 else size - 1, if (signX) 0 else size - 1] + 2,
IntPair(if (signY) size - 1 else 0, if (signX) size - 1 else 0)
)
)
)
acc += block.sumOf { step ->
if (step !in 0..n) return@sumOf 0
val remaining = n - step
if (remaining % 2 == 0) {
(remaining / size / 2 + 1).let { it.toLong() * it }
} else {
((remaining / size + 1) / 2).let { it.toLong() * (it + 1) }
}
}
}
for (axis in 0..<4) {
val sign = axis and 1 == 0
val src = if (sign) 0 else size - 1
val dst = if (sign) size - 1 else 0
val orientation = axis and 2 == 0
var block = origin
do {
val lastBlock = block
block = makeBlock(
(0..<size).map {
IndexedValue(
lastBlock[if (orientation) it else src, if (orientation) src else it] + 1,
IntPair(if (orientation) it else dst, if (orientation) dst else it),
)
}
)
acc += block.count { it in 0..n && it xor n and 1 == 0 }
} while (
block.any { it in 0..n } &&
block.withIndex().any { (i, step) -> step >= 0 && step - lastBlock[i] != size }
)
acc += block.sumOf { step ->
if (step < 0) return@sumOf 0
val remaining = n - step + size
((remaining + 1) / size - remaining.and(1)).coerceAtLeast(0) / 2
}
}
return acc
}
private fun IntPair.neighbors(): List<IntPair> = buildList(4) {
if (first > 0 && grid[first - 1][second] != '#') add(IntPair(first - 1, second))
if (second > 0 && grid[first][second - 1] != '#') add(IntPair(first, second - 1))
if (first < this@Day21.size - 1 && grid[first + 1][second] != '#') add(IntPair(first + 1, second))
if (second < this@Day21.size - 1 && grid[first][second + 1] != '#') add(IntPair(first, second + 1))
}
private operator fun IntArray.get(y: Int, x: Int): Int = this[y * this@Day21.size + x]
private operator fun IntArray.get(pair: IntPair): Int = this[pair.first, pair.second]
private operator fun IntArray.set(y: Int, x: Int, value: Int) {
this[y * this@Day21.size + x] = value
}
private operator fun IntArray.set(pair: IntPair, value: Int) {
this[pair.first, pair.second] = value
}
}