4 kyu
Twice linear
579 of 23,728g964
Loading description...
Mathematics
Algorithms
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.
Function name in OCaml should be
snake_caseFixed. I also increased the OCaml performance requirements.
helps to use excel to expand out the recursive formula to understand it. the description is not the best
very good
This comment has been hidden.
Serious question. Why do you skip x = 2? If you're supposed to fill the list with u(x) for x = 0 to infinity, then it should be [1, 3, 4, 5, 7, 10, 9, 13, 11, 16, 19...]. The test n = 10 list has no "5" element which means u(2) was skipped. Am I wrong? What's happening here?
xis not the index. The description gives a recursive formation rule to calculate new terms from existing terms. The only given term is1. All resulting terms should be ordered ascendingly and the term at then-th position in this ordered sequence isu(n).You cannot create a
2with this rule so neitherxnoryis ever2.Test in C with n = 7375 is ok on my side and takes approx. 2 seconds.
Since my laptop isn't a fancy one (Intel® Core™ i5-8250U CPU @ 1.60GHz × 8), are there more CPU consuming tests after that one ?
In C, there is 100 tests with
nchoosen randomly between 5k and 100k.This comment has been hidden.
Same is mine solution - in bash it takes 5s on my VM box, and fails test with time>12000. Sad (
This comment has been hidden.
Please don't post solution code in the discourse without the spoiler flag.
My bad, I'm sorry, haven't thought much before posting
I don't think your solution is O(n). It uses
Array.appendwhich creates a copy of the input array, which is O(n) already. Enclosed in an O(n) recursion, your solution seems to be more line O(n^2).I will go back to the drawing board now that I've cooled of a bit
You're right. I have switched to a queue. This way is is O(1)
Fixed it by using a queue. Now runs within 50ms
I understood the statement that this is what you are looking for, but I have doubts as to how many numbers the list should have where the numbers are going to be added. In the example provided, dbl_linear(10) the parameter is 10 and u = [1 , 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...] and I see that 10 + 1 positions were produced in the list, is the statement correct? excuse my english
I didnt get it, even AI couldnt get it
I can't find the reason to why this kata is took so much efforts from me to solve. I cannot explain how satisfied I am after solving this afterwards.
This comment has been hidden.
if you mean that you sort repeatedly, then that ought to be bit of a red flag
it may be helpful to do this with pen and paper, the human brain tends to optimize tasks it carries out
Resolved - not a suggestion for kata
This comment has been hidden.
You don't need to compute ahead that way. Even so, I'm able to tweak your code to pass. I don't think it SHOULD pass though - with all the repeated sorting/set conversion, and the magic number you have there. As part of my modification, I set it to 600_000. Maybe it doesn't need to be quite as high but uhm. Probably not much lower either. Unless of course you were to hard-code that specific test which is the only one with a large n. I wouldn't call that cheating but I wouldn't call it solving it either.
This comment has been hidden.
we are supposed to crete an array u which has the mentioned sequence in ascending order. for the return part, given input is an index and its supposed to return the element from that index in the array. This is my understanding. I'm able to run my solution in difference compiler (programmiz) and get correct output for all the mentioned tests, however it's getting timed out here
Excellent kata! Had a lot of fun optimizing the solution!
proper assertion messages for C
Approved !
do i have to sort the u table?
yes
This comment has been hidden.
This comment has been hidden.
Because it's an old kata, published in 2015. Standards have changed in the meantime and now the new katas are voted with lower ranks by power users. However, ranks can't be changed, so even if a similar kata is published today as 6/7 kyu, you can't come back and re-rank an already approved kata. This is why older katas are ranked higher and new katas are ranked lower and it can happen that a 6 kyu published this year may seem more difficult than a very old 4 kyu kata. You can sort the katas you solve by oldest/newest. :P Hope it makes sense. :)
yeah,it makes sense. but man how did you get 1 kyu? I've recently started coding. Can you help ma and give some advises
by solving kata's
Wow, it was like insight when I find my solution
I mean I half solved it, but it times out whenever I submit it to the hella large numbers. Not sure where else to go from here in terms of efficiency.. tried shaving down the length of the sequence that I'm generating but that wasn't enough. Iono :/
after 3-4 hours of time out using python, I finally did it. I never feel so refresh like this.In the end I can beat this kata!!!
100th element should be 471 though test expects 447. I dont understand. If algorithm was wrong earlier values would be wrong too. Here is my output for u(100). Can someone tell me whats the problem? Thanks 1,3,4,7,9,10,13,15,19,21,22,27,28,31,39,40,43,45,46,55,57,58,63,64,67,79,81,82,85,87,91,93,94,111,115,117,118,121,127,129,130,135,136,139,159,163,165,166,171,172,175,183,187,189,190,193,202,223,231,235,237,238,243,244,247,255,256,259,261,262,271,273,274,279,280,283,319,327,331,333,334,343,345,346,351,352,355,364,367,375,379,381,382,387,388,391,405,406,409,418,471,475,477,478,487,489,490,495,496,499,511,513,514,517,519,523,525,526,543,547,549,550,559,561,562,567,568,571,580,607,706,711,712,715,729,730,733,742,759,763,765,766,769,775,777,778,783,784,787,811,813,814,819,820,823,837,838,841,850,1066,1093,1135,1137,1138,1143,1144,1147,1161,1162,1165,1174,1215,1216,1219,1228,1255,1701,1702,1705,1714,1741,1822,2551
Hey @devheptagon - I don't use C# so I can't see your solution, but I can confirm the tests are correct - 447 is indeed the
u(100)value.I compared your list of 100 values to mine and the first 99 values do in fact seem correct, so I don't know why exactly this error is appearing for
u(100).However, you can tell that your own solution is wrong somehow just by looking at its results: your own solution above contains the value
223(after202and before231) - so if your algorithm includes223it should also include2 * 223 + 1 = 447. Yet447doesn't appear in your result.So I would start by looking there for hints on what to debug. You are also missing the value
463 = 2 * 231 + 1before471if that helps you debug as well (note that231appears in your current list but463does not).edit - you are also missing lots of numbers between
607and706- there are12missing values there that your solution is not producing at the moment, so indeed it seems like your approach is incorrect somehow for larger values.447 is the correct value.
Please check why 183,187,189 in your list and you will find the answer.
This comment has been hidden.
Interesting kata. The way the numbers are generated is very important and should be clarified. It seems like the expectation is that the x's, y's, and z's are expected to be generated n times. If you generate them more than that, you'll have too many numbers in your set and your answer will be wrong (even if the nth index). If fewer, you'll have the same problem.
This is also quite challenging to debug due to the lack of feedback. It's easier to debug the small numbers, but larger numbers (e.g. in the thousands) are hard to tell what's going wrong if you get the wrong answer. I think a lot of errors are going to likely be based on the aforementioned assumptions. If you're working on this, the kata expects you to generate x, y, and z exactly n times.
This comment has been hidden.
Hi, and welcome to Codewars!
I'm looking at the Tests for this kata in Python and I think I understand your problem: there is a test with the expected result of
447but the corresponding input value isn = 100and notn = 471as you think.This is a common mistake on Codewars, because of the Error message in Python - I am guessing you see on your screen:
"Expected 471 to equal 447" ? Something like this?
In the above sentence, the value 471 is what your code is currently returning, not the input value.
If you want to see the input value for each test, you can add a
print(n)statement to your code - this will display the value ofnin each test in the console output - as I said, I am guessing you will find that the test you are failing on is corresponding ton = 100.You can also read this page for more such advice:
https://docs.codewars.com/training/troubleshooting/
Hope that helps
Thank you, benjaminzwhite. I was stupid on this. It's clear now. And thank you for the idea of add a print(n). I didn't dare. I thought it would generate an error. :D
Check why 183,187,189 are in your list and you will get the answer.
The tests in c++ version are written horribly. How should I debug my solution, if no output to cout or cerr is getting actually written in test reports? I mean, I can debug it in my terminal and vim, but that kinda defeats the whole purpose of the web-site. Pls, fix
I tried your solution and I get: "Expected: equal to 22 Actual: 16". So writing "...if no output to cout or cerr is getting actually written in test reports" is wrong. What more do you want?
BTW you fail the first test "dotest(10, 22);". In this case you have the input, you have "actual", you have "expected" and, in addition, you have the corresponding exemple in the description: "Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]"... so you have everything you need to debug your code.
when u(x) = 9
y = 2x9+1 = 19
z = 3x9+1 = 28
but in test cases z = 27
same goes when u(x) = 19
'z' should be 58 instead test cases fails saying it should be equal to 57
Language JS ? Sorry there are no errors in the tests.
I had the same issue for a bit. You didnt calculate far enough down the list. 57 should be there.
You are thinking of the value that is generated for that input, but that position may be used by the number generated by a later member of the sequence.
Bear in mind that 1) the array has to be in order and 2) there are no repeating positions.
This comment has been hidden.
Don't give free hints and let users solve the katas by themselves.
Is there any way to log the time it took the function to finish? It's not very helpful if the only information we get is that the whole thing timed out.
This comment has been hidden.
I just resubmitted my Go solution. There does not seem to be a problem with the Go translation.
.
This comment has been hidden.
Thanks!
Does anyone know whats the maximum number value for n in the random testcases? My code works on time for atleast upto n = 20000.
in php: 100 random tests up to 10000
But, my code executes fast for upto n = 20000. The number of tests are adding to the time? They don't get executed concurrently?
I'm not sure I understand your question @AbdulSalphan but there are 2 things for you to consider:
the "maximum number value for n" in the random testcases - this is something like 10,000-20,000 depending on language (15,000 for Python)
the number/amount of random tests performed - again, with Python this is currently = 110
So even if your solution is taking, say, 1 second for a single instance of a test with
n = 20,000, you need to understand that may you have to multiply that number by, at worst,110to get the approximate total test run-time, since that is how many random tests will be performed.This comment has been hidden.
this was very easy, it should be 6 kyu
-110?
This comment has been hidden.
This comment has been hidden.
The array is 0-indexed:
I was getting Execute Timeout multiple time , I think i need some help I get 8 basic test correct with a timeout.
Me two. I used python...
-> TimeOut
This is so hard... I even thought about using matricies with numpy. But the problem is, that the dimension increases with each iteration...
I first used an obscure data structure and then learned a very helpful scope function trick (in Kotlin). Thank you for such an educational kata!
This comment has been hidden.
Thanks!
It's still pending?
I don't understand, I think I had approved it 10 days ago. Approved and thanks again.
This comment has been hidden.
strange... i noticed that if n * 3 it passes but if make it up to 5 - it passes even random tests BUT out of time error appears whats the connection between n times and other info ....
So i m still here 2 days gone ) dblLinear passed but random - TIME OUT(((( what im doing wrong ? Im using structures that have no duplicates from birth - so the reason is not in it - i checked Its in algorythm - but when i campared time of "QuickSort" it was 30ms and of simple "sorted()" it s 15 ms - so i dont even know in what direction to go now....
Please follow the Troubleshooting Guide.
COBOL Translation
Approved.
can i request a longer version of u and what gives what ? or will this spoil the question ?
Use OEIS. Turns out it's called the Klarner-Rado sequence, which you can find just by searching for the numbers you already have.
ETA: frankly, I doubt having more numbers will help you though.
great kata..!!!!! great job....!!!!!!!
Can you explain the idea of kata more clearly?
The kata tasks us with generating the sequence of ordered, unique integers x that begins with 1 and are subsequently generated by 2x+1 and 3x+1. Following those rules, the sequence will start off with 1, 3, 4, 7, 9, 10, 13, 15, 19, ... The goal is to create a function that returns the n-th element of this sequence.
The tests will thus check for dbl_linear(0) = 1, dbl_linear(1) = 3, dbl_linear(2) = 4, and so on.
The challenge is not only creating such a function, but creating it efficient enough to run within the confines of the system memory.
Function must return (n+1)-th element.
u(0): 1st term of sequenceu(1): 2nd term of sequence...
u(n): n+1 th term of sequenceThanks for the explanation! Actually I found it better than the original one.
Hello, With Python what is this error Time: 5721ms Exit Code: 139 :)
Solution should be imported explicitly in Python.
Done.
This comment has been hidden.
I don't know what you're doing but the tests still work just fine in Python. If you need help, post your code in a comment with a spoiler tag. Not a kata issue.
Hi,
not an issue a question.
hint: don't use sort. You shouldn't use that at all, here. If you do, you don't have an approach that can pass the tests. hint2: it's a data structure managment problem.
I see you're 6 kyu. That ofc doesn't mean much, but maybe you just don't know yet about the kind of data structure that is needed to solve this. So if you still feel at loss, I'd suggest that either you forfeit to discover somehting new, or you keep that kata at the back of your head for some time, solve like 30-50-100-... more kata and you go back to it when it clicks (because it will, at some point). I'd vote for the second option.
Closing, since not an issue.(already done) CheersThis comment has been hidden.
Not a kata issue. Notice that more than 1000 people passed the C++ kata.
I see that many have completed the task. But that doesn't solve my problem. The solution works fine on my PC. I've done a lot of tests. Help me with a solution to the problem
This may help: https://docs.codewars.com/training/troubleshooting/.
"Focus on efficiency" - CPU or memory?
Updated Dart translation (Dart 2.14).
Approved, thanks!
This comment has been hidden.
This comment has been hidden.
Sure.
ah ha! wow - nice kata. If anyone wants a really vague hint, the solution is like rubbing your head while patting your belly.
I have a solution I believe will work, but it fails the test cases because the global variables do not reset on each function call (javascript). Is it possible to reset the global variables on each function call? I understood each function call to be independent and therefore I could use the original state of global variables in writing my solution.
You can just not use global variables (preferred), or reset them by yourself when your solution is called, right? But still, global variables will bring more problems to you. The fact that they do not reset is not the only problem when using globals.
This comment has been hidden.
(Lua) when returning u(n) it always seems to be 1 index off. This is even true in the example for the problem in the instructions where it says dblLinear(10) should return 22...but if you count the values in the list 21 is at index 10...not 22. I think that the testing / solutions might not take into account that Lua tables start with index 1, not 0. Please advise?
take care of duplicate values
This comment has been hidden.
This comment has been hidden.
I'm pretty sure I found a bug... check my solution Either that or I got lucky, not sure tbh
Your code is clearly not a solution. I don't really understand how the testing function was fooled... I modified it and your solution doesn't pass anymore. Thanks!
This comment has been hidden.
Thanks!
This comment has been hidden.
Asking for help is not a kata issue, post a question instead. You can note at the top of the page that 968 people passed the C++ kata. Furthermore this test is present in all languages. Cheers.
This comment has been hidden.
Not so many, but it seems some people passed the random tests in Dart too. And yes, all test should pass in less than 12 seconds.
Timing out is not a kata issue. Your code is too slow.
On typescript - passed test with n=1000, but on "attempt" basic tests failed with "Timeout of 2000ms exceeded". Test - 12ms, attempt - more than 6s
Timing out is not a kata issue.
This comment has been hidden.
You say to compare Y and Z in each iteration? Z is always greater than Y, so what do you mean by comparing?
My apologies. What i wrote was confusing. In my approach, you do not compare y and z from the same x, because—like you mentioned—z will always be greater than y.
But y is > than z per different indices.
This comment has been hidden.
print(..., flush=True);)This comment has been hidden.
This comment has been hidden.
"My solution doesn't work for some reason" is not an issue.
your problems comes from that part:
u=[1]. You felt into pyhton's mutable default argument trap. if you test 2 calls to your function locally, you'll see it doesn't output the correct numbers anymore the second time.@Blind4Basics Thanks bro!
This comment has been hidden.
hey, you probably forgot some number at the list, for exemple:
19 can put the numbers 39 and 58 at the list, because: (19 * 2 + 1) = 39 (19 * 3 + 1) = 58
the 57 is gonna be there because of the 28, look: (28 * 2 + 1) = 57
How is 28 evaluated when n=20?
So I think you are incorrect in how you are generating the numbers.
Given y = (x * 2 +1 ), you aren't looking to plug n in there, as x is what is in u.
This sentence might help clear up the issue "1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on..."
So you start with 1, y will equal 1 * 2 + 1 = 3, z =4. So now it looks like [1,3,4] The next step is moving to the next item in the sequence. So you do the same y = 3 * 2 + 1 = 7 and z = 10 and so on. So you aren't plugging into the y or z formula but are using the numbers in the sequence.
Why comments mention 60.000 test being the highest? Dart tests for 300,000, is this some sort of bug or increase in challenge? 60k ones completes in 895ms subsequent smaller checks complete within 1-3ms... Still times out on 200k-300k.
1
Because
2 * 13 + 1 = 27Hi,
For how long after getting n values in the set, do I have to keep calculating the numbers of the sequence?
Since smaller sequence number might come later, how do I decide when to stop calculating? Really need help generalizing this since as the n becomes large(n is going upto 600,000 in test cases), you need to keep calculating sequence way after n numbers of the sequence are calculated. Any hint or suggestion? (I might have misunderstood the problem as well, so please help!)
same question somoene help?
up
My code works in the test, but when i try to attepmpt it i have an error: "Timed out"
It needs to be more efficient in order to pass the full test suite.
The full test suite has much more tests and with much larger
n, than those you see in random tests.This task requires a solution with
O(n)complexity to pass the tests. If you sort the result on each iteration, you'll getO(n*log(n)), which is considerably slower.When you have a lot of work to get done, but somehow get nerd-sniped by a fascinating-seeming kata...
Will try this ASAP. Hopefully, a powerful functional programming language like Haskell with lazy data structures should demolish this!
This comment has been hidden.
Wew, difficult (especially keeping performance in mind!), thanks for the challenge :-)
This comment has been hidden.
good
Thanks!
Thank you for the kata!!
Thanks!
This comment has been hidden.
Hi,
That's not an issue, but a question. Please use the correct tag (issue == problem in the kata itself). I guess what you're forgetting is the possibility of getting duplicates. But after you solve that problem, iirc you'll run into performances troubles... So you actually need another approach ("iirc", again...)
Cheers
This comment has been hidden.
Instead of
you should have
This comment has been hidden.
It's because I am using global variables and calling function multiple times! Figured it out!
This comment has been hidden.
If you take it by a correct way there is no sort to do. Maybe you should try more kata before taking a 4kyu...
I know, but it was still fun to try.
For me it was also quite hard to do, but after half a day I did manage to solve it (very rewarding!).
Hint: don't sort on >every< iteration (this is reaaaalllyyyyy slow), sort only when it is needed :-)
This comment has been hidden.
If you get a timeout error you need to optimize your code to be faster or even rethink how you approach the problem. I think you only have 12000 ms to do 110 tests and the biggest test is n(60000).
what is the meaning of this sentence
"returns the element u(n) of the ordered (with <) sequence u (so, there are no duplicates)."
i still dont get it please help me
It means that all the elements are in order(<) from the smallest one to the largest one and there are no duplicates.
.
Factor translation submitted.
Approved.
The description doesn't say how many numbers the list should consist of. As it is it could be infinite.
yes, that's it. It could. The only thing making it finite is the available amount of time for solving, but you should aim for a solution that could go at any "depth" in the sequence.
I understand. I better check some books on efficient Python as my Python only brought me to 5 kyu. It seems like anything above that will require different thinking.
it's not about python but rather about algorithms and data structures (related to big O notations and time complexity of implementations)
This comment has been hidden.
This comment has been hidden.
Thanks!
Brilliant kata. Without brute force, or high-level algorithm u can do it.Oh! if u think time is the main issue look twice where ur code actually taking long apply finest algorithm u know. For python user don't use sorting too much. All u need to do think straight. Try diff approaches if one fails down go for next one and soo on and soo forth. I really enjoyed this kata. Solved it in python.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
My code passed the test but giving me time issues. could you pls look at it. Thank you
g964 what a brilliant problem!! I had 5 different solutions all of which kept timing out forcing a rethink of the algorithm and learning more Rust. Even then after solving it, looking at others' solutions...the simplicity of some solutions still astounds. Best kata i've attempted so far. Thanks.
Very interesting kata. Thanks
I have been trying to solve this for ages in Scala with a O(n) solution, but keep getting execution timeout errors. Any suggestions?
Unfortunately it seems this is all about the data structure that you use as opposed to an actual solution. Native scala collection types such as ListBuffer timed out for me, however if you use an Array as you would in Java it works, granted you have the correct logic. Disappointing.
This is a very interesting problem! Thank you for creating it. I wanted to know if the solution involves trees?
If I write the code in C, it immediately gives an error. An error occurs with an empty function and if all tests pass.
Test Passed The expression (act) == (exp) is false. fixture.c:7:15: warning: implicit declaration of function 'dblLinear' is invalid in C99 [-Wimplicit-function-declaration] int act = dblLinear(n);
Test Results: dblLinear ShouldPassAllTheTestsProvided (4 of 4 Assertions) Completed in 1.5728ms STDERR fixture.c:7:15: warning: implicit declaration of function 'dblLinear' is invalid in C99 [-Wimplicit-function-declaration] int act = dblLinear(n); ^ 1 warning generated.
/// There is no such error in C ++
The warning doesn't prevent you to pass the tests; I tried several solutions and they passed dispite the warning. This warning has appeared when the C version was updated and I was not advised. I added
extern int dblLinear(int n);so there is no more a warning. I tried your solution; it passes the sample tests but unfortuntely times out.Sorry for the inconvenience due to the warning.
Edit: there are 112 tests.
This comment has been hidden.
you need the correct kind of data structure
maybe you could use recursion to solve this problem
This comment has been hidden.
Java? You have more interesting things than ArrayList.
This comment has been hidden.
My code works for the 4 test cases, but not for the 4 extra tests when you try to submit your answer. Any suggestions?
the same thing happens to me too
Welcome. Be my guest
This comment has been hidden.
OP solved it， closing
This comment has been hidden.
Good fun :) Pleased that my first idea worked - that doesn't happen often!
This comment has been hidden.
I don't well understand your post but it's not a kata problem, could be a C problem?
no, its not a kata problem, maybe a website issue. The point is that i did not submit the solution but is marked as solved.
You might encounter one of two issues:
hi, thanks for your reply, yes i think it's the first case you said, because i was trying some experimental solution and i passed all the test only once without submitting the solution, maybe i was luky with some random test ... dont' know. I'm quite sure tha my code does not work if you run it. So yes, i think that should be changed, storing the solution only after the user have submitted it.
And you cannot use sortedcontainers on codewars....
I pregenerated the list (up to 60001) and pasted it in codewars. Now my solutions tab won't work, but I solved the problem I guess.
Tried refactoring a different answer, still broken because it shows up. Would not recommend doing this.
This comment has been hidden.
Op gone, closing
This comment has been hidden.
me too
Hello
I don't understand how we create sequence. I though we calculate values of y and z function up to certain point and sort them while removing duplicates. I prepared Excel sheet and figured out sorted sequence without duplicates (up to index 17) is 1, 3, 4, (5), 7, 9, 10, (11), 13, 15, (16), (17), 19, 21, 22, (23), (25), 27 In parentheses there are numbers which are not in example from Kata description. This is how I got those numbers: y(2) = 2 * 2 + 1 = 5 y(5) = 5 * 2 + 1 = 11 z(5) = 5 * 3 + 1 = 16 y(8) = 8 * 2 + 1 = 17 y(11) = 11 * 2 + 1 = 23 z(8) = 8 * 3 + 1 = 25
Please let me know what I'm doing wrong.
Oooooh, just googled some solution. So x arguments are not incrementing by 1. but you take result of y(1) and z(1) and they become new arguments and so on.
Random tests in prolog always fail: plunit_dbl_linear:dbl_lin_db/6: "Undefined procedure": dbl_lin/6 (forall bindings = [40])
in line 49 of your test file there is a call to dbl_lin instead of dbl_lin_db (probably that line wasn't updated when the function was pasted in the test file)
Lots of thanks! Modified, could you try again and mark the issue as resolved?
I corrected my solution and this time the tests did work fine. Thanks for your quick fix!
I am able to execute the code on codepen but when running on codewars it's showing stderr timeout
This comment has been hidden.
no 'trick'
I found this one to be an excellent learning experience, but almost inaccessible at first. Other comments suggest a certain class that might be useful, but all are spoiler tagged. Is there some way to point people to the right path without utterly spoiling the problem? I only was able to figure it out by writing a not-so-great solution that barely avoided timing out and then seeing other solutions. Overall, though, this is my favorite kata I've yet encountered.
Thanks!
Fabulous kata!
Thanks!
"*** Error in `./test': free(): invalid next size (fast): " Someone know what is?
That definitely sounds like a dynamic memory allocation problem, check to make sure you stay inside the bounds of any heap memory you allocate
(sorry i know this is an old post)
This comment has been hidden.
This comment has been hidden.
The test case for when n = 10 has the result 22. If you continue processing the result is actually 21. See the example above which shows that for the n = 10 case it is quiting early but the test case is marking it as correct. Later for n=20 it doesn't finish straight away. So either the one is wrong or the other is wrong. I can generate either way but I cna't get past these tests as the n=10 case quits early and the n=20 doesn't!
Have exactly same problem (php). 1, 3, 4, 7, 9, 10, 13, 15, 19, 22 - 1st test, expected 22 1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 43, 46, 58, 64 - 2nd test, expected 67 and at attempt expected 57 (with same n=20)!?!?
no, answer for this yet!!
I am also stuck on this
With what language you encountered this problem? I will solve it and check it out.
In the details see point 1: The number u(0) = 1 is the first one in u.
Look at it like an array. Start counting with 0. Then you have 22 as 10th number. 0=>1, 1=>3, 2=>4, 3=>7, 4=>9, 5=>10, 6=>13, 7=>15, 8=>19, 9=>22, 10=>28 28 is calculated with 9*3+1. Since the order is asscending and you miss 21 in this you have to calculate more values until you have all values that are below the asked position. 0=>1, 1=>3, 2=>4, 3=>7, 4=>9, 5=>10, 6=>13, 7=>15, 8=>19, 9=>21, 10=>22... 21 is caluculated with 10*2+1. Now with 21 calculated the order is right and the position of 22 is 10th.
It took me around 2 hours to realize there can be more than one of same elements...
Same!I mean, the description is a little deceptive about that lol. Edit: Then I realized you have to remove the duplicate .. oops?
The description says:
I think there are some mistakes in this kata. Some test cases are incorrect, eg: dbl_linear(500), dbl_linear(1000) and so on. Because of the incorrect test cases, real answers disappeared in sulution page. Wrong anwsers are misleading. Of course, maybe I am wrong.
your last comment is appropriate because we all make mistakes, however when claiming there's a problem: what can you do to demonstrate a problem if you think there is one?
You are probably right. I should demonstrate the problem at the time. Just wait a minte.
Well, you are definitely right. I got it now. Thx, hahaha.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
u(50) = 175- everything's correct.Boy is my face red. Thanks! Duh.
This comment has been hidden.
Ok, good!
This comment has been hidden.
This comment has been hidden.
What an awesome kata! I had an ok Python solution that computed dbl_linear(60000) in about 500ms. However, the tests kept timing out, which forced me to come up with something better. When the aha moment finally came, it was over 10x faster than my original. I am glad the tests forced me to do better!
Good and thanks!
Hello,
My algorithm is taking 2300ms with my environment Windows/firefox for u(60000) but when I try to to submit it sends me timeout error. is ther anyway to test my function in the same conditions as here.
regards, bmc
It could be the number of tests is different, not only one input value. From what another user posted below, there are 100 random tests and 10 basic ones (in javascript at least).
many thx for your message! I'm trying to refactor ...
regards, bmc
Yopi!!!! I found it! it was the function indexOf which was terribly slowing my algorithm...
Regards, BMC
This can be solved in O(n)! Brilliant!
I believe this is the only challenge i've voted "Very Satisfied". I thought I had a great solution, fast and clean, and still think its good. Though I was pleased to see better solutions than mine, and also worse solutions. How can I know when/if i'm good enought to get a programming job?
One way to find out - apply for one :). If they don't accept you, learn some more and try again (multiple companies). Just keep in mind, that prograsmming job isn't only about writing efficient alghoritms as much as engineering clean and smart architecture of SW.
There is a site called interviewing.io (there, you can do a technical interview anonymously over a shared code editor and shared audio, and uncover you name at the end of the interview if you wish). Another site is called triplebyte (It's an agency. If you pass their online tests, they'll make you skip screening interviews at tech companies). And then, there is pramp.com (that site allows you to do mock tech interviews with other job hunters over video and over a shared code editor. Others interview you. And you interview them. The site provides the questions and the answers. It's a great way to get a feel for the competence of the people you might be competing with).
But otherwise, I agree with Lise. Nothing actually beats applying for jobs and seeing what happens.
Hi there,
i have elixir optimisation issues. I need a hint on the data structure to store u in. I end up using a Map as a cache.
I get a timeout after 30 random tests...
There are 100 random tests.
Hi there,
Currently trying to solve this kata, I'm having optimisation issues : On my first attempt 9 tests passed and then it timed out Second attempt : 60 tests passed, then timeout again.
Just curious, how much tests is there to solve the kata ?
Just solve it, if anyone curions there 100 random test + 10 basic one
This comment has been hidden.
As others have stated, please indicate the sequence must also be a set. Description is incomplete without this detail.
By definition, a sequence can have repeated elements. Thus, the description of this Kata is insufficient. The best solution for a traditional sequence is to use a PriorityQueue. However, since the sequence must also be a set, a SortedSet implementation is required.
This is a very nice kata and I learned a lot. My original solution worked within time limit, but it was too lengthy and not straightforward. I read the clever solutions from others and started a new solution. It was neat and faster!
Thanks!
This comment has been hidden.
Have you checked for duplicates?
Unfortunately, like many of the Kata, this one is under-specified and leaves a critical aspect un-answered. The issue in this case is duplicates. In other words, the same value may be generated from two different values in u. I think the fact that '<' is specified instead of '<=', and the fact that there is no unique answer for a duplicate, suggests that the correct thing to do is to ignore duplicates. In other words, treat u as a set, and order the elements of the set according to '<'.
This comment has been hidden.
I have runtime error, but my code works pretty well. What should I do? Could you help me?
Can't help without seeing your code.
There are 5 solutions for shell. Can someone please tell me if any of them are shell-only, i.e. don't just dump the whole problem to bc, awk or some other more appropriate language?
Interestingly enough, preventing dupe addition is slower overall in bash than just filtering it out later, even though about every fourth element is a dupe (eg. for 6000).
I have a straightforward solution in bash shell, but it keeps getting timed out. Don't know how to optimize the script.
One Important Note: ignore duplicate value
This comment has been hidden.
Thanks for your feedback!
This comment has been hidden.
I was hrdcode this one. I had no ideas what to do with repititions and my range increased too fast, so, i used range n * 5. Didnt think about deque or two lists etc. It was hard for me. IMO, its not 4 kyu.
I read somewhere that n goes to 60k max and my algorithm can compute "dbl_linear(140000) " in sample test under 12000 ms. Then why do i got an Execution Timed Out (12000 ms) at Attempt?
Not an issue.
Bear in mind that there's also a reference solution which also takes some time to calculate the result. Also don't forget that there're multiple tests, and your function may be too slow being called 100 times (idk how many tests there're in C# version but probably at least 100).
Also there're 350 completions in C# which means that the kata can be completed in this language.
This comment has been hidden.
This comment has been hidden.
Add the disclaimer that there are no duplicates in u. Lost a lot of time debugging this shit.
Description definitely needs a disclaimer on how duplicates should be handled. Additionally, a link to N-Linear could also be added.
Guys is this more of a math problem or a programming problem? I have like 5 different working solutions, in sample tests I can compute
dbl_linear(25000)in 7426ms. But I always get time out on submit. What are the constrains of n? Just so I know, whether my approach is just a bit off or completely wrong. This takes away my otherwise peaceful sleep :/ Thanks.n goes to 60000. My solution takes about 1500ms.
OK, thanks. I will probably need to throw in more of the cleverness ingridient :D
OK, so it was really just a problem in my optimization...
For Fortran solution - Can you tell me how many random tests I need to complete? I've optimised my code extensively since proof of concept passed about 50 total test cases with zero failed. I've now solved it for a max. of 108 tests, but with major part being random this may drop to 90. I've used an insert sort (& de-duplication) on the fly so that my data array is sorted from the start. Now I'm finding so-called optimisation, e.g. removing "Size(array)" from loop in favour of a variable, editing my function code to be in-line etc. actually have a negative impact. As I'm usually only the 2nd Fortran user, is the number of tests reasonable?
There are 200 random tests. My solution runs in about 700 ms so I think the number of tests is correct. Maybe the sort on the fly takes too much time. Think more about how you put the numbers in your array and avoid to sort. I'm afraid there are only the two of us to take this kata in Fortran...
Thanks for that very quick response. So, twice or more tests - no more tinkering, major re-think. I do have something in mind and will now give it a go. Cheers :o)
Rule 0 of any algorithm problems: Don't micro-optimize if your algorithm is at the wrong complexity ;-)
You win, g964, that is so neat (and obvious, AFTER I'd stepped through a couple of cycles!).
Yeah, Voile, but who's to know that a better algorithm is out there, waiting to be found! :o)
Bravo! You win too!
For Rust are you compiling+running the solution in Release mode and are the compile times also counted against timeouts?
This comment has been hidden.
This comment has been hidden.
NASM translation (with the test code taken from the C version). Please review and approve.
Done, thanks!
This comment has been hidden.
I wrote a queue class to solve this, and pass the sample test... but time out when trying "attempt".
This comment has been hidden.
oo good question
Mine is recursive, if you want, check it out!
Great kata! It inspired me to create a more general version: N Linear. Instead of
x * 2 + 1andx * 3 + 1, the multipliers are a parameter.This comment has been hidden.
OP solved it， closing
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Probably expected and actual values are flipped again.
Nothing flipped. Expected is 175.
I have the same issue :(. I can't figure out the problems. Have you solved it sasayins?
One note that I would make is to add in the description the fact that there are no duplicate values in u. Took me a little while to get the correct answer as I did not know about this assumption and took me reading some of the discourse to figure that out.
I think the author prefers people to find out how to handle duplicates by reading the discourse section, since the vague note in the instructions, "(with <)" has been unchanged despite all the suggestions to clarify it.
Por favor, mejoren sus especificaciones, me tardo mas en entender que es lo que quieren. En este a saber que es lo que piden.
test pass but timeout .... with a 2 while structra while { while { } }
Is this really a code but a math question ?
great kata! it took me several hours though.. using queue was very helpful
Not a suggestion
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
iam able to pass test cases but while attempting it shows "Server Execution Error: The server attempted to execute your code but there was an issue with the request. This should be a rare issue. Please try running your code again. If the issue persists, please contact us."
help plz
If it keeps happening you might have either allocated an array too big, or your code is too slow.
thanks i got it
The same happened to me but I fixed it by removing some print statements. Just in case anyone else has this issue.
Very satisfying to solve this one (Java). And learned a new API as well. Thanks!
:-)
Thanks for your post!
:) :)
I couldn't believe I actually passed the test with my still very slow solution. Then I couldn't believe there was actually a much simpler way to solve this...omg! Thanks op for the kata!
Is it a wrong expectation there for PHP?
testBasics n=50 > Failed asserting that 189 matches expected 175.
There is no problem in PHP (as you can see at the top of the page lots of guys passed the kata). Maybe you should look at your code.
Haskell
Nice one. I have to say though, I did not have to optimise for speed.
The function name is not the one specified in the description. Not a biggy, but hard to see why that should be.
The description is for all languages and the naming convention are not the same in different languages:-)
This comment has been hidden.
Currently Codewars platform is experiencing issues. It's not a problem of this kata.
https://github.com/Codewars/codewars.com/issues/893
Great kata! My first solution was much worse than my second solution, which took about a day's worth of ruminating. One suggestion in the specification of the problem is to note that duplicate values are excluded. I see @Ellsmell noted this in the Suggestions, but it's still not in the (Javascript) spec.
The description says:
< orderdoesn't allow duplicates.Thanks for your post.
Thanks for clarifying that point for me, and for your huge contribution of katas. I assume the alternative would be <= ordering, which would allow duplicates. Does this notation come from the mathematics of sequences or from computer science? I tried looking it up but couldn't find it.
Maybe its just me, but I didn't understand the task, could you imporve the description?
Basically, you take an array [1] and add the results of 2x+1 and 3x+1 to it. Then you have an array with 3 values [1,3,4]. Then you go through and add the results of 2x+1 and 3x+1 for each of the new numbers. Since you add two numbers each for each number, the amount of calculations you do on each pass increases exponentially. Then you return the nth element of the array. The issue here is that getting to large numbers, just having an array that goes past "n" indices will not guarantee a correct answer, since so many new values are added and some of the lower ones will have 2x+1 and 3x+1 results that are NOT YET part of the array. So you need to overshoot the size of the array in terms of "n" by quite a bit.
Depending on how you want to tackle it, one word to help you out: memoize
This comment has been hidden.
There is the true philosophy of life in this kata.
This comment has been hidden.
Why does the C++ version use a unecessary class?
You already post the same question for another kata.
I can't remember the answer, though. So, what's the reason?
I answered that I did like what I had seen in other kata, I also answered you that for new ones I wrote with no class.
can't submit because of time out :( want to know the reason and solution
CW in trouble or - more certainly - your code is too slow.
Time out :( try 2 ways
In basic tests I passed the first 5 examples but failed the last 5. However, I passed all the random tests, there are also many values of param 'n' in the area of the last 5. I don't know why...
I am having the same problem. 110/110 random tests, but 5/10 basic tests on Python, and I don't know why.
OP solved it， closing
What is the upper limit for
n?This comment has been hidden.
Very interesting and amusing kata! Unlike many katas, the description is smart and concise. Had to optimize the code a few times though (for speed). Fun fact: Last submission saves 99.996% of time taken by the first successful algorithm!!
Your TypeScript version appers to be broken.
I get the error:
In the example tests I fixed this by changing:
to
but I get the same error on the full tests, which I can't change.
Could you please fix the full tests?
Known bug for TS at CW. You write it right and it is saved wrong. I reported the bug many times. Fixed once more. Hope it will work. Thanks for your post
This comment has been hidden.
This comment has been hidden.
Good kata!
But maybe you could improve the description. ;-)
A nice and challenging kata. Had to optimize it twice to get it running fast enough. Also interesting to see some very clever solutions. :)
I do agree that this should be rated a bit higher - I found all the other 5 kyu kata much easier than this one.
Thanks for your post, the kyu is given by a moderator not by the author.
I so confused. I passed examples, but can not pass test. I tried different algo but still no success. I deleted duplicates. Have no idea where is my mistake.
This comment has been hidden.
Thanks for your post!
Another enjoyable & challenging kata. Thank you, g964. I do feel rather guilty about getting this one to pass without really understanding the logic behind optimizing it. Bookmarked for a revisit once my math skills improve =]
Thanks!
This Kata is not correct - or I thought the solution vector should be sorted. Since 2n+1 is increasing slower than 3x+1 after finding the nth number in the solution vector we should iterate forward and check whether there is smaller 2x+1 than result (nth number) we found:
... int res = nums[n - 1]; for ( ; i < n; ++i ) { if ( 2 * nums[i] + 1 < res ) { res = 2 * nums[i] + 1; break; } } return res;
I am very sorry but this kata is correct. 1320 guys passed it, 74 in C++ as you can see at the top of the page. Cheers!
Hi, thanks for your reply. Here is the array I produced for 10 - and index is 4: 4> 1,3,4,7,|9|,10,13,15,19,22,28, here you see at i=4 we got the solution as 22 BUT after i=4 if we move to i++ we get 10*2+1 = 21 < 22. So actually 21 would be in front of 22 and the ordered values: 1,3,4,7,9,10,13,15,19,21,22,27,28.. and you can see that 10th element is 21, not 22.
Please correct me if I understand it wrong or (for those who think like me) clarify the problem.
All the best!
The output is is zero based. u(10) is the 11th item in the sequence, 22.
btw I'm still working on this one.
This comment has been hidden.
This comment has been hidden.
Fixed :)
Very interesting challenge, have been trying to solve it for roughly 2 days. This challenge forced me to learn the concept of python generators which I ended up using in my solution. Though my First final submission is 5.5 seconds I am very happy with the progress.
Hi, Congrats on passing :) I have failed with n = 100 test. *✘ 471 should equal 447 *
But for, u(100) there is no 447 calculated in resulted list(even in unsorted/dublicated). Did you encounter same situation there?
Fixed :)
Description should be clearer that the sequence can't have duplicates. I was stuck with an issue for a while because I didn't realise this.
so did I
Thank you! I didn't realise it too! Now I will fix it))
The description says:
... returns the element u(n) of the ordered (with <) sequence u
< order doesn't allow duplicates.
Thank you! Man, I kept looking at my results going "what the hell, why is this jumping incrementally?"
This comment has been hidden.
I don't think it is a kata problem but maybe a CW one. The kata tests return always the same results. 134 guys passed the C# kata as you can see at the top of the page. Try again and if it goes on; report it as a bug: Forum -> Bugs.
I ran the examples successfully, but when I submit I get this error (using Ruby):
TypeError: buffer.stdout.push is not a function at Socket. (/runner/lib/shovel.js:164:27) at emitOne (events.js:96:13) at Socket.emit (events.js:188:7) at readableAddChunk (_stream_readable.js:176:18) at Socket.Readable.push (_stream_readable.js:134:10) at Pipe.onread (net.js:543:20)
I just tried a few solutions and they worked fine. It is not an issue of the kata. 109 guys passed the Ruby kata. You could try once more, it can be a CW problem or something wrong in your code. If there is no error in your code and it doesn't work report this problem at CW: Forum -> Bugs.
Got it to work after I deleted a debugging line
p sequence_arrayThanks!
Haskell:
Getting warning for tab characters, and I think that's why I can't submit.
They're in the example tests, where I found them myself and took them out (they're at the front of the actual test lines), but for the submit test, I obviously can't do that.
Should I be suppressing warnings somehow? (I'm really really new at Haskell in CodeWars).
Another guy told me the same thing today for another kata. I changed this another kata but for now I don't have enough time to change all my Haskell translations (more than one hundred) :-( All worked fine until now. I reported this bug at CW: https://github.com/Codewars/codewars.com/issues/new bug #700. It would, maybe, useful if you conforted that post so that CW goes back to its previous way. I don't know if we can suppress ourselves these warnings. Sorry for that and thanks for your post.
EDIT: I found a temporary solution with this pragma in all tests: {-# OPTIONS -w #-} Could you try again and tell me if it works for you.
That works for me, yes.
Could someone please tell me if there is any problem with PHP tests? When I click 'Run Examples', testBasics() turns green. However, when I click 'Run Suite' the same testBasics() turns red. It sounds to me that there's some problem when input is 100. Thanks!
I tried and had no problem. Try again and if it doesn't work report at CW as a bug (Forum -> Bugs).
I saw your post #699 on Github. Your answer
471for input100should be false when you run both kinds of tests. I don't understand why you pass the "Run Examples"... with a wrong result...This comment has been hidden.
I run into exactly the same problem. It's the same sequence as well
Your result short of 159, which is 79 * 2 + 1. This happens when the number of calculation is too few. Your result will be filled up with (3 * x + 1) elements, sparing no room for (2 * x + 1) ones.
Thank you, I will re-check my solution.
Funny kata. I had to prepare 4 solutions, one faster than the other. All tests passed, but still too slow. Out of curiosity I compared the final one to the one in test evaluation (much more elegant, but slower): mine was 5 times faster (my dblLinear(100000) was 4.4s, "original" 22.7s) !
So most of the time wasted during test was not because of my solution(s), but because of the test evaluation itself. That's sad... On the other hand I've learned a lesson about speed of PHP array operations, so I'm somewhat satisfied...
What actually means this condition "with<" in the kata description?
Means: strictly increasing.
This comment has been hidden.
Thanks for your post! It's not the author who ranks but a moderator...
I agree: rank should be higher. Not because of the task difficulty, but due to big amount of optimizations necessary to pass the time limit of tests.
This comment has been hidden.
"Process was terminated. It took longer than 12000ms to complete" doesn't always mean that all tests were passed; nevertheless refactoring your code might be useful.
"Focus on efficiency" at the end of kata description is the hint what you shoud do. You'll have to optimize your code...
for js guys: console.log takes time :) (not sure if that qualifies as a spoiler)
debugger as well! I had "debugger;" in my code because I tend to copy my code into the browser console and debug it there and it was keeping me from passing the final test. I removed it and then I passed the kata.
This comment has been hidden.
I am quite sure there are no errors in the tests which are the same in all languages. 860 guys passed the kata (185 in JS), if there were errors they would have already been seen.
Yeah, but at least would you please check what I'm saying? You could generate u[0-200] and compare it to mine (or just put it here so I see where the error is).
This comment has been hidden.
It is in fact an issue, you did not specify there could not be duplicate values.
This comment has been hidden.
There are no errors in the tests,
<doesn't allow duplicates.This comment has been hidden.
I'm pretty stumped on how to optimise my code to pass this. I've tried a few solutions, all off which include sorting, and going by others comments here, I guess that's why my code is too slow to pass.
I'm puzzled at how this can be achieved without sorting?
Any help would be much appreciated!
Nice chewy kata! It took me a while to get it fast enough but doing so was a really valuable exercise. Also very interesting to look at other people's solutions.
Thanks for your post!
like a lot of other people have said, definitely seems like a harder than 5 kyu exercise. Feels like at least a 4.
I agree!