Well well well, what do we have here, after skipping last week's challenge it's time for a new one this week.
Last week I checked and I saw that no one joined and by the end of the week I think I saw only one or two submissions so I thought if there aren't at least four the challenge gets cancelled. But I saw that in the end it still took place, submissions were checked and graded, good to know there isn't a minimum number of submissions required.
Now let's move to this week's challenge, for anyone reading this, we are working on @sergeyk 's challenge that can be found here SLC21 Week6 - Programming Games&Puzzles (part 2).
Image taken from Pixabay
What role do random numbers play in the computer world? How to turn them from "pseudo-random" into more random ones.
Most of the random numbers in "computer world" are not really random, these are more pseudo-randoms, they are likely to be predictable which is not wrong, these can still be used in numerous applications but don't act like the randomness you'd see in a dice roll for example.
Image taken from Pixabay
Random numbers play important roles in multiple applications, the first one that pops in my head is cryptography, they are used in cryptography to generate encryption and secure communications making it hard to predict or reproduce the keys.
Other aplications are:
- Testing and Debugging - helps developers identify bugs and vulnerabilities that would otherwise be hard to find
- Machine learning - the random data for training and testing
- Simulation/Modeling - simulate real world things (example: trafic flow or weather)
- Gaming - provides unpredictability and fairness
- Procedural Generation - creates dynamic content in the digital world (generating infinite worlds in games, generating a forest in games/movies, generating realistic clouds)
- Blockchain and Crypto - private/public keys generation
Now how can you turn a pseudo-random number into a truly random one? You'll have to add external sources from our world into the algorithm.
What external sources you could add, here are a few examples:
- Hardware Sensors - data from keyboard timings, temperature sensors, mouse movements
- User Interaction - the unpredictable user inputs
- Clock - tie the randomness with the time
- Dedicated Hardware - hardware that take into consideration electronic noise as an example
- Biometric Data - leverage random with your finger print as an example
As an example random.org generates random numbers from atmospheric noise, more details here on their page!
Write a random number generator. Explore it.
There is a simple random generation algorithm called Linear Congruential Generator which has a formula like this:
Screenshot from Wikipedia
Based on this we are creating our own formula to generate a random number, we'll do it in a pseudo-random way first and a true random after.
How does this work, well we define some constants at the top of our code, we are going to use these as our formula for generating the random number.
We create our function and give it a seed parameter, we are going to use this seed parameter to generate a new value each time we give it a new seed, using the same seed with our constants will give us the same random number.
The output looks like this for the value 33.
Now this is a pseudo-random generation, let's make it a true random and add an outside element, like the time.
This is a true random number, we added the currentTime which usually returns the number of seconds since 1st of January 1970 some Unix time can't remember exactly. Adding this value instead of our previous seed will result in a true random number since we are using an outside element, the time in this case.
This is the output as an example:
So on a short description how this was implemented, we added a few constants to create the formula, added a dynamic element to create the randomness and returned the formula to show the value.
"Deck of cards" - Find several ways to fill the array 1...N - 1 One way - one point.
--- --- --- Method 1 --- --- ---
First method we simply run a loop to N and put each element in an array, it will look like a "new bought pack of cards" where everything is well put and sorted. We get the output of a sorted array.
--- --- --- Method 2 --- --- ---
Same as the method above but we change the way we put the value inside the array, this time we are putting n-i value which will create a descending order in our array.
--- --- --- Method 3 --- --- ---
For this method I went and added the odd "cards" (numbers) on the even position and the even "cards" (numbers) on odd position.
I am using two variables to keep the odd and even numbers in memory and checking the array position allows me to know on which number I am (odd or even) and attribute the corresponding value.
This is the output
Now let's dive into some random methods.
--- --- --- Method 4 --- --- ---
The idea behind this isn't that hard to understand, I am using rand() % n + 1 to generate a random number between 1 and N, a loop to check if the value is already in the array, if it's unique it gets added otherwise we continue our search. And this goes on until the array is filled with N unique values. We are using time() as seed to always generate a different combination of randoms.
Output looks like this:
--- --- --- Method 5 --- --- ---
A "retarded" way because it one of the worst solutions, pick a random value check if the value is already present inside the array, if it is we generate another random number until we find one that hasn't been added yet, we found it and we add it. It works decently for small N but I gave it a value of 60 and the browser tab stopped responding and timed out after a minute or so.
The output looks like this:
--- --- --- Method 6 --- --- ---
In this case I defined a filled array and using two variables for indexes and while we loop through the array for each position we generate two random indexes that get swapped.
An output would look like this:
For this method while looping only to N if the randomness of indexes is not very unique you might end with elements that never get swapped, to increase the chances of a swap you can change the loop from i<N to i<N*5 or any other value, the bigger the more indexes get generated and more swaps take place.
Construct a table of the dependence of the number of operations when generating a deck of N cards for your methods.
I am not sure if I understand this correctly and we are looking for the Time complexity here, but if that's the case it should look like this.
| Method | Complexity | Operations |
|---|---|---|
| Method 1 | O(N) | N = 10 -> 10 |
| Method 2 | O(N) | N = 10 -> 10 |
| Method 3 | O(N) | N = 10 -> 10 |
| Method 4 | O(NxN) | N = 10 -> 100 |
| Method 5 | O(NxN) | N = 10 -> 100 |
| Method 6 | O(N) | N = 10 -> 10 |
If we are talking about the literal number of operations like looping, changing value, generating a random, a swap etc. then the table would look like this. I tried counting the operations taking place inside the loop, for each i in loop there are several things happening to create the array with it's values.
| Method | Operations | |
|---|---|---|
| Method 1 | Only 1 operation for each loop position -> We have N operations, if N = 5 we get 5 operations | |
| Method 2 | Only 1 operation for each loop position -> We have N operations, if N = 5 we get 5 operations | |
| Method 3 | Only 1 operation for each loop position -> We have N operations, if N = 5 we get 5 operations | |
| Method 4 | Multiple operations, generating a random, verify if the value is in the array, move the value in the array -> We have at least 3*N operations if we get all the values unique all the time, which is almost impossible, and the number based on how many duplicates we generate randomly | |
| Method 5 | Multiple operations inside the loops, we have at least N*N operations, N = 5 we get at least 25 operations | |
| Method 6 | 5 operations for each loop position, we get 5*N operations, if N = 5 we get 25 operations |
That was it for this week, I'd like to invite @r0ssi, @titans and @mojociocio to give it a try.
Until next challenge I wish you a great day.