{{announcement.body}}
{{announcement.title}}

# Solving the Josephus Problem in Kotlin

DZone 's Guide to

# Solving the Josephus Problem in Kotlin

### If you've ever run across the Josephus Problem, it's likely you've searched for a solution. Here's a method for solving it in Kotlin, with a bit of historical background.

· Java Zone ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

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`s 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?

Topics:
java, kotlin

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of Nicolas Frankel . See the original article here.

Opinions expressed by DZone contributors are their own.

# {{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}