Мультивселенная и задачи о переправе16.06.2021 10:31

cf8bd1a5f6c8711cba454b6a8dce9078.png

Как-то прочел на Хабре статью «Перевозим волка, козу и капусту через реку с эффектами на Haskell», которая так понравилась, что решил написать фреймворк для всего класса задач о переправах, используя мультипарадигменное проектирование. Наконец удалось найти время, и вот, спустя почти год, фреймворк готов. Теперь персонажи, их взаимодействия и описание искомого результата задаются через domain-specific language, который позволяет решать любые головоломки подобного рода с пошаговым выводом. Ниже приводится поэтапный разбор реализации DSL. Статья подойдет тем кто изучает язык Kotlin или просто интересуется примерами его использования. Некоторые малозначимые детали (вроде импортов и вывода) для кратости опущены.

Персонажа легко можно описать открытым для наследования классом: 

open class Person(private val name: String)

Также просто определим понятие берега, как набора персонажей задачи: 

typealias Riverside = Set

Дальше построим лодку. Лодка будет знать о населенности обоих берегов, но находится в состоянии квантовой неопределенности между ними, с возможностью инвертировать свое положение: 

abstract class QuantumBoat(
  val left: Riverside, val right: Riverside) {
  
  abstract fun invert(): List
  
  fun where(
    condition: Riverside.() -> Boolean, 
    selector: QuantumBoat.() -> Boolean
  ) = Multiverse(this, condition).search(selector)
}

Лодка также снабжена высокоуровневым методом where, для поиска необходимого состояния через N шагов по реке. Условие (condition) определяет валидность берегов в процессе, а селектор (selector) задает искомое конечное состояние. Обратите внимание, что при использовании этого метода лодка на самом деле не двигается с места, а перебирает альтернативные вселенные, пока не обнаружит подоходящую ​:)
Но об этом мы поговорим позже, а пока что перейдем к простой имплементации лодки для перемещения слева направо: 

class LeftBoat(left: Riverside, right: Riverside) : QuantumBoat(left, right) {

  override fun invert() =
    left.map {
      RightBoat(left - it - Farmer, right + it + Farmer)
    } + RightBoat(left - Farmer, right + Farmer)
}

Инверсия состояния возвращает сразу все возможные варианты перемещения на другую сторону. Это пригодится для реализации нашего мультиверсума. Поскольку по условиям таких задач, фермер выступает необходимым условием передвижения лодки, то перемещаем его во всех случаях вместе с ней. Аналогичным образом имплементируем и перемещение справа налево. Заметьте, насколько лаконичен наш код за счет предопределенных высокоуровневых функций Kotlin и перегрузки операторов для работы с множествами.

Лодку мы реализовали, персонажей тоже, теперь опишем то ради чего все затевалось, а именно, код для записи этапов перемещения. Поскольку мы планируем добавлять данные в конец, опишем их как псевдоним связанного списка состояний лодки: 

typealias History = LinkedList
  
fun Sequence.fork() = sequence {
  for (history in this@fork) {
    for (forked in history.last.invert()) {
      yield((history.clone() as History).apply {
        add(forked)
      })
    }
  }
}

Заодно описали функцию форка мультиверсума (историй перемещений) в следующий набор состояний (шаг). Чтобы все это добро не забивало лишний раз память, используем ленивые последовательности и yield.

Теперь нам осталось всего лишь описать мультиверсум (а код для поиска состояний у нас уже есть): 

/**
 * Мультиверсум для лодки
 * @param boat исходное состояние лодки
 * @param condition валидатор промежуточных состояний
 */
class Multiverse(boat: QuantumBoat, val condition: Riverside.() -> Boolean) {

  /**
   * Все смоделированные истории передвижений лодки
   */
  private var multiverse = sequenceOf(historyOf(boat))

  /**
   * Найти историю подходящей нам лодки
   * @param selector нужное состояние берегов и лодки
   * @return все найденные варианты достижения состояния
   */
  tailrec fun search(selector: QuantumBoat.() -> Boolean): List {
    multiverse = multiverse.fork().distinct().filter {
      it.last.left.condition()
        && it.last.right.condition()
    }
    val results = multiverse.filter { it.last.selector() }.toList()
    return when {
      results.isNotEmpty() -> results
      else -> search(selector)
    }
  }
}

Здесь мы заиспользовали оптимизацию хвостовой рекурсии, благодаря чему kotlinc сгенерирует импертивный цикл для повышения производительности. Что здесь происходит: на каждом шаге мы делаем форк всех состояний мультиверсума перемещая все возможные объекты на другой берег в параллельных вселенных. Затем отбрасываем дубликаты и невалидные состояния (коза и капуста например), а оставшиеся последовательности и будут ответами к задаче. Вуаля!

Наконец, пример использования DSL на всем известной задачке про волка, козу и капусту: 

object Wolf : Person("​")

object Goat : Person("​")

object Cabbage : Person("​")

fun Riverside.rule() =
  contains(Farmer) ||
    (!contains(Wolf) || !contains(Goat)) &&
    (!contains(Goat) || !contains(Cabbage))

fun main() {

  val property = setOf(Wolf, Goat, Cabbage)

  // стартовали с левого берега
  LeftBoat(property)
     // отбросили все невалидные состояния
    .where(Riverside::rule)
    // выбрали из оставшихся те варианты,
    // где все имущество оказалось на правом берегу
    { right.containsAll(property) } 
    // выводим на экран пошаговое решение
    .forEach(History::prettyPrint)
}

Вот что получилось, вставляю скриншотом, потому что смайлики хабр не переваривает:

a6269779d03714ad76f70861b51287b3.png

Всем удачного дня и побольше времени на написание собственных DSL:)

Исходный код здесь: demidko/Wolf-Goat-Cabbage
Приветствуется критика и предложения как сделать лучше.

© Habrahabr.ru