我有一个家庭作业,其目标是使一个单词成为另一个单词,一次只更改一个单词.我选择在 Swift中使用标准BSD字典(/usr/share / dict / words)作为我的单词源. 下面的代码按预期工作.但是,对于某些
下面的代码按预期工作.但是,对于某些组合,它运行得相当慢.例如,define – >系统
我可以使用Grand Central Dispatch和并行处理来加快速度吗？非常感谢！
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)! }
}
}
例子：
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
非常有趣的小问题.在字典中使用本机索引可以让您更快地完成此操作.此外,您可以通过同时从两端搜索单词链来显着减少迭代次数.
我做了一个具有较长设置时间的例子,但是一旦完成了单词索引,单词链结果几乎是瞬时的.
// --- 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
请注意,这可以找到最后两个示例的解决方案,我也注意到很多 – > mand – >主要 – >说 – > …正在替换从“主要”到“说”的两个字母,所以我最终得到了一条不同的路径.
顺便说一句,我把这些函数放在操场上的一个单独的文件中(在Sources下),因为行执行的计数使执行速度变慢到爬行速度.
[编辑]改变迭代次数使其与OP的代码计数方式更加一致.添加了更多示例(对此有太多乐趣).
[编辑]改编为Swift 3,增加了对逻辑的更多解释,进一步简化/优化了代码.