CS2030 Practical Assessment #2

Back to homepage

Random Number Generation

Random numbers that are used in computer simulations are produced via a pseudo-random generator algorithm that appears random but actually deterministic. Given an initial seed value, the same sequence of random values will always be generated.

Once such algorithm is the linear congruential generator (LCG) which produces pseudo-random numbers using

X_n+1 = (a . X_n + c) mod m

where given a start seed X₀, the sequence X₁, X₂, ... can be generated.

As an example, when a = 3, c = 3 and m = 7, a seed value of X₀ = 1 will generate the sequence 6, 0, 3, 5, 4, 1, 6, ...

Task

Your task is to design a computation context for pseudo random number generation, and make use of it for a simulation.

Take Note!

This task comprises a number of levels. You are required to complete ALL levels.

The following are noteworthy constraints imposed on this task.

• Write each class or interface in its own file. DO NOT use single letter names for classes or interfaces. DO NOT make your classes final.
• Ensure that ALL object properties and class constants are declared private final
• Ensure that ALL classes/interfaces are NOT cyclic dependent.
• ONLY the following java libraries ARE allowed:
  • functional interfaces from java.util.function
• The following are NOT allowed:
  • var, null, default, enum
  • instanceof (except checking for an instance of its own class)
• DO NOT use bounded type parameters or bounded wildcards.
• DO NOT define anonymous inner classes or method references ::
  Define lambdas instead.
• Other usual restrictions:
  • Use only &&, || and ! in logical expressions. DO NOT use bitwise operators.
  • You are NOT allowed to use * wildcard imports.
  • You are NOT allowed to define array constructs, e.g. String[] or using ellipsis, e.g.String...
  • You are NOT allowed to perform string processing using methods from String, StringBuffer, StringBuilder, etc.
  • You are NOT allowed to use exception handling
  • You are NOT allowed to use Java reflection, i.e. Object::getClasses and other methods from java.lang.Class

In the following level specifications, you will be guided on the classes and non-private methods to define. DO NOT create any other classes. Any other method you create must be declared private. However, constructors can be non-private as you deem necessary.

The following classes has been provided for you. DO NOT replace them with your own versions.

• Pair class (not a record, but behaves similarly)
• Maybe class
• InfList class (to be used in level 5 only)

To automatically generate HTML documentation from the comments, issue the command: $ javadoc -d doc InfList.java Maybe.java Pair.java You may then navigate through the documentation from allclasses-index.html found in the doc directory.

Level 1

Write the RandInt class with a factory method of that takes in a function (e.g. a linear congruential generator) and returns a RandInt object with the function encapsulated within.

A random integer value is generated by terminating the pipeline with the seed operation that takes in an integer as the seed value.

jshell> RandInt.of(x -> x + 1)
$.. ==> RandInt

jshell> RandInt.of(x -> x + 1).seed(1)
$.. ==> 2

jshell> RandInt.of(x -> x + 1).seed(2)
$.. ==> 3

jshell> RandInt lcg337 = RandInt.of(x -> (3 * x + 3) % 7)
lcg337 ==> RandInt

jshell> lcg337.seed(1)
$.. ==> 6

jshell> lcg337.seed(1)
$.. ==> 6

jshell> lcg337.seed(6)
$.. ==> 0

jshell> lcg337.seed(0)
$.. ==> 3

Level 2

Include the map method to allow a RandInt object to be mapped. We first demonstrate mapping to a different integer value.

jshell> RandInt.of(x -> x + 1).map(x -> x % 2).seed(1)
$.. ==> 0

jshell> RandInt.of(x -> x + 1).map(x -> x % 2).seed(2)
$.. ==> 1

jshell> lcg337.map(x -> x % 2).seed(1)
$.. ==> 0

jshell> lcg337.map(x -> x % 2).seed(6)
$.. ==> 0

jshell> lcg337.map(x -> x % 2).seed(0)
$.. ==> 1

From the test case of using the lcg337 generator, we observe that

• seeding the generator with 1 results in the value 6 (as shown in level 1), then 6 % 2 gives 0
• seeding the generator with 6 results in the value 0 (as shown in level 1), then 0 % 2 gives 0
• seeding the generator with 3 results in the value 3 (as shown in level 1), then 3 % 2 gives 1

The map function should also allow mapping to a value of any type. For simplicity of implementation as well as grading, do not use bounded wildcards.

jshell> lcg337.map(x -> "[" + x + "]").seed(1)
$.. ==> "[6]"

jshell> lcg337.map(x -> "[" + x + "]").seed(6)
$.. ==> "[0]"

jshell> lcg337.map(x -> "[" + x + "]").map(x -> x.length()).seed(1)
$.. ==> 3

jshell> lcg337.map(x -> "[" + x + "]").map(x -> x.length()).seed(6)
$.. ==> 3

Take note that RandInt should NOT be generic; however, map will return a generic Rand object.

jshell> RandInt r = lcg337
r ==> RandInt

jshell> RandInt<Integer> r = lcg337
|  Error:
|  type RandInt does not take parameters
|  RandInt<Integer> r = lcg337;
|  ^--------------^

jshell> lcg337.map(x -> "[" + x + "]")
$.. ==> Rand

jshell> lcg337.map(x -> x + 1)
$.. ==> Rand

Sample runs below demonstrate the application of the laws of the Functor involving map.

jshell> lcg337.map(x -> x).seed(1)
$.. ==> 6

jshell> Function<Integer,String> r = x -> "[" + x + "]"
r ==> $Lambda..

jshell> Function<String,String> s = x -> x + x
s ==> $Lambda..

jshell> lcg337.map(r).map(s).seed(1)
$.. ==> "[6][6]"

jshell> lcg337.map(s.compose(r)).seed(1)
$.. ==> "[6][6]"

Level 3

So far we have generated only one random value. We shall now generate a sequence of random values via flatMap.

jshell> lcg337.seed(1)
$.. ==> 6

jshell> lcg337.flatMap(x -> lcg337).seed(1)
$.. ==> 0

Here is an explanation of what happens when the above pipeline is executed.

• The first Rand object is seeded with 1 and generates 6
• By pipelining with a flatMap, the value of 6 from the first Rand object is then used as the seed for the other Rand object provided by flatMap.
• Hence, the outcome of the pipeline is 0, i.e. the result of running the lcg337 generator twice with an initial seed value of 1.

Below is an example of how we can capture the sequence of values generated as a string with map.

jshell> lcg337.map(x -> x.toString()).seed(1)
$.. ==> "6"

jshell> Function<String,Rand<String>> f = x -> lcg337.map(y -> x + y)
f ==> $Lambda..

jshell> lcg337.map(x -> x.toString()).flatMap(f).seed(1)
$.. ==> "60"

jshell> lcg337.map(x -> x.toString()).flatMap(f).flatMap(f).flatMap(f).seed(1)
$.. ==> "6035"

Using flatMap allows us to have different random number generator functions in a single pipeline, i.e. the value generated from the previous generator can be used as seed for the next generator. Below is an example showing lcg337 followed by a simple increment generator y -> y + 1.

jshell> lcg337.map(x -> x.toString()).
   ...> flatMap(x -> RandInt.of(y -> y + 1). // increment generator
   ...> map(y -> x + y)).seed(1)
$.. ==> "67"

Here is lcg337 followed by a series of incremental generators.

jshell> Function<String,Rand<String>> g = x -> RandInt.of(y -> y + 1).map(y -> x + y)
g ==> $Lambda..

jshell> lcg337.map(x -> x.toString()).flatMap(g).flatMap(g).flatMap(g).seed(1)
$.. ==> "6789"

Sample runs below demonstrate the application of the laws of the Monad involving flatMap.

jshell> Function<Integer,Rand<Integer>> id = x -> RandInt.of(y -> y) // identity generator
id ==> $Lambda..

jshell> lcg337.seed(1)
$.. ==> 6

jshell> lcg337.flatMap(id).seed(1)
$.. ==> 6

jshell> Function<Integer,Rand<Integer>> h = x -> lcg337.map(y -> x + y)
h ==> $Lambda..

jshell> id.apply(1).flatMap(h).seed(1)
$.. ==> 7

jshell> h.apply(1).seed(1)
$.. ==> 7

jshell> lcg337.map(x -> x.toString()).flatMap(f).flatMap(g).seed(1)
$.. ==> "601"

jshell> lcg337.map(x -> x.toString()).flatMap(x -> f.apply(x).flatMap(g)).seed(1)
$.. ==> "601"

Once again you are reminded that for simplicity of implementation and grading, do not use bounded wildcards.

Level 4

Now we need to ensure the minimal evaluation of our computation context.

jshell> RandInt lcg337 = RandInt.of(x -> { 
   ...>    int z = (3 * x + 3) % 7; 
   ...>    System.out.println("lcg:" + z); return z;})
lcg337 ==> RandInt

jshell> lcg337.seed(1)
lcg:6
$.. ==> 6

jshell> Function<Integer,Integer> j = x -> { 
   ...>    System.out.println("beep"); return x + 10;}
j ==> $Lambda..

jshell> lcg337.map(j).seed(1)
lcg:6
beep
$.. ==> 16

jshell> lcg337.map(j).map(j).seed(1)
lcg:6
beep
beep
$.. ==> 26

The following is a check on the minimal evaluation of flatMap.

jshell> Function<Integer,Rand<Integer>> k = x -> {
   ...>    System.out.println("beep"); 
   ...>    return lcg337.map(y -> x + y);}
k ==> $Lambda..

jshell> lcg337.flatMap(k).seed(1)
lcg:6
beep
lcg:0
$.. ==> 6

jshell> lcg337.flatMap(k).flatMap(k).seed(1)
lcg:6
beep
lcg:0
beep
lcg:3
$.. ==> 9

Level 5

Let us use our random number generator to simulate a simplified version of the birthday paradox.

How many people must there be in a group so as to have a fifty percent chance of having two persons with the same birth month?

In this example, we shall use the following linear congruential generator:

jshell> RandInt lcg31511 = RandInt.of(x -> (31 * x + 31) % 511)
lcg31511 ==> RandInt

In level5.jsh, write a function sameMonth that takes in a RandInt generator gen, a group size n, and seed value for random number generation s, and returns true if there are at least two people in the group with the same sameMonth, or false otherwise.

Note that for each random number generated x, the expression x % 12 will result in a value between 0 and 11 which can be used to represent the month. You will need to follow this strictly; otherwise the outcome will not be the same. Moreover, do not include the seed as the first value of the random sequence; otherwise the first value is not random.

jshell> sameMonth(lcg31511, 4, 1)
$.. ==> true

jshell> InfList.iterate(0, x -> x + 1).
   ...> takeWhile(x -> x < 20).
   ...> map(x -> new Pair<>(x, sameMonth(lcg31511, 4, x))).
   ...> forEach(x -> System.out.println(x))
Pair[t=0, u=true]
Pair[t=1, u=true]
Pair[t=2, u=true]
Pair[t=3, u=false]
Pair[t=4, u=true]
Pair[t=5, u=true]
Pair[t=6, u=true]
Pair[t=7, u=false]
Pair[t=8, u=true]
Pair[t=9, u=true]
Pair[t=10, u=false]
Pair[t=11, u=true]
Pair[t=12, u=true]
Pair[t=13, u=false]
Pair[t=14, u=false]
Pair[t=15, u=false]
Pair[t=16, u=true]
Pair[t=17, u=false]
Pair[t=18, u=false]
Pair[t=19, u=false]

The above shows the simulation for twenty trials. As the simulation trials increase, the probability of two person in the group having the same birth month converges. Repeating the simulation for different group sizes n, one can find the minimum group size with a fifty percent chance of two persons with the same birth month. This is left as an extra exercise for you.