Go program to find the shortest path from one word to another

words.go

package main

import "log"
import "bytes"
import "bufio"
import "os"
import "sync"
import "runtime"
import "io/ioutil"

const LETTERS = "abcdefghijklmnopqrstuvwxyz"
const CHAN_BUFF = 1000

type Set map[string]bool
type Graph map[string][]string
type Path []string

type Edges struct {
	word            string
	transformations []string
}

func check(e error) {
	if e != nil {
		panic(e)
	}
}

func makeDictionary(file []byte) (dictionary Set) {
	log.Println("building dictionary from wordlist")
	scanner := bufio.NewScanner(bytes.NewBuffer(file))
	dictionary = make(Set)

	for scanner.Scan() {
		dictionary[scanner.Text()] = true
	}
	return
}

func graphBuilder(wordChan <-chan string, edgeChan chan<- Edges, dictionary Set, wg *sync.WaitGroup) {

	// process each word in the dictionary
	for word := range wordChan {
		var transformations []string

		// process each letter in the word
		for index := range word {
			// delete mutation
			deleted := word[:index] + word[index+1:]
			if dictionary[deleted] {
				transformations = append(transformations, deleted)
			}

			// change mutation
			for _, c := range LETTERS {
				changed := word[:index] + string(c) + word[index+1:]
				if dictionary[changed] && changed != word {
					transformations = append(transformations, changed)
				}
			}
		}

		// add mutation
		for i := 0; i < len(word)+1; i++ {
			for _, char := range LETTERS {
				added := word[:i] + string(char) + word[i:]
				if dictionary[added] {
					transformations = append(transformations, added)
				}
			}
		}

		edgeChan <- Edges{word, transformations}
	}
	wg.Done()
}

func buildGraph(dictionary Set) Graph {
	log.Println("building graph")
	fanOut := runtime.NumCPU()
	graph := make(Graph, len(dictionary))

	wordChannel := make(chan string, CHAN_BUFF)
	edgesChannel := make(chan Edges, CHAN_BUFF)

	var wg sync.WaitGroup
	wg.Add(fanOut)

	for i := 0; i < fanOut; i++ {
		log.Println("spinning up graphBuilder #", i)
		go graphBuilder(wordChannel, edgesChannel, dictionary, &wg)
	}

	go func() {
		for word := range dictionary {
			wordChannel <- word
		}
		close(wordChannel)
	}()

	go func() {
		wg.Wait()
		close(edgesChannel)
	}()

	for edges := range edgesChannel {
		graph[edges.word] = edges.transformations
	}

	log.Println("graph is built")
	return graph
}

func transformWord(graph Graph, start string, goal string) Path {
	log.Println("searching for shortest transformation from " + start + " to " + goal)
	initialPath := Path{start}
	paths := append([]Path{}, initialPath)
	searched := make(Set)

	for len(paths) != 0 {
		currentPath := paths[0]
		paths = paths[1:]
		currentWord := currentPath[len(currentPath)-1]

		if searched[currentWord] {
			continue
		}

		searched[currentWord] = true
		transforms := graph[currentWord]

		for _, transformation := range transforms {
			// found the word we were looking for
			if transformation == goal {
				return append(currentPath, transformation)
			}

			// check if transformation is in the current path -- prevent cycles
			present := false
			for _, pathWord := range currentPath {
				if transformation == pathWord {
					present = true
				}
			}

			// if we don't have a cycle, add the transformation to path queue
			if !present {
				newPath := make(Path, len(currentPath)+1)
				copy(newPath, currentPath)
				newPath = append(newPath, transformation)
				paths = append(paths, newPath)
			}
		}
	}
	return Path{}
}

func main() {
	file, err := ioutil.ReadFile("/usr/share/dict/words")
	check(err)

	if len(os.Args) != 3 {
		panic("usage: " + os.Args[0] + " goal start")
	}
	args := os.Args[1:3]

	dictionary := makeDictionary(file)
	graph := buildGraph(dictionary)
	path := transformWord(graph, args[0], args[1])

	log.Println("path:", path)
}