Course: JavaScript

Progress (0%)

# Exercise: Random Picks

Exercise 12 Easy

Prerequisites for the exercise

## Objective

Create a function to pick a random integer from a given arithmetic sequence.

## Description

In the previous exercise, Sequence In Range, we defined a function printSequence() to print a sequence that starts at a given integer a, proceeds with a common difference d, and ends before an integer b (exclusive).

If you've not attempted to solve the exercise, it's recommended that you do so because this exercise follows from it.

Let's say that a = 1, b = 10, and d = 1. This gives us the following sequence:

1, 2, 3, 4, 5, 6, 7, 8, 9

If we want to randomly pick one integer from this sequence, what could it be? Well, since it's random, it could be anything. 1? Why not. 2? Probably. 9? Probably. 5? You get it.

In this exercise, you have to create a function randomPick() which has the same parameters as printSequence(), just that it doesn't print anything but instead returns a random integer from the underlying sequence.

For example, calling randomPick(1, 10, 1) would return any integer between 1 and 10 (exclusive). Similarly, randomPick(10, 100, 25) would return any integer from the sequence 10, 35, 60, and 85.

As before, if the parameters are such that there's no existing sequence (which we discussed in the Sequence In Range exercise), the function should treat this case specially. In particular, the function should return null (to signify that there's simply nothing to randomly pick).

Here are a couple of usages of randomPick():

randomPick(1, 10, 1)
5
randomPick(1, 10, 1)
9
randomPick(1, 10, 1)
1
randomPick(10, 100, 25)
10
randomPick(10, 100, 25)
85
randomPick(10, 10, 25)
null
randomPick(1, 10, -1)
null

In the second-last statement, since the first two arguments (corresponding to a and b) are the same, the function returns null as there's no sequence to consider.

Similarly, in the last statement, since the first two arguments represent an increasing sequence (starting at a smaller value and ending at a larger one), the d parameter must be positive. However, since it's negative, null is returned.

## New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-12-Random-Picks and put the .html solution files for this exercise within it.

## Solution

The simplest solution to this exercise would be to augment the definition of printSequence() from the Sequence In Range exercise.

Here's the printSequence() function:

function printSequence(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
document.write('Nothing to print');
return;
}
for (var x = a; Math.sign(d) * (x - b) < 0; x += d) {
var sep = ', ';
if (x === a) {
sep = '';
}
document.write(sep + x);
}
}

In order to return a random integer from the underlying sequence, we just ought to address two cases:

• Return null when the parameters represent an empty/non-existing sequence.
• Return a random element from the constructed list of numbers.

The first case is trivial — return null from the if conditional.

Let's accomplish this right after defining the function randomPick():

function randomPick(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
return null;
}
}

Now, we're only left with the second case, i.e. to return a random element from the constructed list of numbers. This is easy as well.

In printSequence(), we right away print the current item of the sequence. In randomPick(), however, we ought to push it to an array — let's call it nums — and then compute a random integer between 0 and n (exclusive), where n is the length of nums.

This random integer acts as the index of the element of nums to return.

Let's implement this now:

function randomPick(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
return null;
}
var nums = [];
for (var x = a; Math.sign(d) * (x - b) < 0; x += d) {
nums.push(x);
}
var randomIndex = Math.floor(Math.random() * nums.length);
return nums[randomIndex];
}

The randomIndex variable defined here stores a randomly-generated integer, as we discussed above, acting as the index of an element of nums to return. And in the end, this is exactly what's done in line 10.

Let's now test this function on a couple of values:

randomPick(1, 10, 1)
5
randomPick(1, 10, 1)
9
randomPick(1, 10, 1)
1
randomPick(10, 100, 25)
10
randomPick(10, 100, 25)
85
randomPick(10, 10, 25)
null
randomPick(1, 10, -1)
null

And this completes the exercise.

But one question remains to be answered: Is this implementation of randomPick() OK?

## An efficient solution

No doubt in that the function above always returns back an integer from the underlying sequence (represented by the given parameters); it never makes up values on its own.

However, gaze at the function for a second or two. Does it seem sensible to take the approach that we're taking right now?

In other words, is it wise enough to create a whole list modeling the sequence and only then extract a random element from it? Should we really be doing so?

Well, as it turns out, there is a quick mathematical trick, following from the theory of arithmetic sequences, that we can leverage in implementing randomPick() without generating a list of numbers whatsoever.

Yes, that's right! We can ditch the list completely. Pure math will instead take over and return a random integer from the sequence represented by the three given parameters of randomPick().

Let's appreciate this mathematical trick.

The general form of an arithmetic sequence's $i^{th}$ term is as follows:

$A(i) = a + di$

where $a$ is the initial term and $d$ is the common difference.

In randomPick(), we are given the maximum integer $b$ right before which the sequence should end. The formula above and this integer $b$ are of particular importance.

That is, we use the formula and $b$ to determine the largest possible value of $i$ for the sequence, where $i$ is known to start at $0$.

In randomPick(), we can then compute a random number between $0$ and this value of $i$ (exclusive) and then plug in the $i$ into the formula above to obtain the corresponding element $A(i)$ of the sequence.

Let's see how to compute this maximum $i$:

$\text{max} \space i = \lceil \dfrac{a - b}{d} \rceil$

The expression inside the ceil function is obtained by rearranging the formula given above for $A(i)$. The ceil function is used because $i$ should be an integer, and it can't be the lesser integer since we need to exclude any value that is equal to $b$.

Let's accomplish this in randomPick():

function randomPick(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
return null;
}
var randomIndex = Math.floor(Math.random() * Math.ceil((b - a)  / d));
return a + d * randomIndex;
}

The Math.ceil() expression is the same as the equation given above. As before, randomIndex represents a random integer denoting the index of an element of the underlying sequence to return.

This element is then computed using randomIndex and the arithmetic sequence's $i^{th}$ term formula: a + d * randomIndex.

And there you have it; an extremely efficient implementation of randomPick().

See how the list has gone away completely. Now when we call randomPick() with a given set of arguments, there's no memory consumed in generating a list to represent the sequence.

Besides memory, the implementation is even more swift is terms of run time. There is no for loop and no list to iterate over — the random element is picked, more or less, in constant time, by some simple yet beautiful mathematics.

"I created Codeguage to save you from falling into the same learning conundrums that I fell into."

— Bilal Adnan, Founder of Codeguage