anagrams - main.go

     1  package main
     2  
     3  import (
     4  	"errors"
     5  	"fmt"
     6  	"os"
     7  	"sort"
     8  	"strings"
     9  	"unsafe"
    10  )
    11  
    12  func main() {
    13  	if err := run(); err != nil {
    14  		fmt.Fprintln(os.Stderr, err)
    15  	}
    16  }
    17  
    18  func run() error {
    19  	var (
    20  		incomplete bool
    21  		plural     bool
    22  	)
    23  	args := os.Args
    24  Loop:
    25  	for {
    26  		args = args[1:]
    27  		if len(args) == 0 {
    28  			return errors.New("no words")
    29  		}
    30  		switch args[0] {
    31  		case "-p":
    32  			incomplete = true
    33  		case "-s":
    34  			plural = true
    35  		default:
    36  			break Loop
    37  		}
    38  	}
    39  	bs, err := os.ReadFile("/usr/share/dict/words")
    40  	if err != nil {
    41  		return fmt.Errorf("error reading dictionary: %w", err)
    42  	}
    43  	ss := strings.Split(strings.ToLower(byteSliceToString(bs)), "\n")
    44  	if plural {
    45  		for _, word := range ss {
    46  			if !strings.HasSuffix(word, "s") {
    47  				ss = append(ss, word+"s")
    48  			}
    49  		}
    50  	}
    51  	sort.Strings(ss)
    52  	wordsList := make([]map[byte][]string, len(args))
    53  	for n, words := range args {
    54  		wordsList[n] = make(map[byte][]string, strings.Count(words, " ")+1)
    55  		for _, word := range strings.Split(words, " ") {
    56  			var first byte
    57  			if len(word) > 0 {
    58  				first = strings.ToLower(word[:1])[0]
    59  			}
    60  			wordsList[n][first] = append(wordsList[n][first], word)
    61  			sort.Strings(wordsList[n][first])
    62  		}
    63  	}
    64  	buildAnagrams(ss, wordsList, make([]int, 0, len(wordsList)), make([]byte, 0, len(wordsList)), make([][]string, 0, len(wordsList)), incomplete)
    65  	sort.Sort(res)
    66  	var last string
    67  	for _, result := range res {
    68  		if result.Word != last {
    69  			fmt.Println(result.Word)
    70  			last = result.Word
    71  		}
    72  		for _, m := range result.Makeup {
    73  			fmt.Print("->")
    74  			for _, w := range m {
    75  				fmt.Print(" ", w)
    76  			}
    77  			fmt.Println()
    78  		}
    79  	}
    80  	return nil
    81  }
    82  
    83  func buildAnagrams(ss []string, wordsList []map[byte][]string, done []int, sofar []byte, words [][]string, incomplete bool) {
    84  	if len(done) < len(wordsList) {
    85  	Loop:
    86  		for n, wordsL := range wordsList {
    87  			for _, d := range done {
    88  				if n == d {
    89  					continue Loop
    90  				}
    91  			}
    92  			d := append(done, n)
    93  			for b, word := range wordsL {
    94  				if b == 0 {
    95  					buildAnagrams(ss, wordsList, d, sofar, words, incomplete)
    96  				} else {
    97  					buildAnagrams(ss, wordsList, d, append(sofar, b), append(words, word), incomplete)
    98  				}
    99  			}
   100  		}
   101  	}
   102  	if (incomplete || len(done) == len(wordsList)) && len(sofar) > 0 {
   103  		s := byteSliceToString(sofar)
   104  		if pos := sort.SearchStrings(ss, s); pos < len(ss) && ss[pos] == s {
   105  			currWords = nil
   106  			printWords(words, make([]int, 0, len(words)))
   107  			res = append(res, result{
   108  				Word:   string(sofar),
   109  				Makeup: currWords,
   110  			})
   111  		}
   112  	}
   113  }
   114  
   115  type result struct {
   116  	Word   string
   117  	Makeup [][]string
   118  }
   119  
   120  type results []result
   121  
   122  var res results
   123  
   124  func (r results) Len() int {
   125  	return len(r)
   126  }
   127  
   128  func (r results) Less(i, j int) bool {
   129  	return r[i].Word < r[j].Word
   130  }
   131  
   132  func (r results) Swap(i, j int) {
   133  	r[i], r[j] = r[j], r[i]
   134  }
   135  
   136  var currWords [][]string
   137  
   138  func printWords(w [][]string, pos []int) {
   139  	if len(pos) == len(w) {
   140  		words := make([]string, len(pos))
   141  		for n, p := range pos {
   142  			words[n] = w[n][p]
   143  		}
   144  		currWords = append(currWords, words)
   145  		return
   146  	}
   147  	for n := range w[len(pos)] {
   148  		printWords(w, append(pos, n))
   149  	}
   150  }
   151  
   152  func byteSliceToString(b []byte) string {
   153  	return *(*string)(unsafe.Pointer(&b))
   154  }
   155