2 kyu
Ludicrous Coloured Triangles
287 of 484rooflack
Loading description...
Puzzles
Mathematics
Algorithms
View
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.
Great follow up kata of the Insane version. First i thought, i had to find a new better approach, but my recursive approach from Insane Colored Trinagles was good enough, it just needed some gradual optimizations. Final testing time of my Python solution was 10109 ms. Thanks for this kata, I learned even more!
This comment has been hidden.
6th example:
RBRGBRBGGRRRBGBBBGG
If going by your logic of start + end = result:
R + G => B
But if we iterate manually:
So... no. It's not
B
. It'sG
. The notation ofstart + end = result
is not always correct.Not a kata issue. Resolved.
Finally, I did it. Python. My time is at the eadge. 11300 ms. I think that for Python some tests should be excluded.
Something does not work with Python, as reported by other users. Even just writing "return 'R'" in the function body, it takes 6-12 seconds to pass/fail all the tests; sometimes it even times out. Some administrator should consider removing the Python version entirely.
I just tested some solutions, and they pass consistently below 10 seconds.
.
The variation in inputs (for Python) causes this Kata to randomly pass or fail solutions due to timeout. Please fix such that the inputs are representative and can be finished in the time budget.
This kata cannot be updated to Node v14 because of the reduced max string length limit which was reverted from 1GB to 256 MB in V8 version 8.2.6: https://github.com/v8/v8/commit/ea56bf5513d0cbd2a35a9035c5c2996272b8b728 Node v14 uses V8 8.4, before since Node v9 (V8: 6.2.100) the 1GB limit was in place.
Python 3.8 should be enabled.
.
Here is my "Translation (attempt)" to Ruby. https://www.codewars.com/kumite/61575a190f76ac0021c0e336?sel=61575a190f76ac0021c0e336 It seems to work fine, although I had to use a "little trick" to "generate the Huge Random strings faster" ==> I hope it's not too much of an issue :/
Note: the solution I coded always passed the tests taking between 5 and 10s, while I also made a test with the 3 "best rated" (Ruby) solutions from "Insane Coloured Triangles" ==> All 3 of them timed out ;) ...So I guess the "tests' level" seems quite appropriate...^^
"Update": here is the "Fork" I made, taking into consideration @Blind4Basics's remarks! [Thanks again! :)] https://www.codewars.com/kumite/61575a190f76ac0021c0e336?sel=615b9c547c1df80027994ac6
This "new version" includes several changes in order to prevent potential "cheating"...
I also(re-)tested the 5 "Highest Rated" Ruby solutions from "Insane Coloured Triangles": all 5 of them always fail [Time Out] very early: either at my "quick little check", or at the "easiest long strings" ("Ultra-Violence": Only 10 million characters) without even reaching the next steps... ;) [Meanwhile, so far, the "Reference Solution" always passes all tests within 5 to 10 sec]
I'm marking my "suggestion" as "resolved", since the translation has now been "Approved" :) (Sorry I'm obliged to "post a comment" in order to do it)
Thanks again to @Blind4Basics! ^^
This comment has been hidden.
This is actually the reason I created this kata in the first place. After solving the 'insane' version and looking at the official solution, I realized it allowed solutions based on algorithms with far from optimal time complexity. So I created this one (the JS version only, the Python translation is not mine), so that people figuring out the actual best way to compute this could earn more points. (So, long story short, the 'free' score increase is actually the 'insane' version, not this one ;-) .)
@rooflack Yeah thanks for the reply (you're right ==> so I just upvoted your Kata :) [and comment^^]) By the way, yesterday, I tried to translate the Kata into Ruby, but (temporarily?) "gave up" :/ (I must confess I'm quite a n00b at Ruby [only "train" Ruby a bit just because it's often easy to translate from Python]; and I guess the way of "efficiently generating the rows" might actually be a bigger issue than the "solution" function itself :/ ...) ((By the way, could you have a look at my solution? :D I think my approach seems to -maybe- be a bit "more direct" than yours; but probably ~"equivalent" in the end; at least it should reach "O(log(n)) complexity" [at least in the "best case(s)"] [Maybe I should have commented my solution; what it does might not be 100% obvious at first glance... :/ ]))
EDIT: now I did publish my "Ruby Translation (attempt)"
(I now added a little comment to explain how my solution works [at least for Python; JS version is basically "the same, but the code looks uglier"^^])
https://www.codewars.com/kata/reviews/5bc78d877bf31d2ace000f06/groups/6155f68d76a8e70001524790
Whats wrong with yours server? My solution solve 100 million character string for 21 sec on my PC. But here 1 million char-string is longer then 12 sec. Upgrade your server!))
100 million characters in 21 seconds is way too slow. The tests test 4/5 strings with 100 million characters and 1 string with 1 billion characters and it has to pass is 12 seconds. That is your solution should pass them in ~6 seconds max because the tests also need to create the huge strings and run the reference solution themselves, which takes a little bit less than half of the 12 seconds.
languages version are inconsistent:
Finally solved, but honestly this feels like 50% optimisation and 50% luck from the server. But maybe my solution is just slow :D
this branch about who can complicate task more than other :)
Este kata falla, sin haber puesto ningun algoritmo, solamente [return "B"] ya me da el error del tiempo.
This comment has been hidden.
O(n) doesn't pass, you need better. If you're saying that the reference solution is O(n), yes, it's a problem and explains the huge variability in the time execution
=> ?
This comment has been hidden.
Can anyone who has completed this before reach out to me, please? I'm pretty certain that I have the correct approach and my code gets through a Massive amount of the larger ones before timing out. I'm wondering if there's room for improvement, or I'm just trying at bad server times. If I can improve my algorithm, I don't see how, but I like this particular kata and would like to know.
You can try to reach for help here: https://gitter.im/Codewars/codewars.com/kata-solving-help. It could also help if you specified the language you are attempting, maybe Python version is affected by the runner performance issue? You would need someone to confirm it though, because I have not solved this kata.
Thanks for the link! I will definitely check it out. I've been trying in javascript though. My code did great on the Insane Coloured Triangles version, but seems to fall short here. Hopefully someone at that link can help me figure out where I'm going wrong.
It appears this kata may not be solvable anymore. Even a blank solution times out in JavaScript.
Well that's a buzzkill. Suppose I probably should have checked that myself tbh. lol... I just assumed it was still good to go. That said, the python one doesn't time out right out of the gate, so maybe I'll refactor and give that a go.
warning, depending on the test frameowrk, returning false may print the input to the console, which may slow down a lot the executions too.
Eh, I give up for now. My python version passed the Insane Coloured Triangles one with flying colors as well, but drops the ball here. I'm going to assume this one's broken for now unless someone who's passed it tells me otherwise. Thanks for the help and the tips everyone!
I've done in JS, but with some cheating for last test; Now I could say it is hard but still doable (I was close): reference and similar solutions could pass the test it JS, near the limit. So I think the idea of kata is worth 1kyu kata, but implementation could be better, e.g. arrays instead of strings...
P.S. It's weird that now after I've only tested reference solution site shows it (under comment) as mine instead of my submitted one. Not a convenient behaviour...
when you test solutions of other users, you should do it through the forks, not through the trainer.
Thank you for your advice. I've tried but when I press fork and then run I got smth like 'ReferenceError: Test is not defined' so it looks like I need to write some simple extra code to make it work. Looks like I should dig a little more into the test framework and how it works with that editor.
P.S. got my code to work without any cheating in 6-9s, so it definitely could be done in JS, but still don't like the way this kata force me to implement very particular idea.
the stuff about
ReferenceError
is because of the python version: by default, the fork panel starts in 3.8, but some older kata have a code that runs only in 3.6 setup.the same idea works for JavaScript. Thank you again.
Well return("") took 8 - 12+ seconds. (Frequently timed out.)
I did manage to get python to pass the test, but I had to submit like 20 times.
I propose to change this kata so that we aren't given a pre-produced string but instead a string-ish object which counts how many accesses to its characters are made and makes up characters on the fly following a certain algorithm. And if the amount of the accesses is too large, it should throw an exception. This way it would not use the brittle timeout-mechanism to ensure the correctness of the algorithm.
I'm pretty sure I have the optimal algorithm, and now I even optimized the code, although the description says that's not what it is about. And still I get timeouts in Python.
It's frustrating to have it this way. Someone should reduce the limits of the test cases to make sense for Python.
actually, it seems that if you time out, that just means you don't have the correct approach.
I clicked on attempt again and again in the end when I had no more ideas. And finaly it accepted my version. I guess my approach is sound algorithmically (feel free to have a look at my solution and correct me), but the test suite is also reported to have issues with timing out for O(1) algorithms :-/
I didn't solve this version, so I cannot. ;)
Oh, well, it's the same algorithm as for my solution for the simpler version (so you probably can compare there?), but I replaced the creation of substrings by passing the limits in the original string instead. Makes it less concise and less readable but probably a little faster. But the complexity should be O(log(n)) in both cases. (I might be wrong about the formula, but its definitely the same for both versions.)
Would anyone do anything about this kata and update the Python version to 3.x???? See the post below.
Updated Python to 3.6 by commenting out the smaller tests.
(Yes it's still timing out most of the time, but that's a much more difficult problem to solve)
I guess there is no hope for python eh?
Well, it's more like trying to figure out what works would take too much effort than what I'm currently willing to spend. So procrastination galore ;-)
Indeed, you are right... I found an interesting solution on Insane Triangles which I am working on it (unravelling what is going on). It is quiet fast and looks promising! Maybe give it a look?
I always get the following error:
Traceback (most recent call last): File "main.py", line 114, in fixed = generate(1, size+1, size)[0] File "main.py", line 68, in generate generate._pool_cache.append(''.join(random.choices(combos, k=chunk_len//combo_len))) AttributeError: 'module' object has no attribute 'choices'
10 basic tests are passed. In Python2 'choices' method not exist. Why Python 3.X interpreters are disabled?
Yeah I am getting the same... any idea?
Don't use anything else than 3.6. Not an issue of the kata.
(edit: reset the trainer: only 3.6 is showing up, for me)
What do you mean "reset the trainer", it is the "Reset" button? I tried it many times, but 3.X interpeters are still disabled.
yes.
Shouldn't be the case... :/ refreshing the page don't do it either? That's weird. I only see 3.6 available, here.
But it is. I reload several times the page with pushing the refresh button many times. And also delete the cookies from the browser so I must to log in again. I opend the Kata and still Python 3.X is disabled.
Same here I see only 2.7!
same here. Traceback (most recent call last): File "main.py", line 114, in fixed = generate(1, size+1, size)[0] File "main.py", line 68, in generate generate._pool_cache.append(''.join(random.choices(combos, k=chunk_len//combo_len))) AttributeError: 'module' object has no attribute 'choices' and cant change python version.
Execution Timed Out (12000 ms) for even O(1) return functions in python.
I have attempted the kata multiple times with a blank function to measure the test generation speed. Many times I time out, most times it takes at least 11 seconds, and I've never seen it go below 10.
I doubt this kata is completable in its current form, given the time constraints.
Same results here.
seems a default solution now leads to something between 5s and time out...
Execution Timed Out (12000 ms)
My solution code:
(sorry for the duplicate, couldn't see my first comment)
as long as nobody answered to your comment, you should be able to remove it. => Try for the one below. ;)
about your problem: I believe the kata is uncompletable for now in python because of a runner issue (edit: see the thread just below yours)
Yep, i also tried it with javascript, with the same result (timed out)
On my local laptop, python for 10^9 string runs at about 4ms, so it should be ok time-wise. However, when i tried to generate a random 10^9 string on my laptop, this took a really long time.
I suspect the issue to be with system entropy pool / random number generator performance.
This times out:
Does the python test suite generate within 12s?
https://github.com/Codewars/codewars-runner-cli/issues/757?
I also experience the same issue, both with python and with javascript
I have the same issue.
Sorry, in my opinion this kata does not make any sense at all. The runtime highly depends on the exact length of the test patterns. If you know the general idea behind the algorithm you know that you can construct worst case scenarios for the input length that lead to a massive penalty regarding the runtime. So, in the end it's all a question of luck that you don't get any of those test patterns that represent such a worst-case scenario. I tried several of the committed solutions on my local machine and they all failed to solve inputs of specific lengths within several minutes. If you don’t believe me try some of the committed solutions with any arbitrary input string that has a length of exactly 387.420.489 characters.
Hi guys, I'm the original author of this kata. Sorry for the very long delay, I haven't been on CodeWars for almost a year. I recently got a few notifications from the site, and I thought it might be worth clarifying a few things here.
First, note that I only wrote the initial JS code, not the Python version, which I haven't really looked at, so I'll only speak about the JS version.
Now, let's talk about speed. Most of the time in this kata is spent generating the samples. It takes a LOT longer to generate the super long strings than to process them. So this is perfectly normal that submitting an empty function still takes several seconds to run. It is also true that the execution times varies significantly depending on the server load, and that you shouldn't expect 99% success rate. That being said, when I created this kata about one year ago, it typically took around 6 to 8 seconds to run. I've just run a few tests and it seems that it is now closer to 9-11 seconds, with great variability (I tried about ten times and got two timeouts, one run under 8 seconds, two between 8 and 9, and the rest between 9 and 11.9 s)... This is not great (I actually expected speed to increase over time, not decrease), but it still leaves room to complete the kata with a decent success rate (say at least 50%): if you're sure your solution should but it still hits the timeout, just submit it once again and it should be ok.
I agree that it's not ideal, especially for people who are limited to using CodeWars at rush hour, but I'm afraid that, by removing some tests or making them less random, it will make it possible to complete the kata without getting the right algorithm and cutting down the complexity, thus defeating the kata's purpose. It was precisely written as a tougher version of Bubbler's "Insane Coloured Triangles", which is rather forgiving in that aspect, so the fact that it runs on the edge of the timeout is kind of a necessary pain.
I'm sorry if this is not very helpful, I wish there were a differentiated, adjustable timeout system that would allow to time the input genration and the solution test separately, thus removing that server load dependency, but unfortunately this is not the way the system works. In the meantime, keep in mind that the solution should litterally be able to crunch gigabyte-sized inputs in fractions of a second. And if the sample input generation takes too long, just hit the 'retry' button until it passes :-/
Cheers.
The number of tests causes runtime to come pretty close to the time limit, sometimes leaving the ability to submit up to how busy the codewars server is. I've even had an empty function submission (ie submit the starting template) result in a timeout. Depending on the solution, the performance difference between different inputs can also be pretty big and decides between timeout or not (ie it can be much less consistent than '99%'). It might be useful to either make the timer a bit more lenient, or limit the variance between inputs more; specifically to use set input lengths even for the random tests if this isn't done yet.
The program execution time with an empty instruction (pass) is 11.1-11.5 / 12 sec, which causes doubts in the ability to perform this task in the Python3. When I try to get the difference between the start of the program time and each return value time using the time.time () function of the time module, I get a time out error.
.
Does this Kata work in Python 3? Description says...
Caution: This kata does not currently have any known supported versions for Python. It may not be completable due to dependencies on out-dated libraries/language versions.
yes ("work" as in "you can run it". But there are problems with the tests, yes)
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
And now I cannot pass again. Miracle.
This comment has been hidden.
python is lacking its sample tests.
When I try to edit it, it runs into the issue
https://github.com/Codewars/codewars.com/issues/1134
So I tried forking it here:
https://www.codewars.com/kumite/5b8957fc979532035500010c?sel=5bd486507645b91db500003f
It appears to be awaiting approval.
still lacking the sample tests, here
Quick note about rank assessment. I believe this should be a 3kyu rather than a 2kyu, as it's a lot easier than other 2kyu I've seen. The problem is that it's based on Bubbler's Insane version, which is already ranked 2kyu, and this one is "harder", in the sense that any solution that beats it will also be valid for the other one. So I thought it wouldn't make sense to give it a lower rank, and chose 2kyu, even though I still think it's kind of overranking.
Did that test case just rickroll me?!
It may have ;-) But it looks like you got the last word. Well done!
Please check out Python translation in kumite https://www.codewars.com/kumite/5b8957fc979532035500010c
Unfortunately, after fiddling with it for a while, I found I still had to reduce the number of test cases to get the solution within the time limit somewhat reliably.
Thanks a lot for the translation!! I'm not sure I'll have time to check this out during the weekend, but I'll have a look at this next week.
Hi. I'm afraid it will take longer than expected, because my computer died :( Sorry for the delay...
No worries! I'll be around whenever you get the chance, just let me know!
hi,
Is that normal that the ref solution along with the random string generation take more than 10s on their own, in python? How much of this is taken by the random generator?
Very nice!
Thank you!