4 kyu
Multiplying Polynomials
118 of 183Yushi.py
Loading description...
Mathematics
Strings
Regular Expressions
.avif)
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 math kata.
The random tests for PHP often expect an incorrect or sometimes empty result:
Testing: 5U^3+7U^2+U and U^2+9U^3-7U-3 Failed asserting that two strings are identical. Expected: '45U^6+68U^5-19U^4-63U^3-28U^2-3U' (My result) Actual : '-12' (Expected by test)
Also the RandomRealyBigPolynomials feel impossible in PHP, the memory limit is very quickly reached.
It should be fixed now for the reference solution, and the expected and actual values are swapped. As for the RandomRealyBigPolynomials, it's the specification of the kata (only 5 tests), and it is possible to solve.
Bugfixing fork to address cases in which the JS reference solution breaks down:
https://www.codewars.com/kumite/65383e33e681c41613bcb605?sel=65383e33e681c41613bcb605
Details on bugfix here:
https://www.codewars.com/kata/63c05c1aeffe877458a15994/discuss/javascript#6536cc0c49d3ef23dade29b1
Waiting on approval.
can't approve the fork yet, but I can directly apply the fix. I don't know what to do here... x_x
Just apply the fix I think - I'm not attached to the fork in any way and the change is literally two characters.
Okay, done. Thanks for the fix.
Are there any Javascript libraries that could be helpful for this? I haven't worked with JS imports before and have no idea if there are any math based one.
If not, is there a way I can get my code from O(n^2) to O(nlogn)?
Also I'm trying to learn complexity so am I right in that assement above?
There are libraries for this, but I don't think they can be used on Codewars.
If you're running node locally, you can find libraries on https://www.npmjs.com/
Complexity
Since you have to multiply every term of one polynomial with each term of the other polynomial,
the best you can do is O(m*n) where m and n are the number of terms in the two polynomials.
You can only get O(n^2) if both polynomials have the same number of terms.
JS random tests sometimes fail with '-NaN' generated by test as a correct answer.
Some logs given below, my solutions are obviously correct (which can be checked with direct calculation):
Confirming this is a bug in the reference solution. When the first polynomial string ends with the variable and the second starts with it the variable is incorrectly detected as being multiple characters, e.g.
Testing: -1+4a and a-9a^3: expected '-36a^4+9a^3+4a^2-a' to equal '-NaN'This is because it's scanning the concatenated string
-1+4aa-9a^3and finding the "variable"aa, then parsing breaks down from there. I've fixed this in a fork here:https://www.codewars.com/kumite/65383e33e681c41613bcb605?sel=65383e33e681c41613bcb605
Just waiting for approval
Fix applied. Thanks @RileyHunter
Maybe reduce the number of tests? I pass 129 tests and time out. I think my code is quite good
It's not really the number of test, but rather their size, the last five tests are very big.
I originally intended for people to use external libraries such as
numpyto do the math part and didn't think people would bother to write the code themselves.The final tests ended up, accidentally, being an extra challenge for those who wanted to give a go at making a more efficient algorithm.
If you just want to get it over with, use imports. Now, if you want a challenge, try to write it yourself.
no reduction, this is 4 kyu
As a result, numpy solved my problems
I first solved this kata very straightforwarly without numpy and no special trick, your original code was probably quite inefficient, I advocate for no reduction too.
JS:
chai.config.truncateThresholdshould be set to0orfalse. User can't see the error of their result in big random tests.config applied.
PHP translation
Javascript translation
Hey man, thanks a lot, two tranlations at once is quite something!
Also thanks for the description, it really needed an update, I gotta learn all this fancy stuff you used.
Again, many thanks, take care bud :D
I forgot the formula for polynomial multiplication and thought you only have to multiply numbers with same powers D:
This comment has been hidden.
Rust translation
Dang, I never thought this would get a translation, especially in Rust of all languages. Thanks man!
If I get the motivation for it, some day you may get one in COBOL too :D
Thanks for approving.
Very fun, I barely made the timeout cut with no optimizations and no libraries. I thought my solution was ugly but in the end I'm quite happy.
I think this kata needs the Performance tag. The inputs are enormous.
It kind of comes down to the use of external libraries.
If you use numpy or something like that, then performance will no longer be an issue.
It's kinda like the use of regex is pretty much required.
Thank you for the hint :) Managed to make it work both ways in the end, nice kata!
no library is needed, actually. ;)
Nice kata. But maybe we should ban numpy, because it makes the problem trivial. Without using numpy it is necessary to implement an algorithm that does not do any extra calculations otherwise you will get a timeout. I had to optimize the calculations several times to get it to work in the end.
I do like your idea. I believe that many katas can be solved very easily through the use of imports.
In a way, this is also the case for this kata, if you consider the mathematical part of the problem to be the main one.
However, as it may be clear from the description, this kata has an enphasis on the regex part of the problem; the main difficulty is to recognize the coefficients of the polynomial by its string representation as well as produce a well-formed one as an answer.
I do believe that a very good kata could be made by forcing the user to create an O(nlogn) algorithm for the polynomial multiplication as a solution. However, I think it would take the main focus away from this problem.
this might give a problem with translations to other languages, the difficulty level will not be the same
Creating a polynomial multiplication algorithm isn't hard (an unoptimized one, that is). So forcing one to do it wouldn't affect the difficulty much.
If one was to create a translation, it would only be necessary for the creator to make it such that even a poorly optimized algorithm would pass.
What I'm saying is that while it would increase the difficulty, it would be minor, as long as the translation creator has this in mind.
Then I guess we can approve this kata. Votes are all over the place though, are you happy with kyu 4?
I was between 3 and 4 kyu, but I'd say 4 is reasonable.
I was inspired by a 3 kyu kata on binomial expansion which was admitedly easier than this one. However, that one was severely overated.
So yeah, I'm happy with 4 kyu. I't nice to have this kata finally approved after 5 months.
Hi,
the kata needs some improvment. But I lined it, overall.
list.pop(random index)makes the building in a loopO(N²). Prefer the use of the dedicated tools, lile:random.choices(range(max_exponent), k=random.randrange(max_exponent))to generate unique exponents (note: nothing forbids to have multiple times the same exponent. In both cases, the behavior should be talked about in the description (I don't remember it, maybe I missed it))random.randint(-max_coeficient, max_coeficient)will do a perfect jobCheers
note:
k=random.randrange(max_exponent)is actually a very bad idea for the last batch of test, because that will make the perf range very wide, but something likek=random.randrange(max_exponent//4,max_exponent//2)or along that line of thoughts should be ok(I cannot edit the first message anymore... 'x) )
Thank you so much for the feedback, it is very much appreciated.
I just republished the kata, fixing the issues you pointed out.
Be sure to notify me if i misinterpreted something, or if you found another mistake.
Thanks again, stay safe mate.
Cool thx.
Some notes about the sample tests:
itblock. It's easier to maintain, and it avoids that some unexpected edge case is tested with them and not in the full test suite. If the tests you currently use there are already in teh full test suite but in different testing blocks, I'd suggest you keep the structure apparent in the sample tests as well, so the maintainers can see what test comes from where.-x...+xx(and possibly degree 0)81x(to spot wrong regex solutions)You should remove the
0case: if the coefficient is 0, the monom just isn't there and there is not point in putting it in the input. Moreover, this is unexcpected, not described in the specs, and not tested in the fixed tests. Again, I was talmking about outputs, not inputs.Hi again, and thanks for the feedback; it's always appreciated.
Sorry for the long time it took to fix and answer; I'm currently traveling and don't have my computer on me, so I'm having to code everything on my phone, lol.
First off, I'm sorry, it's my first time creating a kata, so I often misunderstand or don't understand at all what you mean. I probably should have chosen an easier kata as my first one lol.
Despite this, I made some modifications in an attempt to fix what you said.
Please point out any errors or misunderstandings I made.
I'm not sure what you meant here (I'm terrible at understanding codewars jargon).However, I created a
test.itblock on the full tests with all the tests in the examples.I created a new
test.itblock calledTesting special caseswith five tests regarding what you said here; the variables aren't all x's, but I don't think that matters too much. Would you mind explaining why we tested "81x"? It just seems so random to me.You misunderstood what I did (not me this time, lol). When I said the coefficient would be zero half the time, I meant that half the terms wouldn't show up, so I used
[i for i in range(max_exp) if random.randint(0, 1)]to remove about half of the terms.I added a
test.it(Testing polynomials with 0's in the result), which covers the 0 in output, as you said.While the changes I made ensure that there will be more
1's and-1's in the input than in the output, having more of those in the input almost always ensures that the output has more of those as well.I believe I covered all you talked about. However, be sure to notify me if you find any other problems or I misunderstood something you said.
Again, thanks for the feedback, it really helps.
Cheers mate, stay safe.
How many really big random tests are there? I have no clue how much to optimise my code.
btu the perf problem is on the kata side
just remove those huge tests if this kata is not about performance
na they can stay there. once the generation is done correctly, only bad solutions wouldn't pass
that means we have to use Python builtins to pass the perf requirements
afaik, no. Again, the tests generation is eating up most of the time. If you don't pass the tests, that should mean your approach is not appropriate anyway
Like, for example:
res = res[1:]res being a string, IS A VERY BAD IDEA. Not focusing on performances doesn't imply that anything can pass the tests ;pwoops
Hi, sorry for that.
There are 20, 30, 20 and 5 small, medium, big and really big tests respectivelly.
I updated the description to include that.
Again, sorry for the inconvenience. Be sure to notify me of any other problems you find.
Thanks mate.
I'll just wait for the JS translation.
I'd like to give it a go, once I solved this puppy. Can you wait a year? :-P
@Kees de Vreugd Depends. There might be another user who wants and can translate it first (including me :) ).
Reference solution handles
0incorrectly:It expects 0 if you got no symbol and an empty string otherwise.
This is pretty weird.
I added an if statement to my solution to fix that, it should handle it properly now.
Typo in initial code function name:
polinomial_product->polynomial_productI spent an hour running a grammar check through the whole code, and that was the only place I forgot. Well, it's fixed now.