Wylewanie wody – proceduralne i funkcjonalne Kotlin

(Filippo Scognamiglio) ( 20 września 2019 r.)

Spróbujmy czegoś innego! W tym poście dwa razy rozwiążemy słynny problem „wylewania wody” używając Kotlina: sposób proceduralny i funkcjonalny.

Problem

W standardowej łamigłówce„ wylewanie wody ”dostajesz * n * szklanek o różnych znanych pojemnościach i zostaniesz poproszony o znalezienie listy działań, które prowadzą do pożądanej ilości w jednej lub kilku szklankach. Możesz wykonywać tylko trzy rodzaje czynności:

  • Całkowicie napełnij szklankę
  • Całkowicie opróżnij szklankę
  • Przelej jedną szklankę do drugiej, aż pierwsza jest pusta lub druga pełna

(Wiem, o czym myślisz… Nie możesz oszukiwać napełniając „połowę” szklanki… Widzę Cię).

Domena

Zacznijmy od scharakteryzowania domeny. Będziemy reprezentować stan z następującymi klasami danych:

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

Następnie definiujemy ruch za pomocą klasy abstrakcyjnej z metodą, która przekształca aktualny stan na zmodyfikowana:

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

Zapieczętowana klasa będzie miała trzy możliwe implementacje:

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 }

Będziemy również potrzebować struktury danych, która będzie reprezentować listę ruchów prowadzących do stanu końcowego:

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

Wszystkie te klasy są niezmienne z założenia, i wykorzystamy to w następujących implementacjach.

Implementacja proceduralna

Ten problem można przedstawić jako wykres, gdzie każdy stan jest węzłem, a każdy ruch jest połączeniem krawędzi dwa sąsiednie państwa. Zamierzamy znaleźć rozwiązanie, badając je za pomocą algorytmu „Breath First Search”.

Zacznijmy od wygenerowania każdego możliwego ruchu; możemy napełnić każdą szklankę, opróżnić każdą szklankę i wlać każdą do innej:

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
}

Teraz możemy utworzyć rozwiązać metodę , która przyjmuje żądaną ilość i zwraca najkrótszą listę ruchów definiujących rozwiązanie.

Wszystkie niezbadane stany zsumujemy w a MutableList , który na początku zawiera tylko stan początkowy.

Następnie zaczynamy iterację , na każdym kroku:

  • Zdejmujemy głowę z granicy. Jeśli ten stan jest rozwiązaniem, to koniec. Jeśli stan jest już zbadany, pomijamy go.
  • Dodaj ten stan do zestawu eksplorowanych stanów (zapobiega to wszelkim cyklom).
  • Oblicz wszystkie możliwe stany sąsiadujące, stosując każdy możliwy ruch i dodajemy je na końcu granicy.

Gwarantujemy zakończenie, albo znajdziemy rozwiązanie, albo zbadamy całą przestrzeń wyszukiwania.

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
}

Implementacja funkcjonalna

Przejdźmy do implementacji funkcji. Ogólna struktura będzie podobna i zaczniemy od zmiany metody generationMoves :

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
}

W przypadku rozwiązania zaczniemy czerpać inspirację z Martin Odersky .

Definiujemy funkcję rekurencyjną nextPaths , że dana lista ścieżek o długości n zwraca sekwencję list zawierających ścieżki o długości n+1.

Robi się to przez wywołanie metody rozszerzającej na każdej ze ścieżek wejściowych ze wszystkimi możliwymi ruchami (odfiltrowanie zbadanych stanów).

W ten sposób mamy gwarancję, że najkrótsze ścieżki są przetwarzane jako pierwsze, co prowadzi do kolejnej implementacji pierwszego wyszukiwania oddechu

Ponadto, ponieważ sekwencje Kotlina są leniwie oceniane , wiemy, że dłuższe ścieżki są obliczane tylko wtedy, gdy najkrótsze ścieżki są nie chodzi o rozwiązania problemu.

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

Wnioski

Spróbujmy podkreślić wnioski z tego krótkiego postu:

  • Obie implementacje działały na podanych przypadkach testowych
  • Implementacja proceduralna była 2-3 razy szybsza na tym samym wejściu
  • Implementacja funkcjonalna była bardziej zwięzła i prawdopodobnie czystsza
  • Funkcjonalną implementację można łatwo zoptymalizować, aby wykorzystać wiele rdzeni

Często nie jest łatwo ustalić, które podejście jest najlepsze, a programowanie funkcjonalne nie jest najlepszym rozwiązaniem kula kodowania.

Dobra wiadomość jest taka, że ​​nie potrzebujesz srebrnej kuli (chyba że musisz pokonać starożytną, zmiennokształtną, wyglądającą jak klaun): musimy mieć luksus, aby używać programowania wieloparadygmatycznego język, dzięki czemu możesz łatwo wybrać odpowiednie narzędzie do pracy.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *