Tantangan Multiverse dan Crossing

Suatu kali saya membaca di Habré sebuah artikel "Mengangkut serigala, kambing, dan kubis melintasi sungai dengan efek di Haskell" , yang sangat saya sukai sehingga saya memutuskan untuk menulis kerangka kerja untuk seluruh kelas masalah penyeberangan menggunakan desain multi-paradigma . Akhirnya kami berhasil menemukan waktu, dan sekarang, setelah hampir satu tahun, kerangka sudah siap. Sekarang karakter, interaksinya, dan deskripsi hasil yang diinginkan diatur melalui bahasa khusus domain , yang memungkinkan Anda untuk memecahkan teka-teki semacam ini dengan kesimpulan langkah demi langkah. Di bawah ini adalah rincian langkah demi langkah implementasi DSL. Artikel ini cocok untuk mereka yang sedang mempelajari bahasa Kotlin atau hanya tertarik dengan contoh penggunaannya. Beberapa detail kecil (seperti impor dan keluaran) telah dihilangkan untuk singkatnya.

Karakter dapat dengan mudah digambarkan sebagai kelas terbuka untuk pewarisan:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Inilah yang terjadi, saya menyisipkannya dengan tangkapan layar, karena Habr tidak mencerna emotikon:

Semoga hari Anda menyenangkan dan lebih banyak waktu untuk menulis DSL Anda sendiri :)

Kode sumbernya ada di sini: demidko / teka-teki penyeberangan sungai

Kritik dan saran tentang bagaimana menjadi lebih baik dipersilakan.