Expecting the worst for part 2...

https://gitlab.com/maximoburrito/advent2022/-/blob/main/src/day16/main.clj So ugly. I really struggled for a good representation. I was surprised that part1 worked at a reasonable speed, but it did. For part 2 I brute force extended the solution, but it was too slow. Because it's getting late, I capped the number of positions i consider one the search frontier got large. I got the right answer, but I really need to revisit this tomorrow and use a smarter strategy... Ideas to improve • can I actually filter out paths that can't possibly exceed the best solution? It's easy to compute the minimum score at the end for the best node and to compute the maximum score for the other nodes • can I filter out the zero nodes and simplify the graph before starting? • can part one be re-used, maybe computing everything you can reach in 26 minutes and intelligently combining them?

Apparently this is stumping lots of people.... This was the first time I got in the top 1000.

Since only a fraction of the valves have flow, you can precompute the distance between each pair and only consider those when branching

And another easy way to prune the space in part2 is - when both you and the elephant can go to the same 2 valves, only checks the cheapest option e.g. if at some moment you can go to valve A with cost 3 and B with cost 5 And the elephant can go to A with cost 4 and B with cost 2 then only you->A, elephant->B should considered as the total cost is 3+2 as opposed to 5+4 for the inverse. And the end states are equivalent, one player on each of the valves

A humble visualization. It helped me to solve the problem. (made with graphviz).

@U067R559Q I did the same, (though I learned about :circo from you). Here’s the before/after graph of my cave after “shrinking”

today was hard for me, ended up with some sort of A* on working valves https://github.com/nbardiuk/adventofcode/blob/master/2022/src/day16.clj

p2 sample and input times

"Elapsed time: 19.593426 msecs"
"Elapsed time: 25420.249547 msecs"

@U051HUZLD are you me? 😄 I had the exact same 1705 instead of 1707. In my case I had a typo that was causing the last move to fail.

Starting on the second part now, and feeling lucky I abstracted the search mechanism into a small higher order function… but I’m not done yet …

So as far as I could tell this is a traveling salesman problem preceded by a bfs shortest path problem.

Still waiting to find the optimal solution …. for the real data in part 2

finally got part 1! https://github.com/FelipeCortez/advent-of-code/blob/master/2022/16.clj

It’s a toughie! https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day16/sol.clj

part 2 “Elapsed time: 163016.040392 msecs”

https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2022/16.clj I'm a day behind now but I really enjoyed this one. got to https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/search.clj#L50-L65 part 2 takes <2s

Eventually figured it out. Part 2 is so slow... https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2022/day16.clj

Oh man, part 2 kicked my butt, first time since 2020 that I didn't get it within the 24 hours of release. Eventually got it but took ~25 seconds for part-2 https://github.com/alexalemi/advent/blob/main/2022/clojure/p16.clj

Ugh. I caved after >24 hours and went with a Python solution. Now I'm trying to convert it to Clojure and I'm getting a StackOverflowError. Probably going to give up and prep for day 18.

I am really happy with the solution, using dynamic programming and considering Part 2 in a special way: https://github.com/volesen/aoc2022/blob/main/day16/day16.clj

Now solved it programmatically https://github.com/zelark/AoC-2022/blob/master/src/zelark/aoc_2022/day_16.clj