// Example programming problem from CodeWars.  See also wordenum.py.
// Dict{'1': {"a", "b"}, '2': {"c", "d"}}.GetWords("122") =>
// {"acc", "acd", "adc", "add", "bcc", "bcd", "bdc", "bdd"} in any order.

// Four solutions: breadth-first nonrecursive, depth-first recursive,
// depth-first nonrecursive, depth-first recursive with channels.  The
// breadth-first solution was quickest to write (perhaps because I'd
// already seen it), but I like the recursive solution best.  All the
// solutions generate an O(k**N) amount of output, but the solution
// with channels does it in only O(N) memory, while the others all
// require O(k**N) memory too.  In this example k=2 and N=3.
package main

type Dict map[rune][]string

// breadth-first
func (d Dict) GetWords(pat string) []string {
	result := []string{""} // base case
	for _, patchar := range pat {
		nr := []string{}
		for _, s := range result {
			for _, wc := range d[patchar] {
				nr = append(nr, s+wc)
			}
		}
		result = nr
	}
	return result
}

// depth-first, recursive
func (d Dict) visitor(prefix string, pat []rune, results []string) []string {
	if len(pat) == 0 {
		return append(results, prefix)
	}

	suffix := pat[1:]
	for _, c := range d[pat[0]] {
		results = d.visitor(prefix+c, suffix, results)
	}

	return results
}

func (d Dict) GetWordsDR(pat string) []string {
	return d.visitor("", []rune(pat), []string{})
}

// depth-first, nonrecursive
func (d Dict) GetWordsD(pat string) []string {
	type stackItem struct {
		pos    int
		prefix string
	}

	pr := []rune(pat)
	stack := []stackItem{{0, ""}}
	result := []string{}

	for len(stack) > 0 {
		// Remove the latest work item still pending on the
		// stack.  If we were to pick a different item here,
		// the search would no longer be depth-first; for
		// example, by using a queue it would become
		// breadth-first, or by augmenting the work items with
		// a "goodness" and using a priority queue it would
		// become best-first, for example A*.
		sp := len(stack) - 1
		item := stack[sp]
		stack = stack[:sp]

		if item.pos == len(pr) { // Base case, end of pattern?
			result = append(result, item.prefix)
			continue
		}

		for _, c := range d[pr[item.pos]] {
			item := stackItem{item.pos + 1, item.prefix + c}
			stack = append(stack, item)
		}
	}

	return result
}

// depth-first, recursive with channels
func (d Dict) cvisitor(prefix string, pat []rune, results chan string) {
	if len(pat) == 0 {
		results <- prefix
		return
	}

	suffix := pat[1:]
	for _, c := range d[pat[0]] {
		d.cvisitor(prefix+c, suffix, results)
	}
}

func (d Dict) GetWordsDC(pat string) chan string {
	results := make(chan string)
	go (func() {
		d.cvisitor("", []rune(pat), results)
		close(results)
	})()
	return results
}

func main() {
	d := Dict{
		'1': {"a", "b"},
		'2': {"c", "d"},
	}

	for s := range d.GetWordsDC("122") {
		println(s)
	}
	println("")

	for _, s := range d.GetWordsD("122") {
		println(s)
	}
}