3
\$\begingroup\$

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)
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.