Advertisement
Guest User

Untitled

a guest
Jan 3rd, 2023
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 1.72 KB | None | 0 0
  1. local valves = {}
  2. local links = {}
  3. local valveInd = {}
  4. local working = 0
  5. local i = 0
  6. for line in io.lines(arg[1]) do
  7.     local valve, flow, adj = line:match("Valve (%w+) has flow rate=(%d+); tunnels? leads? to valves? (.+)")
  8.     if flow ~= "0" then
  9.         working = working + 1
  10.         valveInd[valve] = i
  11.         i = i + 1
  12.     end
  13.     valves[valve] = tonumber(flow)
  14.     links[valve] = {}
  15.     for w in adj:gmatch("%w+") do
  16.         table.insert(links[valve], w)
  17.     end
  18. end
  19.  
  20. local function getCosts(start)
  21.     local costs, vis, Q = {}, {}, {start}
  22.     vis[start] = true
  23.     local steps = 0
  24.     while #Q > 0 do
  25.         steps = steps + 1
  26.         local newQ = {}
  27.         for _, p in ipairs(Q) do
  28.             for _, cave in ipairs(links[p]) do
  29.                 if not vis[cave] then
  30.                     vis[cave] = true
  31.                     if valves[cave] ~= 0 then costs[cave] = steps end
  32.                     table.insert(newQ, cave)
  33.                 end
  34.             end
  35.         end
  36.         Q = newQ
  37.     end
  38.     return costs
  39. end
  40.  
  41. local costs = {}
  42. for valve, n in pairs(valves) do
  43.     if valve == "AA" or n ~= 0 then
  44.         costs[valve] = getCosts(valve)
  45.     end
  46. end
  47.  
  48. local function DFS(curr, tLeft, flow, vis, states)
  49.     local key = string.format("%s %d %d %d", curr, tLeft, flow, vis)
  50.     if states[key] then return states[key] end
  51.     local max = flow
  52.     for valve, steps in pairs(costs[curr]) do
  53.         local rem = tLeft - steps - 1
  54.         if rem <= 0 or bit.band(vis, bit.lshift(1, valveInd[valve])) ~= 0 then goto continue end
  55.         max = math.max(max, DFS(valve, rem, flow + valves[valve] * rem, bit.bxor(vis, bit.lshift(1, valveInd[valve])), states))
  56.         ::continue::
  57.     end
  58.     states[key] = max
  59.     return max
  60. end
  61.  
  62. print(DFS("AA", 30, 0, 0, {}))
  63. local b = bit.lshift(1, working) - 1
  64. local max = 0
  65. for i = 1, math.floor(b/2) do
  66.     max = math.max(max, DFS("AA", 26, 0, i, {}) + DFS("AA", 26, 0, b - i, {}))
  67. end
  68. print(max)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement