-
Notifications
You must be signed in to change notification settings - Fork 2
/
Day16.kt
85 lines (73 loc) · 3.35 KB
/
Day16.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
/*
* Copyright (c) 2022 by Todd Ginsberg
*/
/**
* Advent of Code 2022, Day 16 - Proboscidea Volcanium
* Problem Description: http://adventofcode.com/2022/day/16
* Blog Post/Commentary: https://todd.ginsberg.com/post/advent-of-code/2022/day16/
*/
package com.ginsberg.advent2022
import com.github.shiguruikai.combinatoricskt.combinations
import com.github.shiguruikai.combinatoricskt.permutations
class Day16(input: List<String>) {
private val rooms: Map<String, ValveRoom> = input.map { ValveRoom.of(it) }.associateBy { it.name }
private val cheapestPathCosts: Map<String, Map<String, Int>> = calculateShortestPaths()
fun solvePart1(): Int = searchPaths("AA", 30)
fun solvePart2(): Int =
cheapestPathCosts.keys.filter { it != "AA" }
.combinations(cheapestPathCosts.size / 2)
.map { it.toSet() }
.maxOf { halfOfTheRooms ->
searchPaths("AA", 26, halfOfTheRooms) + searchPaths("AA", 26, cheapestPathCosts.keys - halfOfTheRooms)
}
private fun searchPaths(
location: String,
timeAllowed: Int,
seen: Set<String> = emptySet(),
timeTaken: Int = 0,
totalFlow: Int = 0
): Int = cheapestPathCosts
.getValue(location)
.asSequence()
.filterNot { (nextRoom, _) -> nextRoom in seen }
.filter { (_, traversalCost) -> timeTaken + traversalCost + 1 < timeAllowed }
.maxOfOrNull { (nextRoom, traversalCost) ->
searchPaths(
nextRoom,
timeAllowed,
seen + nextRoom,
timeTaken + traversalCost + 1,
totalFlow + ((timeAllowed - timeTaken - traversalCost - 1) * rooms.getValue(nextRoom).flowRate)
)
} ?: totalFlow
private fun calculateShortestPaths(): Map<String, Map<String, Int>> {
val shortestPaths = rooms.values.associate {
it.name to it.paths.associateWith { 1 }.toMutableMap()
}.toMutableMap()
shortestPaths.keys.permutations(3).forEach { (waypoint, from, to) ->
shortestPaths[from, to] = minOf(
shortestPaths[from, to], // Existing Path
shortestPaths[from, waypoint] + shortestPaths[waypoint, to] // New Path
)
}
val zeroFlowRooms = rooms.values.filter { it.flowRate == 0 || it.name == "AA" }.map { it.name }.toSet()
shortestPaths.values.forEach { it.keys.removeAll(zeroFlowRooms) }
val canGetToFromAA: Set<String> = shortestPaths.getValue("AA").keys
return shortestPaths.filter { it.key in canGetToFromAA || it.key == "AA" }
}
private operator fun Map<String, MutableMap<String, Int>>.set(key1: String, key2: String, value: Int) {
getValue(key1)[key2] = value
}
private operator fun Map<String, Map<String, Int>>.get(key1: String, key2: String, defaultValue: Int = 31000): Int =
get(key1)?.get(key2) ?: defaultValue
private data class ValveRoom(val name: String, val paths: List<String>, val flowRate: Int) {
companion object {
fun of(input: String): ValveRoom =
ValveRoom(
input.substringAfter(" ").substringBefore(" "),
input.substringAfter("valve").substringAfter(" ").split(", "),
input.substringAfter("=").substringBefore(";").toInt()
)
}
}
}