-
Notifications
You must be signed in to change notification settings - Fork 2
/
Day17.kt
107 lines (91 loc) · 4.13 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
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
/*
* Copyright (c) 2022 by Todd Ginsberg
*/
/**
* Advent of Code 2022, Day 17 - Pyroclastic Flow
* Problem Description: http://adventofcode.com/2022/day/17
* Blog Post/Commentary: https://todd.ginsberg.com/post/advent-of-code/2022/day17/
*/
package com.ginsberg.advent2022
import kotlin.math.absoluteValue
class Day17(input: String) {
private val jets: List<Point2D> = parseJets(input)
private val shapes: List<Set<Point2D>> = generateShapes()
private val cave: MutableSet<Point2D> = (0..6).map { Point2D(it, 0) }.toMutableSet()
private val down: Point2D = Point2D(0, 1)
private val up: Point2D = Point2D(0, -1)
private var jetCounter: Int = 0
private var blockCounter: Int = 0
fun solvePart1(): Int {
repeat(2022) {
simulate()
}
return cave.height()
}
fun solvePart2(): Long =
calculateHeight(1000000000000L - 1)
private fun simulate() {
var thisShape = shapes.nth(blockCounter++).moveToStart(cave.minY())
do {
val jettedShape = thisShape * jets.nth(jetCounter++)
if (jettedShape in (0..6) && jettedShape.intersect(cave).isEmpty()) {
thisShape = jettedShape
}
thisShape = thisShape * down
} while (thisShape.intersect(cave).isEmpty())
cave += (thisShape * up)
}
private fun calculateHeight(targetBlockCount: Long): Long {
data class State(val ceiling: List<Int>, val blockMod: Int, val jetMod: Int)
val seen: MutableMap<State, Pair<Int, Int>> = mutableMapOf()
while (true) {
simulate()
val state = State(cave.normalizedCaveCeiling(), blockCounter % shapes.size, jetCounter % jets.size)
if (state in seen) {
// Fast forward
val (blockCountAtLoopStart, heightAtLoopStart) = seen.getValue(state)
val blocksPerLoop: Long = blockCounter - 1L - blockCountAtLoopStart
val totalLoops: Long = (targetBlockCount - blockCountAtLoopStart) / blocksPerLoop
val remainingBlocksFromClosestLoopToGoal: Long =
(targetBlockCount - blockCountAtLoopStart) - (totalLoops * blocksPerLoop)
val heightGainedSinceLoop = cave.height() - heightAtLoopStart
repeat(remainingBlocksFromClosestLoopToGoal.toInt()) {
simulate()
}
return cave.height() + (heightGainedSinceLoop * (totalLoops - 1))
}
seen[state] = blockCounter - 1 to cave.height()
}
}
private operator fun IntRange.contains(set: Set<Point2D>): Boolean = set.all { it.x in this }
private operator fun Set<Point2D>.times(point: Point2D): Set<Point2D> = map { it + point }.toSet()
private fun Set<Point2D>.minY(): Int = minOf { it.y }
private fun Set<Point2D>.height(): Int = minY().absoluteValue
private fun Set<Point2D>.normalizedCaveCeiling(): List<Int> =
groupBy { it.x }
.entries
.sortedBy { it.key }
.map { pointList -> pointList.value.minBy { point -> point.y } }
.let {
val normalTo = this.minY()
it.map { point -> normalTo - point.y }
}
private fun Set<Point2D>.moveToStart(ceilingHeight: Int): Set<Point2D> =
map { it + Point2D(2, ceilingHeight - 4) }.toSet()
private fun generateShapes(): List<Set<Point2D>> =
listOf(
setOf(Point2D(0, 0), Point2D(1, 0), Point2D(2, 0), Point2D(3, 0)),
setOf(Point2D(1, 0), Point2D(0, -1), Point2D(1, -1), Point2D(2, -1), Point2D(1, -2)),
setOf(Point2D(0, 0), Point2D(1, 0), Point2D(2, 0), Point2D(2, -1), Point2D(2, -2)),
setOf(Point2D(0, 0), Point2D(0, -1), Point2D(0, -2), Point2D(0, -3)),
setOf(Point2D(0, 0), Point2D(1, 0), Point2D(0, -1), Point2D(1, -1))
)
private fun parseJets(input: String): List<Point2D> =
input.map {
when (it) {
'>' -> Point2D(1, 0)
'<' -> Point2D(-1, 0)
else -> throw IllegalStateException("No such jet direction $it")
}
}
}