Unable to load image

day 16 aoc thread: the np is complete

this is travelling salesmen, eh? i'm pretty sure at least.

14
Jump in the discussion.

No email address required.

Have a solution that works for the test case in p1, but not sure if it works with the real data or just take a bit.

The idea is basically a depth first search and some memoization to store path we have already tried.

Jump in the discussion.

No email address required.

idk if that will work well. they could add weird cases were half going into a branch and later completing it is the best solution.

if you look at the dataset, u can notice there's a lot of rate=0s. i'm thinking maybe turning this into a simplified graph that just represents all distances between all valves with r>0, turning this into almost a raw traveling salesmen.

at that point u just brute force dfs it cause there's no simpler solution possible. at max cost=30, it's not a big issue i don't think.

unless u can solve np. in which case, i'm so down for revolutionizing cs in the process. :marseyparty2:

Jump in the discussion.

No email address required.

My solution actually works fast now, the issue was that the hashmap I used for memo used a shitty hash function, my results are still wrong, but I believe that is due to me entering the input wrong. Had to do other things though so couldn't test it properly so far.

But the other issues is that you can visit the same node multiple times, you can just not turn the valve more than once. This massively increase the amount of possible routes, which forces you into some kind memo solution.

Jump in the discussion.

No email address required.

i don't think u can use memoizing to significantly speed up an np-complete problem into not something np, not without inadvertently missing parts. that's kind of why they are np-complete. ur also going to be unbelievably fricked by part 2

my answer to p1 takes < 60ms in js of all things.

Jump in the discussion.

No email address required.

my answer to p1 takes < 60ms in js of all things.

Are you on the leaderboard?

I'm confused by several people who apparently solved part 1 by simply running DFS on a reduced graph. It still has 15 nodes (plus technically a separate starting node but that doesn't matter), so if you enumerate all possible routes, without pruning the search somehow, that's 15! ~= 10^12 of them, which you can't do in any reasonable amount of time. So how does your code work?

Myself, I did this: you can do dynamic programming using (current node, set of opened valves) and implied current turn as a key. That is, if you know that you can open valve #5 at turn 10 while having opened valves 3 and 7 already, with a maximum score of whatever, then you can ignore how you got to that state. And if you have a priority queue keyed by current turn and steadily work through it, then that's your correct DP computation order (though I somehow convinced myself that I need some extra complications). So now instead of 15! I'm traversing a graph with 15 * 2^15 nodes (plus some spread of future current turns in the queue).

Jump in the discussion.

No email address required.

15! ~= 10^12

u can't actually enumerate out that many cause of the max cost. if you jump across the map and back - it will be very few nodes you enumerate out. if they removed max cost then i suppose it wouldn't be feasible.

So now instead of 15! I'm traversing a graph with 15 * 2^15 nodes (plus some spread of future current turns in the queue).

i'm prolly gunna have to do the dynamic approach cause p2 with plain recursion is kinda nonsense.

Jump in the discussion.

No email address required.

Oh, I see. Hmmm. Interesting.

Note how I did part 2 in 15 minutes which might be a hint in itself :marseysmug2:

Jump in the discussion.

No email address required.

Link copied to clipboard
Action successful!
Error, please refresh the page and try again.