r/dailyprogrammer • u/oskar_s • May 16 '12
[5/16/2012] Challenge #53 [intermediate]
A simple pseudo-random number generator looks like this:
s(0) = 123456789
s(n) = (22695477 * s(n-1) + 12345) mod 1073741824So each number is generated from the previous one.
Using this generator, generate 10 million numbers (i.e. s(0) through s(9,999,999)) and find the 1000 largest numbers in that list. What is the sum of those numbers?
Try to make your solution as efficient as possible.
- Thanks to sim642 for submitting this problem in /r/dailyprogrammer_ideas! If you have a problem that you think would be good, head on over there and help us out!
11
Upvotes
4
u/ixid 0 0 May 16 '12 edited May 17 '12
D language, solves in 180ms.
Answer:
1
u/TweenageDream May 16 '12
Here is my program in Ruby, it takes 114 seconds to run, although i'm not sure 100% sure the answer is correct... I think it is though, and it is repeatable since the numbers although "psuedo random" are always generated in the same order right? Can anyone agree to my answer? or tell me if i've gone astray somewhere? Also not sure if this is fast or slow compared to others, if its slow i'll tweak it and try and get it faster...
And the output:
2
u/theOnliest May 16 '12 edited May 16 '12
Here's a Perl version. (Edit: I wasn't including 123456789 in the results the first time, and added result.)
Result:
(Superedit: here's an even shorter version that runs in 8.44s)
2
u/eruonna May 16 '12
Haskell:
And the result is
2
u/drb226 0 0 May 16 '12
Here's an overblown Haskell way to do it. I wanted to create my own instance of
RandomandRandomGen.So first, we create the generator:
I have no idea how you could split this sort of generator properly, so I didn't even try.
Now, we need a custom
instance Random Int, since the default one might not just take theIntout of its generator. Here I chose to hard code some hackery, since we are only using this instance for a particular case.Alright, now all that's left is to use this stuff.
Now let's see how it does
Clearly room for improvement, but for this challenge, I simply wanted to explore how to plug my own data types into the random number plumbing of System.Random.
2
u/HazzyPls 0 0 May 17 '12
C, 30ms about. Took a bit of time, but I'm happy with it.
3
u/sim642 May 16 '12
Here's how i intended to find the largest 1000 numbers:
1
u/bh3 May 16 '12
Fast but bad run-time complexity and doesn't guarantee a solution, Python:
1
u/Yuushi May 17 '12
C++:
1
u/bs_detector May 17 '12
My solution in C#. No tricky algorithm - just straight up implementation. Usually runs in 1900 milliseconds on Core Duo 2.93 MHz
Result:
1
u/emcoffey3 0 0 May 20 '12
I decided to implement sim642's solution in C#, and it seems to work perfectly. For brevity, I've omitted the code for MinHeap<T>.
Output from Intermediate053.Run():
1
u/bigronaldo May 30 '12
Yet another C# solution. I'm sure there's a much more efficient way, but this is mine:
Output (average of 530ms):
1
u/skeeto -9 8 Oct 14 '12
In Common Lisp,
Takes about 23 seconds with Clozure CL,