Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @WIlChrist,validated by @nikgaevoy,@NinjaFoxYT and @presidentaz.
If you have any issues, feel free to ping them.
2 Likes
Is this even possible in clojure ? All tests pass, but last one timeouts, already sped up everything I could.
Measures times (online):
Test 1: 31.218469 ms
Test 2: 22.809547 ms
Test 3: 57.151565 ms
Test 4: 127.281113 ms
Test 5: 93.632799 ms
Test 6: 785.542012 ms
Measured time for test 7 (own computer): 28128.511991 ms
Did you pre-compute prime numbers before trying combinations ?
Yes, and I generate a single set of primes for the whole test.
Ok, you did what you were supposed to do.
Are you sure you already sped up everything you could ? How do you compute your prime numbers ?
I read every inputs, then I generate a sieve (eratosthenes hash-map) starting at 2 and ending at the biggest sum-input. Removing a multiple of a number from the sieve start at number*number, iterating from 3 with a step of 2 (2 being handled before hand to speed-up the loop, same for generating couples). Couples are generated by checking if (sum - primeNumber) is prime, then numberLimit is set to (sum - primeNumber). All functions are memoized.
Switching to vector to see if there’s any improvements.
I could go for Atkin sieve but I doubt it will cut 20+ seconds, and seems a bit harder for a puzzle tagged as easy.
The sieve of Eratosthenes is enough (I mean it works with me, and all solutions I can see are based on it). The only difference is that I precompute before reading inputs.
I’m sorry I can’t help you more than this.
It’s definitely possible, I just did it and shared it. Only used a transient vector for filling the sieve that I then cast to persistent once I’ve finished. All of this can be done before reading any input. And by the way the puzzle is medium not easy.
The pseudo code of the sieve would be something like (you can probably find a better one by googling):
Summary
→ Initialize a vector “primes” of N = 1000001 elements (from 0 to 1000000 since that’s the upper-bound of the puzzle), the first two being False (0 and 1 are not prime) and the rest True
→ For i from 2 to (upper-bound depending on N) do:
→ If prime i is True then
→ For j from 2*i to (included) N with step n do: set prime j to False
Once you have that the rest should be doable.
All the test cases inside the IDE are working, but number 2 is failing when submitting the solution.
Any idea what I can do? I generate all primes <= 1 million.
Try the small even numbers from 4 to 20 and see if your code generates the correct answers.
I switched to vector-sieve instead of hashmap-sieve, no timeout anymore.
Just spent hours figuring out why the prime number 14369 got removed in vector version: had a debug condition if trying to remove that number → exit, else if already set to false → exit with another message.
That bug caused 2 couples to not be found for last test.
Program exited with 2nd condition, not first.
Problem only occured with vector version of the sieve (only init function changed) because i did return if (contains? sieve multiple) which seems to cause the multiple to reach 2^32, doing (> multiple (count sieve)) fixed the issue. Now last test pass.
First error between hashmap and vector implementation occured with a sieve of size 146544 (prime number 14369, sieve size 20000 went fine for 14369), looks like the inappropriate condition caused an overflow in key., got to dig deeper to understand, been learning clojure for a few days only.
Final word: don’t use hashmap, use pre-conputed vectors, use vector functions, not ISeq functions
PS: you’re right, it’s a medium puzzle
I can see your code is much smaller than mine, how long have you been doing clojure ?
How would you improve mine ? (don’t worry, i always try to make it clean :p)
You don’t have to generate up to 1 million, store inputs, and generate sieve for the biggest of those input, you can keep the same sieve, it’s just a lookup table but it has to be big enough to satisfy the biggest sum.
You haven’t shared your solution so I can’t comment on your implementation nor the bugs.
Code size is far from being a good indicator for proficiency anyway lol.
I haven’t spent too much time with clojure but I’m somewhat familiar with other functional languages. I just translated my python solution with a couple googlings for specific clojure syntax.
Solutions have to be manually shared ? Thought it was automatic once we reach 100%
I copied the URL, I better add you as friend so we don’t pollute the chat here, will be more practical if you have feedbacks.
Cheers.
You can configure that in your profile (auto publish solutions : ON or OFF)
It’s set to true 
Hello. Are there any tips for passing the last test for C++? If I try to create a hash table(unordered map) or a vector for number greater than 10,000, the test fails with a “process has time out” error.
Maybe your sieve is too slow.
Try to find a faster algorithm.
I’m using Python (a slow language compared to C++) and I passed all the validators.
Try with a C array, instead of a map. I had the same problem.
I can get a simple version using vectors to pass without any optimisation. With optimisation pragmas set (using the order to break early) / unordered_set (needed to use reserve in order to get the initial size correct) worked as well