Multiverse and Crossing Challenges

Once I read on Habré an article "Transporting a wolf, a goat and a cabbage across a river with effects in Haskell" , which I liked so much that I decided to write a framework for the entire class of crossing problems using multi-paradigm design. Finally we managed to find the time, and now, after almost a year, the framework is ready. Now the characters, their interactions and the description of the desired result are set through a domain-specific language , which allows you to solve any puzzles of this kind with step-by-step inference. Below is a step-by-step breakdown of the DSL implementation. The article is suitable for those who are studying the Kotlin language or are simply interested in examples of its use. Some minor details (like imports and output) have been omitted for brevity.

The character can be easily described as an open class for inheritance:

open class Person(private val name: String)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

, :

typealias Place = Set<Person>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

. , , :

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

where, N . (condition) , (selector) . , , , ​:)

, :

class LeftBoat(left: Place, right: Place) : 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: Place.() -> 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 Place.isCompatible() =
  contains(Farmer) ||
    (!contains(Wolf) || !contains(Goat)) &&
    (!contains(Goat) || !contains(Cabbage))

fun main() {

  val property = setOf(Wolf, Goat, Cabbage)

  //    
  LeftBoat(property)
     //    
    .where(Place::isCompatible)
    //      ,
    //       
    { right.containsAll(property) } 
    //     
    .forEach(History::prettyPrint)
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Here's what happened, I insert it with a screenshot, because Habr does not digest emoticons:

Have a good day and more time to write your own DSL :)

The source code is here: demidko / river-crossing-puzzle

Critics and suggestions on how to do better are welcome.