Created
December 19, 2022 16:53
-
-
Save cjavdev/b6f1f78bad76f69130cef4532742c97a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
if ARGV.empty? | |
data = DATA.readlines(chomp: true) | |
else | |
data = File.readlines(ARGV[0], chomp: true) | |
end | |
VALVES = {} | |
GRAPH = {} | |
data.each do |line| | |
match = /Valve (?<name>[A-Z]{2}) has flow rate=(?<rate>\d+); tunnels? leads? to valves? (?<valves>.*)/.match(line) | |
VALVES[match[:name]] = match[:rate].to_i | |
GRAPH[match[:name]] = match[:valves].split(', ') | |
end | |
p VALVES | |
p GRAPH | |
$cache = {} | |
def max_flow(current, opened, time) | |
return 0 if time <= 0 | |
key = [current, opened, time] | |
return $cache[key] if $cache.key?(key) | |
max = 0 | |
# If we open the current valve | |
if !opened.include?(current) | |
current_opened = opened + [current] | |
pressure = VALVES[current] * (time - 1) | |
if pressure != 0 | |
current_max = pressure + max_flow(current, current_opened.sort, time - 1) | |
max = current_max if current_max > max | |
end | |
end | |
GRAPH[current].each do |next_valve| | |
current_max = max_flow(next_valve, opened, time - 1) | |
max = current_max if current_max > max | |
end | |
$cache[key] = max | |
max | |
end | |
p max_flow("AA", [], 30) | |
__END__ | |
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB | |
Valve BB has flow rate=13; tunnels lead to valves CC, AA | |
Valve CC has flow rate=2; tunnels lead to valves DD, BB | |
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE | |
Valve EE has flow rate=3; tunnels lead to valves FF, DD | |
Valve FF has flow rate=0; tunnels lead to valves EE, GG | |
Valve GG has flow rate=0; tunnels lead to valves FF, HH | |
Valve HH has flow rate=22; tunnel leads to valve GG | |
Valve II has flow rate=0; tunnels lead to valves AA, JJ | |
Valve JJ has flow rate=21; tunnel leads to valve II |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://youtu.be/LzDRS7igO1k