Earn extra honor and gain new allies!
Honor is earned for each new codewarrior who joins.
Learn more
  • Profile pic

    The expected results is provided...

    ...no it isn't. How did this Kata get out of beta when the description isn't even complete?

  • Profile pic

    So I think it's about 9--10 big tests in JS and 4--5 big test in Ruby (including random) for about any reasonable O(n) to pass.

  • Profile pic

    Is this Rust-specific, or would you say this applies to JS as well?

    I'd say it should be a default assumption for allocating memory dynamically in general in any language. I don't know much about memory allocators; obviously, it's extra work to do at each iteration, but I'd guess that with reference counting it's probably the same block of memory each time because it's freed by the next iteration, but with garbage collection it has to find a new free block every time and then collect all that garbage.

  • Profile pic

    @JohanWiltink:

    the tests seem limited to m = 4 so that's practically a constant.

    The description was misleading, I clarified it. The intention of "Tests use large m," was to test high values in m, not a large set size.

    I specifically included large values in m, because they can cause overflow problems. My first naive Rust solution panicked on large m values.

    Testing large m set size does not seem necessary.

    I think requiring such extreme performance is overdoing it just a little - that seems to come with 3 kyu and "implement advanced requirements in a scalable fashion".

    My intention is to allow any O(n) solution, and deny the naive solution which repeatedly scans further and further back into the sequence. Balancing the correct amount of tests to achieve this can be difficult, especially when execution time varies based on server load and language version.

  • 18171520?v=3

    allocating memory in a loop isn't the best idea in general

    Is this Rust-specific, or would you say this applies to JS as well?

    I don't really see the problem, its scope is explicitly limited to the current iteration of the loop, and it would be entirely possible to allocate the memory once, outside of the loop, and reuse it on every iteration, but I'd actually consider that a worse idea than what it's doing now.

  • Profile pic

    I guess it's up to the author... The first JS solution runs in less than 6 s in Rust, even though allocating memory in a loop isn't the best idea in general, so it might be reasonable to decrease the number of big number tests in JS. (Same for the Ruby translation too, it's even slower than JS.)

  • 18171520?v=3

    I left my first attempt in, so you can see the differences.

    It's all just in the constant factor of O(Cn). Therefore, I think my first attempt could have passed, because constant factors should not be prohibitive for big-O performance. Mine was about 2 times too slow; allow for a bit more leeway in C, also, as mentioned, if O(n) performance is desired instead of O(mn), test with bigger values of m but smaller values of n. The description hints at this, but doesn't follow up with tests.

    It really comes down to the intent of the kata. Which may be a deeper question than author initially asked himself ( I've been there - there's no shame in that ). But it's out there now.

    Given its 4 kyu ranking, I think requiring such extreme performance is overdoing it just a little - that seems to come with 3 kyu and "implement advanced requirements in a scalable fashion". For 4, required performance could be on the correct order of magnitude, but not necessarily the correct absolute magnitude. But I'm reading quite a lot into the ranking explanations here, I'm aware of that.

  • Profile pic

    @JohanWiltink IDK what the intent is, but what is the solution that you think should pass? JS tests are the same as in Rust; my optimized solution in JS is about 25% slower than in Rust (approx. 5500 ms vs 4500 ms), but I just translated an existing solution, so I'm not sure what intermediate stages could be when solving it in JS.

  • 4537539?v=4

    I'm agree this kata is difficult for 4 kuy, but my first translation with easier tests wasn't approved, sorry.

  • 18171520?v=3

    I think the JS tests may be just a little over the top ( and I really mean just a little ).

    My first attempt was 2 times too slow. Not any order of magnitude, though it was O(mn) and not O(n), but the tests seem limited to m = 4 so that's practically a constant.

    If that's the intent of the kata, fine. But if the intent of the kata is just to require O(mn) performance, consider scaling back the tests just the above-mentioned little. Also, if not just O(mn) is required but actually O(n), consider scaling up the tests with some longer ms.

    This comment is probably directed as much at the original author as at the translator; author guidance may apply to other languages as well.

  • 38586565?v=4

    Hello! Can someone approve my Ruby translation or give advice on what needs changing? I think my tests might be a bit too lenient, but I'm not certain.

  • 18171520?v=3

    Apparently all tests didn't pass before the time-out. Not a kata issue then. Closing.

  • 4537539?v=4

    Thank you very much!

  • Profile pic

    JS translation approved.

  • Profile pic
  • Loading more items...