8
\$\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\$
6
+200
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for sharing these great insights. When I wrote the code I had thought that the variable names were obvious to any reader. Now that I spelled out all the abbreviations, the code should be even understandable by a beginner trying to learn boolean expressions, which I think could really be the target of this quiz. — Since Kotlin is a different language than Java, I didn't want to blindly follow the "put everything into classes" suggestion. Instead I went the other way and moved the probabilities out of the BinaryOperator class, since these are not general-purpose enough. \$\endgroup\$ – Roland Illig Jan 12 at 13:24
  • 1
    \$\begingroup\$ @RolandIllig It's true that you don't have to put everything into different classes, but another way to structure the code is to put everything into different files - which you can still do. Especially the round, question and main methods. \$\endgroup\$ – Simon Forsberg Jan 12 at 13:31
  • \$\begingroup\$ Using kotlin.Random instead of java.util.Random sounded like a great idea at first since it removes the dependency on Java. The only downside is that in kotlin.Random, Future versions of Kotlin may change the algorithm of this seeded number generator, which would break my tests for no reason. Therefore it would require much more code to get this right. \$\endgroup\$ – Roland Illig Jan 12 at 13:38
  • 1
    \$\begingroup\$ @RolandIllig Honestly, I don't think you should rely on any randomness in your tests - seeded or not. The loops that randomizes two million times are fine because they make sure that your math is correct. But for generating specific boolean constructs a better approach would be to separate the randomness from the generation a bit so that you can test a specific generation. It's not the randomness that you want to test, assertThat(construct(7, Random(0), 0.5)....toString.. tests that a very specific construct has a specific result for the toString call - that is what you want to test. \$\endgroup\$ – Simon Forsberg Jan 12 at 19:41
  • 1
    \$\begingroup\$ @RolandIllig What you could do is to replace rnd: Random in your method with intProvider: (Int) -> Int and give one implementation in your real usage - rnd.nextInt(it) and in your tests you could feed the results from a list of pre-specified numbers. Sure it's a bit more code to write, but it's a lot more bullet-proof. \$\endgroup\$ – Simon Forsberg Jan 12 at 19:44
2
\$\begingroup\$

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);
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What, in your mind, would be the benefit of using object-oriented patterns or abstract methods here? To me, your code looks more complicated. In my code one can directly see how the different operators differ since their implementations are in adjacent lines. \$\endgroup\$ – Roland Illig Jan 7 at 16:21
  • \$\begingroup\$ Replacing conditionals with polymorphism is a common refactoring pattern (see google.com/search?q=conditional+vs+polymorphism ). For me the main advantage is that it's impossible to accidentally create a new, bugged instance of BinOp, because you forgot to update one of the when statements. I personally prefer having all the functionality which form one instance together at one place, however I understand wanting to have all variants close together. One way to do that would be to put the lambdas together in variables. \$\endgroup\$ – RoToRa Jan 8 at 8:37
  • \$\begingroup\$ Your "main advantage" doesn't apply in this case. I cannot forget one of the branches since the compiler will tell me. I intentionally kept the methods with the when expressions quite short. Your second reason for using abstract methods doesn't convince me either. I applied the refactorings you suggested, and the code becomes either more bloated (because of the additional override declarations) or becomes so short that it doesn't even offer a convenient place where the probabilities function could be documented. Therefore I still prefer my variant. \$\endgroup\$ – Roland Illig Jan 8 at 18:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.