A solution to a honeycomb word search problem.

honeycomb.go

package main

import (
	"fmt"
	"io/ioutil"
	"os"
	"sort"
	"strings"
)

var honeycomb [][]byte
var startLetterMap = make(map[byte][]cellLocation)

type cellLocation struct {
	layer int
	index int
}

func getLayer(cell int) int {
	return ((cell - 1) / 6) + 1
}

func getChar(loc cellLocation) byte {
	if hasLayer(loc.layer) {
		if loc.index < 0 {
			loc.index = lengthOfLayer(loc.layer) + loc.index
		}

		return honeycomb[loc.layer][loc.index%lengthOfLayer(loc.layer)]
	} else {
		return 0
	}
}

func hasLayer(layer int) bool {
	return len(honeycomb) > layer
}

func lengthOfLayer(layer int) int {
	if layer == 0 {
		return 1
	}

	return layer * 6
}

func layerSideLength(layer int) int {
	return lengthOfLayer(layer) / 6
}

func cornerIndexOfLayer(corner int, layer int) int {
	return layerSideLength(layer) * corner
}

func getNeighbourCells(loc cellLocation) []cellLocation {
	if loc.layer == 0 && hasLayer(1) {
		return []cellLocation{
			cellLocation{1, 0},
			cellLocation{1, 1},
			cellLocation{1, 2},
			cellLocation{1, 3},
			cellLocation{1, 4},
			cellLocation{1, 5},
		}
	}

	distFromCorner := loc.index % layerSideLength(loc.layer)
	closestCorner := loc.index / layerSideLength(loc.layer)
	cornerUp := cornerIndexOfLayer(closestCorner, loc.layer+1)
	cornerDown := cornerIndexOfLayer(closestCorner, loc.layer-1)

	if distFromCorner == 0 {
		// Is a corner value
		return []cellLocation{
			cellLocation{loc.layer + 1, cornerUp},
			cellLocation{loc.layer + 1, cornerUp + 1},
			cellLocation{loc.layer, loc.index + 1},
			cellLocation{loc.layer - 1, cornerDown},
			cellLocation{loc.layer, loc.index - 1},
			cellLocation{loc.layer + 1, cornerUp - 1},
		}
	}

	return []cellLocation{
		cellLocation{loc.layer, loc.index + 1},
		cellLocation{loc.layer, loc.index - 1},
		cellLocation{loc.layer + 1, cornerUp + distFromCorner},
		cellLocation{loc.layer + 1, cornerUp + distFromCorner + 1},
		cellLocation{loc.layer - 1, cornerDown + distFromCorner},
		cellLocation{loc.layer - 1, cornerDown + distFromCorner - 1},
	}
}

func hasBeenSeen(seen []cellLocation, loc cellLocation) bool {
	for _, seenLoc := range seen {
		if loc == seenLoc {
			return true
		}
	}

	return false
}

func checkWordDFS(seen []cellLocation, loc cellLocation,
	remainder string) bool {
	var newSeen = make([]cellLocation, len(seen))
	copy(newSeen, seen)
	newSeen = append(newSeen, loc)

	cells := getNeighbourCells(loc)

	for _, cell := range cells {
		if getChar(cell) == remainder[0] && !hasBeenSeen(seen, cell) {
			if len(remainder) == 1 {
				return true
			}

			if checkWordDFS(newSeen, cell, remainder[1:]) {
				return true
			}
		}
	}

	return false
}

func checkForWord(word string) bool {
	if _, ok := startLetterMap[word[0]]; !ok {
		return false
	}

	for _, loc := range startLetterMap[word[0]] {
		if checkWordDFS([]cellLocation{}, loc, word[1:]) {
			return true
		}
	}

	return false
}

func main() {
	file, err := os.Open("honeycomb.txt")
	if err != nil {
		panic(err)
	}

	data, err := ioutil.ReadAll(file)
	if err != nil {
		panic(err)
	}

	lines := strings.Split(string(data), "\n")[1:]

	for layer, line := range lines {
		if len(line) > 0 {
			honeycomb = append(honeycomb, []byte{})
		}

		for _, char := range line {
			startLetterMap[byte(char)] = append(startLetterMap[byte(char)],
				cellLocation{layer, len(honeycomb[layer])})

			honeycomb[layer] = append(honeycomb[layer], byte(char))
		}
	}

	file.Close()

	file, err = os.Open("dictionary.txt")
	if err != nil {
		panic(err)
	}

	data, err = ioutil.ReadAll(file)
	if err != nil {
		panic(err)
	}

	dictionary := strings.Split(string(data), "\n")
	sort.Strings(dictionary)

	for _, word := range dictionary {
		if len(word) > 0 && checkForWord(word) {
			fmt.Println(word)
		}
	}
}