Solving Water Pouring Problem using Kotlin
I wanted to explore how I can rewrite the solution described by Martin Odersky using Kotlin and I realized two things - one is that the immutable data structures that Kotlin offers are simply wrappers over Java Collections library and are not truly immutable, secondly the solution using Streams feature in Java will be difficult. However, the Vavr offers a good alternative to both - a first-class Immutable collections library and a Streams library and I took a crack at replicating the solution with Kotlin and Vavr.A Cup looks like this, represented as a Kotlin data class:
import io.vavr.collection.List
data class Cup(val level: Int, val capacity: Int) {
override fun toString(): String {
return "Cup($level/$capacity)"
}
}
Since the water pouring problem repesents the "state" of a set of cups, this can be simply represented as a "typealias" the following way:
typealias State = List<Cup>
There are 3 different types of moves that can be performed with the water in the cup - Empty it, Fill it, or Pour from one cup to another, represented again as Kotlin Data classes:
interface Move {
fun change(state: State): State
}
data class Empty(val glass: Int) : Move {
override fun change(state: State): State {
val cup = state[glass]
return state.update(glass, cup.copy(level = 0))
}
override fun toString(): String {
return "Empty($glass)"
}
}
data class Fill(val glass: Int) : Move {
override fun change(state: State): State {
val cup = state[glass]
return state.update(glass, cup.copy(level = cup.capacity))
}
override fun toString(): String {
return "Fill($glass)"
}
}
data class Pour(val from: Int, val to: Int) : Move {
override fun change(state: State): State {
val cupFrom = state[from]
val cupTo = state[to]
val amount = min(cupFrom.level, cupTo.capacity - cupTo.level)
return state
.update(from, cupFrom.copy(cupFrom.level - amount))
.update(to, cupTo.copy(level = cupTo.level + amount))
}
override fun toString(): String {
return "Pour($from,$to)"
}
}
The implementation is making use of Vavr's List data structures "update" method to create a new list with just the relevant elements updated.
A "Path" represents a history of moves leading to the current state:
data class Path(val initialState: pour.State, val endState: State, val history: List<Move>) {
fun extend(move: Move) = Path(initialState, move.change(endState), history.prepend(move))
override fun toString(): String {
return history.reverse().mkString(" ") + " ---> " + endState
}
}
I am using the "prepend" method of the list to add elements to the beginning of history. Prepending to a list is an O(1) operation whereas appending is O(n), hence the choice.
Given a "state", a set of possible moves to change the "state" are the following -
1. Empty the glasses -
(0 until count).map { Empty(it) }
2. Fill the glasses -
(0 until count).map { Fill(it) }
3. Pour from one glass to another -
(0 until count).flatMap { from ->
(0 until initialState.length()).filter { to -> from != to }.map { to ->
Pour(from, to)
}
}
Now, all these moves are used for advancing from one state to another. Consider say 2 cups with capacity of 4 and 9 litres, initially filled with 0 litres of water, represented as "List(Cup(0/4), Cup(0/9))", with all possible moves the next set of states of the cups are the following:
Similarly, advancing each of these states to a new set of states would like this(in a somewhat simplified form):
As each State advances to a next set of states based on all possible moves, it can be seen that there will be an explosion of possible paths, this is where laziness offered by the Stream data structure of Vavr comes in. The values in a stream are only computed on request.
Given a set of paths, new paths are created using Stream the following way:
fun from(paths: Set<Path>, explored: Set<State>): Stream<Set<Path>> {
if (paths.isEmpty) {
return Stream.empty()
} else {
val more = paths.flatMap { path ->
moves.map { move ->
val next: Path = path.extend(move)
next
}.filter { !explored.contains(it.endState) }
}
return Stream.cons(paths) { from(more, explored.addAll(more.map { it.endState })) }
}
}
So, now given a stream of potential paths from the initial state to a new state, a solution to a "target" state becomes:
val pathSets = from(hashSet(initialPath), hashSet())
fun solution(target: State): Stream<Path> {
return pathSets.flatMap { it }.filter { path -> path.endState == target }
}
That covers the solution, a test with this code looks like this - there are two cups of 4 litre and 9 litre capacity, initially filled with 0 litres of water. The final target state is to get the second cup filled with 6 litres of water:
val initialState = list(Cup(0, 4), Cup(0, 9))
val pouring = Pouring(initialState)
pouring.solution(list(Cup(0, 4), Cup(6, 9)))
.take(1).forEach { path ->
println(path)
}
when run, this spits out the following solution:
Fill(1) Pour(1,0) Empty(0) Pour(1,0) Empty(0) Pour(1,0) Fill(1) Pour(1,0) Empty(0) ---> List(Cup(0/4), Cup(6/9))
Graphically represented, the solution looks like this:
It may be easier to simply follow a working version of the sample which is available in my github repo - https://github.com/bijukunjummen/algos/blob/master/src/test/kotlin/pour/Pouring.kt
