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

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

  • Profile pic
  • Profile pic

    Should remove the test case for (4, 1), since a divisor is guaranteed to exist.

  • Profile pic

    You need chars() to safely iterate UTF characters of a str. Strings are always UTF-8 encoded, so accessing the bytes directly would be problematic. The collect() at the end consumes the Iterator into a String.

    For better functional composition, a more flexible signature would be:

    fn no_space(x: impl IntoIterator<Item=char>) -> impl Iterator<Item=char>
    

    This way you could pass any iterable into the function (including str.chars()), and chain the function lazily, without allocating a String for output.

  • Profile pic

    Make sure you handle n = 0. size_t is unsigned, so i < n - 1 is true until i is size_t's max value.

    I suspect this solution is still too slow. The set u is size O(n); growing huge sets consumes time O(n log n) and is cache unfriendly.

    Think about how you could solve this kata linearly. That is, allocate a single vector with enough space to store U(m)[0] through U(m)[n], then fill each element in order. If you keep track of the right data along the way, you won't need to search through all previous elements, you can index directly into them.

  • Profile pic

    Thanks, I added random large tests!

  • Profile pic

    Instead of random tests, you could exhaustively test all 256 possible unsigned bytes.

  • Profile pic

    Great kata! It inspired me to create a more general version: N Linear. Instead of x * 2 + 1 and x * 3 + 1, the multipliers are a parameter.