AoC 2022 | Day 16 | Solutions & Spoilers

[celest idol]

with the cavitys

but it was not recursively done

:S?

[neon wind]

DFS you can do as a recursive function because you have a stack, or you can implement a stack yourself

because BFS needs a queue you have to implement the queue yourself

[mystic cedar]

or ocllections deque

[neon wind]

anyway, DFS is the way to go for d16 p1

[neon wind]

yeah I mean you have to define the queue

[mystic cedar]

ah

[neon wind]

so that is one way of doing it, there are others in Python std lib as well

[celest idol]

whats the "queue"

i dont know what that means

[neon wind]

so, you know what a queue is, right?

[celest idol]

no

[mystic cedar]

you have a queue of paths/nodes to check next

[neon wind]

a queue is like a list where you retrieve items from one end and append to the other end

[celest idol]

unless you mean literal translation of people standing behind each other ^^

[mystic cedar]

yea thats it

the first element you put in is the first to come out

[neon wind]

usually you wouldn't use an actual list though, because Python lists are bad at popping/appending from the beginning

so a deque is better, which has O(1) time complexity at either end because it's implemented as a doubly-linked list

that last part isn't important, but the key part is that you append items to one end and pop items from the other

^ going back to my diagram

you would start with a queue that looks like [A] - a one element queue

then, when you pop it off the queue, you look for all its neighbours and append to the queue

A's neighbours are B and C, so the queue looks like [B, C]

now let's say we pop from the left and append to the right

if we pop B from the left, its neighbours are D and E. And those get appended to the right of the queue
So it looks like [C, D, E]

Then you pop C from the left, and it's neighbours are F and G. And those get appended to the right of the queue

So [D, E, F, G]

and then those end nodes have no neighbours so as you go through all of those you'd deplete the queue

but the point is, you visit A, then B and C, then D E F G

the queue let's you visit all that is one away from the start, then all that is two away, and so on

hence why its "breadth-first" search

[celest idol]

hmm

but i thought the whole program with d16 is that you cannot do it

[neon wind]

yes, indeed

[celest idol]

because its too many permutations to traverse through

[neon wind]

BFS doesn't work

DFS does

and the key reason DFS does is because of the 30 min timer

maybe here is where you could have an aha moment

because you are going DFS, you are trying to go as deep into the graph as you can as quickly as you can

and so you can very quickly see if you are going to exhaust 30 mins for a particular path

and discard it, if you do

in this way you can limit the search space

[celest idol]

hmm not sure why aha moment missing

but if all nodes have many possible paths

and i can go 30 depths

for two tunnels each node

isnt that already like 2**30 permutations?

[neon wind]

oh, you can also cut down the number of tunnels

you really only care about the tunnels with valves

so formulate your graph to cut out the tunnels without valves and join up the tunnels with valves to have longer distances

[celest idol]

dont i need to traverse through the permutations first to see how many tunnels without valves lead to the valves to begin with?

[neon wind]

depends what you mean by traverse

as a first pass through the data you would need to traverse through the tunnels without valves

but you can create a graph with only valve tunnels before you even start simulating the pressure release paths

[celest idol]

i mean like here

get from A to N

ABDGILN

is possible

but also ABDFILN

[neon wind]

there are cycles in the graph

but when you do a BFS you can eliminate them

by figuring out the shortest path between any two valve tunnels

anything inbetween is irelevant

[celest idol]

oh so i need to do a BFS

to reduce my graph system

[neon wind]

for the initial parse

[celest idol]

?

[neon wind]

yes

[celest idol]

=(

so i start at A

i do BFS

and then i get all the minute-distances

from all relevant valve points

and then i do DFS brute force ?

[neon wind]

well, it's more than that (i think)

you'd want to do the BFS for each valve tunnel (plus AA) to every other valve tunnel

so, do the BFS x times, where x is the number of valve tunnels

shouldn't be a problem though, if you can do it once you can do it multiple times

[celest idol]

hmm

is the tunnels one directional?

i couldnt infer it from the text

[neon wind]

so the input is done in an unambiguous way

even if you took them to be one-directional, they work out so that everything is bi-directional

AA leads to DD and DD leads to AA

[celest idol]

oh i see

[neon wind]

however, if you start at AA and work out AA -> DD and AA -> CC and AA -> HH

[celest idol]

its written in the input text

[neon wind]

you still need to work out CC -> HH

[celest idol]

is it true

[neon wind]

which is why you need to do a BFS from all valve tunnels

[celest idol]

that if in the task 60 minutes are available

and like 30 rooms have valves

it would nto be optimizable?

*not

because u cannot reduce it enough?

[neon wind]

i think so

[celest idol]

except if you make assumptions

[neon wind]

not entirely sure

[celest idol]

like kill all valves

under threshold

and hope for best?

[neon wind]

seems about right though

for sure 30 minutes is set so you can get the perfect solution in a quick time here

[celest idol]

if you know what you are doing that is

how long did it take you to do part1+2 on this day?

[neon wind]

well yeah, but that's the case for all of them :)

It took me too long to do day 16 p1 because I didn't trust myself :)

[celest idol]

i dont know what im doing --> and did the early days easily

now its beoming tooo hard for me tho

minus today lol

[neon wind]

I, like you, though my solution would be nowhere near as performant as it needed to be. So I kept thinking about alt solutions even though I had the solution already from 16th

[neon wind]

as long as you are continuously learning, it's worth it

you shouldn't feel disheartened if you need some help with some days

[celest idol]

well if i tried day16 without getting input like this from you now

i would not get far because the site itself does not get hints

*give

not saying i can solve it now

but i at least have some idea how its doable

[neon wind]

right, but if you get hints from others and complete it, that's something new you have learned

[celest idol]

is what you described me

"floyd marshall algorithm"

[neon wind]

not a clue lol

[celest idol]

i read it in here somewhere

[neon wind]

I'm really not knowledgeable in specific algos other than the basics

[celest idol]

same

but you are right

i already learned alot

and learning by doing is the best kind of learning imo

[neon wind]

so looking up Floyd-Warshall, it looks like you could use that for the initial graph parsing to cut out the empty tunnels

BFS is fine though

all path lengths are 1 which makes BFS the easy choice, IMO

[celest idol]

ye i did not really understand it when i just read it

i have big problem reading comprehension in english

👎

[neon wind]

A lot of the graph-related algorithms will be difficult to read up and immediately understand

and most of the time the complicated ones are unnecessary anyway

[celest idol]

BFS so cool tho for example

[neon wind]

BFS is nice and easy to understand

given every length is distance 1 (which it is in the unmodified graph) it is guaranteed to give you the shortest path between two nodes

[celest idol]

yep but i mean more like

i can see bfs being useful

whereas this valve example is nice probably to know but i wouldnt know where id ever use it

at least at this point in time 😆

ill take a look into valve thing later when i am more comfortable in python ig

it seems like very hard to me right now even with your explanation

ty for that btw :P

[neon wind]

if nothing else you get good practice with recursion and queues and stacks

which is definitely a good thing

[celest idol]

ohhh

i was about to ask why BFS for each node as starting point - end point pair

but now when i think about it it make sense

lol

[celest idol]

ye recursion is my biggest problem

everytime i try something

it either works first time

or not at all

no matter how hard i look at it

[neon wind]

When it doesn't work at all, you need to debug and find out why :)

we have a test input

so you can know what you are looking for, and compare against what you should get

[celest idol]

yep that sounds easier than done for me tho

anyway ty alot for the in-"depth" explanation

[neon wind]

nice one haha

[celest idol]

ill use it for "depth"first search hehe

[neon wind]

badum tssh!

[regal trail]

Finally got to it late, but I got to it and I finished.
1.774549961090088 seconds part 1
1.2118897438049316 seconds part 2

But I'm not sure why part 1 is slower, sorted() should be slower than max(), I must have optimized something else somewhere.

Things I learned: networkx is fast at some things but accessing the data inside a graph can be terribly slow, so it can be better to pre-compute for instance a list of nodes where the valve rate is greater than zero and not yet turned on, if you're fancy enough you don't even need to modify the graph during nested search iterations...

[dense wasp]

Ah nice. What was your approach for part 2?

Question for anyone interested: Let's say the problem were flipped around, and instead of finding the optimum plan in the shorted amount of time, you instead have to devise the best plan possible within a time limit (assume the search space is too large to search for the optimum plan). What would be your strategy?

[regal trail]

I reasoned that I didn't need to build a new path planner to list off all possible paths, I just needed to select 2 paths from the list according to a different criteria from before. So instead of max() on a generator, I stored the results, sorted() those results, and iterated from the higher score end, this way when searching for possible elephant routes, I only had to iterate over the partition from my current route down to routes who's scores when combined with my possible route COULDN'T give a total higher than the best pair found so far.

To find compatible routes I precomputed sets of valves opened along the way, and if (my_valves & elephant_valves) was truthy rejected the pair.

Take 2 minutes to teach All the elephants to open valves/differentiate open/vs closed valves and tell them to run and get them all. 🙂

[worn kestrel]

yeah, I have been surviving aoc from his explanations, then I am like ""oOoh', i get it now

[vernal reef]

His take on aoc is so different than mine, I appreciate that he uses essentially no python specific libraries or even features, no comprehensions or lambdas, his code can almost be line for line translated into any language.

[sullen pagoda]

I have a solution that works but it's too slow, even for the example. I do depth-first search, but too slow. How could I improve it?

[mystic cedar]

what are your optimizations so far

[delicate ice]

ffs really ?

2 days, for that ?

because the 'AA' node wasn't the first on the input ?

*heavy sight*

[sullen pagoda]

@mystic cedar I didn't do any, I thought it would work fine. One idea that I didn't implement yet is to take out nodes whose flow rate is 0. This way the graph would be smaller. In this case the weight of edges could be higher than 1. I don't have any more optimization ideas.

I have a graph data structure and when I modify it, I make a deep copy of it during the depth-first search. I think it's also expensive but I don't know how to avoid it. I tried breadth-first search too but it ate up the memory.

[mystic cedar]

You only need to try and visit Valves > 0 that is super important and cuts down on possibilities massively. I don't think there is a way to avoid creating a copy of each path each iteration.
Once your algorithm works for the example you need to start optimizing:

1. Bigger valves should come earlier in general so reverse-sort first
2. keep track of your current best and find some kind of theoretical best for your remaining branches, if the theoretical best is lower than your current best, there should be no way to reach actual best and you can stop that branch

Theoretical best might be some compromise like, 1 valve opened every 2 steps. The closer you get to what the actual best of that path would be the faster you're gonna run.

[sullen pagoda]

Thanks! Is it a good idea to get rid of nodes with value 0? This way the graph would be smaller.

If a valve with value 0 connects exactly two other nodes, then it could be bridged IMO.

But then the distance between the bridged nodes would be 2.

[mystic cedar]

you only need to concern yourself with 2 questions: 1) in what order do i want to visit valves that actually produce output and 2) how long does it take to move between those

so you need an algorithm to find the shortest path between any two nodes

[dire haven]

some greedyish thing

that's what stuff like google hashcode boils down to

rather greedy optimization of some metric, with some clever insights

[viral cliff]

Damnit I was so close to it but this made it finally click. Thanks!

[regal trail]

I shoved the whole network into networkx then precomputed the best path routes between each pair of valves with non-zero pressure (and the start location), then calculate a path across that much reduced (fully connected, but weighted graph). I also tried storing valve state in the network at first but copying the network before writes turned out way too slow, and a tuple of opened valves as a paremeter to depth first search was sufficient. But a tuple of UNOPENED valves was even faster.

[mystic cedar]

good lord bfs is so much faster than dfs for this problem

old dfs solution 1 minute, new bfs solution 2 seconds

[halcyon loom]

@dense gorge i.e. if you open a pipe with flow 20 at minute 2, the total amount of flow should be 20 * (30 - 2) iirc

so there's no need to keep track of opened pipes 👍

[dense gorge]

hmm

right, that makes sense, i see

why does that mean i don't need to keep track of opened pipes though?

how exactly do i utilize that trick

[halcyon loom]

if you have an elephant at like pipe AA and you want to get to pipe like XX, you don't need to know what pipes it goes through, only how long it takes no?

and each of the XX pipes should be an unopened pipe

otherwise why are you going there

[dense gorge]

because you might be backtracking to get to a pipe you haven't opened yet?

[halcyon loom]

assuming flow rates of b/d are like 1 and a/c/e/f are 0 and you initially head towards pipe d

does it really matter what pipes you're going through

either DCAB or DEFB

regardless you're gonna need 3 minutes to head there 🤷‍♂️

same thing if you're backtracking

[dense gorge]

are we starting at A in this example?

[halcyon loom]

doesn't really matter where you start

if you're starting at A

it'll take 1 minute to head to b, 2 minutes to head to d

from b it takes 1 minute to head to a, 3 to head to d

from d it takes 2 minutes to head to a, 2 minutes to head to b

who cares what pipes you have to go through

[dense gorge]

hmm

[halcyon loom]

if you're just passing through pipes no need to care whether it's 1 million flow rate or 0

you're not gonna stop and open it

[dense gorge]

i suppose, but i'm failing to think of an approach that actually utilizes this idea

[halcyon loom]

ok assuming you have an elephant at like minute 16 whose heading towards pipe XX which takes like 5 minutes lets say

if the elephant at minute 16 is heading towards that pipe

then assuming you time travel earlier to like the person at minute 3

you don't need to go to pipe XX right?

or reverse that

assuming a person at minute 3 is heading towards pipe XX which takes 5 minutes

elephant at minute 16 doesn't need to head towards the pipe because it's opened right?

the current timesteps of the person/elephant don't have to be coupled together

the only thing each cares about is what pipes are unopened

i.e. which ones to head to

[dense gorge]

i sorta understand what you're saying

[halcyon loom]

ok assuming b/f/d each have a flow rate of 1 and you and the elephant both are in play and you both are starting at a

assuming elephant heads towards d and you head towards b

you'll arrive at b at timestep 2 and elephant will arrive at d at timestep 3

but then once u arrive at b and open the valve, you can then continue on to pipe f while the elephant is opening valve d

and then when the elephant finishes opening its valve, it sees there's no more pipes to open

so you can terminate the program

[dense gorge]

i suppose, but the question is how do I know where to send myself and the elephant. And what does this solution actually look like? am i representing this as a queue in a bfs implementation?

[halcyon loom]

well then just try out all the nodes 🤷‍♂️

it might take a bit but it'll be a lot faster than if you try to simulate timestep by timestep

you can probably priority queue based off of total flow rate or smth

really basic implementation could be finding the minimum timestep of whose done, and then iterating over each unopened pipe (and just not moving) and for each pipe just checking to see if you can make it there before the 28 mins are up, and if so removing it from the unopened pipe list and adding the amount of flow that pipe would give to the total amount of flow

[halcyon loom]

also another thing it doesn't really matter if you're going to b and the elephant going to d or you're going to d and the elepehant going to b

[dense gorge]

hmm

[upbeat mango]

also uh

||meet-in-the-middle||

is a viable strat for this problem

[dense gorge]

is that an alg? not sure i'm familiar

[upbeat mango]

so what i did was

it's optimal for you & the elephant

to open completely separate valves

so if you open A, B, and C

see how good the elephant can do, given that it doesn't care about those valves at all (basically 0)

possible w/ precalculation bfs & stuff

[dense gorge]

i feel like i'm too stupid for this problem

[halcyon loom]

time complexity of that vs just a naiive solution with unopened valves?

[amber totem]

Finally figured part 1 of this out, and now I'm stumped on part 2

[viral cliff]

I'm in a similar state. I can solve it for the sample input but it takes too long to run against the main input. But i'm making progress 🙂

[amber totem]

Futher along than me at least. I'm still trying to figure out how I want to approach this

[viral cliff]

I'm trying something like this: https://www.youtube.com/watch?v=DgqkVDr1WX8

But having implementing it isn't goign well which suggests I don't really understand the solution :/

[mystic cedar]

i think there are two ways, you either write a copy of the algorithm which incorporates more states dealing with the elephant as well, or reusing the p1 solution and pre-splitting the valves

[viral cliff]

Aaaah pre-splitting the valves makes sense, I'ma try that, thanks

[amber totem]

What do you mean by pre-splitting the valves?

[viral cliff]

Like say player 0 will only attempt to open the first 4 flow-yielding valves, and the elephant will only attempt the latter 4, then sum the result of both for that guess. Then try again for every permutation of dividing the useful valves between the two players

I'm currently working on making a generator that will iterate through those permutations, I think I've figured it out, but not quite sure

(well actually I'm cleaning up from Christmas dinner, but I'm thinking about it for when I'm done :p)

[amber totem]

Ah, so just brute force it?

[mystic cedar]

basically yea, you'll only have to do the combinations for length 1 to n//2 since anything more will only repeat the same but mirrored

and when your solution takes 2-3 seconds that makes something like 1-2 minutes

[neon wind]

For day 16, I initially had a recursive solution. I only used BFS for ditching nodes with no flow rate cos who cares about that?

I had no idea wtf floyd warshall was so I didn't use that

[celest idol]

yes i mean thats what you toldme

reduce node with BFS

and then apply DFS recursively

to obtain solution

[neon wind]

yup

well, I tried to rework my DFS so that I could cache it

which I did

and my solution time did not change by any big margin lol

[celest idol]

if you dont mind when i reached day19 i would like to ping you maybe for a Tom-Marvolo-Fiddle type of explanation for it

xd

[neon wind]

Lol no worries :)

I can chat in day 19 now if you want?

[celest idol]

sure if you have time

i am free rn

[neon wind]

I have unit tests for day 16 that basically never end. I didn't realise I was running them in the background and it consumed all my RAM

16GB swallowed

only noticed it when my PC started slowing down

[dire haven]

I never reduced things by computing all distances

no clue if that would make it a lot faster

[viral cliff]

lol thats how I knew my day 12 solution was retracing it's steps too

[rustic smelt]

Well my solution seems to just run forever.... I think I need to eliminate some paths rather than "try every path"

Im trying using dfs and it looks like this: ```py
def dfs_best_path(location, data, remaining_time, open_valves=[]):
    print("At", location, "with", remaining_time, "time left")
    if remaining_time <= 0:
        return 0

route_value = 0
    if location not in open_valves:
        if (x := get_valve_flowrate(location, data)) != 0:
            valve_value = get_valve_value(x, remaining_time)
            route_value += valve_value
            open_valves.append(location)
            remaining_time -= 1

sub_routes = []
    for n in get_valve_neighbors(location, data):
        sub_routes.append(dfs_best_path(n, data, remaining_time - 1, open_valves))

return route_value + max(sub_routes)

Essentially I have three stages, the first checks if time has run out and then returns 0 as the path has 0 value. Next I check if the valve should be opened (always open a valve, except if it is 0 or already open), then finally I go down each of the sub routes recursively and check which has the highest score.

I feel like this isnt quite right...

[mystic cedar]

Think about some upper bounds and try to cut off branches that are essentially the same but worse

      don't bother with this branch anymore```