Generate die rolls using coin flips

Question

Problem

I've seen this basic interview question in a couple of places, but never implemented it.

Create an algorithm to output a fair die roll (values between 1 and 6, inclusive), given a function that outputs the outcome of a fair coin toss (0 or 1).

Approach

The idea here is to use three coin flips to generate the binary values from 000 to 111 (0 to 7 in Base 10). Then, ignore the values 110 (6) and 111 (7) so that we are only considering the binary values from 000 to 101 (0 to 5 in Base 10).

Note that 110 and 111 will be the only values that start with two 1s, so any time the first two rolls start with two 1s we know to ignore the previous values and try rolling again.

If the first two rolls do not start with two 1s, then we roll a third time, concatenate the three values to form our binary representation and then convert the binary value into Base 10 (while adding one since the value will be 0-5 and we want 1-6).

Implementation Discussion

Most of my questions might be coming from the over-engineering part of my brain.

That part of my brain basically wants to create Enums for coin toss outcomes and for the die roll outcomes (DieRoll.ONE, DieRoll.TWO, etc.).

Partly because it feels kind've weird that getCoinToss returns an int when it really represents a binary (i.e. boolean) value. Is it better to return a boolean here? I thought about it, but ultimately ended up not doing so because I would've had to convert the booleans into 1s and 0s when generating the String binary representation.

Same thing (but to a lesser extent) with generateValue - the possible values are really 1-6.

Implementation

public class RandomDieValueGenerator {
    public static int generateValue() {
        int firstCoinToss = RandomDieValueGenerator.getCoinToss();
        int secondCoinToss = RandomDieValueGenerator.getCoinToss();

        if (firstCoinToss * secondCoinToss == 1) {
          return RandomDieValueGenerator.generateValue();
        }

        String binaryRepresentation = String.valueOf(firstCoinToss) + secondCoinToss + RandomDieValueGenerator.getCoinToss();
        return Integer.parseInt(binaryRepresentation, 2) + 1;
    }

    private static int getCoinToss() {
        return Math.toIntExact(Math.round(Math.random()));
    }
}

Answer 1

I think your solution still has some potential but you don't need an Enum for the #getCoinToss method because you don't have any advantage over using an Integer. Not using simple integers might even lead to your code getting more complex than it should, as you would have to implement some kind of way to convert the Integer to an Enum constant. This would be possible could affect the time complexity of your code even tho it would not be heavily noticable.

Binary

For handling the binary values I would not use an integer but instead a byte for obvious reasons:

The values of the two integral types are integers in the following ranges:

1. For byte, from -128 to 127
2. For int from -2147483648 to 2147483647

As you only need zero and one for representing binary data I would suggest using the "smaller" data type.

#generateValue Return Value

For this method, I would stick with an Integer as this method is public and might be used by other methods later on and an int is the most common data type. If you use a byte as the return value here you might have to cast the return value of this method when using it because most other methods don't use bytes as their arithmetic differs.

Still, you could use an Enum here which would have the advantage of the user not being able to create for example if-Statements that can't be true:

if (RandomDieValueGenerator.generateValue() == 7)

This problem would be solved if you provide an Enum for this return value because then, the user could only check if the return value of this method is one of the six defined possible enum constants.

Putting it all together

public class RandomDieValueGenerator {

    enum DieValue {
        ONE, TWO, THREE, FOUR, FIVE, SIX
    }

    public static DieValue generateValue() {
        int firstCoinToss = RandomDieValueGenerator.getCoinToss();
        int secondCoinToss = RandomDieValueGenerator.getCoinToss();

        if (firstCoinToss * secondCoinToss == 1) {
            return RandomDieValueGenerator.generateValue();
        }

        String binaryRepresentation = String.valueOf(firstCoinToss) + secondCoinToss + RandomDieValueGenerator.getCoinToss();
        return DieValue.values()[Integer.parseInt(binaryRepresentation, 2)];
    }

    private static byte getCoinToss() {
        return (byte) Math.toIntExact(Math.round(Math.random()));
    }
}

Answer 2

I would be wary of the recursive approach - just incase random decided to be really mean to you and cause a stack overflow exception. I would write a loop similar to this:

while(true){
    int firstCoinToss = RandomDieValueGenerator.getCoinToss();
    int secondCoinToss = RandomDieValueGenerator.getCoinToss();

    if (firstCoinToss * secondCoinToss == 1) {
      continue;
    }

    String binaryRepresentation = String.valueOf(firstCoinToss) + secondCoinToss + RandomDieValueGenerator.getCoinToss();
    return Integer.parseInt(binaryRepresentation, 2) + 1;
}

Answer 3

generateValue

The conversion to and from strings slows your method down, bitshifts are more appropiate (firstCoinToss<<2|secondCoinToss<<1|getCoinToss() returns the same result). As @Piers Williams already stated, an iterative approach is preferable. A possible implementation:

public static int generateValue() {
    int val = coinToss();
    while ((val ^= coinToss() << 2 | coinToss() << 1) >= 0b110) {}
    return val + 1;
}

In the context of the quoted task I would stick with int, documenting the possible return values should be sufficient (besides maybe renaming the method to something more meaningful like rollDice).

getCoinToss

Using Random#nextBoolean or Random#nextIntwould avoid quite a few calculations and thus would be significantly faster. Additionally the current approach will perform poorly if the Math#random method is accessed by many threads.

private static int coinToss() {
    return ThreadLocalRandom.current().nextInt() >>> -1;
}

In my opinion returning an int is the best option as the generateValue method requires ints, anything else would imply additional conversions.