How to implement a random coroutines challenge generator
It was evening in a small city close to London. I walked back to my hotel after a whole day teaching coroutines to a group of really smart developers, and a realization struck me. I ended this day with confronting group with different challenges that required and trained understanding of different coroutine concepts. Challenges like those:
suspend fun main() {
coroutineScope {
launch {
delay(1000)
println("A")
}
launch {
delay(500)
println("B")
}
}
println("C")
}
suspend fun a() {
delay(1000)
println("A")
}
suspend fun main(): Unit = coroutineScope {
val a = async { a() }
val b = async { a() }
val c = a()
println(a.await() + b.await() + c)
}
In each of those challenges, I asked the group what will be printed, in what order, and how much time exactly are we going to wait between those prints. For instance, the first challenge shows that coroutineScope waits for all its children to complete, so C is printed last. The second challenge shows that the last async is not necessary, since in this code all a() calls are asynchronous, so this code will wait just one second before it prints "AAA". A realization struck me, that challenges like those could be generated randomly, and that would be a great way to practice coroutine concepts.
Since I already worked on Coroutines Mastery course, and I actively looked for ways to make learning coroutines more productive and fun, I decided to implement such a generator. I got so fascinated by this idea that I implemented its initial version that very evening. However, the work was not done, I needed many more nights to make it generate truly interesting challenges.
My original idea was very simple. I needed to represent a result challenge, so I made a sealed hierarchy of classes. That suited my needs, since it allowed those elements to keep blocks of code or other elements.
sealed class ChallengeStatement {
sealed class ChallengeBlock : ChallengeStatement() {
abstract val statements: List<ChallengeStatement>
abstract fun withStatements(statements: List<ChallengeStatement>): ChallengeBlock
}
data class Delay(val time: Int, ) : ChallengeStatement()
data class Print(val text: String) : ChallengeStatement()
data class Launch(override val statements: List<ChallengeStatement>) : ChallengeBlock() {
override fun withStatements(statements: List<ChallengeStatement>): ChallengeBlock =
copy(statements = statements)
}
data class CoroutineScope(override val statements: List<ChallengeStatement>, ) : ChallengeBlock() {
override fun withStatements(statements: List<ChallengeStatement>): ChallengeBlock =
copy(statements = statements)
}
// ...
}
// Example challenge
val challenge = ChallengeStatement.CoroutineScope(
statements = listOf(
ChallengeStatement.CoroutineScope(
statements = listOf(
ChallengeStatement.Launch(
statements = listOf(
ChallengeStatement.Delay(1000),
ChallengeStatement.Print("A")
)
),
ChallengeStatement.Launch(
statements = listOf(
ChallengeStatement.Delay(500),
ChallengeStatement.Print("B")
)
)
)
),
ChallengeStatement.Print("C")
)
)
Then I needed a function to generate a random challenge. My initial idea was to just add random statements to a block until I reach a certain number of statements, and to repeat the same for sub-blocks. This is how it looked like:
// Result challenge is always wrapped in a coroutineScope
suspend private fun generateChallengeBlock(
expectedStatements: Int
): ChallengeBlock = ChallengeStatement.CoroutineScope(
statements = generateBodyStatements(expectedStatements)
)
private fun generateBodyStatements(
statementLeft: Int,
): List<ChallengeStatement> {
var left = statementLeft
buildList {
while (left > 0) {
val elementType = randomStatementType()
if (elementType.isBlock) {
if (left < 2) continue // not enough space for a block
val blockSize = Random.nextInt(2, left)
add(generateRandomBlock(elementType, blockSize))
left -= blockSize
} else {
add(generateRandomStatement(elementType))
left -= 1
}
}
}
}
private enum class StatementType(val isBlock: Boolean) {
Delay(isBlock = false),
Print(isBlock = false),
Launch(isBlock = true),
CoroutineScope(isBlock = true),
// ...
}
private fun randomStatementType(): StatementType =
StatementType.entries.random()
private fun generateRandomBlock(
type: StatementType,
expectedStatements: Int
): ChallengeBlock = when (type) {
StatementType.CoroutineScope -> ChallengeStatement.CoroutineScope(
statements = generateBodyStatements(expectedStatements - 1)
)
StatementType.Launch -> ChallengeStatement.Launch(
statements = generateBodyStatements(expectedStatements - 1)
)
// ...
}
private fun generateRandomStatement(type: StatementType): ChallengeStatement = when (type) {
StatementType.Delay -> ChallengeStatement.Delay(
time = Random.nextInt(1, 3) * 1000
)
StatementType.Print -> ChallengeStatement.Print(
text = ('A'..'Z').random().toString()
)
// ...
}
The actual solution needed to be a bit more complex, since async required await, which needed to be used after the async block. I also needed to use different kinds statement types for different game levels. Finally, I needed to introduce a class that guarantees that different strings are printed. Nevertheless, even with all that implemented this algorithm gave me very poor results. Most statements in generated challenges were too pointless and did not affect the result, so many challenges were just boring. Would you enjoy solving this challenge?
suspend fun main(): Unit = coroutineScope {
println("A")
println("B")
delay(2000)
println("C")
}
suspend fun main(): Unit = coroutineScope {
coroutineScope {
delay(1000)
println("A")
}
println("B")
launch {
delay(1000)
println("C")
}
}
I wanted interesting, creative challenges that would require real thinking and understanding of coroutines. So I started purging blocks that were just boring.
My new algorithm generated some initial random block, but the heart lied in the process of adding blocks to reach expected number of statements, and then purging boring blocks. This process repeated until purging did not change the block anymore. That means all blocks are meaningful, and this challenge it as interesting as possible. This is how it looks:
private fun generateChallengeBlock(
expectedStatements: Int,
vg: CoroutinesGameValueGenerator = CoroutinesGameValueGenerator(),
types: List<ChallengeStatementType> = ChallengeStatementType.entries,
): ChallengeBlock {
var state: ChallengeBlock = ChallengeStatement.CoroutineScope(
statements = generateInitialBodyStatements(statementLeft = expectedStatements, vg = vg, types = types)
)
do {
val statementsToAdd = expectedStatements - state.countStatements()
repeat(statementsToAdd) {
state = state.addRandomStatementToRandomBlock(statementLeft = statementsToAdd, vg = vg, types = types)
}
state = state.purgeBoringBlocks(vg)
} while (state.countStatements() < expectedStatements)
return state
}
So what do we purge? Beyond all, I wanted to purge blocks that do not affect the result. That turned out to be easier said than done. For blocks, I needed to check if inlining their body leads to the same result. If yes, I should remove the block as it is pointless. Prints and delays are pointless when they are called one after another, or when they are just called alternately. I implemented different heuristics to remove such pointless statements. Then I needed to repeat the process for all subblocks, and then repeat the whole process until nothing changes. This is how it looks:
fun ChallengeBlock.purgeStatementsThatNotAffectResult(): ChallengeBlock {
// We must compare like statements, otherwise comparing launch or async is useless
fun getResult(statements: List<ChallengeStatement>) =
ChallengeStatement.CoroutineScope(statements = statements).getResult()
val currentResult = getResult(statements)
fun theSameResult(statements: List<ChallengeStatement>) = getResult(statements) == currentResult
var newStatements = statements
// Purge print that is the first statement
newStatements.firstOrNull()?.let { firstStatement ->
if (firstStatement is ChallengeStatement.Print) {
newStatements -= firstStatement
}
}
// Try inlining different statements
newStatements.forEach { statement ->
if (statement !is ChallengeBlock) return@forEach
val afterInlining =
statements.flatMap { if (it == statement) statement.statements else listOf(it) }
.removeUsages(statement)
if (theSameResult(afterInlining)) {
newStatements = afterInlining
}
}
// Try removing different statements
newStatements.forEach { statement ->
val afterRemoving = (newStatements - statement).removeUsages(statement)
if (theSameResult(afterRemoving)) {
newStatements = afterRemoving
}
}
// Remove empty blocks
val emptyBlocks = newStatements.filter { it is ChallengeBlock && it.statements.isEmpty() }
newStatements = newStatements.minus(emptyBlocks)
for (emptyBlock in emptyBlocks) {
newStatements = newStatements.removeUsages(emptyBlock)
}
// Remove block with only print
for (statement in newStatements) {
if (statement is ChallengeStatement.ChallengeBlock && statement.statements.all { it is ChallengeStatement.Print }) {
newStatements -= statement
}
}
// Remove try-catch blocks with only throw inside
for (statement in newStatements) {
if (statement is ChallengeStatement.TryCatch && statement.statements.singleOrNull() is ChallengeStatement.ThrowException) {
newStatements -= statement
}
}
// Remove repeating print or delay
for ((curr, next) in newStatements.zipWithNext()) {
if (curr is ChallengeStatement.Print && next is ChallengeStatement.Print) {
newStatements -= curr
}
if (curr is ChallengeStatement.Delay && next is ChallengeStatement.Delay) {
newStatements -= curr
}
}
// Remove repeating print+delay or delay+print
for ((e1, e2, e3, e4) in newStatements.windowed(4, 1)) {
if (e1 is ChallengeStatement.Print && e2 is ChallengeStatement.Delay && e3 is ChallengeStatement.Print && e4 is ChallengeStatement.Delay) {
newStatements -= e3
newStatements -= e4
}
if (e1 is ChallengeStatement.Delay && e2 is ChallengeStatement.Print && e3 is ChallengeStatement.Delay && e4 is ChallengeStatement.Print) {
newStatements -= e3
newStatements -= e4
}
}
// Try the same for all statements
newStatements =
newStatements.map { if (it is ChallengeBlock) it.purgeStatementsThatNotAffectResult() else it }
if (newStatements != statements) {
return withStatements(newStatements)
.purgeStatementsThatNotAffectResult()
} else {
return this
}
}
Yes, that it extremally complex, but I needed all that to achieve the desired result. There are more purging functions. If we removed await, we turn async into launch, or if launch produces a job that is never used, we remove this variable definition. I also removed prints that happen at the same time, because I was worried that such result will confuse players. For that I needed to get result of a challenge, and find prints that happen at the same time. Then I just removed one of those prints. This is how it looks:
private fun ChallengeBlock.purgePrintsThatHappenAtTheSameTime(): ChallengeBlock {
val results = this.getResult()
var newStatement = this
for ((elem, next) in results.zipWithNext()) {
if (elem.time == next.time) {
val findPrint = this.findStatement { it is ChallengeStatement.Print && it.text == elem.value }
?: this.findStatement { it is ChallengeStatement.Print && it.text == next.value }
?: continue
newStatement = this - findPrint
}
}
return newStatement
}
To get the result of a challenge, I decided to just execute it inside runTest. That gives me precise execution, and allows me to read virtual time using currentTime. So I execute all statements, and whenever I print something, I add to a collection the printed text and current time.
fun ChallengeStatement.getResult(): List<PrintWithTime> = buildList<PrintWithTime> {
val jobs = mutableMapOf<String, Job>()
val deferred = mutableMapOf<String, Deferred<String>>()
runTest(timeout = 1.seconds) {
suspend fun evaluate(statement: ChallengeStatement, scope: CoroutineScope) {
when (statement) {
is ChallengeStatement.CoroutineScope -> coroutineScope {
statement.statements.forEach { evaluate(it, this@coroutineScope) }
}
is Launch -> scope.launch {
statement.statements.forEach { evaluate(it, this@launch) }
}
is Async -> deferred[statement.variableName] = scope.async {
statement.statements.forEach { evaluate(it, this@async) }
statement.resultString
}
is ChallengeStatement.Delay -> delay(statement.time.toLong())
is Print -> add(PrintWithTime(statement.text, currentTime))
is Cancel -> jobs[statement.variableName]?.cancel()
is Join -> jobs[statement.variableName]?.join()
is PrintAwait -> add(PrintWithTime(deferred[statement.variableName]?.await().orEmpty(), currentTime))
// ...
}
}
evaluate(this@getResult, this)
backgroundScope.cancel()
add(PrintWithTime("(done)", currentTime))
}
}
Since my final code includes different kinds of exceptions, I also needed to catch them and add their representation to the result. I had more problems with exceptions, because runTest specified its own exception handler, that makes it fail if any uncaught exception happens. To solve that, I needed to set custom CoroutineExceptionHandler that just ignores exceptions. I also needed to add timeout in case of deadlock, that might happen because of synchronization mechanisms I added to the game. Finally, I added coroutines started on some background scope, so I needed to create it based on backgroundScope provided by runTest. The final code looks like this:
fun ChallengeStatement.getResult(): List<PrintWithTime> = buildList<PrintWithTime> {
try {
val jobs = mutableMapOf<String, Job>()
val deferred = mutableMapOf<String, Deferred<String>>()
runTest(timeout = 1.seconds) {
val ignoringHandler = CoroutineExceptionHandler({ _, _ -> })
val backgroundScope = CoroutineScope(backgroundScope.coroutineContext + SupervisorJob() + ignoringHandler)
try {
withContext(ignoringHandler) {
withTimeout(10_000_000) {
suspend fun evaluate(statement: ChallengeStatement, scope: CoroutineScope) {
when (statement) {
is ChallengeStatement.CoroutineScope -> coroutineScope {
statement.statements.forEach { evaluate(it, this@coroutineScope) }
}
is Launch -> scope.launch {
statement.statements.forEach { evaluate(it, this@launch) }
}
is ScopeLaunch -> backgroundScope.launch {
statement.statements.forEach { evaluate(it, this@launch) }
}
is LaunchJob -> jobs[statement.variableName] =
scope.launch {
statement.statements.forEach { evaluate(it, this@launch) }
}
is Async -> deferred[statement.variableName] =
scope.async {
statement.statements.forEach { evaluate(it, this@async) }
statement.resultString
}
is ChallengeStatement.Delay -> delay(statement.time.toLong())
is Print -> add(
PrintWithTime(
statement.text,
currentTime
)
)
is Cancel -> jobs[statement.variableName]?.cancel()
is Join -> jobs[statement.variableName]?.join()
is PrintAwait -> add(
PrintWithTime(
deferred[statement.variableName]?.await().orEmpty(),
currentTime
)
)
is ChallengeStatement.Job -> jobs[statement.variableName] = Job()
is CompleteJob -> (jobs[statement.variableName] as? CompletableJob)?.complete()
is SupervisorScope -> supervisorScope {
statement.statements.forEach { evaluate(it, this@supervisorScope) }
}
is TryCatch -> when (statement.exceptionType) {
ExceptionType.CancellationException -> try {
statement.statements.forEach { evaluate(it, this) }
} catch (e: CancellationException) {
add(PrintWithTime("Got exception", currentTime))
}
ExceptionType.Exception -> try {
statement.statements.forEach { evaluate(it, this) }
} catch (e: Exception) {
add(PrintWithTime("Got exception", currentTime))
}
ExceptionType.MyException -> try {
statement.statements.forEach { evaluate(it, this) }
} catch (e: MyException) {
add(PrintWithTime("Got exception", currentTime))
}
}
is ThrowException -> when (statement.exceptionType) {
ExceptionType.CancellationException -> throw GameCancellationException()
ExceptionType.Exception -> throw GameException()
ExceptionType.MyException -> throw MyException()
}
}
}
evaluate(this@getResult, this)
backgroundScope.cancel()
add(PrintWithTime("(done)", currentTime))
}
}
} catch (t: TimeoutCancellationException) {
add(PrintWithTime("(waiting forever)", currentTime))
} catch (npe: GameException) {
add(PrintWithTime("(exception)", currentTime))
} catch (npe: MyException) {
add(PrintWithTime("(exception)", currentTime))
} catch (npe: GameCancellationException) {
add(PrintWithTime("(cancellation exception)", currentTime))
}
}
} catch (e: Throwable) {
println("Exception for ${this@getResult}")
throw e
}
}
The result list of prints with time can be transformed into a sequential representation of prints with delays using the following function:
fun ChallengeStatement.getSequentialResult(): List<String> {
val result = getResult()
return result
.windowed(size = 2, step = 1, partialWindows = true)
.flatMapIndexed { i, window ->
buildList {
if (window.size == 2) {
val (elem, next) = window
if (i == 0 && elem.time != 0L) {
add("(${elem.time / 1000} sec)")
}
add(elem.value)
if (elem.time != next.time) {
val timeDiffSec = (next.time - elem.time) / 1000
add("($timeDiffSec sec)")
}
} else { // last element
val (elem) = window
if (result.size == 1 && elem.time > 0) add("(${elem.time / 1000} sec)")
add(elem.value)
}
}
}
}
Turning this representation into code turned out to be quite simple. It is just a recursive function that turns each statement into code, and for blocks it turns their body into code with proper indentation. This is how it looks:
private fun ChallengeStatement.toCode(): String = when (this) {
is ChallengeStatement.CoroutineScope -> "coroutineScope {\n${statements.toCodeWithIndent()}\n}"
is ScopeLaunch -> "backgroundScope.launch {\n${statements.toCodeWithIndent()}\n}"
is Launch -> "launch {\n${statements.toCodeWithIndent()}\n}"
is LaunchJob -> "val $variableName = launch {\n${statements.toCodeWithIndent()}\n}"
is Async -> "val $variableName = async {\n${statements.toCodeWithIndent()}\n \"$resultString\"\n}"
is ChallengeStatement.Delay -> "delay($time)"
is Print -> "println(\"${text}\")"
is PrintAwait -> "println($variableName.await())"
is Join -> "$variableName.join()"
is Cancel -> "$variableName.cancel()"
is ChallengeStatement.Job -> "val $variableName = Job()"
is CompleteJob -> "$variableName.complete()"
is SupervisorScope -> "supervisorScope {\n${statements.toCodeWithIndent()}\n}"
is TryCatch -> {
val exception = when (exceptionType) {
ExceptionType.CancellationException -> "CancellationException"
ExceptionType.Exception -> "Exception"
ExceptionType.MyException -> "MyException"
}
"try {\n${statements.toCodeWithIndent()}\n} catch (e: $exception) {\n println(\"Got exception\")\n}"
}
is ThrowException -> {
val exception = when (exceptionType) {
ExceptionType.CancellationException -> "CancellationException()"
ExceptionType.Exception -> "Exception()"
ExceptionType.MyException -> "MyException()"
}
"throw $exception"
}
}
private fun List<ChallengeStatement>.toCodeWithIndent() = joinToString(separator = "\n") {
it.toCode().prependIndent(" ")
}
To provide a complete code I needed to add suspend fun main() and optional backgroundScope declaration. This is how it looks:
fun ChallengeBlock.toCompleteCode(): String = buildString {
if (this@toCompleteCode.anyStatement { it is ScopeLaunch }) {
appendLine("val backgroundScope = CoroutineScope(SupervisorJob())")
appendLine()
}
append("suspend fun main(): Unit = \n${toCode()}")
}
I am very satisfied with the final result. The generator creates interesting challenges that require real thinking and understanding of coroutines. I made this game for Coroutines Mastery course, but I decided to share it with the community, so others can enjoy it as well. You can find the game here. You can find complete source code of the generator here.
