tutorial - nsoperationqueue swift 3 example

Una solución más rápida para caminar de una palabra a otra

Question

Tengo una tarea de tarea donde el objetivo es hacer que una palabra se convierta en otra, cambiando solo un personaje a la vez. Elijo hacerlo en Swift y usar el diccionario BSD estándar ( /usr/share/dict/words ) para mi fuente de palabras.

El siguiente código funciona como se esperaba. Sin embargo, para algunas combinaciones, funciona bastante despacio. Por ejemplo, define -> system

¿Puedo usar Grand Central Dispatch y procesamiento paralelo para hacerlo más rápido? ¡Muchas gracias!

import Foundation

typealias CString = [CChar]

// Get list of words from the standard BSD dictionary
let wordList = try! String(contentsOfFile: "/usr/share/dict/words")
    .componentsSeparatedByString("/n")
    .map { $0.lowercaseString.cStringUsingEncoding(NSUTF8StringEncoding)! }


func distance(fromCString: CString, toCString: CString) -> Int {
    guard fromCString.count == toCString.count else {
        fatalError("The two strings must have the same number of characters")
    }

    var distance = 0
    for i in 0..<fromCString.count {
        if fromCString[i] != toCString[i] {
            distance++
        }
    }
    return distance
}

func find(start: String, _ end: String) -> [String]? {
    guard start.characters.count == end.characters.count else {
        fatalError("''/(start)'' and ''/(end)'' must have the same number of characters")
    }

    // String is slow. Switch to bytes array for speed
    let startCString = start.cStringUsingEncoding(NSUTF8StringEncoding)!
    let endCString   = end.cStringUsingEncoding(NSUTF8StringEncoding)!

    // Get list of words with same length
    var candidates = wordList.filter { $0.count == startCString.count }

    // If either start or end is not in the dictionary, fail
    guard (candidates.contains { $0 == startCString }) else {
        fatalError("''/(start)'' is not in the dictionary")
    }
    guard (candidates.contains { $0 == endCString }) else {
        fatalError("''/(end)'' is not in the dictionary")
    }

    // Do the search
    var i = 0
    var iterations = 0
    var queue = [[CString]]()
    queue.append([startCString])

    while queue.count > 0, let lastWord = queue[0].last where lastWord != endCString {
        iterations++
        i = 0

        while i < candidates.count {
            if candidates[i] == lastWord {
                candidates.removeAtIndex(i)
            } else if distance(lastWord, toCString: candidates[i]) == 1 {
                queue.append(queue[0] + [candidates[i]])
                candidates.removeAtIndex(i)
            } else {
                i++
            }
        }

        queue.removeAtIndex(0)
    }

    if queue.isEmpty {
        print("Cannot go from ''/(start)'' to ''/(end)''")
        return nil
    } else {
        return queue[0].map { String(CString: $0, encoding: NSUTF8StringEncoding)! }
    }
}

Ejemplos:

find("bat", "man")       // bat -> ban -> man. 190 iterations, fast.
find("many", "shop"))    // many -> mand -> main -> said -> saip -> ship -> shop. 4322 iterations, medium

find("define", "system") // impossible
find("defend", "oppose") // impossible

Answer 1

Pequeño problema muy interesante. Usar la indexación nativa en los diccionarios te permitirá hacer que esto vaya mucho más rápido. Además, puede reducir considerablemente el número de iteraciones buscando una cadena de palabras de ambos extremos al mismo tiempo.

Hice un ejemplo que tiene un tiempo de configuración más largo pero, una vez que se hace la indexación de palabras, los resultados de la cadena de palabras son prácticamente instantáneos.

// --- wordPath.swift ---

// create a list of link patterns for a word
// ------------------------------------------
// A link pattern is an ordered list of letters in a word where one letter is missing
//
// This corresponds to a combination of letters that can from the word
// by adding a single letter and, conversely to combinations of letters that
// are possible by removing a letter from the word
//
// Letters are sorted alphabetically in order to ignore permutations
//
// for example:   
//
//   "corner" has 6 link patterns (one of which is a duplicate)
//                
//   the sorted letters are : "cenorr"
//
//   the links are the 6 combinations of 5 out of 6 letters of "cenorr"
//   with letters kept in alphabetical order.
//
//   because letters are sorted, the combinations can be obtained by
//   removing one letter at each position.
//
//   removing position 1 : enorr
//   removing position 2 : cnorr
//   removing position 3 : ceorr
//   removing position 4 : cenrr 
//   removing position 5 : cenor 
//   removing position 6 : cenor (this is the duplicate)
//  
public func linksOfWord(_ word:String)->[String]
{
  var result:[String] = []

  // sort letters
  let sortedLetters = word.characters.sorted()

  // return one string for each combination of N-1 letters
  // exclude duplicates (which will always be consecutive)
  var wordLink = ""
  for skipChar in sortedLetters.indices
  { 
    let nextLink = String(sortedLetters[0..<skipChar]) 
                 + String(sortedLetters[skipChar+1..<sortedLetters.count]) 
    if nextLink == wordLink { continue }

    wordLink = nextLink
    result.append(wordLink)
  }

  return result
}


// Create an index of wordlinks to the words that can be fromed from them
// ----------------------------------------------------------------------
// - The wordLinks dictionary contains a list of all the words that can be formed
//   by adding one letter to a given link pattern
// - This is essentially the reverse of linksOfWord for all words in the dictionary
// - note: Swift will use lazy initialization for this global variable, only executing the closure once.
//
public var wordsOfLink:[String:[String]] = 
{
  var result:[String:[String]] = [:]

  // get all words
  let wordList = try! String(contentsOfFile: "/usr/share/dict/words")
                      .lowercased()
                      .components(separatedBy:"/n")

  // add each word to the index of its wordLinks                        
  for word in wordList
  {
     for wordLink in linksOfWord(word)
     {
        result[wordLink] = (result[wordLink] ?? []) + [word]
     }
  }

  return result   
}()

// Iteration counted, for comparison with OP
public var iterations = 0

// word path seeking algorithm
// ---------------------------
// - Go through word paths using linksOfWord and wordsOfLink as a virtual tree structure
//   linksOfWord("word") -> 1:N array of links -> wordsOfLink("Link") -> 1:N array of words
// - Performs a breadth-first tree search by exausting shorter path lengths before moving on to longer ones
// - Simultaneously search forward and backward to minimize the exponential nature of path expansions
//

public func findWordPath(from fromWord:String, to toWord:String, shortestPath:Bool=false) -> [String]?
{
   iterations = 0

   // both words must be same length
   guard fromWord.characters.count == toWord.characters.count
   else  { return nil }

   // processing in lowercase only
   let startWord = fromWord.lowercased()
   let endWord   = toWord.lowercased()

   // keep track of links already processed (avoid infinite loops)
   var seenLinks = Set<String>() 
   var seenWords = Set<String>()

   // path expansion from starting word forward to ending word  
   var forwardLinks:[String:[String]] = [:]           // links that have a forward path connecting to the starting word
   var forwardPaths                   = [[startWord]] // partial forward paths to examine
   var forwardIndex                   = 0             // currently examined forwardPath (index) 

   // path expansion from ending word backward to starting word
   var backwardLinks:[String:[String]] = [:]            // links that have a backward path connecting to the ending word
   var backwardPaths                   = [[endWord]]    // partial backward paths to examine
   var backwardIndex                   = 0              // currently examined backwardPath (index)

   // establish initial links to start and end words 
   // - allows logic to only check path to path connections 
   //   (and not path to word in addition to it)
   linksOfWord(startWord).forEach{forwardLinks[$0] = [startWord]}
   linksOfWord(endWord).forEach{backwardLinks[$0]  = [endWord]}


   // Explore shorter paths in each direction before moving on to longer ones
   // This improves performance but does not guarantee the shortest word path 
   // will be selected when a connection is found 
   // e.g. forward(4)->backward(3) could be found before backward(4)->forward(2)
   //      resulting in a 7 word path when a 6 word path exists.
   // Finding the shortest possible word path requires that we explore forward only
   // (which is what the shortestPath parameter controls)
   var currentLength = 1

   // Examine partial word paths in multiple passes with an increasing path length (currentLength)
   // - For each path length, check if forward and backward paths can connect to one another.
   // - For each length, forwardIndex and backwardIndex advance through the paths
   //   of the current length thus exhausting both forward and backward paths of that length
   //   before moving on to the next length.
   // - As paths of the current length are examined, the partial path arrays receive new (longer) word paths
   //   to examine. 
   // - The added paths have 1 additional word which creates a new group of paths for the next pass
   //   at currentLength + 1
   // - When none of the partial word paths can be extended by adding a word that was not seen before
   //   the forward or backward path array will stop growing and the index will reach the end of the array
   //   indicating that no word path exists between start and end words
   while forwardIndex < forwardPaths.count 
         && ( backwardIndex < backwardPaths.count || shortestPath )
   {
       // Examine forward path links (of current length) for connection
       // to the end word or to a backward path that connects to it
       while forwardIndex < forwardPaths.count
          && forwardPaths[forwardIndex].count == currentLength
       {
          let forwardPath = forwardPaths[forwardIndex]

          forwardIndex   += 1
          iterations     += 1

          // expand links for last word of "forward" path
          for wordLink in linksOfWord(forwardPath.last!) 
          {
             // link connects to a backward path, return the combined forward and backward paths
             if let backwardPath = backwardLinks[wordLink]
             { return forwardPath + backwardPath }

             // don''t explore links that have already been examined
             if !seenLinks.insert(wordLink).inserted
             { continue }

             // record forward path to allow linking from backward paths
             // i.e. this link is known to lead to the starting word (through forwardPath)
             if !shortestPath
             { forwardLinks[wordLink] = forwardPath }

             // for all words that can be created by adding one letter to the word link   
             // add new forward paths to examine on the next length pass
             for word in wordsOfLink[wordLink] ?? []
             { 
               if seenWords.insert(word).inserted
               {
                 forwardPaths.append(forwardPath + [word])
               }
             }
          } 
       }

       // Examine backward path links (of current length) for connection
       // to the start word or to a forward path that connects to it
       // allowing one length backward path to support unknown end words
       while !shortestPath
          && backwardIndex < backwardPaths.count
          && backwardPaths[backwardIndex].count == currentLength
       {
          let backwardPath = backwardPaths[backwardIndex]

          backwardIndex   += 1
          iterations      += 1

          // expand links for first word of "backward" path
          for wordLink in linksOfWord(backwardPath.first!)
          {
             // link connects to starting path, combine and return result
             if let forwardPath = forwardLinks[wordLink]
             { return forwardPath + backwardPath }

             // don''t explore links that have already been examined
             if !seenLinks.insert(wordLink).inserted
             { continue }

             // record backward path to allow linking from forward paths
             // i.e. this link is known to lead to the ending word (through backwardPath)
             backwardLinks[wordLink] =  backwardPath

             // for all words that can be created by adding one letter to the word link   
             // add new backward paths to examine on the next length pass
             for word in wordsOfLink[wordLink] ?? []
             { 
                if seenWords.insert(word).inserted
                {
                  backwardPaths.append( [word] + backwardPath ) 
                }
             }
          } 
       }

       // all forward and backward paths of currentLength have been examined
       // move on to next length
       currentLength += 1
   }

   // when either path list is exausted, there are no possible paths.
   return nil
}

...

// --- Playground ---

// compute word path and print result
func printWordPath(_ firstWord:String, _ lastWord:String)
{
  print("    printWordPath(/"/(firstWord)/",/"/(lastWord)/")")

  let startTime = ProcessInfo().systemUptime
  if let foundPath = findWordPath(from:firstWord, to:lastWord, shortestPath:false)
  { 
    let time = String(format:"%.5f",ProcessInfo().systemUptime-startTime)
    print("    ///(foundPath.count) words :  /(foundPath)/n    //        /(iterations) iterations, /(time) sec ")
  }
  else
  { print("    // No Path Found between /(firstWord) and /(lastWord)") }
  print("")
}

printWordPath("bat","man")
// 3 words :  ["bat", "amt", "man"]
//        16 iterations, 6.34718 sec <-- longer time here because of initializations

printWordPath("many","shop")
// 5 words :  ["many", "hymn", "homy", "hypo", "shop"]
//        154 iterations, 0.00752 sec 

printWordPath("many","star")
// 4 words :  ["many", "maty", "mast", "star"]
//        101 iterations, 0.00622 sec 

printWordPath("define","system")
// 6 words :  ["define", "fenite", "entify", "feisty", "stymie", "system"]
//        574 iterations, 0.02374 sec 

printWordPath("defend","oppose")
// 6 words :  ["defend", "depend", "depone", "podeon", "pooped", "oppose"]
//        336 iterations, 0.01273 sec 

printWordPath("alphabet","integers")
// 7 words :  ["alphabet", "lapithae", "apterial", "epistlar", "splinter", "sterling", "integers"]
//        1057 iterations, 0.04454 sec 

printWordPath("Elephant","Microbes")
// 8 words :  ["elephant", "antelope", "lapstone", "parsonet", "somepart", "imposter", "comprise", "microbes"]
//        2536 iterations, 0.10133 sec 

printWordPath("Microbes","Elephant")
// 8 words :  ["microbes", "comprise", "persicot", "petrolic", "copalite", "pectinal", "planchet", "elephant"]
//        2232 iterations, 0.09649 sec 

printWordPath("Work","Home")
// 4 words :  ["work", "worm", "mohr", "home"]
//        52 iterations, 0.00278 sec 

printWordPath("Head","Toes")
// 4 words :  ["head", "ahet", "ates", "toes"]
//        146 iterations, 0.00684 sec 

printWordPath("North","South")
// 3 words :  ["north", "horst", "south"]
//        22 iterations, 0.00189 sec 

printWordPath("Employee","Pesident")
// 7 words :  ["employee", "employed", "redeploy", "leporide", "pedelion", "disponee", "pesident"]
//        390 iterations, 0.01810 sec 

printWordPath("Yellow","Orange")
// 5 words :  ["yellow", "lowery", "royale", "royena", "orange"]
//        225 iterations, 0.01025 sec 

printWordPath("Whale","shark")
// 4 words :  ["whale", "hawse", "asher", "shark"]
//        94 iterations, 0.00473 sec 

printWordPath("Police","Fellon")
// 4 words :  ["police", "pinole", "lionel", "fellon"]
//        56 iterations, 0.00336 sec 

printWordPath("religion","insanity")
// 6 words :  ["religion", "triolein", "reinstil", "senility", "salinity", "insanity"]
//        483 iterations, 0.02411 sec 

printWordPath("ebony","ivory")
// 4 words :  ["ebony", "eryon", "irony", "ivory"]
//        53 iterations, 0.00260 sec 

printWordPath("electronic","mechanical")
// 7 words :  ["electronic", "citronelle", "collineate", "tellinacea", "chatelaine", "atechnical", "mechanical"]
//        316 iterations, 0.01618 sec 

printWordPath("detrimental","appropriate")
// 7 words :  ["detrimental", "pentremital", "interpolate", "interportal", "prerational", "preparation", "appropriate"]
//        262 iterations, 0.01319 sec 

Tenga en cuenta que esto encuentra soluciones para sus dos últimos ejemplos y también noté que muchos -> mand -> main -> dijo -> ... estaba reemplazando dos letras que iban de "main" a "said", así que terminé con un camino diferente

Por cierto, puse las funciones en un archivo separado en el patio de juegos (en Fuentes) porque el recuento de ejecuciones de línea estaba ralentizando la ejecución hasta un rastreo.

[EDITAR] Las iteraciones modificadas cuentan para que sea más coherente con la forma en que contaba el código del OP. Se agregaron más ejemplos (se divirtieron demasiado con esto).

[EDIT] adaptado para Swift 3, agregó más explicación de la lógica, simplificó / optimizó aún más el código.