// Package wordsearch is for solving word search game.
package wordsearch
import (
	"fmt"
	"unicode/utf8"
)
type crds [2][2]int
type result struct {
	crd crds
	w   string
	err error
}
type grid []string
// Solve returns the word map with coordinates.
func Solve(words []string, g grid) (map[string][2][2]int, error) {
	res := make(chan result)
	// Check words in parallel. Does not make sense here, because findWord() is cheap
	// and it only adds overhead, but was fun to write, so I kept this way.
	for _, w := range words {
		go g.findWord(res, w)
	}
	var ret = map[string][2][2]int{} // reflect.DeepEqual does not work with other types
	for i := 0; i < len(words); i++ {
		r := <-res
		if r.err != nil {
			return nil, r.err
		}
		ret[r.w] = r.crd
	}
	return ret, nil
}
func (g grid) findWord(res chan<- result, word string) {
	first, _ := utf8.DecodeRuneInString(word)
	if first == utf8.RuneError {
		res <- result{crds{}, word, fmt.Errorf("no first rune in word")}
		return
	}
	for lNo, line := range g {
		for i, ch := range line {
			if ch == first {
				if g.findRight(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i + len(word) - 1, lNo}}, word, nil}
					return
				}
				if g.findLeft(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i - len(word) + 1, lNo}}, word, nil}
					return
				}
				if g.findTopBottom(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i, lNo + len(word) - 1}}, word, nil}
					return
				}
				if g.findBottomTop(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i, lNo - len(word) + 1}}, word, nil}
					return
				}
				if g.findTopLeftBottomRight(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i + len(word) - 1, lNo + len(word) - 1}}, word, nil}
					return
				}
				if g.findBottomRightTopLeft(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i - len(word) + 1, lNo - len(word) + 1}}, word, nil}
					return
				}
				if g.findBottomLeftTopRight(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i + len(word) - 1, lNo - len(word) + 1}}, word, nil}
					return
				}
				if g.findTopRightBottomLeft(lNo, i, word) {
					res <- result{crds{{i, lNo}, {i - len(word) + 1, lNo + len(word) - 1}}, word, nil}
					return
				}
			}
		}
	}
	res <- result{crds{}, word, fmt.Errorf("word not found")}
	return
}
func (g grid) findRight(lNo, pos int, word string) bool {
	if pos+len(word) >= len(g[lNo]) {
		return false
	}
	if g[lNo][pos:pos+len(word)] == word {
		return true
	}
	return false
}
func (g grid) findLeft(lNo, pos int, word string) bool {
	if pos-len(word)+1 < 0 {
		return false
	}
	runes := []rune(word)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	word = string(runes)
	if g[lNo][pos-len(word)+1:pos+1] == word {
		return true
	}
	return false
}
func (g grid) findTopBottom(lNo, pos int, word string) bool {
	for i, ch := range word {
		if i+lNo == len(g) || ch != rune(g[i+lNo][pos]) {
			return false
		}
	}
	return true
}
func (g grid) findBottomTop(lNo, pos int, word string) bool {
	for i, ch := range word {
		if lNo-i < 0 || ch != rune(g[lNo-i][pos]) {
			return false
		}
	}
	return true
}
func (g grid) findTopLeftBottomRight(lNo, pos int, word string) bool {
	for i, ch := range word {
		if lNo+i == len(g) || pos+i == len(g[lNo+i]) ||
			ch != rune(g[lNo+i][pos+i]) {
			return false
		}
	}
	return true
}
func (g grid) findBottomRightTopLeft(lNo, pos int, word string) bool {
	for i, ch := range word {
		if lNo-i < 0 || pos-i < 0 || ch != rune(g[lNo-i][pos-i]) {
			return false
		}
	}
	return true
}
func (g grid) findBottomLeftTopRight(lNo, pos int, word string) bool {
	for i, ch := range word {
		if lNo-i < 0 || pos+i == len(g[lNo-i]) || ch != rune(g[lNo-i][pos+i]) {
			return false
		}
	}
	return true
}
func (g grid) findTopRightBottomLeft(lNo, pos int, word string) bool {
	for i, ch := range word {
		if lNo+i == len(g) || pos-i < 0 || ch != rune(g[lNo+i][pos-i]) {
			return false
		}
	}
	return true
}

	var mysieve = genPrimesAtkin(MAX)

	// var mysieve = genPrimesAtkin(MAX)
	var mysieve = genPrimesE(MAX)

		if mysieve[i] { // this was !mysieve[i] with Erastothenes

		if !mysieve[i] { // this was !mysieve[i] with Erastothenes