4 kyu
Exponentials as fractions
51 of 527g964
Loading description...
Fundamentals
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.
This comment has been hidden.
python new test frameworks + random tests
.
This comment has been hidden.
done for python.
Issue re-raised for other languages
Hopefully I'm going to solve more and harder ones like this one even though I've got to say this particular kata is basically entry level.
I guess I could have saved myself about 30 minutes had I properly read the description and realized that the digits are talking about the numerator and not of precision.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Ahh, I see. Thank you for the clarification. Great problem!
Thanks g964!! this is the first kata that made me learn a new module!!
for others, yesterday, i spend more then 4 hours doing this kata without reading the whole instruction!! questining the kata questining myself, i did try all in my way to manuver decimal, created 5-6 extra function, but all they could return was the correct result for the whole numbers, then i read the instruction again the kind auther mentions a method, and i learned from the discourse there is a fraction module.............. thats it, the kata is actually very simple.
expand(1.5, 10) --> [36185315027,8074035200]
is the result okay?
because numerator has 11 digit, i get 39070599481 by 8717829120 and if its 10 digit, i get 2146736219 by 479001600
i know many people has solved this kata, so this should be alright but i cannot find my fault??!!
Useful kata, I acquired new knowledge, thanks to the author. For me, it was more difficult than many other 4kyu because I had not used the Rational class before and therefore at first tried to solve it in not the most optimal ways.
This comment has been hidden.
Python 3.10 should be enabled. If you do that, please remove your kata from this list.
.
As it was previously noted, some tests with floating point values are incorrect. For example, Python:
1.6is3602879701896397/2251799813685248, the next value after1/1in the series is5854679515581645/2251799813685248.I don't understand your post:
Yes, but it only shows that limiting the number of digits in the numerator doesn't necessarily result in good precision.
1.6as a fraction is 3602879701896397/2251799813685248, the series for it starts from: 1 / 1, 5854679515581645 / 2251799813685248, ... There is no 27425286391 / 5537109375 in the series.Answer by PM at Zulip.
I had such a problem because of the incorrect translation of numbers from float to rational(Ruby). I found the answer in the documentation of the Rational class
@Unnamed: ok, there's a problem, but what exactly is the solution to it?
Either the tests should be changed to match the description or the description should be changed to match the tests, there is no other way. And
No random tests...
raised as an issue.
This was waaaay too easy for a 4 kyu. I usually spend at least 4 hours to solve a 4 kyu. This took me 15 minutes.
Not a suggestion: the kyu is given by a moderator and not by the author; can't be changed. By the way how smart you are! though you don't finish in 15 mn but in
01h 07m 03s, nevertheless not too bad:-)Sorry I didn't mean to sound obnoxious. I was kind of disapointed to solve it this fast. Perhaps forbid the use of imports such as "fractions", that would bump the difficulty a whole lot.
g964lmaooWhen
xis a float, the value to use is not the same that is passed to the function.Please which language? Can you be more explicit? I don't understand what you mean, sorry.
Python.
For example in 11th test
xis7656119366529843 / 4503599627370496but the function should returnexp(17/10).I don't understand... In that test it is
1.7that is passed to the function, not7656119366529843 / 4503599627370496; then, it is up to the CW's code to take a value for x that it thinks convenient for the afterpart of its code; your code - and mine - take exactly17/10for x and both return the same result for this test. So where is the problem?Issue marked as resolved.
Why is so many kata designed around so bad handling of floating point values?
Perhaps it is too late to ask that question : the author wrote this kata in 2015.
How does this matter? It's not something what would change during last 5 years. And problems were reported since beginning.
This comment has been hidden.
At first, I was happy that I solved it(kata of 4kyu) pretty fast. Then I looked at the comments and found out how easy it was. Now, I am not happy anymore.
on to the next one from g964 👍.
Definitely too easy for 4kyu. Wording of the kata could be better but ok.
Using Ruby the Rational function doesn't work correctly for certain numbers i.e. Rational(1.6) will not give (8/5) unless you first convert it to a string. This caused me a huge headache.
I think this kata is relatively too easy to be ranked as 4 kyu.
The kyu is not given by the author but by a moderator or a power user.
I see. (that's a really quick reply)
In other words, the person who approves the kata decides its kyu.
another piece of crap test. Bye bye codewars
Lots of unstated assumptions. Is base 2 exp, base 10? What coefficient? I'll assume 1*10**x but it should be explained.
Exponential function is e^x
This comment has been hidden.
9 guys passed the R kata, not that much but enough to say there are no errors in the tests. 81 guys passed the Python translation and 21 the Ruby one. Python and Ruby give the same results as my R solution for your two cases. The number of digits of the numerator for your two cases have exactly the required length.
So, I'm confused by something basic in terms of what this is asking, as I don't even understand the first example given. Hopefully by walking through my thought process, someone can spot my error and clarify for me:
Taking the first example,
expand(1,2), the answer we're given is65/24. If I do the math by hand I see I can get this sequence of fractions by stopping atn = 4:which when summed gives me the result provided in the example:
So, assuming I've got this much right, if we are supposed to return a value as soon as we calculate a numerator with as many or more digits as specified by the second argument, in this case
2, shouldn't the answer to this actually be16/6, given by expanding out only ton = 3?Considering I'm the first person to mention this I can only imagine that my understanding or calculations are somehow mistaken. Any help would be appreciated--thanks!
You have to reduce the fraction first:
16/6 = 8/3That seems...arbitrary? Or maybe it just makes this particular kata seem arbitrary in terms of what it is after.
Ah, that's the bit in the description I missed then. Thanks.
This comment has been hidden.
I get [6976892759,1556755200] for exp(1.5,10) instead of [36185315027,8074035200]
So what?
[6976892759,1556755200] is closer to exp(1.5) than [36185315027,8074035200] and it has the requested 10 digits.
This comment has been hidden.
Good pick. The problem comes from Python (same with Ruby) conversion of "float" to "rational". I changed my solution and re-published it to get correct results but I suppress the case (1.85, 60) in order not to invalidate all the already passed solutions. With Python (and Ruby) Fraction(1.85) is (4165829655317709, 2251799813685248) instead of (37, 20)... Thanks for your post!
This comment has been hidden.
This comment has been hidden.
???
I guess he passed in the argument like this and so it didn't work:
This comment has been hidden.
Well, that's how every
BigInteger/Decimalclass/module in many languages work.If you want to pass an exact value into their constructors, you gotta pass it in as a string.
There is an error in the test. The function is specified to use Double for the input of the value of the exponential. The number 1.2 has no exact representacion in IEE-754, so it is aproximated (I guess to 1.2000000476837158203125). So, in Haskell 1.2 is 5404319552844595/4503599627370496. The output of my function is correct.
There are no errors in the tests. 24 guys passed the Haskell kata.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Using Python, I got through the first 9 test cases okay but I'm stuck at the x = 1.85, digit = 60. My answer for the numerator is 60 digits long and starts with 502.. divides out to 6.3598195226 (so, a close approximation). I can only assume, given that others have completed this in Python, that I'm doing something wrong and my algorithm is somehow "cheating" on this particular test case.. has anyone else had the same result for this 10th case?
Thanks!
This comment has been hidden.
I'm stuck exactly at this test case... any pointer would be appreciated. To be honest, I don't really understand how the alogrithm works when x is a float. To me it would make sense to round
x**nbut this is not what the author wants. Pretty lost here.This comment has been hidden.
Hint: floating point precision
Edit: Don't flag this comment as spoiler, it's an hint!
Well... It's nice to get the points for a 4 kyu but... Why is it 4 kyu??? :o (I'm completely stuck with some of your other mathematical katas that are 6 or 5kyu only, so I'm a bit surprised to get this one in less than 20 minutes! ;) )
'Was approved with another language? (maybe you shouldn't have had translated it to python?)
Anyway, just a question, no importance... (and thanks for the points! ;) )
(PS: java version on it's way ?)
It's not the author who gives the kyu but a moderator...
Yeah right, I forgot that... ;)
This comment has been hidden.
36 guys passed the Python kata; that is not a lot but enough to reasonably think there are no errors in the tests.
irrelevant
sorry, i was wrong. looked solutions and found out why it happens.
I don't think bootkeen is wrong. The fact that the author's solution gives 6.10 means something is clearly wrong. 36 guys passing the test means the error is likely not in the algorithm, but in the internal data handling.
This comment has been hidden.
This comment has been hidden.
Print the input and you will see the given test.
Well that's so simple that I'm ashamed not to have done it before.
Enjoyable, thanks.
This is about a 6 kyu in python. I take it that the 4 kyu grade is correct for another/other language/s - is it that you can only have one grade for all translations?
Unfortunately the grade is the same for all languages:-( The kyu is not given by the author but by a moderator from the average of ranks given by those who passed the kata.
Doubles and fractions don't mix. How am I supposed to do calculations with
1.5? I know it looks like 3/2, but for all you or I know it might really be 30000001/20000000 (well, add a couple more zeroes).I could work with a rational, but I honestly don't know what to do with a double. It's not an exact number.
Haskell? Looks rather like a question than an issue?
Yes, Haskell.
Given the current design and description, the kata is not solvable. A few people apparently guessed correctly at your approximation.
Do we agree that floating point numbers are inexact? Please add to the description how to rework them to a rational number.
This comment has been hidden.
The relation between a Real and a Rational thus depends on an Epsilon.
I think the essence of the problem is Epsilon is unspecified.
Of course I can approximate a Rational with a Real. For Epsilon = 1, I can get away with just truncing x. Would that give a correct solution?
This comment has been hidden.
Exactly like others said, in the current state this makes not much sense.
I know that this kata is a bit problematic...
The description already says: The function expand will return an array of the form [numerator, denominator]; we stop the loop when numerator has a number of digits >= the required number of digits. and the way is to use Taylor expansion of the exponential function...
Are you sure that the
digitth series expansion gives at least "digit" digits? How to change the test cases so that they expect the numerator is exactly "digit" digits long? In some cases the Taylor expansion gives "digits + 1". Maybe I could say: "The function expand will return an array of the form [numerator, denominator]; we stop the Taylor expansion when numerator has a number of digits >= the required number of digits". What do you think of that sentence?Usually in
exp(x)x is a real so an int or a float. Nevertheless I will add in the description an example where x is a float.Sounds good to me.
Regarding the 2nd bit, I can certainly agree that exp is usually defined over R. But if you don't have a mathematical background, this is something you'll easily miss and would lead to frustration.
Modifications done. Lots of thanks for your posts!
Like other comments say, you should include an example using non-integer x in the program description.
In general, I don't think that allowing non-integer x makes the problem any more interesting. The integer version basically uses the same steps and is a lot easier to understand.
I don't see very well what you want...
The Haskell version should use a pair instead of a list:
Also,
Intis enough forexpand. You don't want more than 2 million digits, right?After all a pair is a list of two, no? Int is enough but who could the more could the less:-) Maybe I'll try to change list to pair; it seems to be not much work.
No. A list in Haskell acts as a an unknown amount of answers (or as an actual list, but that's not important here). It could be none (
[]), one ([a]), two ([a,b]), many ([a,b,....z]) or even infinite.A pair can only have exactly two elements. Never more, never less. If a function has type
a -> (b, c), you can be certain that you'll get a pair.I modified [Integer] to (Integer, Integer) and Integer to Int. In my opinion it should have been a suggestion rather than an issue.
I think you didn't see or read my answer so I consider the issue as resolved:-)
Write
exp(x)orexponential(x)instead of plain text "exponential(x)" (you can use a whole lot formatting in your post in general). Even better, write ex.Corrected. When I wrote this kata I didn't know about 3 backticks... I need a full course about how to format posts and descriptions. Look: I don't know how to write e exposant x, so I can't do better!
That's simply HTML :D.
e<sup>x</sup>(<sup>erscript and<sub>script. Simple mnemonic:<sup>erman flies, the<sub>way is underground). The codex already contains a section on formatting, although HTML-specific tags aren't captured (I don't want to write a complete HTML/Markdown tutorial, after all :D).Thanks for the explanation and for the link. It would be good if Codewars has links in its doc to all of your guides. For the time being all is scattered in so many places.
Not a complete guide but the things that are the most common:-)
Just browse the repository or grab the PDF. I usually change a thing or two during the week. You can also subscribe to changes.
This comment has been hidden.
Not considered for the moment but possible. Thanks!
This has already been asked many times, but I still don't understand why expand(1,5) has 6 digits in the numerator. It doesn't fulfil your requirements.
For expand(1,5), I found [98641,36288], and it seems a really good estimation for me…
Could you please precise why expand(1,5) should have 6 digits ?
Whatever language I use I find expand(1, 5) with 6 digits, same as expand(1, 6). I think my solutions are unable to find exactly 5 digits, I don't have other explanation than the use of Taylor expansion... The loops stop as soon as the numerator has a digits count >= required number of digits. Are you using Taylor expansion?
I am, but the algorithm doesn't stop when it's >=, but ==, since "it takes two parameters [...], "digits" which is the required number of digits for the numerator" If I change my algorithm to >=, I got your answer.
Maybe your should precise this in order to clarify any ambiguity :-)
I'll try to change it but with ">=" it should stop if number of digits == required number of digits, no? I put ">=" only by security... Do you consider the issue as resolved?
Nope, it depends on fraction simplification, so it's not certain, my solution with 5 numbers on the numerator comes later in the sequence than the one with 6 :)
For me, this issue is resolved, and thanks for this kata :)
This comment has been hidden.
This comment has been hidden.
Yes, email is valid, let us compare solutions.
I get 57/20 as 1 + 1.85 - first two terms of Taylor expansion.
@Bodigrim: Kata is re-published. Thanks for your help!
Thank you, very nice kata!
Now I know that Python Fractions module contains something else besides gcd() function . :)
You didn't bother me and thanks for the feedback, enjoy Python Fractions!-)
Why for
expand(1, 5)the[109601, 40320]is considered a valid solution while[37441, 13824] is not?Maybe I was wrong but I got [109601, 40320] using Taylor expansion as indicated and so I declared [109601, 40320] valid:-) How did you get [37441, 13824]? Did you use the Taylor expansion of exponential? Do you see another method for testing the results?
Sorry, I've found a bug in my algorithm implementation. :) Sorry to bother you.
Why is expand(1,5) = [109601, 40320] although 109601 (numerator) contains 6 digits? exp(1) has continued fraction (see Wolfram Alpha) [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10....] [2;1,2,1,1,4,1,1,6,1,1,8,1,1] = 49171/18089 [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10] = 517656/190435 IMHO, [49171,18089] is more appropriable for expand(1,5) If you want irreducible fraction only Taylor series then this moment must be designated in the description. Also exp(1.85) = 6.359819523 but expand(1.85,60) = [ 1255640015507986459344754396106984611112931890102125595005801691, 205688069665150755269371147819668813122841983204197482918576128]. 125...1 / 205...8 = 6.1045 Nearest irreducible fraction of Taylor series is [ 17212490183856113080811676174541242934582010358766327687597249 2706443181710666438004021657600000000000000000000000000000000].
Yes expand(1, 5) is the same as expand(1, 6) (within the method that is used); same for other values. In so far Codewariors use the Taylor expansion there is no problem and nevertheless there you are right: I'll precise in the kata description and give a few references about Taylor expansion of exponential.
I thought Taylor expansion gives a reasonable good approximation, continued fractions are certainly better but less easy to manipulate, as already Taylor expansion has not a big success! Maybe you could write a kata with continued fractions.
I based the solution on the number of digits, another choice could have been to ask for a given epsilon approximation.
Anyway thanks for your feedback, I'll take it into good account.
First, problem as described makes no sense if x is a float, as it is in test cases.
Second, what is this supposed to do if results are 3 and then 6 digits when it's asking for 5?
Third, description is super confusing.
First, problem makes sense even with float numbers, you can find an approximation of exponential(0.5) with fractions as you can find an approximation of pi with, for example, 22/7. Second, if it is asked for 5 digits and you give 6, you don't fulfill the requirements. Third, it's a matter of appreciation... Fourth, did you read https://en.wikipedia.org/wiki/Exponential_function#Formal_definition or view "Taylor's expansion" as an approximation? (http://en.wikipedia.org/wiki/Taylor_series)
I have no idea what this kata is asking for.
Did you read the description and the reference on wikipedia? We want to express an approximation of exponential(x) as a rational the numerator of which has a given number of digits (more digits, better the approximation). So in first approximation e = exponential(1) is 65/24 with 2 digits in the numerator 65. In a similar manner an approximation of "pi" is 22/7.
It may be worth pointing folks to the power series expansion for ex, in case anyone is unfamiliar with the math:
http://en.wikipedia.org/wiki/Exponential_function#Formal_definition
Thanks, done.