ShareMyScreen/AdventOfCode/2022/16/ProboscideaVolcanium
This is a terrifying problem. A graph-maximization problem, but I have to find the absolutely best answer, which means I have to try all the possibilities. I peek at my problem data and my terror grows. There seem to be 50 valves! Just turning each one on or not would take 250 trials. What will I do?
On these big problems the strategies are:
- reduce the number of options at each turn
- prune the search tree by cutting off branches that can't hold the solution
- try the best alternatives first
- after each move see if it is impossible for the position to lead to a best solution
Cutoff is usually where the big gain is, but it's easier to trim the search. I'll start with trimming.
Looking again, I see two interesting features in my puzzle data:
- 30 of the valves have flow 0 and don't need to be turned on
- most of the valves lead to just one other valve, forming a chain of valves with no options
But no, that last bit isn't right. You could have a valuable valve in the middle of a long chain, and it could be right to go just far enough to pick up that valve and then turn around and come back. But I can certainly combine sequential valves of flow 0 into a single node of the graph. That says that I should represent the connectivity by having each valve connect only to valves that have nonzero flow, giving the amount of time it takes to reach that valve.
For that matter, there's no reason for the problem to contain any valves with 0 flow. I can tear them out and replace them with connections between valves with nonzero flow. That will replace one branching node with an increased branching factor at its neighbors. Is that a good trade? Yes it is, because it will give each node a direct pointer/distance to its neighbors, which will allow it to order its alternatives better.
In fact, I can make this simplification to the graph as the solution proceeds: when I turn on a valve I will tear its node out of the problem. Of course I'll have to remember what I did so that I can patch the valve back in when I backtrack.
I'm seeing only 6 nodes with branching factors of 5 so if I can hold the number of evaluations to some multiple of 65 it will be OK. I am hoping that the 30-minute cutoff will help stop the search.
I am ready to read in the data. When I finish I will have
- flows - the flow of each valve
- nbrs - for each neighbor, a box containing a table, each row of which is (neighbor,distance). To start with the distances will be 1.
I will sort the names so that I know the starting node comes first.
require 'strings'
oneline =: {{ NB. y is a line for a valve, result is valvename;flow;list of boxed valvenames
name =. 2 {. 'Valve ' takeafter y NB. 2-character name
flow =. 0 ". ';' taketo '=' takeafter y NB. Integer flow rate
neigh =. _4 <@(2&{.)\ ' ' takeafter 'valve' takeafter y NB. boxed list of neighbors
name;flow;<neigh
}}
]lines =. /:~ oneline onaoclines
+--+--+----------+
|AA|0 |+--+--+--+|
| | ||DD|II|BB||
| | |+--+--+--+|
+--+--+----------+
|BB|13|+--+--+ |
| | ||CC|AA| |
| | |+--+--+ |
+--+--+----------+
...
Because of the way x ; y is defined I had to box the last thing in the result of oneline because it was already boxed. Now I will extract flows and nbrs, giving the initial distance of 1:
]flows =: > 1{"1 lines
0 13 2 20 3 0 0 22 0 21
]nbrs =. ,.&1&.> ({."1 lines)&i.&.> {:"1 lines
+---+---+---+---+---+---+---+---+---+---+
|3 1|2 1|3 1|2 1|5 1|4 1|5 1|6 1|0 1|8 1|
|8 1|0 1|1 1|0 1|3 1|6 1|7 1| |9 1| |
|1 1| | |4 1| | | | | | |
+---+---+---+---+---+---+---+---+---+---+
I still have an uneasy feeling about this. At each valve I will have to try opening the valve and then moving, but also moving without opening the valve, because if the valve has a small flow the time might be more valuable than the flow. Are there times when I can be sure that I should open the valve? I can think of two:
- when the valve has the highest flow among all unopened valves
- when the valve was a one-valve cul-de-sac. In that case if I don't open the valve the move to it was certainly wasted. (I see that there are several such valves in my puzzle data and this will change their branching factor from 2 to 1).
There is still the possibility of unproductive thrashing as the solution tries not-opening one valve after another and eventually runs out of time in each branch after many tries. Cutoff would help that. I can certainly implement a simple improvement: I won't move back to a valve v if no valve has been opened since the last time I visited v. Actually I can do better: I won't even visit a valve if I could have visited it earlier and have opened no valves since. That will reduce the thrashing; whether enough, I don't know.
I guess it's time for typing. I start a script.
best =: 0 NB. the final result: the best total flow found
nmoves =: 0
NB. emulate the passage of time
time =: {{ NB. x is clock,(flow from opened valves),(total flow so far) y is duration result is new clock,flow,total (or _1 _1 _1 to call for exit)
'clock flow total' =. x NB. extract current state
total =. total + flow * y =. y <. 30 - clock NB. limit duration to the end of the simulation period; add to total flow
clock =. clock + y NB. advance the clock
if. cutoff res =. clock,flow,total do. _1 _1 _1 return. end. NB. check for cutoff; if so, abort
res
}}
NB. check for termination, whether early or not
cutoff =: {{ NB. y is clock,(flow from opened valves),(total flow so far) result is 1 if branch should be pruned. Updates best if branch completes
'clock flow total' =. y NB. extract current state
best =: total >. best NB. immediately update best total so it can prune other branches
clock = 30 NB. the only pruning is when time expires
}}
NB. move to a new cell.
move =: {{ NB. x is clock,(flow from opened valves),(total flow so far) y is (new valve,duration,1 to force opening);(list of valves visited since most recent opening)
'ddata excl' =. y NB. extract destination, force-opening, valves excluded from nonopening move
'valve delay fopen' =. ddata NB. extract move and force-open flag
'clock flow total' =. x time delay NB. extract current state and account for move delay
if. clock < 0 do. i. 0 0 return. end. NB. if branch ended, return
vflow =. valve { flows NB. get the flow of the valve we have moved to
if. vflow = >./ flows do. fopen =. 1 end. NB. if we are standing at the largest flow, always open it
dests =. valve {:: nbrs NB. extract list of neighbors
destsc =. dests ,. 01 = (dvalves =. {."1 dests) #@{::"0 _ nbrs NB. before we change the topology, see if each move is to a cul-de-sac (valves with only 1 nbr, which must be this valve)
NB. first case: open the valve we are on and take it out of the connections
if. vflow do. NB. special case of 1st node which might have no flow: don't open
mparms =. (0,vflow,0) + (clock,flow,total) time 1 NB. delay 1 minute for valve-opening delay, and increase the flow for subsequent moves
if. 0 > {. mparms do. i. 0 0 return. end. NB. if branch ended, return
restore =. vacate valve NB. remove the valve from the connection list
flows =: 0 valve} flows NB. once the valve has been opened, there is no gain to be had from it
for_d. destsc do. mparms move d;dvalves end. NB. try each move; don't allow a non-opener to go to anywhere we could have moved to directly
flows =: vflow valve} flows NB. undo the valve opening: restore flows...
nbrs =: (1{::restore) (0{::restore)} nbrs NB. ...and connections
else. vacate valve NB. valve has no flow. remove the valve from the connection list permanently
end.
NB. second case: don't open the valve
if. -. fopen do.
mparms =. clock,flow,total [ excl =. excl , valve [ destsc =. destsc #~ -. dvalves e. excl NB. remove excluded dests, append this valve to excluded list
for_d. destsc do. mparms move d;excl end. NB. apply exclusion
end.
i. 0 0
}}
NB. tear a valve out of the connections
vacate =: {{ NB. y is valve number to vacate; result is (indexes on nbrs that changed);(previous values)
'dvalve ddist' =. |: y {:: nbrs NB. indexes of valves to change, and distance from this valve to there
oldconns =. dvalve { nbrs NB. save the old connections for restoration
newconns =. dvalve ,."1 +/~ ddist NB. Each row gives connections to add to corresponding box of nbrs
newconns =. y (00 ,.~ 2 $"0 i.#dvalve)} newconns NB. diagonals are reflexive and must be removed; change the dest to y, which also must be removed
newconns =. newconns <@((, <./)/../@:|:@:, >)"2 0 oldconns NB. append new to old and take minimum of duplicate paths
newconns =. y ((~: {."1) # ])&.> newconns NB. remove the now-dead link to y
nbrs =: newconns dvalve} nbrs NB. Install the new connections. Leave y, as it is now orphaned
dvalve;<oldconns NB. return info to restore what we did
}}
Time to test. To save time I will forcibly vacate cells where the flow is 0, except for the starting cell which must remain so I can move to it initially.
vacate"0 I. 0 (0}) 0 = flows 0 0 0 move 0 0 0;$0 NB. initial move: clock,flow,total=0, move to cell 0 with delay 0 and no forced opening; empty exclusion list
The moment of truth...
best 1458
...or of failure. 1651 was expected. Hung be the heavens with black. All I know is that the answer is wrong, with no information available for troubleshooting. I look at flows and nbrs which should have been restored to their initial values, and indeed they were. This is a Scott of the Antarctic moment. I am just going outside and I may be some time...
I have to fix it. But it seemed so right. I was worried that the program might run too long, not that it would be wrong. Should I roll up my sleeves and start tracing and adding debug typeout, or think about what might be wrong? In such situations I always rush headlong into thought.
I'm sure I don't visit a valve twice. It must be that I am discarding a path improperly: that one of my time-saving tricks was overeager.
After a few minutes I haven't seen anything. This is going to require my ultimate debugging measure: I'll sleep on it.
When I wake up I realize that I did make a mistake. When there are no more moves to make, the branch ends immediately and prematurely. It should stay active until the 30 seconds are up. That will be easy to fix. I will simply check for that case and call move right after I have opened the valve with the line
if. 0 = #dests do. i. 0 0 [ mparms time 30-clock return. end. NB. If we are opening the last valve, run out the clock and exit
Another moment of truth...
0 0 0 move 0 0 0;$0 NB. initial move: clock,flow,total=0, move to cell 0 with delay 0 and no forced opening; empty exclusion list best 1651
...with success this time. Now I try my full puzzle data.
After a minute I run jbreak to interrupt it. Rats. I will have to prune the tree.
Pruning doesn't have to be perfect. Most of the branches are making bad decisions early and wallowing around in the middle of the solution space. I'll order the alternatives so that each list of neighbors goes to the valve with the highest flow
nbrs =: (\: flows {~ {."1)&.> nbrs
(I also put a similar line into vacate so that the tunnels stay ordered after a valve is vacated.)
I will try a very simple cutoff first. I will cut off if the flow established so far will not beat the best total to date even if I immediately turn on the biggest valve, then the next-biggest, and so on, till all valves are turned on. The fastest I could turn on the valves is one every other turn.
This will create a schedule of maximum improvement for each number of cycles left that will not change unless a valve is opened. This suggests that I compute the schedule only when a valve is opened.
NB. prep for cutoff: called after any valve opened, after connections & flows have been updated
NB. returns previous value
cutoffprep =: {{ NB. y is clock
NB. max you could get is highest for 2 clocks, then top-2-highest etc
(cutoffvec =: +/\ 2 # +/\ (<. -: 31 - y) {. \:~ flows) ] cutoffvec NB. calculate new value and return old
}}
cutoff will use the cutoffvec calculated in cutoffprep.
NB. check for termination, whether early or not
cutoff =: {{ NB. y is clock,(flow from opened valves),(total flow so far) result is 1 if branch should be pruned. Updates best if branch completes
'clock flow total' =. y NB. extract current state
if. best >: total + (flow&* + {&cutoffvec) 30 - clock do. 1 return. end. NB. get max total if we continue flow and open valves quickly; prune if too small
best =: best >. total NB. update best-so-far
clock = 30 NB. also prune when time expires
}}
All that remains is to call cutoffprep when a valve is opened. I do this immediately before & after the moves from the opened valve:
... restorecutoff =. cutoffprep clock NB. establish new cutoff profile for_d. destsc do. mparms move d;dvalves end. NB. try each move; don't allow a non-opener to go to anywhere we could have moved to directly cutoffvec =: restorecutoff NB. Restore cutoff profile ...
Full of hope, I try the new version. It completes in about a second, and with the correct answer.
In Part 2, I have to train an elephant as a helper and the two of us will roam the tunnels simultaneously. That changes my view of the problem:
- there will be 2 positions/times/exclusion lists
- the valve state will become a global value
- the times for the players must be kept as close together as possible to make cutoff more effective
Can I still simplify the connections by vacating rooms as I turn valves off? Yes, that will still work because vacating a room leaves its tunnel connections unchanged. If I vacate a room while the elephant is in it no harm will be done.
I am going to rewrite the whole program (except vacate which is unchanged). It will be an easy rewrite since the structure is unchanged. Now that I know the cutoff scheme is effective, I type happily.
best =: 0 NB. the final result: the best total flow found
openedflowtoend =: 0 NB. total flow contributed at end-of-problem by valves in 'opened'
MAXTIME =: 26 NB. number of cycles to run
cutoffvec =: (MAXTIME+1)$1e6 NB. cumulative max flow possible for each cycle
opened =: MAXTIME$0 NB. valves opened for each minute
NB. emulate the passage of time in the first player
time =: {{ NB. x is list of clock times y is duration result is new times (or empty to call for exit)
if. cutoff x =. (MAXTIME <. y + {. x) 0} x do. '' return. end. NB. check for cutoff; if so, abort
x
}}
NB. restore to position before cutoffprep. y is value returned from cutoffprep
cutoffrestore =: {{ 'openedflowtoend cutoffvec' =: y }}
NB. prep for cutoff: called after any valve opened, after connections & flows have been updated
NB. returns previous value
cutoffprep =: {{ NB. y is clock times
res =. openedflowtoend;cutoffvec NB. previous state
NB. max you could get is highest 2 for 2 clocks, then top-2-highest etc
openedflowtoend =: +/ +/\ opened NB. total contributed at end by opened valves
cutoffvec =: +/\ 2 # +/\ _2 +/\ ((MAXTIME+1) - <./ y) {. \:~ flows NB. max flow available from opening 2 valves every other cycle
if. best < openedflowtoend do. bestopened =: opened end.
best =: best >. openedflowtoend NB. extrapolated flow is legit - this way we don't have to mark time till MAXTIME
res
}}
NB. check for termination, whether early or not
cutoff =: {{ NB. y is clock times result is 1 if branch should be pruned. Updates best if branch completes
if. best >: openedflowtoend + (MAXTIME-<./y) { cutoffvec do. 1 return. end. NB. cut off is possible
MAXTIME = <./ y NB. if time not up, keep looking. best was updated when the valve was opened
}}
NB. move to a new cell. The move is made at the head of all lists
move =: {{ NB. x is (clock times; locations; exclusion lists) y is (new location,transit time)
'moveto delay' =. y NB. extract move, delay
'clock locs excls' =. x NB. extract current state
if. '' -: clock =. clock time delay do. i. 0 0 return. end. NB. Update clock, cut off if possible
locs =. moveto 0} locs NB. move to new position
NB. To keep the clocks close together, make the move in the earliest clock
earlyx =. (i. <./) clock
clock =. earlyx |. clock [ locs =. earlyx |. locs [ excls =. earlyx |. excls NB. Now we will make move in the head
if. ({.clock) >: MAXTIME-1 do. i. 0 0 return. end. NB. if there's not enough time for earliest player to open a valve, cut off
valve =. {. locs NB. the valve we are at
vflow =. valve { flows NB. get the flow of the valve we have moved to
allownoopen =. vflow < >./ flows NB. if we are standing at the largest flow, always open it
dests =. valve {:: nbrs NB. extract list of neighbors
NB. first case: open the valve we are on and take it out of the connections
if. vflow do. NB. special case of 1st node which might have no flow: don't open
if. '' -: oclock =. clock time 1 do. i. 0 0 return. end. NB. delay 1 minute for valve-opening delay, possibly cutting off
NB. Open the valve and save all restorable state
otime =. {. oclock NB. cycle when valve starts running
rc =. cutoffprep oclock [ rv =. vacate valve [ flows =: 0 valve} flows [ opened =: (vflow + ro =. otime { opened) otime} opened
NB. move to this valve with 0 delay to move to other valves; clear exclusion list for this player
(oclock;locs;<((<i. 0 2)) 0} excls) move valve,00
NB. restore state before valve opening
cutoffrestore rc [ flows =: vflow valve} flows [ nbrs =: (1{::rv) (0{::rv)} nbrs [ opened =: ro otime} opened
elseif. 0 = >./ clock do. vacate valve NB. if valve has no flow, it has been vacated - except for room AA where we start
end.
NB. second case: don't open the valve
if. allownoopen do.
NB. Create list of excluded dests and the times at which they become excluded - nodes that earlier paths will visit
extimes =. extimes , MAXTIME [ 'exdests extimes' =. |: 0 {:: excls NB. append high time for 'not found'
NB. add to the exclusions this valve and any other valve we can reach, for use by descendants
excls =. (< (, <./)/../ |: (valve,0) ,~ (dests +"1 (0,{. clock)) , 0 {:: excls) 0} excls NB. keep only the earliest exclusion
mparms =. clock;locs;<excls NB. parms for loop
for_d. dests do. if. (({.clock) + 1{d) < extimes {~ exdests i. {.d do. mparms move d end. end. NB. apply exclusion
end.
NB. after we have exhausted our possibilities, set our time to max and let the others finish
((MAXTIME 0} clock);locs;<excls) move valve,0
i. 0 0
}}
NB. tear a valve out of the connections
vacate =: {{ NB. y is valve number to vacate; result is (indexes on nbrs that changed);(previous values)
'dvalve ddist' =. |: y {:: nbrs NB. indexes of valves to change, and distance from this valve to there
oldconns =. dvalve { nbrs NB. save the old connections for restoration
newconns =. dvalve ,."1 +/~ ddist NB. Each row gives connections to add to corresponding box of nbrs
newconns =. y (00 ,.~ 2 $"0 i.#dvalve)} newconns NB. diagonals are reflexive and must be removed; change the dest to y, which also must be removed
newconns =. newconns <@((, <./)/../@:|:@:, >)"2 0 oldconns NB. append new to old and take minimum of duplicate paths
newconns =. y ((~: {."1) # ])&.> newconns NB. remove the now-dead links to y/reflexive
newconns =. (\: flows {~ {."1)&.> newconns NB. order largest values first
nbrs =: newconns dvalve} nbrs NB. Install the new connections. Leave y, as it is now orphaned
dvalve;<oldconns NB. return info to restore what we did
}}
After fixing a bug (the next-to-last line in move was omitted), it works. The program runs for a couple of minutes: I guess alternating between the two players gives a much deeper region where thrashing can occur. I'm not going to look into it any more, though.
This was an interesting problem.
Revision
After sleeping on it another night I realize that I had another bug. I reasoned that if A, B, and C are mutually connected and I am moving from A to B without opening A's valve, I can put C onto the exclusion list, meaning that C must not be visited until a valve has been opened. The justification was that A could have moved to C quicker directly than by going to B first. That is true when all tunnels have delay 1, but after some vacating the delays have increased. It might be that A to C directly takes 3 minutes, but A to B and B to C each 1 minute so I must keep C alive.
That is easy to fix, by making the list of excluded nodes into a table of nodes, each with a time at which it should become excluded. Visiting the node before that time is still allowed. This change is included in the part-2 version above.