blob: 5209fdd4fc8f806049696662a961c957ae01e4f0 (
plain)
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
|
class Valve
def initialize(flow_rate, tunnels)
@flow_rate = flow_rate
@tunnels = tunnels
@distance = {}
@open = false
end
attr_reader :flow_rate, :tunnels, :distance
def open?
@open
end
def open!
@open = true
end
end
valves = {}
$stdin.readlines.each do |line|
fr = line.scan(/\d+/)[0].to_i
name, *tunnels = line.scan(/[A-Z]{2}/)
valves[name] = Valve.new(fr, tunnels)
end
valves.each do |k, v|
seen = [k]
v.distance[k] = 0
q = v.tunnels.map{|nv|[nv, 1]}
until q.empty?
nv, d = q.shift
seen << nv
v.distance[nv] = d if v.distance[nv].nil?
q += valves[nv].tunnels.reject{ |t| seen.include?(t) }.map{ |nv| [nv, d+1] }
end
end
pointful_valves = valves.select { |k, v| v.flow_rate != 0 }.keys
at = "AA"
time_rem = 30
relief = 0
loop do
nv = nil
pointful_valves.each do |this|
next if valves[this].open?
nv = this if pointful_valves.map { |that|
(
valves[that].open? ?
0 :
(valves[at].distance[this] - valves[at].distance[that] + 1) *
valves[that].flow_rate - valves[this].flow_rate
) <= 0
}.all?
end
break if nv.nil?
time_rem -= valves[at].distance[nv]
time_rem -= 1
break if time_rem < 0
puts nv
puts time_rem
valves[nv].open!
relief += (time_rem * valves[nv].flow_rate)
at = nv
end
pp relief
exit
num_valves = pointful_valves.count
max_relief = 0
pointful_valves.permutation.each do |order|
at = "AA"
num_open = 0
time_rem = 30
relief = 0
until time_rem < 0 || num_open == num_valves
nv = order.shift
time_rem -= valves[at].distance[nv]
time_rem -= 1
relief += time_rem * valves[nv].flow_rate
at = nv
num_open += 1
end
max_relief = relief if relief > max_relief
end
puts max_relief
|
