Vertido de agua – Kotlin de procedimiento y funcional

Publicado el

(Filippo Scognamiglio) ( 20 de septiembre de 2019)

¡Probemos algo diferente! En este post vamos a resolver el famoso problema del “vertido de agua” usando Kotlin dos veces: la forma procedimental y la forma funcional.

El problema

En el acertijo estándar de» vertido de agua «se le dan * n * vasos con diferentes capacidades conocidas y se le pide que busque una lista de acciones que conduzcan a una cantidad deseada en uno o más vasos. Solo puede realizar tres tipos de acciones:

  • Llenar completamente un vaso
  • Vaciar completamente un vaso
  • Verter un vaso en otro hasta el primero está vacío o el segundo está lleno

(Sé lo que estás pensando… No puedes hacer trampa llenando “medio” vaso… puedo verte).

El dominio

Empecemos por caracterizar el dominio. Vamos a representar un estado con las siguientes clases de datos:

data class Glass(val capacity: Int, val value: Int)
data class State(val glasses: List)

A continuación, definimos un movimiento usando una clase abstracta con un método que transforma el estado actual en la modificada:

sealed class Move {
abstract fun update(state: State): State
}

La clase sellada tendrá las tres posibles implementaciones:

data class Fill(val index: Int): Move() {
override fun update(state: State): State =
State(state.glasses.mapAtIndex(index) {
it.copy(value = it.capacity)
})
}

data class Empty(val index: Int): Move() {
override fun update(state: State): State =
State(state.glasses.mapAtIndex(index) {
it.copy(value = 0)
})
}

data class Pour(val from: Int, val to: Int): Move() {
override fun update(state: State): State {
val fromGlass = state.glasses[from]
val toGlass = state.glasses[to] val maxFromQuantity = fromGlass.value
val maxToQuantity = toGlass.capacity - toGlass.value val quantity = min(maxFromQuantity, maxToQuantity)

return State(
state.glasses
.mapAtIndex(from) {
it.copy(value = it.value - quantity)
}
.mapAtIndex(to) {
it.copy(value = it.value + quantity)
}
)
}
}// Utility extension function
private fun List.mapAtIndex(index: Int, f: (T) -> T) =
this.mapIndexed { i, t -> if (i == index) f(t) else t }

También necesitaremos una estructura de datos para representar una lista de movimientos que lleva a un estado final:

data class Path(val finalState: State, val moves: List) {
fun extend(move: Move): Path {
val nextState = move.update(finalState)
val nextMoves = moves + move
return copy(finalState = nextState, moves = nextMoves)
}
}

Todas estas clases son inmutables por diseño, y aprovecharemos esto en las siguientes implementaciones.

La implementación procedimental

Este problema se puede representar como un gráfico, donde cada estado es un nodo y cada movimiento es un borde que conecta dos estados vecinos. Vamos a encontrar la solución explorándola utilizando un algoritmo de Breath First Search.

Comencemos generando todos los movimientos posibles; podemos llenar cada vaso, vaciar cada vaso y verter cada vaso en uno diferente:

private fun generateMoves(): List {
val result = mutableListOf()

val indices = initialState.glasses.indices

for (i in indices) {
result.add(Move.Fill(i))
result.add(Move.Empty(i))
}

for (i in indices) {
for (j in indices) {
if (i != j)
result.add(Move.Pour(i, j))
}
}

return result
}

Ahora podemos crear un método solve , que toma una cantidad deseada y devuelve la lista más corta de movimientos que definen una solución.

Acumulamos todos los estados inexplorados en una MutableList que, al principio, solo contiene el estado inicial.

Luego comenzamos a iterar , en cada paso nosotros:

  • Sacamos la cabeza de la frontera. Si este estado es una solución, hemos terminado. Si el estado ya está explorado, lo omitimos.
  • Agregue este estado al conjunto de los explorados (esto evita cualquier tipo de ciclo).
  • Calcule todos los estados vecinos posibles aplicando cada movimiento posible, y los agregamos al final de la frontera.

Esto está garantizado para completar, ya sea que encontremos una solución o exploremos el espacio de búsqueda completo.

fun solve(amount: Int): Path? {
val explored = mutableSetOf()
val frontier = mutableListOf(Path(initialState, listOf()))

while (frontier.isNotEmpty()) {
val currentPath = frontier.removeAt(0)

if (isSolution(amount, currentPath.finalState)) {
return currentPath
}

if (explored.contains(currentPath.finalState)) {
continue
}

explored.add(currentPath.finalState)

for (move in moves) {
val nextPath = currentPath.extend(move)
frontier.add(nextPath)
}
}

return null
}

La implementación funcional

Pasemos a la implementación de la función. La estructura general será similar, y comenzaremos cambiando el método generateMoves :

private fun generateMoves(): List {
val indices = initialState.glasses.indices

val fillMoves = indices.map { Move.Fill(it) }
val emptyMoves = indices.map { Move.Empty(it) }
val pourMoves = indices
.flatMap { i -> indices.map { j -> i to j } }
.filter { (i, j) -> i != j }
.map { (i, j) -> Move.Pour(i, j) }

return fillMoves + emptyMoves + pourMoves
}

Para la funcional resolver vamos a inspirarnos en Martin Odersky .

Definimos una función recursiva nextPaths que dada una lista de rutas con longitud n devuelve una secuencia de listas que contienen las rutas de longitud n+1.

Esto se hace llamar al método extender en cada una de las rutas de entrada con todos los movimientos posibles (filtrando los estados explorados).

De esta manera, se garantiza que las rutas más cortas se procesan primero, lo que lleva a otra implementación de la búsqueda de respiración primero algoritmo.

Además, dado que las secuencias de Kotlin se evaluadas de forma perezosa , sabemos que las rutas más largas se calculan solo si las rutas más cortas No hay soluciones al problema.

fun solve(amount: Int): Path? {
val firstPath = Path(initialState, listOf()) return nextPaths(listOf(firstPath), setOf())
.flatten()
.filter { isSolution(amount, it.finalState) }
.firstOrNull()
}

fun nextPaths(paths: List, explored: Set): Sequence> {
return if (paths.isEmpty()) emptySequence()
else {
sequence {
val nextPaths = paths.flatMap {
extendWithMoves(it, explored)
}
val nextExplored = explored + paths.map {
it.finalState
}

yield(nextPaths)
yieldAll(nextPaths(nextPaths, nextExplored))
}
}
}

fun extendWithMoves(path: Path, explored: Set): List {
return moves
.map { path.extend(it) }
.filter { !explored.contains(it.finalState) }
}

Conclusiones

Intentemos resaltar las conclusiones de esta breve publicación:

  • Ambas implementaciones funcionaron en los casos de prueba dados
  • La implementación del procedimiento fue de 2 a 3 veces más rápida con la misma entrada
  • La implementación funcional fue más concisa y posiblemente más limpia
  • La implementación funcional podría optimizarse fácilmente para aprovechar múltiples núcleos

A menudo no es fácil descubrir cuál es el mejor enfoque, y la programación funcional no es la plata bala de codificación.

La buena noticia es que no necesitas una bala de plata (a menos que necesites derrotar a una criatura antigua, que cambia de forma y que parece un payaso): tenemos el lujo de usar una programación de múltiples paradigmas idioma, para que pueda elegir fácilmente la herramienta adecuada para el trabajo.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *