eine Falte in Scala

Question

ich geschrieben habe eine einfache Tiefensuche in Scala mit einer rekursiven Funktion wie folgt aus:

search(labyrinth, path, goal) 

wo Labyrinth ist eine Spezifikation des Problems (als Grafik oder was auch immer), Pfad ist eine Liste, die den bisherigen Pfad enthält und Ziel ist eine Spezifikation des Zielzustands. Die Funktion gibt einen Pfad zum Ziel als List und Nil zurück, wenn kein Pfad gefunden werden kann.

Die Funktion expandiert z.B. findet alle geeigneten nächsten Knoten (Kandidaten) und muss sich dann rekursiv selbst nennen.

ich tun dies, indem

candidates.foldLeft(Nil){ 
    (solution, next) => 
    if(solution == Nil) 
     search(labyrinth, next :: path, goal) 
    else 
     solution 
} 

Bitte beachten Sie, dass ich einige unescessary Details weggelassen. Bis jetzt funktioniert alles gut. Wenn jedoch innerhalb des Aufrufs von foldLeft eine Lösung gefunden wird, wird diese Lösung einfach durch den else-Teil der if-Anweisung kopiert. Gibt es eine Möglichkeit, dies zu vermeiden, indem Sie das FoldLeft aufbrechen oder vielleicht eine andere Funktion anstelle von FoldLeft verwenden? Eigentlich könnte ich wohl eine Version von foldLeft schreiben, die bricht, sobald "not Nil" selbst zurückgegeben wird. Aber gibt es einen in der API?

Answer 1

Ich bin mir nicht sicher, ob ich den Wunsch verstehe, die Schleife kurzzuschließen. Ist es teuer, die Kandidaten zu durchlaufen? Ist die Kandidatenliste potenziell groß?

Vielleicht könnten Sie die Methode verwenden „finden“:

candidates.find { c => 
    Nil != search(labyrinth, c :: path, goal) 
} match { 
    case Some(c) => c :: path 
    case None => Nil 
} 

Wenn die potentielle Tiefe des Suchraums groß ist, können Sie Ihren Stack überlaufen könnte (Fitting, diese Site-Namen angegeben). Aber das ist ein Thema für einen anderen Beitrag.

Für kichern, hier ist eine tatsächliche ausführbare Implementierung. Ich musste eine lokale veränderbare Variable (FullPath) hauptsächlich aus Faulheit einführen, aber ich bin mir sicher, dass du diese herausnehmen könntest.

object App extends Application { 

    // This impl searches for a specific factor in a large int 
    type SolutionNode = Int 
    case class SearchDomain(number: Int) { 
     def childNodes(l: List[Int]): List[Int] = { 
      val num = if (l.isEmpty) number else l.head 
      if (num > 2) { 
       (2 to (num - 1)) find { 
        n => (num % n)==0 
       } match { 
        case Some(i) => List(i, num/i) 
        case None => List() 
       } 
      } 
      else List() 
     } 
    } 
    type DesiredResult = Int 


    def search (labyrinth: SearchDomain, path: List[SolutionNode], goal: DesiredResult): List[SolutionNode] = { 

     if (!path.isEmpty && path.head == goal) return path 
     if (path.isEmpty) return search(labyrinth, List(labyrinth.number), goal) 

     val candidates: List[SolutionNode] = labyrinth.childNodes(path) 
     var fullPath: List[SolutionNode] = List() 
     candidates.find { c => 
      fullPath = search(labyrinth, c :: path, goal) 
      !fullPath.isEmpty 
     } match { 
      case Some(c) => fullPath 
      case None => Nil 
     } 
    } 

    // Is 5 a factor of 800000000? 
    val res = search(SearchDomain(800000000), Nil, 5) 
    println(res) 

} 

Answer 2

Ich mag Mitch Blevins Lösung, da es eine perfekte Ergänzung für Ihren Algorithmus ist. Sie könnten an my own solution zu einem anderen Labyrinth Problem interessiert sein.