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