2 kyu
Power tower modulo m
251 of 333ecolban
Loading description...
Refactoring
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.
Pretty challenging kata mathematically speaking though.
Lua translation!
we've put all translations on hold, due to clarification needed for some edge cases; maybe talk with monadius about this
I could hardly deal with the case that a and m are coprime, but still can't deal with the case that they are not.
Is there any hint?
Yes. Read the description carefully.
I solved the problem but there were 3 test cases where I hardly-coded them
Would you explain how to deal with it and mark it as a spoiler because I still didn't really understand how to deal with them
This comment has been hidden.
This comment has been hidden.
.
I don't know what I am missing
I think I searched correctly for the relation between numbers
I have passed 163 tests
.
from how long was this kata released?
It's been around for 6-7 years now.
.
"However, tower(13, 3, 31) == pow(13, tower(13, 2, 30), 31)."
Is this correct for only b=13,h=3,m=31 or for all inputs?
This recursive relation is correct for any base, height and modulo(if you apply it correctly too, as per the description)
Thank you
This comment has been hidden.
Very good Kata!!! Thanks to author! Obviously Kata needs perfomance version. =)
This comment has been hidden.
Thanks for your report, I will add this edge cases and publish the fork with updates.
Done! C++ Fork
Hello everyone,
I have a "good" solution in Cobol, by operating the powers by an occurs, but quickly the result is too big to my working. Is there a way to avoid calculating these results before the modulo ?
Thanks
the entire point of this kata is to find that out ..
Javascript Translation
Language: C++
The reference solution expected incorrect result than it comes to
small/medium/largetests. After numerous tests with solutions from other languages with constraints whereexponent == 1most of them gave wrong answers and could easily be invalidated if those translations covers that case.I don't understand what is supposed to be corrected here:
The best option would be to fix the C++ reference solution and ensure that other languages also cover this "corner case". Either reduce this case from translation considering that the Author is no longer here...
(note: the author is still active)
I meant the author ot translation =)
Here's the C++ Fork!
That fork has been approved, can this issue be resolved?
is the random test of c++ version broken?
I noticed that too. Sometimes my solution pass the random tests and sometimes it results in incorrect answer for extremely large tests where exponent is small enough.
UPD: Tested my solution against reference solution with large
base/moduloand exponent between1/100. It's guaranteed that in the caseexponent >= 1 <= 7my solution fails.yes, finally i chose the python version and passed
I have an issue with one of the tests: For (3, 4, 1001) my solution give 27 whereas your's says it should be 482. A quick python check of (3**19683)%1001 gives 27, so I don't know who is correct
482 is correct:
C++ Translation ready for your review. Go easy, this is my first!
This comment has been hidden.
This comment has been hidden.
The kata description has been as it is for such a long time now that modifying the difficulty would be unfair to people who see it for the first time. Be careful, however, not to give away anything more in comments. I marked yours as a spoiler.
Ah I see. Btw I thought I marked my comment as containing spoilers when I originally sent it, my apologies for any inconvenience.
On my attempt I receive a fairly odd failed test (for random inputs):
Test tower(6, 2, 8) 4 should equal 0
Given that 6^6 mod 8 = 4 I am confident my code is correct in this case, while the Python test seems to be incorrect. My attempt also fails at multiple other tests for larger inputs, e.g.:
Test tower(30318, 1648, 586) 582 should equal 430
Here I don't know which is correct, but a brute force tower code I wrote for testing using totient phi(586)=292 produces the same result as the optimised code, i.e. 582. Now I am wondering whether this, too, is an issue with the tests or with my attempt at a solution.
6 × 6 % 8 = 4 4 × 6 % 8 = 0 0 × 6 % 8 = 0 ==> 6^6 % 8 = 0
Thank you for the fast reply! I had made a basic error in thinking about how the totient works for non-coprime values.
The Kata tests positive now (not for any virus, thankfully). Excellent Kata, by the way: just started using codewars, and it was a lot of fun training this Kata. Plus, I learned something interesting.
Factor Translation
I'll just have to trust you. I hadn't even heard of Factor before now. Reminds me of the ol HP calculators!
I can get someone from Discord to review it if you'd like? I think dfhwze meddles with Factor, he could have a look.
Edit: Oh you've already approved :D all good, I am around if there turns out to be an issue.
C# Translation ready for review
Approved
closed
Bizarre test case in Python. You are testing Python's builtin 'pow' method.
Removed.
closed
Could you approve this fork of COBOL translation, with some improvements in tests? You approved an old version (I'm use to doing a new fork when performing some change, so it can be more easily checked): https://www.codewars.com/kumite/61ac7f4e3f4ec100574f1bd3?sel=61afbe8e46519d00079a4760
Done.
Nice kata! Might seem like difficult math but a lot of the math is actually given in kata description so all that is needed is profficiency and confidence in reasonably basic (for 2kyu level) mathematics. The math involved (that you are essentially given) is relevant to several important fields including encryption.
COBOL translation.
approved by author
Hi everybody, I do not understand why I have an "Execution Time Out" when I do the tests on the server since all is fine at home. I do not use brute force. when I use the maximum value allowed by the instructions :
tower(int(1e20),int(1e20),10000000)
the result is obtained in 703 ns ± 6.63 ns
When I do all the tests shown in the SampleTests part, the tests are ended in 10 µs ± 765 ns
any idea that can help me solve that Time prob?
I use python 3.8
I have not solved the kata in Python, but you could try following things:
return 1should do). All tests will fail, but you will see how many of them is there and what are parameters used. As far as I see, there's 200 test cases.Sadly your tips do not work. when i return 1 and print the args i have only the test case shown in the "'sample test" (around 16 tests) windows and i have already test tehm with success %%timeit tower(3,4,1001) tower(729, 0, 1) tower(729, 0, 2) tower(1, 897, 8934279) tower(3, 3, 25) tower(2, 2, 1000) tower(2, 3, 100000) tower(2, 4, 100000000) tower(4, 2, 10000000) tower(4, 3, 10) tower(7, 1, 5) tower(28, 3, 25) tower(28 % 25, 3, 25) tower(13, 3, 31) pow(13, tower(13, 2, 31), 31) tower(13, 3, 31) pow(13, tower(13, 2, 30), 31) tower(13, 3, 31) pow(13, 30 + tower(13, 2, 30), 31) m = 1001 t_3_3 = 3 ** 3 ** 3 t_3_4 = pow(3, t_3_3, m) tower(3, 4, m) t_2_4 = pow(2, 2 ** 2 ** 2) t_2_5 = pow(2, t_2_4, 720) t_2_6 = pow(2, 720 + t_2_5, m) tower(2, 6, m) => 10 µs ± 765 ns per loop (mean ± std. dev. of 7 runs, 1 loop each)
I wonder what we two do differently, because first of all, Python 3.8 version is unavailable for me here on CW, I can select only 3.6. When I do so, I submit following dummy solution:
what obviously makes all tests fail, but it gives some potentially useful output which I pasted here. It's not really interesting except last ~30 cases with big numbers, which you could use for benchmarking.
Unfortunately I haven't solved the kata yet so I won't ask you for your code, but if your benchmarks run locally on above inputs efficiently but still timeout on CW, you might want to ask for help on kata solving channel.
FYI, I just reran one of my past solutions, which completed the 200 tests in less than a second on the server.
@hobovsky : when i say i use python 3.8 it was on my computer not on teh web site. I also think you have misunderstood me : I had the timeout message on the 'Test' when you obviously show me the 'Attempt' result. Test use 17 tests :
.
@ecolban : you are a naughty boy. I finally understand where come the message of 'Times out' = that comes from your code to caculate totients (G = {i for i in range(1, m) if gcd(i, m) == 1}). If i used anotehr method all is good
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
the prob is that you gave code not only definition. That code mislead me because I naively think you wanted we used that code. Perhaps just give only definition and not code or precise that the code you give is not efficient on CW web site (btw that code is perfectively fine on my computer even with very big number)
in the random test tower(6,1,4) has answer 0 but I think the answer should be 2( and my solution produced 2). could you explain why it is 0?
That was an error in the test code. It should be fixed now. Thanks for pointing this out.
Looking at the solutions, it seems that you forgot to
from math import logyourself in the tests, and we have to do that for you in our code ;-)It's there.
Should've resolved this myself a long time ago ;-)
typo in the description:
Corrected.
This comment has been hidden.
Fixed.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Made some minor edits on top of Bubbler's.
Looks great :)
This comment has been hidden.
This comment has been hidden.
I believe it's fixed now.
This comment has been hidden.
Done! Thanks again for verifying the code. It's so difficult to notice these things when my solution code is part of the test code.
:)
Wolfram Alpha suggests that tower(28, 3, 25) or (28^(28^(28))) mod 25 == 21 and tower(28 % 25, 3, 25) or (3^(3^(3))) mod 25 == 12. https://www.wolframalpha.com/input/?i=28%5E(28%5E(28))+mod+25, https://www.wolframalpha.com/input/?i=3%5E(3%5E(3))+mod+25.
I'm pretty sure I'm missing something so some clarification would be great :)
You are so right. I've corrected the tests and the solution code. Thanks for pointing out the mistake.
Expected and actual values are flipped in the example tests (and maybe in the actual tests too).
Yeah, I never know what the convention is. In Java, the expected value is to the left. Thanks for pointing this out. It's corrected now. Please mark this as resolved.
;-)