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

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

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

/**
* Мультиверсум для лодки
* @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)
    }
  }
}

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