5 kyu

Prime Ant - Performance Version

106anter69
Description
Loading description...
Performance
Algorithms
View
AllIssues1QuestionsSuggestions2Show Resolved
  • Please sign in or sign up to leave a comment.
  • udovr Avatar

    Here I thought I was gonna be a 'smart' cookie by doing quick jumps to queued positions, to make it faster. (the distance can be up to tens or hundreds of "steps" from the lowest position)

    My solution passes 1 out of 5 times, depending on the inputs.

    Think i'll skip the "insane" version, looking at the other solutions i feel a python noob hahaha.

    Great Kata though!

  • dfhwze Avatar

    I don't understand this kata. Perhaps a couple of sample tests with very low values of n to see what we need to return wouldn't hurt. I don't know whether we should return the full sequence A (for 1e6 items) sliced with the corresponding p for n or the sequence at the time we reach n during generation of the seqence.

    • dfhwze Avatar

      I managed to solve it, but I still think in the sample tests there should be a couple of startup tests with low value of n

  • augustjdl Avatar

    This comment has been hidden.

  • GGor Avatar

    Should I try to finde a mathematical logic in the final result's list and than apply the formula or should I optimise my algorithme?

  • Blind4Basics Avatar

    your python version test isn't explainative enough:

    # make sure it's python 3
from sys import version
test.assert_equals(version[0], '3')

=> '2' should equal '3'

    How the user is supposed to understand what the problem is? ;)

    => needs an update of the message. Note that you could put a f-string somewhere, and that would restrict the language versions to 3.6 directly "at the kata level".

    cheers

    • anter69 Avatar

      I updated the error message, although it seems that 2.7 is not available in the kata, so it may not even be necessary.

      Cheers

      Issue marked resolved by anter69 6 years ago
  • lechevalier Avatar

    The tests may be too tight now, nearly CW-charge dependent. I tried 15 times with my first version, but it finally pass the tests. I already used a sieve and a cache made no difference: still hard to validate a solution. If your purpose is only to invite players to use cache and sieve, may I suggest to lower test requirements? Otherwise, if you want them to make more tricky tweaks, it is fine - but it would be better if you warn players at the end of the description ;-)

    • anter69 Avatar

      As you can read below, earlier I had a problem with too few tests, so "naive" solutions could pass. So I raised the number of tests to make people think a bit. Some of the valid solutions are still "naive" in a way, but they use the right kind of optimization. After all, I planned to make this a performance kata, where you have to consider using e.g. a list vs. a set, or caching some (partial) results, etc. Isn't that optimization?

      My reference solution (puzzled from multiple solutions) runs the final tests in about 10000ms (on average), which leaves - I think - a large enough margin for other solutions. But that also means that you won't necessarily succedd with your first try... Probably the ranking should be rather 4kyu instead of 5, to give a hint? But I can't change it :-)

    • anter69 Avatar

      This comment has been hidden.

    • lechevalier Avatar

      This comment has been hidden.

    • anter69 Avatar

      I removed the precalculation timer -- now let me see that solution! :-)

    • anter69 Avatar

      Hold your horses! -- I will rather make a "crazy" version of the kata, where you have to do 1000+ tests with big enough numbers :-) And probably change this one a bit too, to have only one HUGE test, instead of many...

    • lechevalier Avatar

      Good idea!

    • Blind4Basics Avatar

      Hi,

      maybe you should relax a bit more the tests, don't you think? Look at my solution: it mostly applies what you wanted to get, tho it passed only by chance (11,7s) this morning while it was failing around 254 passed tests yesterday. I guess it's because I append the elements rather than create a whole list right at the beginning, so that sounds a bit too much like an enforced microptimization to me. What's your opinion?

      Note: confirmed: when I change that part of the code, I get around 9,5s.

    • Blind4Basics Avatar

      additionnal note: the current top solution is timing out like hell, whatever I try, btw. ;o

    • anter69 Avatar

      Reduced the number of tests by 20% (to 200 + 20). I hope this solves the timeout problems while still excluding the naive solutions.

      Cheers

      Suggestion marked resolved by anter69 6 years ago
  • Bubbler Avatar

    This comment has been hidden.

  • stefanie.sulzer Avatar

    Could you open up the Beta to JavaScript? Python's on the docket, but I'm not there yet.

    • anter69 Avatar

      I'm not sure I understand you correctly, but I cannot provide a JS version, until somebody translates it.