Feedback on the Josephus problem
Nicolas FrankelMy last week article was about the solving the Josephus problem in Kotlin. For ease of comparison, here’s the version I wrote originally:
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
}
}
The post ended with an open question: was the code the right way to do it? In particular:
- Is the code idiomatic Kotlin?
- Lack of
for
means usingwhile
withvar
s - Too many mutability (
var
) for my own liking
I’ve received great feedback from the community on many different channels, including Ilya Ryzhenkov from JetBrains, Cédric Beust, Peter Somerhoff and Gaëtan Zoritchak. Thanks guys!
I think the most interesting is this one, very slightly modified from the original Gist by Gaëtan:
class Soldier(val position: Int, var state:State = State.Living) {
fun suicide() {
state = State.Dead
}
fun isAlive() = state == State.Living
}
enum class State {
Living, Dead
}
class Circle(val size: Int, val step: Int) {
val soldiers = Array( size, {Soldier(it)}).toList()
fun findSurvivor(): Soldier {
var soldier = soldiers.first()
(2..size).forEach {
(1..step).forEach {
soldier = soldier.nextLivingSoldier()
}
soldier.suicide()
}
return soldier.nextLivingSoldier()
}
tailrec private fun Soldier.nextLivingSoldier():Soldier =
if (next().isAlive())
next()
else
next().nextLivingSoldier()
private fun Soldier.next() = soldiers.get(
if (position == size - 1)
0
else
position + 1
)
}
I like this code a lot because it feels more Kotlin-esque. Improvements are many.
- The code is shorter without any loss of readability
- It’s entirely functional, there’s only a single
var
involved:- the 2
while
loops with their associatedvar
counter have been replaced by simpleforEach
onInt
ranges. - Chaining
Soldier
instances is not handled in theSoldier
class itself through thenext()
method but by the containingCircle
. Thus, a simple backing array can store them and there’s no need for custom code with mutable variables.
- the 2
- The recursive
nextLivingSoldier()
function has been “annotated” withtailrec
in order for the compiler to run its optimization magic. - The
Soldier
class doesn’t know about its containerCircle
‘ssize
, so functions using it have been moved inside theCircle
class as extension functions to theSoldier
class. This is a great usage of Kotlin’s extension functions.
This experience reinforced my belief that learning a language by just reading about it is not enough. To truly make it yours, steps should be those:
- obviously, learn the syntax of the language – and its API,
- code a solution or an app with this language,
- ask for feedback,
- read, analyze and understand the feedback,
- rinse and repeat.