@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 😅.

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.

Solved

It's not a kata issue.

Fixed.

As far as I know "expected" and "actual" are switched in the PHP test cases. That means, that the test cases expect 'rovwsoiv' (which is indeed the correct encryption), while you provide it with 'acosaecs'.
I have seen this issue in multiple katas so far, it might be an issue of PHPtest, but i can't say that for sure.

The number will always be a positive integer greater than 0.