तोड़ या स्काला

Question

में एक गुना shortcircuit मुझे लगता है कि जैसे एक पुनरावर्ती समारोह के साथ स्काला में एक साधारण गहराई-पहले खोज में लिखा है:

search(labyrinth, path, goal) 

जहां भूलभुलैया समस्या का एक विनिर्देश है (ग्राफ या जो कुछ भी रूप में), पथ एक ऐसी सूची है जो अब तक उठाए गए पथ को रखती है और लक्ष्य लक्ष्य राज्य का एक विनिर्देश है। यदि कोई पथ नहीं मिल पाता है तो फ़ंक्शन लक्ष्य और नील के रूप में लक्ष्य के लिए पथ प्रदान करता है।

फ़ंक्शन फैलता है, उदा। सभी उपयुक्त अगले नोड्स (उम्मीदवार) पाता है और फिर उसे खुद को कॉल करना पड़ता है।

मैं द्वारा

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

ऐसा करने कृपया ध्यान दें कि मैं कुछ unescessary विवरण नहीं दिखाए हैं। सब कुछ ठीक काम कर रहा है। लेकिन फ़ोल्ड लेफ्ट कॉल के अंदर एक समाधान मिलने के बाद, यह समाधान बस-कथन के दूसरे भाग द्वारा कॉपी किया जाता है। क्या FoldLeft को तोड़कर या शायद foldLeft के बजाय एक अलग फ़ंक्शन का उपयोग करके इसे टालने का कोई तरीका है? असल में मैं शायद फोल्ड लेफ्ट का एक संस्करण लिख सकता हूं जो एक बार "नील" नहीं लौटाता है। लेकिन क्या एपीआई के अंदर कोई है?

Answer 1

मुझे यकीन नहीं है कि मैं लूप को शॉर्ट-सर्किट करने की इच्छा को समझता हूं। क्या उम्मीदवारों के माध्यम से इसे फिर से महंगा करना महंगा है? क्या उम्मीदवार संभावित रूप से बड़े हैं?

हो सकता है कि आपको "" विधि इस्तेमाल कर सकते हैं:

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

तो खोज स्थान की क्षमता का गहराई बड़ी है, तो आप अपने ढेर (फिटिंग, इस साइट का नाम दिया) अतिप्रवाह सकता है। लेकिन, यह एक और पोस्ट के लिए एक विषय है।

गिगल्स के लिए, यहां एक वास्तविक चलन योग्य कार्यान्वयन है। मुझे स्थानीय म्यूटेबल वैरिएबल (फुलपाथ) को ज्यादातर आलस्य से बाहर करना पड़ा, लेकिन मुझे यकीन है कि आप उन्हें बाहर ले जा सकते हैं।

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

मैं Mitch Blevins समाधान चाहते, क्योंकि यह आपके एल्गोरिथ्म के लिए एक आदर्श मुकाबला नहीं है। आपको my own solution में किसी अन्य भूलभुलैया की समस्या में रुचि हो सकती है।