Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @Westicles,validated by @Ayush-Kukreti,@Zimtrolle and @TheOtherAKS.
If you have any issues, feel free to ping them.
I’ve tried an implementation of Cuhdnovskyl’s algorithm in Java… and in Python. I’ve also tried an implementation of Bellard’s algorithm. I’ve tried optimizing by using parallel streams/threads. I’ve also tried different optimization techniques for factorials and pre-computation of primes. I can get the first test to pass, but all of the other tests fail because I’m out of time. Has anyone solved this in Java? If not, what languages are successful solvers using?
When I click on Solutions I see “Bash” as the one listed. So, I started looking into how to solve this in Bash. Specifically, I looked into using the arctan function a() along with bc (the arbitrary precision decimal arithmetic command). This worked for sequentially solving for pi digits, but quickly became slow as the number of digits increased.
Thanks for any pointers.
1 Like
The only solution published is in C++. It is wrapped in Bash to get access to the GMP library.
I can’t find any examples of using a bash script to execute custom C++ code in Codingame… that approach seems like a hack to work around Codingame. Is it not possible to solve this in a straightforward way with the supported languages and libraries?
Sure, this was just a lazy way to avoid implementing bignum in C++. No need to do it that way.
But if you are curious, you can do it like this:
I would be interested in seeing a pure solution to this, but I’m not sure it is possible.
Python code works, but is way too slow to have any chance of passing the tests.
In Rust, the two pure Rust bignum libs I tried are also too slow (and would be a pain to inline), only the GMP-based one was fast enough. The nice thing is that you can call directly into GMP without needing to wrap in bash, this is what my solution does.
I’m pretty sure that a “random” bignum implementation in C/C++ would also be too slow. Even inlining GMP code might not be enough because of the optimization limits when all you can use are #pragmas.
Finally, wrapping in bash “cheats” in two ways : not only do you hack around the platform specs, but you get the 5s bash time limit instead of the 0.5s of C/C++ (OK, you need the compilation time).
Are the “per language time limit” values documented somewhere? What are the limits for other languages?
Are the “per language time limit” values documented somewhere?
Maybe, but I don’t know where 
I tested that when a Python version was too slow, but it also failed in C++, needed another algorithm (I think it was an NP-hard problem that had “easy” cases if tackled from the right angle). This is where I measured a bit, and convinced myself of the .5s vs 5s for Python, which I think is the same for other interpreted languages. I’m pretty sure C# is 1s, but won’t bet the house on it.