That's true. But then I'd have to do -1 in 3 places. And my two < would become <=.

Assigning is slightly faster than pushing (~20%). Either way is fine though.

I did some measurements on my machine and put the values into this chart: https://codepen.io/andrewmaxwell88/full/YzGGExw
It would appear that my solution is roughly O(n log(n)) and without memoization is O(n^2). Do I need to edit my kata to specify the time complexity?

I agree with Johan. And I also did not neet to add anything to my solution to handle "no paths". A grid with an area > 0 would have at solution with length >= 1, and a grid with area zero would always have a solution of length 0. I concede that it is entirely possible if I had thought of the problem differently and come up with a different algorithm, it would likely affect my opinion on this matter.

Do I have to specify a time complexity? For me, part of the fun of more difficult katas is finding that my solution is too slow and I need to come up with a faster algorithm. If the tests need to be different for different languages due to CW constraints, so be it.

But the current performance requirements apparently force micro-optimisation as well as appropriate Big-O complexity.

Do I have any micro-optimizations in my solution? I purposely tried not to. I bet I could cut my runtime in half by switching to for-loops, but I opted to use map/filter/reduce instead because I think it makes the code a lot cleaner.

It sounds like I have a lot to learn here.

1. I don't know much about Haskell. Why is it so much slower than JS? Isn't it compiled?
2. I'm not sure how to calculate the runtime complexity of this kata. I assume it's more than O(n) and possibly less than O(n^2) where n is the size of the input. Any ideas?
3. If I were to specify a runtime complexity in my kata, how would I go about enforcing it?

I realize these are probably noob questions, but this is my first kata after all.
Thank you for your help and contribution to the kata!

Thank you for the suggestions! I have improved the memoization of my solution, rewritten the description, and added your suggested random tests. I also changed the estimated kyu to 3.

Thanks, I have added tests for these 4 cases.

That's true! Thank you for taking the time to show me that, I really appreciate that!

XRFXLP, you caught that fast! I realized I forgot something while I was taking a walk and I hoped no one would notice before I could fix it. I have updated the kata. If the issue persists, please post or send me the input and your output so I can figure out what's going on. This is more difficult than I had expected. My admiration for all of you kata contributors is through the roof!

Thank you for pointing that out! I have updated the kata to include "In the event of a tie, return the path that comes first alphabetically.". Thank you again!

I am new to writing katas, thank you for your feedback. I had mistakenly thought it would be sufficient to generate random tests and paste the results into my tests. I have updated the tests to generate new random tests every time it is run.

I am new to writing katas, so thank you for your feedback. I have added "Your solution must work on 50 tests with up to 25 rows and 25 columns within the time limit." to the end of the kata description. Do you think that adequately conveys the performance requirements?