-
Notifications
You must be signed in to change notification settings - Fork 4
/
Day15.kt
59 lines (54 loc) · 2.44 KB
/
Day15.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
package com.github.ephemient.aoc2022
import kotlin.math.abs
@Day
class Day15(lines: List<String>) {
private val inputs = lines.map {
val x0 = it.substring(it.indexOf("x=") + 2, it.indexOf(',')).toInt()
val y0 = it.substring(it.indexOf("y=") + 2, it.indexOf(':')).toInt()
val x1 = it.substring(it.lastIndexOf("x=") + 2, it.lastIndexOf(',')).toInt()
val y1 = it.substring(it.lastIndexOf("y=") + 2).toInt()
x0 to y0 to (x1 to y1)
}
private val isTestInput = inputs.all { (sensor, _) -> sensor.first in 0..20 && sensor.second in 0..20 }
@Day.Part
fun part1(): Int {
val y = if (isTestInput) 10 else 2000000
val intervals = mutableListOf<IntRange>()
val beacons = mutableSetOf<Int>()
for ((sensor, beacon) in inputs) {
val dx = abs(sensor.first - beacon.first) + abs(sensor.second - beacon.second) - abs(y - sensor.second)
if (dx >= 0) intervals.addInterval(sensor.first - dx..sensor.first + dx)
if (beacon.second == y) beacons.add(beacon.first)
}
return intervals.sumOf { it.last - it.first + 1 } - beacons.size
}
@Day.Part
fun part2(): Long = sequence {
val size = if (isTestInput) 20 else 4000000
for (y in 0..size) {
val intervals = mutableListOf<IntRange>()
for ((sensor, beacon) in inputs) {
val dx = abs(sensor.first - beacon.first) + abs(sensor.second - beacon.second) - abs(y - sensor.second)
val lo = (sensor.first - dx).coerceAtLeast(0)
val hi = (sensor.first + dx).coerceAtMost(size)
if (lo <= hi) intervals.addInterval(lo..hi)
}
val hi = intervals.fold(0) { prev, interval ->
for (x in prev until interval.first) yield(4000000L * x + y)
interval.last + 1
}
for (x in hi..size) yield(4000000L * x + y)
}
}.single()
}
private fun MutableList<IntRange>.addInterval(range: IntRange) {
val loIndex = binarySearch { it.last.compareTo(range.first - 1) }.let { it shr 31 xor it }
val hiIndex = binarySearch(fromIndex = loIndex) { it.first.compareTo(range.last + 1) }.let { it shr 31 xor it }
val mergedRange = if (loIndex < hiIndex) {
minOf(this[loIndex].first, range.first)..maxOf(this[hiIndex - 1].last, range.last)
} else {
range
}
subList(loIndex, hiIndex).clear()
add(loIndex, mergedRange)
}