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 5 questions, 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

interface Expr {
    fun eval(): Boolean
}

class Literal(private val value: Boolean) : Expr {
    override fun eval() = value
    override fun toString() = "$value"
}

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

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 calc(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 prob(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.calc(a.eval(), b.eval())
    override fun toString() = "($a ${op.sym} $b)"
}

fun construct(deg: Int, rnd: Random, resProb: Double): Expr {

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

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

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

    val op = BinOp.values()[opIndex - 1]
    val lprob = op.lbias.prob(resProb)
    val rprob = op.rbias.prob(resProb)
    val left = construct(leftDeg, rnd, lprob)
    val right = construct(rightDeg, rnd, rprob)

    return Binary(left, op, right)
}

fun main(args: Array<String>) {
    var difficulty = 1
    var n = 0
    val rnd = Random()

    while (true) {
        val expr = construct(difficulty, rnd, 0.5)

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

        if (answer != "true" && answer != "false") {
            println("Answer must be either \"true\" or \"false\".")
        } else if (answer != "${expr.eval()}") {
            println("Wrong.")
        }

        n++
        if (n >= 5) {
            difficulty++
            n = 0
        }
    }
}

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.prob(1.0))
                .isEqualTo(1.0)
        assertThat(Bias.XorRight.prob(1.0))
                .isEqualTo(0.0)

        // TODO: This is currently too boring.
        assertThat(Bias.XorLeft.prob(0.7))
                .isEqualTo(0.7)
        assertThat(Bias.XorRight.prob(0.7))
                .isEqualTo(0.0)
    }
}
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.