2
\$\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. For the Xor operation 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. Up to now the distribution of the operands is boring.

Giving both operands roughly equal probabilities of evaluating to true or false is much more difficult than expected. From what I experimented until now, that part requires solving nested quadratic equations, and I did not finish this yet. Nevertheless, the program at a whole is runnable and already useful.

Here is the code implementing the whole quiz:

package de.roland_illig.boolquiz

import java.util.Random

/**
 * 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.)
 *
 * To generate a random expression having a fixed probability of returning
 * true, the probabilities of the operands must be adjusted by a bias.
 */
enum class BinOp(val sym: String, val lbias: Bias, val rbias: Bias) {
    And("and", Bias.Up, Bias.Up),
    Or("or", Bias.Down, Bias.Down),
    Impl("implies", Bias.NegUp, Bias.Down),
    Xor("xor", Bias.XorLeft, Bias.XorRight);

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

enum class Bias {
    Up, Down, NegUp, XorLeft, XorRight;

    fun probability(prob: Double) = when (this) {
        Up -> Math.sqrt(prob)
        Down -> 1.0 - Math.sqrt(1.0 - prob)
        NegUp -> Math.sqrt(1.0 - prob)
        XorLeft -> prob
        XorRight -> 0.0 // TODO: probability 0.0 is boring
    }
}

class Binary(private val a: Expr, private val op: BinOp, private val b: Expr) : Expr {
    override fun eval(): Boolean = 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 lprob = op.lbias.probability(prob)
    val rprob = op.rbias.probability(prob)
    val left = construct(leftDeg, rnd, lprob)
    val right = construct(rightDeg, rnd, rprob)

    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(args: Array<String>) {
    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.Percentage
import org.junit.Test
import java.util.Random

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("(false xor false)")

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

        assertThat(construct(7, Random(4096), 0.5).toString())
                .isEqualTo("(((true and true) xor (false or false)) xor not(true or not 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() < Math.sqrt(0.3)
            val b = rnd.nextDouble() < Math.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 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(false), BinOp.Xor, Literal(true)).eval())
                .isEqualTo(true)
        assertThat(Binary(Literal(true), BinOp.Xor, Literal(true)).eval())
                .isEqualTo(false)
    }

    @Test
    fun bias_Xor() {
        assertThat(Bias.XorLeft.probability(1.0))
                .isEqualTo(1.0)
        assertThat(Bias.XorRight.probability(1.0))
                .isEqualTo(0.0)

        // TODO: This is currently too boring.
        assertThat(Bias.XorLeft.probability(0.7))
                .isEqualTo(0.7)
        assertThat(Bias.XorRight.probability(0.7))
                .isEqualTo(0.0)
    }
}
\$\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.