import Foundation | |
let url = try URL(string: "http://norvig.com/ngrams/TWL06.txt").unwrap() | |
let data = try Data(contentsOf: url) | |
let string = try String(data: data, encoding: .utf8).unwrap() | |
let array = string.components(separatedBy: .newlines) | |
let lexicon = Set(array.fourLetterStrings()) | |
let allLetters = Array("ABCDEFGHIJKLMNOPQRSTUVWXYZ") | |
func findPath(between sourceWord: String, and targetWord: String) -> [String]? { | |
if sourceWord == targetWord { return [] } | |
var seen: Set = [sourceWord] | |
var queue: [(item: String, path: [String])] = [(sourceWord, [])] | |
while true { | |
if queue.count == 0 { return nil } | |
let (item, path) = queue.removeFirst() | |
if item == targetWord { return path + [item] } | |
let sourceAsArray = Array(item) | |
for characterIndex in sourceAsArray.indices { | |
for letter in allLetters { | |
var copy = sourceAsArray | |
copy[characterIndex] = letter | |
let oneLetterAway = String(copy) | |
if lexicon.contains(oneLetterAway) && !seen.contains(oneLetterAway) { | |
queue.append((oneLetterAway, path + [item])) | |
seen.insert(oneLetterAway) | |
} | |
} | |
} | |
} | |
} | |
let path = try findPath(between: "TOON", and: "PLEA").unwrap() | |
print(path) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment