commit b1b2109acbcd8b3b5231655aab9b73c7396e593a
parent 322415223efdef2e6ea97254c2b5cf1539c45677
Author: aabacchus <ben@bvnf.space>
Date: Sat, 17 Dec 2022 01:58:24 +0000
22.16.1 in Lua
Diffstat:
| A | 2022/16/d.lua | | | 149 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/16/example | | | 10 | ++++++++++ |
| A | 2022/16/input | | | 55 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 files changed, 214 insertions(+), 0 deletions(-)
diff --git a/2022/16/d.lua b/2022/16/d.lua
@@ -0,0 +1,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)
diff --git a/2022/16/example b/2022/16/example
@@ -0,0 +1,10 @@
+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
diff --git a/2022/16/input b/2022/16/input
@@ -0,0 +1,55 @@
+Valve NA has flow rate=0; tunnels lead to valves MU, PH
+Valve NW has flow rate=0; tunnels lead to valves KB, MH
+Valve MR has flow rate=0; tunnels lead to valves GC, FI
+Valve XD has flow rate=0; tunnels lead to valves UN, CN
+Valve HK has flow rate=0; tunnels lead to valves AA, IF
+Valve JL has flow rate=0; tunnels lead to valves IF, WB
+Valve RQ has flow rate=13; tunnels lead to valves BL, DJ
+Valve AB has flow rate=0; tunnels lead to valves BO, RU
+Valve PE has flow rate=0; tunnels lead to valves AZ, IF
+Valve QF has flow rate=0; tunnels lead to valves TD, AZ
+Valve BA has flow rate=0; tunnels lead to valves RF, GU
+Valve SY has flow rate=0; tunnels lead to valves MH, MU
+Valve NT has flow rate=0; tunnels lead to valves DJ, UN
+Valve GU has flow rate=21; tunnels lead to valves VJ, BA, YP
+Valve AZ has flow rate=12; tunnels lead to valves QF, PI, AS, PE
+Valve WQ has flow rate=23; tunnels lead to valves VJ, UM, CN
+Valve DR has flow rate=0; tunnels lead to valves GA, CQ
+Valve UM has flow rate=0; tunnels lead to valves IE, WQ
+Valve XI has flow rate=0; tunnels lead to valves IE, IF
+Valve SS has flow rate=0; tunnels lead to valves CQ, MH
+Valve IE has flow rate=22; tunnels lead to valves YP, UM, XI, XA
+Valve BT has flow rate=24; tunnels lead to valves KB, BL, GA
+Valve GA has flow rate=0; tunnels lead to valves DR, BT
+Valve AR has flow rate=0; tunnels lead to valves IF, FI
+Valve DJ has flow rate=0; tunnels lead to valves RQ, NT
+Valve PI has flow rate=0; tunnels lead to valves FI, AZ
+Valve WB has flow rate=0; tunnels lead to valves TD, JL
+Valve OQ has flow rate=0; tunnels lead to valves ME, TD
+Valve RU has flow rate=19; tunnel leads to valve AB
+Valve IF has flow rate=7; tunnels lead to valves AR, JL, HK, PE, XI
+Valve BO has flow rate=0; tunnels lead to valves ME, AB
+Valve CN has flow rate=0; tunnels lead to valves WQ, XD
+Valve HH has flow rate=0; tunnels lead to valves AA, FS
+Valve AS has flow rate=0; tunnels lead to valves AA, AZ
+Valve FS has flow rate=0; tunnels lead to valves HH, MH
+Valve PQ has flow rate=0; tunnels lead to valves TD, AA
+Valve AA has flow rate=0; tunnels lead to valves HH, CO, AS, HK, PQ
+Valve ME has flow rate=18; tunnels lead to valves OQ, BO, PH
+Valve RF has flow rate=0; tunnels lead to valves UN, BA
+Valve MH has flow rate=8; tunnels lead to valves FS, NW, SS, SY
+Valve YP has flow rate=0; tunnels lead to valves IE, GU
+Valve FI has flow rate=11; tunnels lead to valves PI, MR, AR, CO, DI
+Valve UU has flow rate=0; tunnels lead to valves CQ, MU
+Valve CO has flow rate=0; tunnels lead to valves AA, FI
+Valve TD has flow rate=16; tunnels lead to valves QF, GC, OQ, WB, PQ
+Valve MU has flow rate=15; tunnels lead to valves SY, UU, NA
+Valve BL has flow rate=0; tunnels lead to valves BT, RQ
+Valve PH has flow rate=0; tunnels lead to valves ME, NA
+Valve XA has flow rate=0; tunnels lead to valves IE, DI
+Valve GC has flow rate=0; tunnels lead to valves TD, MR
+Valve KB has flow rate=0; tunnels lead to valves BT, NW
+Valve DI has flow rate=0; tunnels lead to valves XA, FI
+Valve CQ has flow rate=9; tunnels lead to valves UU, DR, SS
+Valve VJ has flow rate=0; tunnels lead to valves WQ, GU
+Valve UN has flow rate=20; tunnels lead to valves NT, XD, RF
