Over a million developers have joined DZone.
{{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

Download Microservices for Java Developers: A hands-on introduction to frameworks and containers. Brought to you in partnership with Red Hat.

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 vars 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?

Download Building Reactive Microservices in Java: Asynchronous and Event-Based Application Design. Brought to you in partnership with Red Hat

Topics:
kotlin ,java

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

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

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

{{ parent.tldr }}

{{ parent.urlSource.name }}