Skip to content

Instantly share code, notes, and snippets.

@dthtvwls
Last active May 24, 2017 11:41
Show Gist options
  • Save dthtvwls/ccd4abe4b5091bb69b90596f69c9264e to your computer and use it in GitHub Desktop.
Save dthtvwls/ccd4abe4b5091bb69b90596f69c9264e to your computer and use it in GitHub Desktop.
Search stems in the dictionary using a trie
package main
import (
"bufio"
"flag"
"io/ioutil"
"log"
"net"
"os"
"strconv"
"strings"
"unicode"
)
type Node struct {
children map[byte]*Node
}
func NewNode() *Node {
return &Node{children: make(map[byte]*Node)}
}
func (n *Node) Add(word string) {
for _, letter := range word {
val := byte(letter)
if _, ok := n.children[val]; !ok {
n.children[val] = NewNode()
}
n = n.children[val]
}
}
func (n *Node) Contains(word string) bool {
for _, letter := range word {
val := byte(letter)
if _, ok := n.children[val]; !ok {
return false
}
n = n.children[val]
}
return true
}
var trie = NewNode()
func init() {
if file, err := os.Open("/usr/share/dict/words"); err != nil {
log.Fatalln(err)
} else {
defer file.Close()
scanner := bufio.NewScanner(file)
SCAN:
for scanner.Scan() {
word := scanner.Text()
if unicode.IsUpper(rune(word[0])) {
continue
}
for _, letter := range word {
if !unicode.IsLetter(letter) {
continue SCAN
}
}
trie.Add(word)
}
}
flag.Parse()
}
func main() {
if ln, err := net.Listen("tcp", flag.Arg(0)); err != nil {
log.Fatalln(err)
} else {
defer ln.Close()
for {
if conn, err := ln.Accept(); err != nil {
log.Println(err)
} else {
go func() {
defer conn.Close()
if message, err := ioutil.ReadAll(bufio.NewReader(conn)); err != nil {
log.Println(err)
} else {
conn.Write([]byte(strconv.FormatBool(trie.Contains(strings.TrimSpace(string(message))))))
}
}()
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment