Quiz for random boolean expressions

Question

Inspired by the various quiz programs on this site, as well as Simon Tatham's puzzle collection, I thought I'd write a quiz that constructs its questions automatically and randomly. A typical session looks like this:

What is (true and false)? false
What is (true and true)? true
What is (true implies false)? false
What is (false or false)? false
What is not true? false
What is (true and (false or false))? false
What is (true and (false implies false))? true
What is ((true implies false) xor false)? true
Wrong.
What is (true or (true implies false))? true
What is (true or (false and false))? true
What is (((true or true) and false) or true)? true

The longer you play, the more complicated the expressions get. Every time after answering 5 questions correctly, the expressions get 1 operator longer.

A special feature is that the expressions are constructed in a way that guarantees equal probabilities for the outcomes true or false. For the And, Or and Implies operations, this was already a bit harder than I had expected at first. The Xor probabilities took me a bit longer to get right. My first guess was that it should be simpler than the other operators since xor is associative and commutative and already has a 50:50 distribution. It took me a few months until I sat down, did the math again and suddenly had the correct solution.

Here is the code implementing the whole quiz:

package de.roland_illig.boolquiz

import java.util.Random
import kotlin.math.sqrt

/**
 * A boolean expression is either a literal value,
 * or a complex expression consisting of at least one subexpression.
 */
interface Expr {
    fun eval(): Boolean
}

/** A boolean literal is either "true" or "false". */
class Literal(private val value: Boolean) : Expr {
    override fun eval() = value
    override fun toString() = "$value"
}

/** Not negates its argument. */
class Not(private val a: Expr) : Expr {
    override fun eval() = !a.eval()
    override fun toString() = "$a".run {
        if (startsWith("(")) "not$this" else "not $this"
    }
}

/**
 * There are 16 binary boolean operators, of which only a few
 * are interesting enough to be given a name.
 *
 * Each of these operators needs to handle 4 different cases for its arguments.
 * The operators differ in the number of cases in which they return true
 * (Or returns true in 3 cases, while And returns true only in a single case.)
 */
enum class BinOp(val sym: String) {
    And("and"),
    Or("or"),
    Impl("implies"),
    Xor("xor");

    fun eval(a: Boolean, b: Boolean): Boolean {
        return when (this) {
            And -> a && b
            Or -> a || b
            Impl -> !a || b
            Xor -> a != b
        }
    }

    /**
     * Returns the probabilities for the two arguments of a binary expression,
     * so that the resulting expression becomes true with the given probability.
     *
     * To generate such a random expression, the probabilities of the operands
     * are adjusted by a bias, pointing upwards for And (since it only becomes
     * true in 1/4 cases), or downwards for Or and Impl (since it becomes true
     * in 3/4 cases), or really complicated for Xor.
     */
    fun probabilities(prob: Double, rnd: Random): Pair<Double, Double> {
        return when (this) {
            And -> sqrt(prob).let { Pair(it, it) }
            Or -> (1.0 - sqrt(1.0 - prob)).let { Pair(it, it) }
            Impl -> sqrt(1.0 - prob).let { Pair(it, 1.0 - it) }
            Xor -> probabilitiesXor(prob, rnd)
        }
    }

    /**
     * Returns the probabilities for the two arguments of an xor expression,
     * so that the resulting expression becomes true with the given probability.
     *
     * The current implementation aims at keeping the returned probabilities
     * "interesting". It would have been easy to just return `Pair(0.0, prob)`
     * or `Pair(prob, 0.0)`, but that would have been boring.
     *
     * Instead, the returned probabilities are as close together as possible.
     * This involves solving a quadratic equation with center point 0.5. Since
     * Pair(0.3, 0.3) produces the same output probability as Pair(0.7, 0.7),
     * it is decided randomly whether to return high or low probabilities.
     */
    private fun probabilitiesXor(prob: Double, rnd: Random): Pair<Double, Double> {
        val pm = if (rnd.nextBoolean()) +1.0 else -1.0
        return if (prob < 0.5) {
            val a = 0.5 + pm * sqrt(0.25 - 0.5 * prob)
            Pair(a, a)
        } else {
            val a = 0.5 + pm * sqrt(0.25 - 0.5 * (1.0 - prob))
            Pair(a, 1.0 - a)
        }
    }
}

class Binary(private val a: Expr, private val op: BinOp, private val b: Expr) : Expr {
    override fun eval() = op.eval(a.eval(), b.eval())
    override fun toString() = "($a ${op.sym} $b)"
}

/**
 * Constructs a random boolean expression containing [deg] operators
 * that evaluates to true with probability [prob].
 */
fun construct(deg: Int, rnd: Random, prob: Double): Expr {

    if (deg == 0) return Literal(rnd.nextDouble() < prob)

    val opIndex = rnd.nextInt(BinOp.values().size + 1)
    if (opIndex == 0) return Not(construct(deg - 1, rnd, 1.0 - prob))

    val leftDeg = rnd.nextInt(deg)
    val rightDeg = deg - 1 - leftDeg

    val op = BinOp.values()[opIndex - 1]
    val (leftProb, rightProb) = op.probabilities(prob, rnd)
    val left = construct(leftDeg, rnd, leftProb)
    val right = construct(rightDeg, rnd, rightProb)

    return Binary(left, op, right)
}

private enum class Answer { Correct, Wrong, EOF }

private fun question(difficulty: Int, rnd: Random): Answer {
    val expr = construct(difficulty, rnd, 0.5)

    print("What is $expr? ")
    val answer = readLine() ?: return Answer.EOF

    if (answer != "true" && answer != "false") {
        println("Answer must be either \"true\" or \"false\".")
        return Answer.Wrong.also { }
    }

    if (answer.toBoolean() == expr.eval()) return Answer.Correct

    println("Wrong.")
    return Answer.Wrong
}

private fun round(difficulty: Int, rnd: Random): Boolean {
    var correct = 0
    while (correct < 5) {
        when (question(difficulty, rnd)) {
            Answer.Correct -> correct++
            Answer.Wrong -> Unit
            Answer.EOF -> return false
        }
    }
    return true
}

fun main() {
    val rnd = Random()
    for (difficulty in 1..Integer.MAX_VALUE)
        if (round(difficulty, rnd).not()) return
}

I also added a few automatic tests:

package de.roland_illig.boolquiz

import org.assertj.core.api.Assertions.assertThat
import org.assertj.core.data.Offset
import org.assertj.core.data.Percentage
import org.junit.Test
import java.util.Random
import kotlin.math.sqrt

class BoolQuizKtTest {

    @Test
    fun testConstruct() {
        assertThat(construct(0, Random(0), 0.5).toString())
                .isEqualTo("false")

        assertThat(construct(0, Random(4096), 0.5).toString())
                .isEqualTo("true")

        assertThat(construct(1, Random(0), 0.5).toString())
                .isEqualTo("not false")

        assertThat(construct(1, Random(4096), 0.5).toString())
                .isEqualTo("(true xor false)")

        assertThat(construct(7, Random(0), 0.5).toString())
                .isEqualTo("not((true or true) implies " +
                        "((false implies false) xor " +
                        "(true and (false xor true))))")

        assertThat(construct(7, Random(4096), 0.5).toString())
                .isEqualTo("(((true and true) and (false or true)) " +
                        "xor (false or not(true implies false)))")
    }

    @Test
    fun testConstructProbability() {
        var falseCount = 0
        var trueCount = 0

        val rnd = Random(0)
        for (i in 0 until 2_000_000) {
            val expr = construct(1, rnd, 0.3)
            if (expr.eval())
                trueCount++
            else
                falseCount++
        }

        assertThat(falseCount / (trueCount + falseCount).toDouble())
                .isCloseTo(0.70, Percentage.withPercentage(2.0))
        assertThat(trueCount / (trueCount + falseCount).toDouble())
                .isCloseTo(0.30, Percentage.withPercentage(2.0))
    }

    @Test
    fun testConstructProbabilityAnd() {
        var falseCount = 0
        var trueCount = 0

        val rnd = Random(0)
        for (i in 0 until 2_000_000) {
            val a = rnd.nextDouble() < sqrt(0.3)
            val b = rnd.nextDouble() < sqrt(0.3)
            val and = a && b
            if (and)
                trueCount++
            else
                falseCount++
        }

        assertThat(falseCount / (trueCount + falseCount).toDouble())
                .isCloseTo(0.70, Percentage.withPercentage(2.0))
        assertThat(trueCount / (trueCount + falseCount).toDouble())
                .isCloseTo(0.30, Percentage.withPercentage(2.0))
    }

    @Test
    fun testConstructProbabilityXor() {
        val rnd = Random(12345678)
        for (percent in 0..100) {
            val pOutExpected = percent / 100.0
            val (pa, pb) = BinOp.Xor.probabilities(pOutExpected, rnd)
            val pANotB = pa * (1.0 - pb)
            val pBNotA = pb * (1.0 - pa)
            val pOutActual = pANotB + pBNotA
            assertThat(pOutActual)
                    .withFailMessage("$percent")
                    .isCloseTo(pOutExpected, Offset.offset(1.0e-14))
        }
    }

    @Test
    fun testEval() {
        assertThat(Literal(false).eval())
                .isEqualTo(false)
        assertThat(Literal(true).eval())
                .isEqualTo(true)

        assertThat(Not(Literal(false)).eval())
                .isEqualTo(true)
        assertThat(Not(Literal(true)).eval())
                .isEqualTo(false)

        assertThat(Binary(Literal(false), BinOp.And, Literal(true)).eval())
                .isEqualTo(false)
        assertThat(Binary(Literal(true), BinOp.And, Literal(true)).eval())
                .isEqualTo(true)

        assertThat(Binary(Literal(false), BinOp.Or, Literal(false)).eval())
                .isEqualTo(false)
        assertThat(Binary(Literal(false), BinOp.Or, Literal(true)).eval())
                .isEqualTo(true)

        assertThat(Binary(Literal(true), BinOp.Impl, Literal(false)).eval())
                .isEqualTo(false)
        assertThat(Binary(Literal(false), BinOp.Impl, Literal(false)).eval())
                .isEqualTo(true)

        assertThat(Binary(Literal(true), BinOp.Xor, Literal(true)).eval())
                .isEqualTo(false)
        assertThat(Binary(Literal(false), BinOp.Xor, Literal(true)).eval())
                .isEqualTo(true)
    }
}

Answer 1

Very fun game you created here, I like it. Your calculations for the probabilities are also impressive, and well tested.

---

Some small suggestions:

• UI improvement: Print a message when "leveling up".
• Answer.Wrong.also { } has a redundant .also that can be removed.
• Enum constants are usually written in uppercase, making it AND, OR, XOR, IMPLIES.
• The usage of Answer has a EOF result, which gives me a feeling that whether or not the user gives the correct answer could be instead represented as the nullable type Boolean?
• The import java.util.Random can be changed to kotlin.random.Random, which you can access a default instance from by using kotlin.random.Random.Default or by using a constructor through kotlin.random.Random(seed).
• Many names have been unnecessarily shortened, prob -> probability, rnd -> random, deg -> ??? (honestly not sure what this is short for), Expr -> Expression...
• Code organization:
  • Separate the game model from the view, so that it becomes easier to create other clients (REST service or Desktop application for example).
  • Create more classes instead of having many methods as top-level functions.

---

Some possible changes that could be done but that not necessarily improves anything:

• Expr could be changed to typealias Expr = () -> Boolean
• A toString method is mostly for debugging and logging purposes and not to be displayed to users. It could be separated to a different method.

• All your expressions have a toString and eval method, but the constant values of these are known already on creation. This would make it possible to do something like the following:

  interface Expression {
      val text: String
      val eval: Boolean
  }
  
  /** A boolean literal is either "true" or "false". */
  class Literal(override val value: Boolean) : Expression {
      override val text: String = eval.toString()
      override val eval: Boolean = value
  }
  

  Again though, this doesn't necessarily improve anything as your code is already very readable by having both a toString and eval method.

I also tried to experiment with other approaches, such as making a class for an expression and to have a ExpressionFactory that could create both literals, the not function, and the binary expressions, but in the end I felt that it became unnecessary complex.

Summary

Some organization of the code could be improved to better separate between the game logic and the user interaction, and some different minor improvements as mentioned in the beginning. But overall, nicely done and fun game.

Answer 2

What stands out to me is the use of when in BinOp instead of object oriented patterns. The eval and probabilities methods could be replaced with lambda properties and/or by overriding abstract methods.

For example:

enum class BinOp(val sym: String, val eval: (Boolean, Boolean) -> Boolean) {
    // For the eval property use a lambda
    And("and", { a, b -> a && b }) {
        override fun probabilities(prob: Double, rnd: Random): Pair<Double, Double> =
            sqrt(prob).let { Pair(it, it) }
    },
    // .. or reference an existing method
    Xor("xor", Boolean::xor) {
        override fun probabilities(prob: Double, rnd: Random): Pair<Double, Double> {
            val pm = if (rnd.nextBoolean()) +1.0 else -1.0
            return if (prob < 0.5) {
                val a = 0.5 + pm * sqrt(0.25 - 0.5 * prob)
                Pair(a, a)
            } else {
                val a = 0.5 + pm * sqrt(0.25 - 0.5 * (1.0 - prob))
                Pair(a, 1.0 - a)
            }
        }
    };

    abstract fun probabilities(prob: Double, rnd: Random): Pair<Double, Double>
}

---

Here a quick example how to group the methods together:

typealias booleanOperation = (Boolean, Boolean) -> Boolean
typealias probabilityCalc = (Double, Random) -> Pair<Double, Double>


fun andEval(a: Boolean, b: Boolean) = a && b 
fun xorEval(a: Boolean, b: Boolean) = a xor b 


fun andProb(prob: Double, rnd: Random) = 
    sqrt(prob).let { Pair(it, it) } 

fun xorProb(prob: Double, rnd: Random): Pair<Double, Double> {
    val pm = if (rnd.nextBoolean()) +1.0 else -1.0
    return if (prob < 0.5) {
        val a = 0.5 + pm * sqrt(0.25 - 0.5 * prob)
        Pair(a, a)
    } else {
        val a = 0.5 + pm * sqrt(0.25 - 0.5 * (1.0 - prob))
        Pair(a, 1.0 - a)
    }
}


enum class BinOp(val sym: String, val eval: booleanOperation, val probabilities: probabilityCalc) {
    And("and", ::andEval, ::andProb),
    Xor("xor", ::xorEval, ::xorProb);
}