Veden kaataminen – menettelyllinen ja toiminnallinen Kotlin

(Filippo Scognamiglio) ( 20. syyskuuta 2019)

Kokeillaan jotain erilaista! Tässä viestissä aiomme ratkaista kuuluisan ”veden kaatamisen” ongelman käyttämällä Kotlinia kaksi kertaa: menettelytapa ja toiminnallinen tapa.

Ongelma

Tavallisessa” veden kaatamista ”koskevassa palapelissä sinulle annetaan * n * lasia, joiden tunnetut kapasiteetit ja sinua pyydetään etsimään luettelo toiminnoista, jotka johtavat haluttuun määrään yhdessä tai useammassa lasissa. Sinulla on oikeus suorittaa vain kolmenlaisia ​​toimintoja:

  • Täytä lasi kokonaan
  • Tyhjennä lasi kokonaan
  • Kaada yksi lasi toiseen, kunnes ensimmäinen on tyhjä tai toinen on täynnä

(tiedän mitä ajattelet … Et voi huijata täyttämällä ”puoli” lasia … näen sinut).

Verkkotunnus

Aloitetaan karakterisoimalla verkkotunnus. Esittelemme tilaa, jolla on seuraavat dataluokat:

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

Seuraavaksi määritämme siirron abstraktin luokan avulla menetelmällä, joka muuttaa nykyisen tilan muokattu:

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

Suljetulla luokalla on kolme mahdollista toteutusta:

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 }

Tarvitsemme myös tietorakenteen edustamaan lopulliseen tilaan siirtyvien siirtojen luetteloa:

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)
}
}

Kaikki nämä luokat ovat muuttumattomia suunnittelun perusteella, ja hyödynnämme tätä seuraavissa toteutuksissa.

Menettelytoteutus

Tämä ongelma voidaan esittää kaaviona, jossa kukin tila on solmu ja jokainen liike on reuna, joka yhdistää kaksi naapurivaltiota. Löydämme ratkaisun tutkimalla sitä Breath First Search -algoritmilla.

Aloitetaan luomalla kaikki mahdolliset siirrot; Voimme täyttää jokaisen lasin, tyhjentää jokaisen lasin ja kaataa jokaisen lasin toiseen:

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
}

Nyt voimme luoda solution -menetelmä, joka ottaa halutun määrän ja palauttaa lyhimmän luettelon liikkeistä, jotka määrittävät ratkaisun.

Keräämme kaikki tutkimattomat tilat a MutableList , joka alussa sisältää vain alkutilan.

Sitten aloitamme iteroinnin , jokaisessa vaiheessa me:

  • Pistä pää rajan yli. Jos tämä tila on ratkaisu, olemme valmiit. Jos tila on jo tutkittu, ohitamme sen.
  • Lisää tämä tila tutkittujen joukkoon (tämä estää kaikenlaisen pyöräilyn).
  • Laske kaikki mahdolliset naapuritilat soveltamalla jokainen mahdollinen siirto ja lisätään ne rajan loppuun.

Tämä on taattu, joko löydämme ratkaisun tai tutkimme koko hakutilan.

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
}

Toiminnallinen toteutus

Siirrytään funktion toteutukseen. Yleinen rakenne on samanlainen, ja aloitamme muuttamalla geneMoves -menetelmää:

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
}

Toiminnalliselle ratkaise otamme inspiraation kohteesta Martin Odersky .

Määritämme rekursiivisen funktion nextPaths , jolle annettu polkujen luettelo, jonka pituus on n , palauttaa luettelon, joka sisältää polut, joiden pituus on n+1.

Tämän tekee kutsuu laajennusmenetelmä jokaiselle tulopolulle kaikilla mahdollisilla liikkeillä (suodatetaan tutkitut tilat).

Tällä tavoin voimme taata, että ensin käsitellään lyhyimmät polut, mikä johtaa hengityksen ensimmäinen haku toiseen toteutukseen. algoritmi.

Koska Kotlin-sekvenssit arvioidaan laiskasti , tiedämme, että pidemmät polut lasketaan vain, jos lyhyimmät polut a eivät ole ratkaisuja ongelmaan.

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) }
}

Johtopäätökset

Yritetään tuoda esiin tämän lyhyen viestin takaiskuja:

  • Molemmat toteutukset toimivat annetuissa testitapauksissa
  • Menettelyllinen toteutus oli 2-3 kertaa nopeampi samalla syötteellä
  • Toiminnallinen toteutus oli suppeampi ja kiistatta puhtaampi
  • Toiminnallinen toteutus voidaan helposti optimoida hyödyntämään useita ytimiä.

Usein ei ole helppoa selvittää, mikä on paras tapa, ja toiminnallinen ohjelmointi ei ole hopea koodausluettelo.

Hyvä uutinen on, että et tarvitse hopea luotia (ellei sinun tarvitse voittaa muinaista, muotoa muokkaavaa, klovneja näyttävää olentoa): meidän on ylellisyyttä käyttää monen paradigman ohjelmointia kielellä, joten voit valita helposti oikean työkalun työhön.

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *