generated from kotlin-hands-on/advent-of-code-kotlin-template
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day05.kt
137 lines (117 loc) · 4.87 KB
/
Day05.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
136
137
package io.liodev.aoc.aoc2023
import io.liodev.aoc.Day
import io.liodev.aoc.readInputAsString
import io.liodev.aoc.runDay
// --- 2023 Day 5: If You Give A Seed A Fertilizer ---
class Day05(val input: String) : Day<Long> {
override val expectedValues = listOf(35L, 289863851, 46, 60568880)
private val almanac = input.toSeedAlmanac()
private val almanacWithRanges = input.toSeedAlmanacWithRanges()
data class SeedAlmanac(val seedsRange: List<LongRange>, val mappers: List<Mapper>) {
fun calculateMinLocationSlow() = // MANY minutes in Part2
seedsRange.minOf { seedRange ->
var min = Long.MAX_VALUE
for (seed in seedRange) {
var result = seed
for (mapper in mappers) {
result = mapper.pass(result)
}
min = min.coerceAtMost(result)
}
min
}
fun calculateMinLocationReversed(): Long = // 9 seconds in Part2 (but very bad for Part1)
(1..Long.MAX_VALUE).first {
var result = it
for (mapper in mappers.reversed()) {
result = mapper.reverse(result)
}
seedsRange.any { seedRange -> result in seedRange }
}
fun calculateMinLocation() = // 3 milliseconds in Part2
seedsRange.let { seedsRange ->
var listOfRanges = seedsRange
for (mapper in mappers) {
listOfRanges = listOfRanges.fold(listOf()) { acc, range ->
acc + mapper.passRange(range)
}
}
listOfRanges.minOf { it.first }
}
}
data class Mapper(val ranges: List<MapperRange>) {
fun pass(value: Long): Long {
for (range in ranges) {
if (value in range.source) return range.destination.first + value - range.source.first
}
return value
}
fun reverse(value: Long): Long {
for (range in ranges) {
if (value in range.destination) return range.source.first + value - range.destination.first
}
return value
}
fun passRange(range: LongRange): List<LongRange> {
val convert = mutableListOf<LongRange>()
val result = mutableListOf<LongRange>()
for (mapperRange in ranges) {
val y1 = maxOf(range.first, mapperRange.source.first)
val y2 = minOf(range.last, mapperRange.source.last)
if (y1 <= y2) {
val s1 = mapperRange.source.first
val d1 = mapperRange.destination.first
convert.add(y1..y2)
result.add(y1 - s1 + d1..y2 - s1 + d1)
}
}
convert.sortBy { it.first }
var cur = range.first
for (convertRange in convert) {
if (convertRange.first > cur) result.add(cur..<convertRange.first)
cur = convertRange.last + 1
}
if (cur <= range.last - 1) result.add(cur..range.last)
return result
}
}
data class MapperRange(val source: LongRange, val destination: LongRange)
private fun String.toSeedAlmanac(): SeedAlmanac {
return SeedAlmanac(
substringBefore("\n\n").parseSeedsAsSingleRange(),
substringAfter("\n\n").parseMappers()
)
}
private fun String.toSeedAlmanacWithRanges(): SeedAlmanac {
return SeedAlmanac(
substringBefore("\n\n").parseSeedsAsRanges(),
substringAfter("\n\n").parseMappers()
)
}
private fun String.parseSeedsAsSingleRange(): List<LongRange> =
substringAfter("seeds: ")
.split(" ")
.map { it.toLong()..it.toLong() + 1 }
private fun String.parseSeedsAsRanges(): List<LongRange> =
substringAfter("seeds: ")
.split(" ")
.map { it.toLong() }
.chunked(2)
.map { (it[0]..it[0] + it[1]) }
private fun String.parseMappers(): List<Mapper> =
split("\n\n").map { mapperStr ->
Mapper(mapperStr.split("\n").drop(1).map { it.toMapperRange() })
}
private fun String.toMapperRange(): MapperRange {
val range = this.split(" ").map { it.toLong() }
return MapperRange(range[1]..<range[1] + range[2], range[0]..<range[0] + range[2])
}
override fun solvePart1() = almanac.calculateMinLocationSlow()
override fun solvePart2() = almanacWithRanges.calculateMinLocation()
}
fun main() {
val name = Day05::class.simpleName
val testInput = readInputAsString("src/input/2023/${name}_test.txt")
val realInput = readInputAsString("src/input/2023/${name}.txt")
runDay(Day05(testInput), Day05(realInput), printTimings = true)
}