(Filippo Scognamiglio) ( 2019. szeptember 20.)
Próbáljunk ki mást! Ebben a bejegyzésben a híres „vízöntési” problémát Kotlin segítségével kétszer fogjuk megoldani: az eljárási módot és a funkcionális módszert.

A probléma
A szokásos„ vízöntő ”rejtvényben különféle ismert kapacitású * n * poharakat kap és megkérjük, hogy találjon egy listát azokról a műveletekről, amelyek egy vagy több pohárban a kívánt mennyiséghez vezetnek. Csak háromféle műveletet hajthat végre:
- Töltsön ki teljesen egy poharat
- Teljesen ürítsen ki egy poharat
- Öntsön egy poharat a másikba, amíg az első üres vagy a második tele van
(tudom, mire gondolsz … Nem csalhatsz úgy, hogy megtöltöd a „fél” poharat … látlak.)
A domain
Kezdjük a domain jellemzésével. Állapotot fogunk képviselni a következő adatosztályokkal:
data class Glass(val capacity: Int, val value: Int)
data class State(val glasses: List)
Ezután egy absztrakt osztály használatával definiálunk egy lépést egy olyan módszerrel, amely az aktuális állapotot átalakítja a módosított:
sealed class Move {
abstract fun update(state: State): State
}
A lezárt osztálynak három lehetséges megvalósítása lesz:
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 funList .mapAtIndex(index: Int, f: (T) -> T) =
this.mapIndexed { i, t -> if (i == index) f(t) else t }
Szükségünk lesz egy adatstruktúrára is a végső állapotba kerülő mozgások listájának ábrázolásához:
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)
}
}
Mindezek az osztályok megváltoztathatatlanok, és ezt a következő megvalósításokban fogjuk kiaknázni.
Az eljárási megvalósítás
Ez a probléma grafikonként ábrázolható, ahol minden állapot egy csomópont, és minden lépés egy él összekötő. két szomszéd állam. Megtaláljuk a megoldást egy Breath First Search algoritmus segítségével.
Kezdjük minden lehetséges lépés előállításával; minden poharat kitölthetünk, minden poharat kiüríthetünk, és minden poharat másba tölthetünk:
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
}
Most létrehozhatunk egy megoldani metódust, amely egy kívánt mennyiséget vesz fel, és a megoldást meghatározó mozdulatok legrövidebb listáját adja vissza.
Az összes felfedezetlen állapotot felhalmozzuk a MutableList , amely az elején csak a kezdeti állapotot tartalmazza.
Ezután elkezdjük az iterációt , minden lépésnél:
- Pattintsuk a fejet a határról. Ha ez az állapot megoldás, akkor elkészültünk. Ha az állapot már fel van fedezve, akkor kihagyjuk.
- Adja hozzá ezt az állapotot a feltárottak halmazához (ez megakadályozza a kerékpározást).
- Számítsa ki az összes lehetséges szomszédos állapotot alkalmazással minden lehetséges mozdulatot, és hozzáadjuk a határ végéhez.
Ez garantáltan teljes lesz, vagy találunk megoldást, vagy feltárjuk a teljes keresési teret.
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
}
A funkcionális megvalósítás
Térjünk át a függvény megvalósítására. Az általános struktúra hasonló lesz, és a generatorMoves módszer megváltoztatásával kezdjük:
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
}
A funkcionális megoldáshoz a Martin Odersky .
Rekurzív függvényt definiálunk nextPaths , amely a n hosszúságú elérési utak listáját adja meg, a n+1.
hosszúságú utakat tartalmazó listák sorozatát adja vissza meghosszabbítás metódus meghívása minden bemeneti útvonalon minden lehetséges mozdulattal (a feltárt állapotok kiszűrése).
Így garantáltan a legrövidebb utakat dolgozzuk fel először, ami a lehelet első keresésének újabb megvalósításához vezet algoritmus.
Továbbá, mivel a Kotlin-szekvenciákat lustán kiértékelik , tudjuk, hogy a hosszabb utakat csak akkor számolják, ha a legrövidebb nem jelentenek megoldást a problémára.
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) }
}
Következtetések
Próbáljuk kiemelni ennek a rövid bejegyzésnek a kivonatait:
- Mindkét megvalósítás működött az adott teszteseteken
- Az eljárási megvalósítás 2-3-szor gyorsabb volt ugyanazon a bemeneten
- A funkcionális megvalósítás tömörebb és vitathatatlanul tisztább
- A funkcionális megvalósítás könnyen optimalizálható a több mag kihasználása érdekében
Gyakran nem könnyű kideríteni, melyik a legjobb megközelítés, és a funkcionális programozás sem ezüst kódolási golyó.
A jó hír az, hogy nincs szükséged ezüst golyóra (hacsak nem kell legyőznöd egy ősi, alakváltó, bohóc kinézetű lényt): luxust kell adnunk ahhoz, hogy több paradigmás programozást használjunk. nyelvet, így könnyen kiválaszthatja a munkához megfelelő eszközt.