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
|
import java.lang.Long.max
object Day21 {
private class Dice {
private var nextRoll = 1
var rollCount = 0
private set
private fun roll(): Int {
rollCount++
return nextRoll.also { nextRoll = nextRoll % 100 + 1 }
}
fun rollThrice() = roll() + roll() + roll()
}
fun part1(firstPosition: Int, secondPosition: Int): Int {
val dice = Dice()
val playerPositions = mutableListOf(firstPosition, secondPosition)
val playerScores = mutableListOf(0, 0)
var nextPlayer = 0
while (playerScores.none { it >= 1000 }) {
playerPositions[nextPlayer] = wrapPosition(playerPositions[nextPlayer] + dice.rollThrice())
playerScores[nextPlayer] += playerPositions[nextPlayer]
nextPlayer = 1 - nextPlayer
}
return playerScores[nextPlayer] * dice.rollCount
}
private val tripleRollSumFrequencies = sequence {
(1..3).let { range ->
range.forEach { a ->
range.forEach { b ->
range.forEach { c ->
yield(a + b + c)
}
}
}
}
}.groupingBy { it }.eachCount()
private fun wrapPosition(position: Int) = (position - 1).mod(10) + 1
private data class RecursionInput(val endingPos: Int, val score: Int, val turns: Int, val initialPos: Int)
private val universeSolutionCache = mutableMapOf<RecursionInput, Long>()
private fun universeCount(i: RecursionInput): Long {
universeSolutionCache[i]?.let { return it }
if (i.score !in 0 until 21 + i.endingPos) return 0
if (i.turns == 0) return (if (i.score == 0 && i.endingPos == i.initialPos) 1L else 0L)
return tripleRollSumFrequencies.map { (rolledSum, occurrences) ->
occurrences * universeCount(
RecursionInput(
wrapPosition(i.endingPos - rolledSum),
i.score - i.endingPos,
i.turns - 1,
i.initialPos
)
)
}.sum().also { universeSolutionCache[i] = it }
}
private fun countWinningUniverses(winnerInitialPos: Int, loserInitialPos: Int, isSecondWinner: Boolean) =
combinations(1..10).sumOf { (winnerEndPos, loserEndPos) ->
combinations(21..30, 0..20).sumOf { (winnerScore, loserScore) ->
(0..10).sumOf { turns ->
universeCount(
RecursionInput(
winnerEndPos,
winnerScore,
turns,
winnerInitialPos
)
) * universeCount(
RecursionInput(
loserEndPos,
loserScore,
if (isSecondWinner) turns else turns - 1,
loserInitialPos
)
)
}
}
}
fun part2(firstPosition: Int, secondPosition: Int) = max(
countWinningUniverses(firstPosition, secondPosition, false),
countWinningUniverses(secondPosition, firstPosition, true)
)
}
fun main() {
check(Day21.part1(4, 8) == 739785)
check(Day21.part2(4, 8) == 444356092776315)
println(Day21.part1(2, 7))
println(Day21.part2(2, 7))
}
|
