@hexolio as to the Math.hypot thing - pesky implementation details. If I had to guess it's because Math.hypot is variadic and handles a bunch of stuff we don't really care about, like infinities. Calculating the L2 norm "by hand" avoids the overhead of all that. I'd initially thought that it was the function call itself which was slowing things down but interestingly calling Math.sqrt was quite a bit faster than using x**.5 - presume there's special logic for square roots due to how common they are. Fascinating stuff.

As to your Python performance issue I'd suggest it's because without Cython or JIT, Python is just really bloody slow compared to JS. I have a feeling you could vectorise the Python solution to bring it up to speed (e.g. Numpy matrix math replacing the loops) but that's more work than I can commit to so you'll have to try yourself if you want it. Plus, I'm getting a bit weary about how much specialist optimisation knowledge we're expecting from submitters.

You're definitely on the right path.

In my first reply to you (that was hidden as a spoiler), I explained why the tests take so long even if you just submit a function that returns immediately. It's because the reference solution needs to calculate the answers for each of the random tests, regardless of what your function returns. That was what was taking 6 seconds before. But with the help of RileyHunter, we optimized the reference solution so that now it only takes about 0.75 seconds for 15,000 islands (!). That means you have more than 11 seconds to work with now, so make the most of it 😅.

@RileyHunter is correct, since I haven't finished the kata there are no partial spoilers for me. Thank you for breaking up the comment for me, that's very helpful information.

Update: Your solution was so fast that it takes less than a second to calculate 15,000 islands. I think it's fair now to increase the limit to that, since everyone will still have 11 seconds to play with, lol.

I implemented exactly the same reference solution in Python, but it's still not fast enough to go above 5000 islands. What gives?

That's weird about the Math.hypot thing — using math.dist in Python speeds it up considerably.

Thank you very much for the optimized solution. Using that as the random test solver will leave the vast majority of the time to the user's solution. Now I just need to do a similar thing in Python...

Giving hints and suggestions that aren't code isn't usually an issue, especially when the implementation is non-trivial.

I don't know – I've had comments marked as spoilers simply for mentioning the phrase "minimum spanning tree" 🤨

(Also I believe stormhaul cannot see the spoiler'd comments at all because they have yet to finish the kata)

Hint 1: This is not a Travelling Salesman Problem; a Travelling Salesman computes a Hamiltonian cycle through the graph, but this problem doesn't actually need a cycle, just what we call a "spanning tree".

Hint 2: Although algorithmic complexity is critical, it's not the only limiting factor. I can write a near-optimal solution which only solves 3k islands in the time limit and I can write a provably not-optimal one that solves 45k. Pay close attention to the performance of your code from a language perspective, not just an algorithms perspective.

@hexolio the spoiler tag is specifically to prevent sharing code that solves (or helps solve) the problem:

You should mark any comment as a spoiler if it contains code within it that might give the solution away to other users.

Giving hints and suggestions that aren't code isn't usually an issue, especially when the implementation is non-trivial.

I also think taking up half the compute time with the reference solution isn't great. I've got an implementation which solves the current problem set in about 5% of the time; I'll share it below.

It's not a strong spoiler – it doesn't tell you what kind of problem it is, but what kind of problem it's not. And it's at the bottom of the comment, clearly marked, so you can avoid it if you want to.

People here tend to be pretty strict about marking comments as spoilers if they contain any slight clue, so I thought I'd err on the side of caution. Unfortunately there's no way (that I know of) to mark only part of a comment as a spoiler.

While I appreciate the rapid reply, it's very frustrating to have the comment be hidden as if I wanted to "spoil" I could just see the solutions and immediately understand what I'm missing xD

Yeah, I agree the maximum tests should be slightly lower, but not by that much. The more islands in the calculation, the bigger effect changing the number of islands has on the calculation time (because of the time complexity of the algorithms). I've changed the Python and JS versions from 5000 and 10,000 to 4500 and 9000 respectively. That seems to leave enough breathing room for variations. The JS reference solution, for example, takes around 9 seconds now.

I'm confused. This looks like a TSP problem, however the javascript tests take > 6 seconds to run when all the function does is return immediately. That implies in order to successfully solve the kata I would need an O(n) efficiency approximation within 1e-9 accuracy of a TSP problem and there is no such algorithm. Not sure what I'm doing wrong.

explicit is better than implicit.

what is this magic? :D

Solved