vízöntés – eljárási és funkcionális Kotlin

(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 fun List.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.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük