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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
local f = assert(io.open(arg[1], "r"))
function parse(f)
local nodes = {}
for line in f:lines() do
for name,flow,conns in line:gmatch("Valve (..) has flow rate=(%d+); tunnels? leads? to valves? (.*)$") do
local flow = tonumber(flow)
local c = split(conns, ",")
assert(nodes[name] == nil)
nodes[name] = {flow=flow, c=c, dists=nil, on=false}
end
end
return nodes
end
function split(s, sep)
local c = {}
for a in s:gmatch("[^%s"..sep.."]+") do
table.insert(c, a)
end
return c
end
-- make a grid of all the shortest paths between each nonzero node.
-- BFS to find shortest paths.
-- k is the name of the node to find closest distances to.
-- returns a table with keys of node names and vals of distances.
function closest_dists(k, nodes)
v = nodes[k]
local queue = {}
table.insert(queue, {name=k, d=0})
local cnt = 0
local visited = {}
while true do
local n = table.remove(queue, 1) -- removing from front makes this BFS
if (n == nil) then
break
end
if visited[n.name] then
goto cont
end
visited[n.name] = n.d
--[[
if n.name == start and n.d ~= 0 then
break
end
--]]
for _, c in ipairs(nodes[n.name].c) do
table.insert(queue, {name=c, d=n.d+1})
end
::cont::
end
return visited
end
local nodes = parse(f)
for name in pairs(nodes) do
nodes[name].dists = closest_dists(name, nodes)
-- remove self
nodes[name].dists[name] = nil
--print(name)
end
function tableclone(t)
local copy = {}
for ok,ov in pairs(t) do
copy[ok] = ov
end
return copy
end
-- DFS on all the possible paths, counting pressure released.
local stack = {}
local ends = {}
table.insert(stack, {name="AA", timeleft=30, pressure=0, parent={}, on={}})
while true do
io.write(tostring(#stack), "\r")
local n = table.remove(stack)
if n == nil then break end
if n.on[n.name] then
goto cont2
end
n.on[n.name] = true
if not ends[n.name] or ends[n.name].pressure < n.pressure or n.timeleft <= 0 then
-- save best paths as their ending valves
ends[n.name] = n
end
if n.timeleft <= 0 then goto cont2 end
local cntr = 0
for k,v in pairs(nodes[n.name].dists) do
local nt = n.timeleft - v
local np = n.pressure
if nodes[k].flow > 0 and not n.on[k] then
nt = nt - 1
if nt <= 0 then goto cont3 end
np = np + nt*nodes[k].flow
local non = tableclone(n.on)
cntr = cntr + 1
local npa = tableclone(n.parent)
table.insert(npa, n.name)
table.insert(stack, {name=k, timeleft=nt, pressure = np, parent=npa, on=non})
end
::cont3::
end
::cont2::
end
function sort_by_p(a, b)
return a.pressure > b.pressure
end
local oends = {}
for k,v in pairs(ends) do
table.insert(oends, {name=k, pressure=v.pressure, timeleft=v.timeleft, parent=v.parent})
end
table.sort(oends, sort_by_p)
local max = 0
local maxn = nil
print("==", "end", "pressure", "time left")
for _,v in ipairs(oends) do print("::",v.name,v.pressure,"",v.timeleft)
if v.pressure > max then
max = v.pressure
maxn = v
end
end
print("==")
-- print path
io.write("Best path: ")
for _,p in ipairs(maxn.parent) do io.write(p, " -> ") end
print(maxn.name)
print(maxn.pressure)
|
