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.

part 1 optimized code

About 1.1s runtime on input, which is tremendous compared to early iterations of the code.

What I do is shortcut paths that take zero-flow nodes, prune those zero-flow nodes (all but AA), compute floyd-warshall and replace the actual graph by this one, which basically skips having to go to already activated nodes or travel through useless nodes. Also replaced my queue BFS with a recursive DFS since most of the BFS was spent inserting into the queue (like 89% lmao). Removed the useless dict to skip identical situations (happened literally only once ever).

![](/images/1671304521390218.webp)

Jump in the discussion.

No email address required.

Okay here's part 2. Tried a global variable approach because doing shit with recursion is usually painful, but ended up with very slow code and a result with 200k+ paths. Did it the recursive way and only 113 paths to search lmao.

I am officially unfiltered

![](/images/16713082009308453.webp)

Jump in the discussion.

No email address required.

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