algorithm - Kotlin Cannibals and Missionaries 算法 - 如何转换为完整的 FP

Question

关于如何改进以下代码以使其更加面向函数式编程的任何建议。具体如何删除表示历史状态的 MutableList。有两个数据类：Bank，表示河岸（传教士人数和目前在河岸上的食人族人数）和 BankState，表示两个河岸的历史状态（源河岸、目标河岸和boatAtSource - 一个布尔值，表示船目前是在源岸还是目标岸）。重载的运算符函数 plus 将传教士和食人者添加到河岸，而函数 minus 将它们从河岸中删除。船功能是最重要的功能。您可以像这样从 fun main (app.kt) 调用以下算法：

应用程序.kt

fun main(args:Array<String>) {
    val source:Bank = Bank(3,3)
    val target:Bank = Bank()
    source boat target
}

银行.kt

data class Bank(val missionaries:Int=0,val cannibals:Int=0)
data class BankState(val sourceTarget:Pair<Bank,Bank>,val boatAtSource:Boolean)

operator fun Bank.plus(b:Pair<Int,Int>):Bank = Bank(this.missionaries+b.first,this.cannibals+b.second)
operator fun Bank.minus(b:Pair<Int,Int>):Bank = Bank(this.missionaries-b.first,this.cannibals-b.second)
infix fun Bank.boat(target:Bank):List<BankState> {
    val begin = Pair(this,target)
    val history = mutableListOf<BankState>(BankState(begin,true))
    boat(begin,true,this.missionaries,this.cannibals,history)   
    return history
}

fun boat(sourceTarget:Pair<Bank,Bank>,
         boatAtSource:Boolean,
         totalMissionaries:Int,
         totalCannibals:Int,
         history:MutableList<BankState>):Boolean {

    if(sourceTarget.first.cannibals+sourceTarget.second.cannibals==totalCannibals &&
            sourceTarget.first.missionaries + sourceTarget.second.missionaries==totalMissionaries &&
            sourceTarget.first.cannibals>=0 &&
            sourceTarget.first.missionaries>=0 &&
            sourceTarget.second.cannibals>=0 &&
            sourceTarget.second.missionaries>=0 &&
            (sourceTarget.first.missionaries==0 || sourceTarget.first.missionaries>=sourceTarget.first.cannibals) &&
            (sourceTarget.second.missionaries==0 || sourceTarget.second.missionaries >= sourceTarget.second.cannibals)) {


            if(sourceTarget.second.missionaries==totalMissionaries &&
                    sourceTarget.second.cannibals==totalCannibals) {
                history.forEach(::println)              
                return true
            } else {


                val deltas = listOf(Pair(0,1),Pair(1,1),Pair(1,0),Pair(2,0),Pair(0,2))

                val comparator = object : Comparator<Pair<Pair<Boolean,Int>,Pair<Bank,Bank>>> {
                    override fun compare(arg1:Pair<Pair<Boolean,Int>,Pair<Bank,Bank>>,arg2:Pair<Pair<Boolean,Int>,Pair<Bank,Bank>>):Int {
                        if(arg1.first.first && arg2.first.first) {
                            return if(arg1.first.second<arg2.first.second) -1 else if(arg1.first.second>arg2.first.second) 1 else 0
                        } else if(arg1.first.first){
                            return 1
                        } else if(arg2.first.first) {
                            return -1
                        }
                        return 0
                    }
                }

                val result = deltas.map{
                    checkNext(it.first,it.second,totalMissionaries,totalCannibals,history,sourceTarget,boatAtSource)
                }.maxWith(comparator)


                if(result?.first?.first!=null && result.first.first) {
                    history.add(BankState(result.second,!boatAtSource))
                    return true;
                }       

            }
    }

    return false
}

fun checkNext(missionariesDelta:Int,
              cannibalsDelta:Int,
              totalMissionaries:Int,
              totalCannibals:Int,
              history:MutableList<BankState>,
              sourceTarget:Pair<Bank,Bank>,
              boatAtSource:Boolean):Pair<Pair<Boolean,Int>,Pair<Bank,Bank>> {
                val nextSrcTgt = if(boatAtSource) Pair(sourceTarget.first-Pair(missionariesDelta,cannibalsDelta),sourceTarget.second+Pair(missionariesDelta,cannibalsDelta))
                                    else Pair(sourceTarget.first+Pair(missionariesDelta,cannibalsDelta),sourceTarget.second-Pair(missionariesDelta,cannibalsDelta))
                val bankState:BankState = BankState(nextSrcTgt,!boatAtSource)
                if(!history.contains(bankState)) {
                    history.add(bankState)
                    val combo2:Boolean = boat(nextSrcTgt,!boatAtSource,totalMissionaries,totalCannibals,history)
                    val combo2Depth = history.size
                    history.remove(bankState)
                    return Pair(Pair(combo2,combo2Depth),nextSrcTgt)
                } else {
                    return Pair(Pair(false,0),nextSrcTgt)
                }
}

标签： algorithmfunctional-programmingkotlin