-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day12.kt
117 lines (87 loc) · 3.7 KB
/
Day12.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
package be.vreijsenj.aoc.days
import be.vreijsenj.aoc.utils.PuzzleUtils
import kotlin.time.measureTime
val CACHE = mutableMapOf<Triple<Int, Int, Int>, Long>()
data class ConditionRecord(val springs: List<String>, val groups: List<Int>) {
companion object {
@JvmStatic
fun parse(line: String, times: Int): ConditionRecord {
val (springs, groups) = line.split(" ")
return ConditionRecord(
springs = unfold(springs, times, "?").chunked(1),
groups = unfold(groups, times, ",").split(",").map { it.toInt() }
)
}
private fun unfold(line: String, times: Int, separator: String): String {
return (0..< times).fold(line) {
acc, _ -> acc + separator + line
}
}
}
fun arrangements(): Long {
CACHE.clear()
return group(0, 0, 0)
}
private fun group(currentPositionIndex: Int, currentGroupIndex: Int, currentGroupLength: Int): Long {
val signature = Triple(currentPositionIndex, currentGroupIndex, currentGroupLength)
if(signature in CACHE) {
return CACHE[signature]!!
}
// Check whether we are out of bounce, which means we reached the end.
if(currentPositionIndex == springs.size) {
// Check whether we just finished a group, and were preparing for the next
if(currentGroupIndex == groups.size && currentGroupLength == 0) {
return 1
}
// Check whether we could have closed off the last group
if(currentGroupIndex == groups.size - 1 && currentGroupLength == groups.last) {
return 1
}
return 0
}
var count = 0L
val possibilities = listOf("#", ".")
possibilities.onEach { possibility ->
val value = springs[currentPositionIndex]
if(value == possibility || value == "?") {
// Prevent closing an "empty" group
if (possibility == "." && currentGroupLength == 0) {
// Unable to create group, continue and try to create group again
count += group(currentPositionIndex + 1, currentGroupIndex, 0)
}
// Check whether the group is actually valid, giving the current group constraints
if (possibility == "." && currentGroupLength > 0 && currentGroupIndex < groups.size && groups[currentGroupIndex] == currentGroupLength) {
// Close current group, move on to next group
count += group(currentPositionIndex + 1, currentGroupIndex + 1, 0)
}
if (possibility == "#") {
// Continue current group
count += group(currentPositionIndex + 1, currentGroupIndex, currentGroupLength + 1)
}
}
}
CACHE[signature] = count
return count
}
}
object Day12 {
@JvmStatic
fun main(args: Array<String>) {
val elapsed = measureTime {
val input = PuzzleUtils.getInput(12, 1)
val resultPartOne = runPartOne(input)
val resultPartTwo = runPartTwo(input)
println("Sum of possible arrangements (pt.1): $resultPartOne")
println("Sum of possible arrangements (pt.2): $resultPartTwo")
}
println("Took: $elapsed")
}
fun runPartOne(input: List<String>): Long {
return input.map { ConditionRecord.parse(it, 0) }
.sumOf { it.arrangements() }
}
fun runPartTwo(input: List<String>): Long {
return input.map { ConditionRecord.parse(it, 4) }
.sumOf { it.arrangements() }
}
}