Create a gist now

Instantly share code, notes, and snippets.

@khanlou /WordLadder.swift Secret
Last active Apr 18, 2018

What would you like to do?
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