Русский
Русский
English
Статистика
Реклама

Зачем я это сделал

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

16.06.2021 04:11:19 | Автор: admin

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

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

open class Person(private val name: String)

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

typealias Riverside = Set<Person>

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

abstract class QuantumBoat(  val left: Riverside, val right: Riverside) {    abstract fun invert(): List<QuantumBoat>    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<QuantumBoat>  fun Sequence<History>.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<History> {    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)}

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

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

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

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru