-
Notifications
You must be signed in to change notification settings - Fork 4
/
Day21.kt
124 lines (113 loc) · 5.06 KB
/
Day21.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
package com.github.ephemient.aoc2022
@Day
class Day21(lines: List<String>) {
private val monkeys = buildMap {
for (line in lines) {
val (name, definition) = line.split(": ", limit = 2)
this[name] = definition.toIntOrNull()?.let { Expr.Literal(it) }
?: definition.split(' ', limit = 3).let { (lhs, symbol, rhs) ->
val op = when (symbol) {
"+" -> Operation.Add
"-" -> Operation.Subtract
"*" -> Operation.Multiply
"/" -> Operation.Divide
else -> throw IllegalArgumentException(symbol)
}
Expr.Binary(op, lhs, rhs)
}
}
}
@Day.Part
fun part1(): Long = DeepRecursiveFunction<String, Long> { name ->
when (val expr = monkeys.getValue(name)) {
is Expr.Literal -> expr.value.toLong()
is Expr.Binary -> when (expr.op) {
Operation.Add -> callRecursive(expr.lhs) + callRecursive(expr.rhs)
Operation.Subtract -> callRecursive(expr.lhs) - callRecursive(expr.rhs)
Operation.Multiply -> callRecursive(expr.lhs) * callRecursive(expr.rhs)
Operation.Divide -> callRecursive(expr.lhs) / callRecursive(expr.rhs)
}
}
}("root")
@Day.Part
fun part2(): Long {
val (_, lhs, rhs) = monkeys.getValue("root") as Expr.Binary
val eval = DeepRecursiveFunction<String, Pair<Rational, Rational>> { name ->
if (name == "humn") return@DeepRecursiveFunction Rational(1) to Rational(0)
when (val expr = monkeys.getValue(name)) {
is Expr.Literal -> Rational(0) to Rational(expr.value.toLong())
is Expr.Binary -> {
val (a, b) = callRecursive(expr.lhs)
val (c, d) = callRecursive(expr.rhs)
when (expr.op) {
Operation.Add -> a + c to b + d
Operation.Subtract -> a - c to b - d
Operation.Multiply -> when {
a.numerator == 0L -> b * c to b * d
c.numerator == 0L -> a * d to b * d
else -> TODO()
}
Operation.Divide -> if (c.numerator == 0L) a / d to b / d else TODO()
}
}
}
}
val (m, b) = eval(lhs)
val (n, c) = eval(rhs)
val x = (c - b) / (m - n)
check(x.denominator == 1L)
return x.numerator
}
private enum class Operation {
Add, Subtract, Multiply, Divide,
}
private sealed class Expr {
data class Literal(val value: Int) : Expr()
data class Binary(val op: Operation, val lhs: String, val rhs: String) : Expr()
}
private data class Rational(val numerator: Long, val denominator: Long = 1) {
init {
require(denominator > 0)
assert { gcd(numerator, denominator) == 1L }
}
operator fun plus(other: Rational): Rational {
val gcd1 = gcd(this.denominator, other.denominator)
val multiplier = this.denominator / gcd1
val denominator = multiplier * other.denominator
val numerator = this.numerator * (other.denominator / gcd1) + other.numerator * multiplier
val gcd2 = gcd(numerator, denominator)
return Rational(numerator / gcd2, denominator / gcd2)
}
operator fun minus(other: Rational): Rational {
val gcd1 = gcd(this.denominator, other.denominator)
val multiplier = this.denominator / gcd1
val denominator = multiplier * other.denominator
val numerator = this.numerator * (other.denominator / gcd1) - other.numerator * multiplier
val gcd2 = gcd(numerator, denominator)
return Rational(numerator / gcd2, denominator / gcd2)
}
operator fun times(other: Rational): Rational {
val gcd1 = gcd(this.numerator, other.denominator)
val gcd2 = gcd(other.numerator, this.denominator)
val numerator = (this.numerator / gcd1) * (other.numerator / gcd2)
val denominator = (this.denominator / gcd2) * (other.denominator / gcd1)
return Rational(numerator, denominator)
}
operator fun div(other: Rational): Rational {
require(other.numerator != 0L)
val gcd1 = gcd(this.numerator, other.numerator)
val gcd2 = gcd(other.denominator, this.denominator)
val numerator = (this.numerator / gcd1) * (other.denominator / gcd2)
val denominator = (this.denominator / gcd2) * (other.numerator / gcd1)
return Rational(numerator, denominator)
}
}
companion object {
private fun gcd(a: Long, b: Long): Long {
var x = a
var y = b
while (y != 0L) x = y.also { y = x % y }
return if (x < 0 != b < 0) -x else x
}
}
}