Skip to content

Commit dd18156

Browse files
LiquidFunLiquidFun
committed
Add day 16
1 parent ef017b9 commit dd18156

File tree

7 files changed

+136
-1
lines changed

7 files changed

+136
-1
lines changed

‎2022/16/16.kt

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
import java.util.PriorityQueue
2+
3+
data class State(
4+
var time: Int,
5+
var current: String,
6+
var elTime: Int? = null,
7+
var elephant: String? = null,
8+
var opened: Set<String> = setOf(),
9+
var flow: Int = 0,
10+
) : Comparable<State> {
11+
override fun compareTo(other: State) = compareValuesBy(this, other, { -it.flow })
12+
}
13+
14+
fun main() {
15+
val input = generateSequence(::readlnOrNull).toList()
16+
.map { Regex("([A-Z]{2}|\\d+)").findAll(it).toList().map { it.value } }
17+
val neighbors = input.associate { it[0] to it.slice(2..it.size-1) }
18+
val flows = input.associate { it[0] to it[1].toInt() }
19+
20+
fun getNonZeroNeighbors(curr: String, dist: Int = 0, visited: Set<String> = setOf()): Map<String, Int> {
21+
val neigh = HashMap<String, Int>()
22+
for (neighbor in neighbors[curr]!!.filter { it !in visited }) {
23+
if (flows[neighbor]!! != 0)
24+
neigh[neighbor] = dist+1
25+
for ((name, d) in getNonZeroNeighbors(neighbor, dist+1, visited + setOf(curr)))
26+
neigh[name] = minOf(d, neigh.getOrDefault(name, 1000))
27+
}
28+
return neigh
29+
}
30+
val nonZeroNeighbors = input.associate { it[0] to getNonZeroNeighbors(it[0]) }
31+
32+
fun solve(initialState: State): Int {
33+
val queue = PriorityQueue<State>().also { it.add(initialState) }
34+
var best = 0
35+
val visited: MutableMap<List<String>, Int> = mutableMapOf()
36+
while (queue.isNotEmpty()) {
37+
var (time, current, elTime, elephant, opened, flow) = queue.remove()
38+
best = maxOf(best, flow)
39+
val vis = (opened.toList() + listOf(current, elephant ?: "")).sorted()
40+
if (visited.getOrDefault(vis, -1) >= flow)
41+
continue
42+
visited[vis] = flow
43+
if (elTime != null && elephant != null && time < elTime) {
44+
time = elTime.also { elTime = time }
45+
current = elephant.also { elephant = current }
46+
}
47+
for ((neighbor, dist) in nonZeroNeighbors[current]!!) {
48+
val newTime = time-dist-1
49+
val newFlow = flow+flows[neighbor]!!*newTime
50+
if (newTime >= 0 && neighbor !in opened)
51+
queue.add(State(newTime, neighbor, elTime, elephant, opened+setOf(neighbor), newFlow))
52+
}
53+
}
54+
return best
55+
}
56+
solve(State(30, "AA")).run(::println)
57+
solve(State(26, "AA", 26, "AA")).run(::println) // Takes ~10 seconds
58+
59+
}

‎2022/16/example.ans

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
1651
2+
1707

‎2022/16/example.in

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
2+
Valve BB has flow rate=13; tunnels lead to valves CC, AA
3+
Valve CC has flow rate=2; tunnels lead to valves DD, BB
4+
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
5+
Valve EE has flow rate=3; tunnels lead to valves FF, DD
6+
Valve FF has flow rate=0; tunnels lead to valves EE, GG
7+
Valve GG has flow rate=0; tunnels lead to valves FF, HH
8+
Valve HH has flow rate=22; tunnel leads to valve GG
9+
Valve II has flow rate=0; tunnels lead to valves AA, JJ
10+
Valve JJ has flow rate=21; tunnel leads to valve II

‎2022/16/input.ans

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
1789
2+
2496

‎2022/16/input.in

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
Valve AW has flow rate=0; tunnels lead to valves LG, TL
2+
Valve OM has flow rate=0; tunnels lead to valves XK, IM
3+
Valve BG has flow rate=0; tunnels lead to valves MP, SB
4+
Valve XB has flow rate=0; tunnels lead to valves MA, TL
5+
Valve CD has flow rate=0; tunnels lead to valves VL, OF
6+
Valve VF has flow rate=0; tunnels lead to valves CS, XK
7+
Valve HK has flow rate=0; tunnels lead to valves RL, QB
8+
Valve QN has flow rate=0; tunnels lead to valves IV, QR
9+
Valve OF has flow rate=4; tunnels lead to valves TQ, CD, IR, IM, JE
10+
Valve QB has flow rate=14; tunnels lead to valves HK, XE, CS, VO
11+
Valve ZE has flow rate=7; tunnels lead to valves JB, NC, SE, OI
12+
Valve OW has flow rate=0; tunnels lead to valves MB, JB
13+
Valve MA has flow rate=0; tunnels lead to valves XB, MB
14+
Valve MP has flow rate=0; tunnels lead to valves VK, BG
15+
Valve UE has flow rate=9; tunnels lead to valves ZM, RZ, WI, HO, FO
16+
Valve QR has flow rate=24; tunnel leads to valve QN
17+
Valve TQ has flow rate=0; tunnels lead to valves OF, AA
18+
Valve SE has flow rate=0; tunnels lead to valves ZE, ZZ
19+
Valve AQ has flow rate=20; tunnel leads to valve CX
20+
Valve XE has flow rate=0; tunnels lead to valves JQ, QB
21+
Valve DC has flow rate=8; tunnels lead to valves ZD, MJ, RZ
22+
Valve ZM has flow rate=0; tunnels lead to valves YJ, UE
23+
Valve VK has flow rate=21; tunnel leads to valve MP
24+
Valve VR has flow rate=0; tunnels lead to valves WV, PS
25+
Valve BH has flow rate=0; tunnels lead to valves AA, MB
26+
Valve ZR has flow rate=0; tunnels lead to valves LG, AI
27+
Valve JE has flow rate=0; tunnels lead to valves OF, HO
28+
Valve IR has flow rate=0; tunnels lead to valves IV, OF
29+
Valve FO has flow rate=0; tunnels lead to valves XQ, UE
30+
Valve AA has flow rate=0; tunnels lead to valves NC, VY, BH, TQ, YJ
31+
Valve ZZ has flow rate=0; tunnels lead to valves SE, TL
32+
Valve XQ has flow rate=0; tunnels lead to valves IV, FO
33+
Valve WI has flow rate=0; tunnels lead to valves UE, VO
34+
Valve VY has flow rate=0; tunnels lead to valves AA, LG
35+
Valve XK has flow rate=15; tunnels lead to valves VF, OM, ZD
36+
Valve CX has flow rate=0; tunnels lead to valves AQ, MB
37+
Valve JQ has flow rate=0; tunnels lead to valves XE, IV
38+
Valve LG has flow rate=3; tunnels lead to valves VY, PS, ZR, AW, OI
39+
Valve JB has flow rate=0; tunnels lead to valves ZE, OW
40+
Valve OI has flow rate=0; tunnels lead to valves ZE, LG
41+
Valve YJ has flow rate=0; tunnels lead to valves ZM, AA
42+
Valve NC has flow rate=0; tunnels lead to valves AA, ZE
43+
Valve KR has flow rate=0; tunnels lead to valves SB, MJ
44+
Valve MB has flow rate=17; tunnels lead to valves CX, BH, AI, OW, MA
45+
Valve AI has flow rate=0; tunnels lead to valves ZR, MB
46+
Valve TL has flow rate=16; tunnels lead to valves ZZ, XB, AW
47+
Valve RL has flow rate=0; tunnels lead to valves WV, HK
48+
Valve CS has flow rate=0; tunnels lead to valves VF, QB
49+
Valve WV has flow rate=25; tunnels lead to valves RL, VL, VR
50+
Valve ZD has flow rate=0; tunnels lead to valves XK, DC
51+
Valve IV has flow rate=23; tunnels lead to valves XQ, IR, JQ, QN
52+
Valve PS has flow rate=0; tunnels lead to valves VR, LG
53+
Valve RZ has flow rate=0; tunnels lead to valves DC, UE
54+
Valve VO has flow rate=0; tunnels lead to valves WI, QB
55+
Valve MJ has flow rate=0; tunnels lead to valves DC, KR
56+
Valve IM has flow rate=0; tunnels lead to valves OM, OF
57+
Valve VL has flow rate=0; tunnels lead to valves CD, WV
58+
Valve SB has flow rate=18; tunnels lead to valves BG, KR
59+
Valve HO has flow rate=0; tunnels lead to valves JE, UE

‎Media/2022/16.png

7.62 KB
Loading

‎README.md

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44

55
<!-- AOC TILES BEGIN -->
66
<h1 align="center">
7-
2022 - 30 ⭐
7+
2022 - 32 ⭐
88
</h1>
99
<a href="2022/01/01.kt">
1010
<img src="Media/2022/01.png" width="161px">
@@ -51,6 +51,9 @@
5151
<a href="2022/15/15.kt">
5252
<img src="Media/2022/15.png" width="161px">
5353
</a>
54+
<a href="2022/16/16.kt">
55+
<img src="Media/2022/16.png" width="161px">
56+
</a>
5457
<h1 align="center">
5558
2021 - 50 ⭐
5659
</h1>

0 commit comments

Comments
 (0)