В первый раз, когда я увидел, что проблема заливки воды программно решена, были отличные лекции по функциональному программированию Мартина Одерского на Coursera . Решение демонстрирует силу
ленивая оценка в потоках со Scala .
Решение проблемы заливки воды с помощью Kotlin
Я хотел изучить, как я могу переписать решение, описанное Мартином Одерским, с использованием Kotlin, и я понял две вещи: во-первых, неизменяемые структуры данных, которые предлагает Kotlin, являются просто обертками над библиотекой Java Collections и не являются действительно неизменяемыми, во-вторых, решение, использующее Streams Функция в Java будет сложной. Тем не менее, Vavr предлагает хорошую альтернативу — первоклассную библиотеку неизменяемых коллекций и библиотеку Streams, и я взял на себя смелость реплицировать решение с Kotlin и Vavr.
Кубок выглядит следующим образом, представленный в виде класса данных Kotlin :
|
1
2
3
4
5
6
7
8
|
import io.vavr.collection.Listdata class Cup(val level: Int, val capacity: Int) { override fun toString(): String { return "Cup($level/$capacity)" }} |
Поскольку проблема слива воды повторяет «состояние» набора чашек, это можно просто представить как «typealias» следующим образом:
|
1
|
typealias State = List<Cup> |
Есть 3 различных типа движений, которые можно выполнить с водой в чашке: опустошить, наполнить или перелить из одной чашки в другую, представленные снова как классы Kotlin Data:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
interface Move { fun change(state: State): State}data class Empty(val glass: Int) : Move { override fun change(state: State): State { val cup = state[glass] return state.update(glass, cup.copy(level = 0)) } override fun toString(): String { return "Empty($glass)" }}data class Fill(val glass: Int) : Move { override fun change(state: State): State { val cup = state[glass] return state.update(glass, cup.copy(level = cup.capacity)) } override fun toString(): String { return "Fill($glass)" }}data class Pour(val from: Int, val to: Int) : Move { override fun change(state: State): State { val cupFrom = state[from] val cupTo = state[to] val amount = min(cupFrom.level, cupTo.capacity - cupTo.level) return state .update(from, cupFrom.copy(cupFrom.level - amount)) .update(to, cupTo.copy(level = cupTo.level + amount)) } override fun toString(): String { return "Pour($from,$to)" }} |
Реализация использует метод «обновления» структур данных Списка Вавра для создания нового списка с обновлением только соответствующих элементов.
«Путь» представляет историю ходов, ведущих к текущему состоянию:
|
1
2
3
4
5
6
7
|
data class Path(val initialState: pour.State, val endState: State, val history: List<Move>) { fun extend(move: Move) = Path(initialState, move.change(endState), history.prepend(move)) override fun toString(): String { return history.reverse().mkString(" ") + " ---> " + endState }} |
Я использую метод «prepend» списка, чтобы добавить элементы в начало истории. Перед списком стоит операция O (1), а добавлением — O (n), отсюда и выбор.
Учитывая «состояние», набор возможных шагов для изменения «состояния» следующие:
1. Опорожнить бокалы —
|
1
|
(0 until count).map { Empty(it) } |
2. Заполните очки —
|
1
|
(0 until count).map { Fill(it) } |
3. Налить из одного стакана в другой —
|
1
2
3
4
5
|
(0 until count).flatMap { from -> (0 until initialState.length()).filter { to -> from != to }.map { to -> Pour(from, to) }} |
Теперь все эти шаги используются для перехода из одного состояния в другое. Предположим, что 2 чашки вместимостью 4 и 9 литров, изначально заполненные 0 литрами воды, представлены как «Список (Кубок (0/4), Кубок (0/9))», со всеми возможными ходами следующего набора состояний из чашек являются следующие:
Точно так же продвижение каждого из этих состояний к новому набору состояний должно выглядеть следующим образом (в несколько упрощенной форме):
По мере того как каждое состояние переходит к следующему набору состояний на основе всех возможных перемещений, можно увидеть, что произойдет взрыв возможных путей, и именно здесь появляется лень, предлагаемая структурой данных потока Vavr. Значения в потоке рассчитываются только по запросу.
Учитывая набор путей, новые пути создаются с помощью Stream следующим образом:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
fun from(paths: Set<Path>, explored: Set<State>): Stream<Set<Path>> { if (paths.isEmpty) { return Stream.empty() } else { val more = paths.flatMap { path -> moves.map { move -> val next: Path = path.extend(move) next }.filter { !explored.contains(it.endState) } } return Stream.cons(paths) { from(more, explored.addAll(more.map { it.endState })) } }} |
Итак, теперь, учитывая поток потенциальных путей из начального состояния в новое состояние, решением для «целевого» состояния становится:
|
1
2
3
4
5
|
val pathSets = from(hashSet(initialPath), hashSet())fun solution(target: State): Stream<Path> { return pathSets.flatMap { it }.filter { path -> path.endState == target }} |
Что касается решения, тест с этим кодом выглядит следующим образом — есть две чашки емкостью 4 литра и 9 литров, изначально заполненные 0 литрами воды. Конечная цель — наполнить вторую чашку 6 литрами воды:
|
1
2
3
4
5
6
7
|
val initialState = list(Cup(0, 4), Cup(0, 9))val pouring = Pouring(initialState)pouring.solution(list(Cup(0, 4), Cup(6, 9))) .take(1).forEach { path -> println(path) } |
при запуске это выдает следующее решение:
|
1
|
Fill(1) Pour(1,0) Empty(0) Pour(1,0) Empty(0) Pour(1,0) Fill(1) Pour(1,0) Empty(0) ---> List(Cup(0/4), Cup(6/9)) |
Графически представленное решение выглядит так:
Может быть проще просто следовать рабочей версии примера, которая доступна в моем репозитории github https://github.com/bijukunjummen/algos/blob/master/src/test/kotlin/pour/Pouring.kt
Вывод
Хотя Kotlin не хватает первоклассной поддержки нативных неизменяемых структур данных, я чувствую, что комбинация Vavr с Kotlin делает решение столь же элегантным, как и Scala.
|
См. Оригинальную статью здесь: Проблема заливки воды с Котлин и Вавр Мнения, высказанные участниками Java Code Geeks, являются их собственными. |