6 kyu
Back and forth then Reverse!
1,134 of 1,854RNOH
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.
javascript
I tried so hard but i can not speed up my algo. It always
Execution Timed Out (12000 ms)
Ruby translation
Approved by someone
Nice!
vv nice kata 100%
CoffeeScript translation
Approved!
This comment has been hidden.
s.reverse()ands.pop(0)has to go through the entire list, which is very slow.Good kata. But it is easy for 6 kyu. I surprised when I saw people who take time error.
It was much easier than I thought at first.
My code fails the time test. Could you check if it's a code breach or server load?
Server is fine, your code is too slow.
I redid it without revers, the same result. Not sure what is taking so long
Do it without slice ;)
Nice kata!
This comment has been hidden.
Try find a solution where you don't have to actually physically reverse the list, but rather just treat the list as if it is reversed, if that makes sense. Reversing a list a lot will slow a solution way down.
Ok this makes sense instead of doing a reverse function, switching the ordering of what gets pushed in the array first/second.
I'm still timing out.
Factor translation
approved!
It doesn't seem to be?
Edit: I went ahead and approved it since I think you must have forgot :P
oh wait it wasn't?, thats weird :/
Even with slices and virtual sequences the code does time out. Isn't that too strict on the potential solutions?
The kata is intended as a performance kata, and it isn't overly strict. I think your solution just doesnt have the expected time complexity.
For comparison, Python has 6 "Big" tests, Factor has 8. If I reduce this to only 1 "Big" test, your solution still times out.
Could you help me with a hint, i can't pass 'Big size' condition in Attempt i write code for this condition 'size of S goes up to 10^6' lenght has to be less then 10^6 but unfortunately it doesnt work i dont know how to solve this problem
Таже проблема. В этом то и сложность этого кода. Нужно максимально его оптимизировать чтоб блина списка в 10**6 могла быстро решится. Сам думаю над решением ;)
You don't have to worry about the size of the input (don't need to test if the length of the list is less than 1M).
The problem is that your solution takes a time that is proportional to the length of the list squared. It means that if the input is 3 times as big, your solution will run 9 (3x3) times longer. The goal of this kata is to find a way to code a solution that takes a time proportional to the length of the argument.
With big words, your solution currently runs in O(n^2) and you have to make it run in O(n).
is it due to a loop that's causing the O(n^2) ? do i have to make it O(n) ?
Please review and approve, thanks !
Approved! thanks! :)
JS translation
Done!
D translation
Approved!
NASM translation
Approved!
Impossible in Rust since the stack overflows once the Vector gets too big (1.5MB) and dynamically sized arrays/slices aren't supported.
9 users solved it in Rust already
You cause the buffer overflow by printing the inputs.
This comment has been hidden.
It seems indeed the tests in Python should be redesigned to stop as soon as bad answer is given (or to exclude logs for larger tests), because if they continue no matter what, the data of the last bunch of tests overflows the buffer. I see no solution from user side :/
ohh okay, thanks for the answer
C Translation
approved
Go translation
Approved, thanks! :)
Rust translation
approuvé
I got here searching for python katas with the "esoteric languages" tag, but this kata isn't an esolang task. Suggest removing that tag. Nice kata besides that :)
.
The description is misleading since it states first Remove the first and last element from the list S and add them to the list T and eventually Don't mutate the input. It should be reworded.
You're right, changes have been made.
I have the following test result (test2): [4, 2] should equal [4, 2, 3]. No more information. Test 4 is the same pattern: [] should equal [1]. As well test 3: [9, 1, 5, 7, -2, 6, -3, 8] should equal [9, 1, 5, 7, -2, 6, -3, 8, 5]. There is always one number added at the end of the list. There is no connection to the instructions to me. There is nothing about, that an additional number should be added at one point. This number seems to me is coming out of the blue. Could you please give a hint?
your result array is one less than the input array. you have the add the last remaining character of the array to the output array when the length of the input array is odd.
why can't we mutate the input? I tested the code outside of codewars and it worked fine, but I get errors for all the results based on the tests.
This comment has been hidden.
So you are doing s = ... The idea is that you dont mutate the input, which will be one of the errors you will get with this while code testing. I think you would likely also timeout with the [::-1] reverse method?
I'm getting the 'don't mutate the input' error for pretty much all the tests. I don't understand what that is testing for. Can you explain that please?
well, that means you're currently "mutating the input" while you shouldn't... ;)
=> don't use pop/insert/append, or stuff like that. A bit of googling might help too.
Dont change s (the input list)
.... but the instructions tell us to remove them : "Remove the first and last element from the list S" so in my opinion the instructions are not clear
I agree with the comment about the instructions being unclear but will accept the challenge to not use pop - as that was part of my solution. Thanks for feedback everyone.
uh, I specifically added a note about mutation of the input when I approved the kata but the author lost some changes when he added his BF version.
@RNOH: I corrected the description, adding language specific blocks
Yes i saw thanks!
Nice kata - thanks for this. A good emphasis on time complexity for this one. My first solution was really simple but obviously no good for very large lists. My second one was faster, but only just scraped it with like 10000 ms haha, nice to see the other solutions though.
This comment has been hidden.
You may want to read on the topic of 'Time Complexities' in code (Also search for 'Big O notation'). The tests in this kata are so large that you pretty much need to have an algorithm that is O(n) - which means it looks at each element of the original list only once.
To do even one single
reverserequires looking at each element once, so if you use it even a couple times, your algorithm is probably too slow.pop()is nice and fast, but taking elements from the front (pop(0)) means that all other elements have to be moved up one index, so it is also O(n). There are clever ways around this, but I won't tell you what they are. (Google might be your friend. You are looking for 'constant time operations')This comment has been hidden.
Of course, that was corrected here with my new code version. But had I not put a copy of
sindthe error would come, even though the explanatory text misleadingly says so to empty the S list.Yes, there's clearly a contradiction between the instructions and the test.
Nice kata!
Thanks a lot!
This comment has been hidden.
This comment has been hidden.
how? (you won't get much there, i believe) numpy?
This comment has been hidden.
This kata will test your code on some very large inputs. You need to have a solution which works very fast for it to work. using
s.reverse()(and some other things in your solution) is very slow.(Also, please don't post your code without marking it as a spoiler)
This is also not a kata issue. If you have problems you need to mark them as Question
m=s.pop() IndexError: pop from empty list
it shows this type of error. only test case 5 solved run correctly. What to do ?
print the input or look at the code of the tests cases, to see what case your code is failing
where can I see test cases?
I like this algo-concept as it is relatively basic and because of that there's bound to be many different interesting ways to approach it.
I like the Kata, but you're only testing that the generated list
Tis populated correctly, not that listSis empty. Also, my very naive solution passed so efficency is not requuired currentlyI believe the point of this kata is not to test whether S is empty or not. It is to test the filling of T, so point 1 is not a suggestion.
it is (a suggestion).
Thanks a lot for approving!
This comment has been hidden.
note: 'asking more info about this. I'm not sure about the time complexity of this operation
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
.
Hi,
Issue part:
Suggestion part:
cheers
ohh yes will look into it!. thanks.
I think its resolved now.