I recently stumbled upon a post telling about the Josephus problem and trying to solve it in different scripting languages. For the sake of brevity, here’s the problem (taken from the referenced post):
Flavius Josephus was a roman historian of Jewish origin. During the Jewish-Roman wars of the first century AD, he was in a cave with fellow soldiers, 40 men in all, surrounded by enemy Roman troops. They decided to commit suicide by standing in a ring and counting off each third man. Each man so designated was to commit suicide…Josephus, not wanting to die, managed to place himself in the position of the last survivor. In the general version of the problem, there are n soldiers numbered from 1 to n and each k-th soldier will be eliminated. The count starts from the first soldier. What is the number of the last survivor?
It seemed like a good challenge to test my building Kotlin skills. Here’s the solution I’ve come up with. First, the test class, using TestNG and a data provider - it’s the perfect use-case:
class JosephusTest {
@DataProvider
fun data(): Array<Array<Int>> {
return arrayOf(
arrayOf(2, 1, 0),
arrayOf(3, 1, 0),
arrayOf(10, 1, 0),
arrayOf(3, 2, 0),
arrayOf(4, 2, 1)
)
}
@Test(dataProvider = "data")
fun circle_of_size_and_step_should_survive_position(size: Int, step: Int, expectedPosition: Int) {
val circle = Circle(size, step)
val survivor = circle.findSurvivor()
assertEquals(survivor.position, expectedPosition)
}
}Now, the code:
class Soldier(val position: Int) {
var state = State.Living
lateinit var next: Soldier
fun suicide() {
state = State.Dead
}
fun isDead() = state == State.Dead
}
enum class State {
Living, Dead
}
class Circle(private val size: Int, private val step: Int) {
private val first = Soldier(0)
init {
var person = first
while (person.position < size - 1) {
person = createNext(person)
}
val last = person
last.next = first
}
private fun createNext(soldier: Soldier): Soldier {
val new = Soldier(soldier.position + 1)
soldier.next = new
return new
}
fun findSurvivor(): Soldier {
var soldier: Soldier = first
var numberOfDead = 0
while (numberOfDead < size - 1) {
var count: Int = 0
while (count < step) {
soldier = nextLivingSoldier(soldier)
count++
}
soldier.suicide()
numberOfDead++
}
return nextLivingSoldier(soldier)
}
private fun nextLivingSoldier(soldier: Soldier): Soldier {
var currentSoldier = soldier.next
while (currentSoldier.isDead()) {
currentSoldier = currentSoldier.next
}
return currentSoldier
}
}This code works fine and the tests are successful.
However, while trying to code the solution, I realized that there were no data-structure implementing circular linked lists neither in Java nor in Kotlin. I had thus to implement my own circular data-structure, but without implementing common collection features.
Now, my problem with the above code is that while the Soldier class looks fine by me, the Circle class doesn’t.
There are too many var in Circle and it feels too much like imperative programming.
The lack of for(;;) in Kotlin forces me to use a while with an outside variable - twice: count and numberOfDead.
I’ve been thinking that I could improve the situation by changing the data-structure. I just don’t know how… Now, Kotlin and FP gurus, do you have any proposal?