6 kyu
Count the photos!
666 of 1,381billgewrgoulas
Loading description...
Algorithms
Performance
Arrays
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Done Rust translation, please approve: https://www.codewars.com/kumite/650f00c4b838490012d37b5c?sel=650f00c4b838490012d37b5c
Approved
This one was so hard for being a yellow kata you have no idea, because it's all about dynamic programming and optimizing, so I'd rank it up, really funny, yet more complex than challenging.
Very cool kata, thanks so much!
Language : C++
There is a problem with 1 (and only 1) of the fixed tests in the
Hidden Test Cases:This test case ends with the chars
')- i.e. chars which are not><or.- this was probably an accident while pasting the string from another language version where strings are terminated with'.I don't think it's deliberate/intended to be a test case for input validation (invalid chars) because such tests don't appear in the other language I have solved (Python) and isn't mentioned in Description.
Fixed!, Thanks for your help!
No worries; and my apologies - I rudely forgot to say thanks for the nice kata before raising the Issue, so thanks!
This was fun. Thanks!
Almost timed out but did it... Nice kata.
Lua translation!
Thanks for the translation!
Thanks for the approval!
This comment has been hidden.
Hello. you have a nested for loop so that makes the complexity of your function O(n^2). Try to iterate over the string once or twice and think what you need to calculate during each step.
This comment has been hidden.
At each iteration, you search something in the whole list: your code isn't
O(n), it isO(n²).The method
.countis O(n) itself, so when it is inside a loop, that makes itO(n*n)==O(n^2)time complexity. The only subtle hint I could give is to avoid nested loops. Even if you loop the list 3 times, it can still be O(n).Hi - to answer your question, even though you only have 1 "visible"
forloop, you are actually performing a lot more "loops" inside your code:The
.count(".")function, each time you call it, is looping through the entire list (or at least a significant fraction of the list => all the elements after indexchar_list[i:]) which means that your solution is closer to beingO( n * n)because for each of thenelements in theforloop, you are then doing anotherapprox ~ noperations each time you use thecountmethod.You're very close to a faster solution though, so I won't spoil too much - think about what you do and do not need to calculate at each step of your for loop.
2 small issues with Python translation:
function name should be in snake_case
count_photos. Only 8 solutions in Python so far if you want to change this quickly.some of the fixed tests have invalid characters, presumably from copy-pasting:
I will past a copy of a link to this post in a reply to the Python translator @macambira
Nice, and thanks again/obrigado for the translation!
C++ translation, followed python random test case generation https://www.codewars.com/kumite/631bb49b585a390024989834
nice! Thanks
has been approved
My solution is proven to work and works quick in PyCharm but here it times out after 12 seconds with failed tests(?) Running the failed tests in PyCharm does not provide the same result as given here. Not quite sure how I could speed it up anymore or how to not make it fail tests that work fine in another IDE.
Yeah, generating is being a weird bottleneck (somehow using numpy is slower in this environment?!?), so I changed the random tests to make its time similar to the time i got from JS, so maybe now you can? It depends on how good is the performance of your solution.
hmm i think your solution is not O(n) thats why its failing the big tests...
Hi @Dmillenaar and welcome to Codewars;
Since you are new I just wanted to clarify something, in case that's what is causing the difference between your IDE and Codewars:
When you click "Test" on any kata, your code is tested against the (small, few in number) tests visible in the bottom right of the kata environment. In this kata, these are the
SAMPLESthat are approximately 6-7 in number, with small input strings. These are designed to be "easy" tests, to check your code logic etc.When you click "Attempt" you will then encounter the full set of kata tests which can be very large.
If you are only copying the "small tests" into your IDE, then that is why you are timing out here and not in your IDE.
If you want to recreate the size of the full kata tests to see the performance of your code in your own IDE, then randomly generate a string of length
5000000consisting of>, <, and .and see how long it takes on your PC.In JavaScript, the biggest test case in the full test suite has
11000000tiles, so it must be a linear (O(n)) algorithm. (other languages should have similar sizes)Thank you BenjaminZWhite for the detailed explanation, I now have all tests fully working with your comment but I guess I need to look into speeding up things.
Python translation
@macambira Please see my Issue post, with 2x small issues with Python translation, raised above:
https://www.codewars.com/kata/6319dba6d6e2160015a842ed/discuss/python#631bcf7c0b9cb00120ed1543
Cheers and thanks for translating
C Translation
This kumite shows that tests are too strict.
That solution is strictly
O(n), but iterates twice instead of once ( "O(2n)", which isO(n)). But it times out -- unlike the solution it is based on, which iterates once.If you require
O(n), the constant factor should, within reason, not matter. I don't think this approach is unreasonable. Use fewer, bigger, tests to test performance.are u sure? My JS solution is also 2n and passes easily :)
that solution is not exactly O(2n). I tested it on my machine and compared to the optimal which requires 1 pass its around 7-8 times slower.
Technically, the O(2n) notation is the same as O(n). Nonetheless, even if your algorithm is already O(n), it must be optimized further to iterate through the string only once.
The whole point is that failing an
O(n)solution means micro-optimisations are required. I know myreduceis slower than myfor .. ofby a constant factor.Iterating the input twice does not make a solution not
O(n). Usingreducedoes not make a solution notO(n).Requiring micro-optimisations is not the way to test performance. Any
O(n)( again, within reason wrt the constant factor ) should pass.This comment has been hidden.
To complete the task it's preferrable to run over the array only once (or twice if impossible) without array mutations. Otherwise you won't complete similar tasks
This comment has been hidden.
@billgewrgoulas I'll approve as 6kyu. Is that ok for you?
Yes its fine. Thanks!
Done!
This comment has been hidden.
Hi,
Cheers
More than 2 seconds difference 😅
Thank you for your advice. I will try to change it :)
push to an array then join
yep i did just that
.