imjasonh/.gitignore

## .gitignore
main.prof
main
*.txt

## README.md

      
    Raw
  

              README.md
            
          
    Spelling Bee

Generates NYT Spelling Bee puzzles and answers
Rules

Spelling Bee puzzles present solvers with seven letters in a circle, with one
letter in the middle. The game is to identify as many words as possible using
only these letters, which can be repeated, and where the letter in the center
must be used.
Each word is worth one point, and words using all seven letters are worth three
points.
Generally, underneath the puzzle there's a scale saying "XX points is good, YY
points is great, ZZ points is genius". The list of answers is printed in next
week's issue.
Example
For the purposes of generating puzzles, a puzzle is considered "valid" if it has
at least ten answers, to weed out puzzles with too few answers, and if there is
at least one answer that uses every letter, because finding the three-pointer is
best part.
Runtime

Without parallelism, generating seven-letter puzzles takes about five and a half
hours, and generates 51,912 unique puzzles.
Results

The list of all valid puzzles is here:
https://storage.googleapis.com/spelling-bee/ls-7.txt
The name of the puzzle is the letters in the puzzle, sorted A-Z, then rotated so
that the required letter is first.
A puzzle with letters R, T, D, A, S, I, and the required center
letter E is named by the letters in the puzzle, sorted (adeirst), then
rotated so it starts with e (eirstad).
So the answers to that puzzle are at:
https://storage.googleapis.com/spelling-bee/eirstad.txt
The last line of the file is the total number of points for that puzzle.
Findings

Longest answers

48 puzzles include an answer with 15 letters, all of which are three-point
answers.
unconsciousness
superstructures
nonintervention
interconnection
inconveniencing
inconsistencies
consciousnesses
nationalization

Most popular answers

The most popular answer is "deeded", which is found in 3,630 different puzzles.
Basically, any puzzle that has "e" and "d" in it, where either "e" or "d" is the
required letter.
3630 deeded
3569 sissies
3569 sises
3516 serer
3516 seers
 ...

Least popular answers

62 different words are only found once in all the puzzles.
Nearly all of these are three-point answers using all the letters in the puzzle.
Exceptions come from puzzles without enough answers to be valid, or answers like
chintz where the only longer answer is chintzy which is a three-point
answer.
backward
bigotry
blindfold
bloodhound
bobwhite
bullhorn
bumpkin
burdock
chintz
chintzy
crudity
dizzy
dogfight
drawback
equinox
exorcize
forklift
fortify
frigidity
fullback
girlhood
gluttony
gryphon
halfback
helpful
homepage
homophobia
hoodwink
horribly
hunchback
hurtful
imbroglio
invincibly
jackpot
jollity
jovial
jovially
judicial
kazoo
liturgy
luxury
menfolk
mindful
monthly
mortify
mythology
orthodoxy
pettifog
prodigy
public
publicly
quandary
quickly
rhombi
rhomboid
truthful
truthfully
unkempt
unmindful
wakeful
windfall
withhold

Puzzles with the most answers

The puzzle eirstad has the most answers, at 456. Interestingly, deeded is an
answer in the #1 and #3 puzzles in the list.
456 eirstad
445 eiprsta
440 eprstad
440 einrsta
439 elprsta
...

Puzzles worth the most total points:

The puzzle einrsta (#4 on the list of most answers) has the most total points
available, because it contains a lot 3-point answers.
The puzzle with the most answers, eirstad, has the second-most available
points.
504 einrsta
484 eirstad
484 staeinr
484 taeinrs
482 einrstd
...

Puzzles with the fewest answers

There are 563 puzzles with only ten answers, among them:
abcdkrw
abcfhkl
abdgotu
abehitu
abeiotv
...and 558 more

Puzzles worth the fewest total points:

517 puzzles only have 12 points.
12 points is the fewest possible points for a valid puzzle, since every puzzle
must have ten answers and at least one of them must be worth three points.
abcfhkl
abdgotu
abehitu
abeiotv
aceiloz
...and 512 more

Puzzles that have only 10 answers worth more than 12 points must include
multiple three-point answers.
Other puzzle variants

Nothing requires the puzzle to have 7 available letters. If we only provide 6
letters, we get fewer valid puzzles, but it takes less time to compute them.


# letters
time
# puzzles


3
20s
0


4
2m20s
189


5
10m29s
6139


6
40m39s
29105


7
180m41s
51912


Times are using -parallel=100 on a 12-core machine.

  
## LICENSE
Apache License
                           Version 2.0, January 2004
                        http://www.apache.org/licenses/

   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION

   1. Definitions.

      "License" shall mean the terms and conditions for use, reproduction,
      and distribution as defined by Sections 1 through 9 of this document.

      "Licensor" shall mean the copyright owner or entity authorized by
      the copyright owner that is granting the License.

      "Legal Entity" shall mean the union of the acting entity and all
      other entities that control, are controlled by, or are under common
      control with that entity. For the purposes of this definition,
      "control" means (i) the power, direct or indirect, to cause the
      direction or management of such entity, whether by contract or
      otherwise, or (ii) ownership of fifty percent (50%) or more of the
      outstanding shares, or (iii) beneficial ownership of such entity.

      "You" (or "Your") shall mean an individual or Legal Entity
      exercising permissions granted by this License.

      "Source" form shall mean the preferred form for making modifications,
      including but not limited to software source code, documentation
      source, and configuration files.

      "Object" form shall mean any form resulting from mechanical
      transformation or translation of a Source form, including but
      not limited to compiled object code, generated documentation,
      and conversions to other media types.

      "Work" shall mean the work of authorship, whether in Source or
      Object form, made available under the License, as indicated by a
      copyright notice that is included in or attached to the work
      (an example is provided in the Appendix below).

      "Derivative Works" shall mean any work, whether in Source or Object
      form, that is based on (or derived from) the Work and for which the
      editorial revisions, annotations, elaborations, or other modifications
      represent, as a whole, an original work of authorship. For the purposes
      of this License, Derivative Works shall not include works that remain
      separable from, or merely link (or bind by name) to the interfaces of,
      the Work and Derivative Works thereof.

      "Contribution" shall mean any work of authorship, including
      the original version of the Work and any modifications or additions
      to that Work or Derivative Works thereof, that is intentionally
      submitted to Licensor for inclusion in the Work by the copyright owner
      or by an individual or Legal Entity authorized to submit on behalf of
      the copyright owner. For the purposes of this definition, "submitted"
      means any form of electronic, verbal, or written communication sent
      to the Licensor or its representatives, including but not limited to
      communication on electronic mailing lists, source code control systems,
      and issue tracking systems that are managed by, or on behalf of, the
      Licensor for the purpose of discussing and improving the Work, but
      excluding communication that is conspicuously marked or otherwise
      designated in writing by the copyright owner as "Not a Contribution."

      "Contributor" shall mean Licensor and any individual or Legal Entity
      on behalf of whom a Contribution has been received by Licensor and
      subsequently incorporated within the Work.

   2. Grant of Copyright License. Subject to the terms and conditions of
      this License, each Contributor hereby grants to You a perpetual,
      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
      copyright license to reproduce, prepare Derivative Works of,
      publicly display, publicly perform, sublicense, and distribute the
      Work and such Derivative Works in Source or Object form.

   3. Grant of Patent License. Subject to the terms and conditions of
      this License, each Contributor hereby grants to You a perpetual,
      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
      (except as stated in this section) patent license to make, have made,
      use, offer to sell, sell, import, and otherwise transfer the Work,
      where such license applies only to those patent claims licensable
      by such Contributor that are necessarily infringed by their
      Contribution(s) alone or by combination of their Contribution(s)
      with the Work to which such Contribution(s) was submitted. If You
      institute patent litigation against any entity (including a
      cross-claim or counterclaim in a lawsuit) alleging that the Work
      or a Contribution incorporated within the Work constitutes direct
      or contributory patent infringement, then any patent licenses
      granted to You under this License for that Work shall terminate
      as of the date such litigation is filed.

   4. Redistribution. You may reproduce and distribute copies of the
      Work or Derivative Works thereof in any medium, with or without
      modifications, and in Source or Object form, provided that You
      meet the following conditions:

      (a) You must give any other recipients of the Work or
          Derivative Works a copy of this License; and

      (b) You must cause any modified files to carry prominent notices
          stating that You changed the files; and

      (c) You must retain, in the Source form of any Derivative Works
          that You distribute, all copyright, patent, trademark, and
          attribution notices from the Source form of the Work,
          excluding those notices that do not pertain to any part of
          the Derivative Works; and

      (d) If the Work includes a "NOTICE" text file as part of its
          distribution, then any Derivative Works that You distribute must
          include a readable copy of the attribution notices contained
          within such NOTICE file, excluding those notices that do not
          pertain to any part of the Derivative Works, in at least one
          of the following places: within a NOTICE text file distributed
          as part of the Derivative Works; within the Source form or
          documentation, if provided along with the Derivative Works; or,
          within a display generated by the Derivative Works, if and
          wherever such third-party notices normally appear. The contents
          of the NOTICE file are for informational purposes only and
          do not modify the License. You may add Your own attribution
          notices within Derivative Works that You distribute, alongside
          or as an addendum to the NOTICE text from the Work, provided
          that such additional attribution notices cannot be construed
          as modifying the License.

      You may add Your own copyright statement to Your modifications and
      may provide additional or different license terms and conditions
      for use, reproduction, or distribution of Your modifications, or
      for any such Derivative Works as a whole, provided Your use,
      reproduction, and distribution of the Work otherwise complies with
      the conditions stated in this License.

   5. Submission of Contributions. Unless You explicitly state otherwise,
      any Contribution intentionally submitted for inclusion in the Work
      by You to the Licensor shall be under the terms and conditions of
      this License, without any additional terms or conditions.
      Notwithstanding the above, nothing herein shall supersede or modify
      the terms of any separate license agreement you may have executed
      with Licensor regarding such Contributions.

   6. Trademarks. This License does not grant permission to use the trade
      names, trademarks, service marks, or product names of the Licensor,
      except as required for reasonable and customary use in describing the
      origin of the Work and reproducing the content of the NOTICE file.

   7. Disclaimer of Warranty. Unless required by applicable law or
      agreed to in writing, Licensor provides the Work (and each
      Contributor provides its Contributions) on an "AS IS" BASIS,
      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
      implied, including, without limitation, any warranties or conditions
      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
      PARTICULAR PURPOSE. You are solely responsible for determining the
      appropriateness of using or redistributing the Work and assume any
      risks associated with Your exercise of permissions under this License.

   8. Limitation of Liability. In no event and under no legal theory,
      whether in tort (including negligence), contract, or otherwise,
      unless required by applicable law (such as deliberate and grossly
      negligent acts) or agreed to in writing, shall any Contributor be
      liable to You for damages, including any direct, indirect, special,
      incidental, or consequential damages of any character arising as a
      result of this License or out of the use or inability to use the
      Work (including but not limited to damages for loss of goodwill,
      work stoppage, computer failure or malfunction, or any and all
      other commercial damages or losses), even if such Contributor
      has been advised of the possibility of such damages.

   9. Accepting Warranty or Additional Liability. While redistributing
      the Work or Derivative Works thereof, You may choose to offer,
      and charge a fee for, acceptance of support, warranty, indemnity,
      or other liability obligations and/or rights consistent with this
      License. However, in accepting such obligations, You may act only
      on Your own behalf and on Your sole responsibility, not on behalf
      of any other Contributor, and only if You agree to indemnify,
      defend, and hold each Contributor harmless for any liability
      incurred by, or claims asserted against, such Contributor by reason
      of your accepting any such warranty or additional liability.

   END OF TERMS AND CONDITIONS

   APPENDIX: How to apply the Apache License to your work.

      To apply the Apache License to your work, attach the following
      boilerplate notice, with the fields enclosed by brackets "{}"
      replaced with your own identifying information. (Don't include
      the brackets!)  The text should be enclosed in the appropriate
      comment syntax for the file format. We also recommend that a
      file or class name and description of purpose be included on the
      same "printed page" as the copyright notice for easier
      identification within third-party archives.

   Copyright {yyyy} {name of copyright owner}

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.


## main.go
package main

import (
	"bufio"
	"flag"
	"fmt"
	"io"
	"log"
	"os"
	"runtime/pprof"
	"strings"
	"sync"
	"time"
)

const alphabet = "abcdefghijklmnopqrstuvwxyz"

var (
	wordsFile  = flag.String("words_file", "/usr/share/dict/words", "File containing valid words")
	numLetters = flag.Int("num_letters", 3, "Number of letters in resulting puzzles")
	parallel   = flag.Int("parallel", 3, "Number of goroutines to use to generate puzzles")
	v          = flag.Bool("v", false, "verbose logging")

	cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
)

func main() {
	flag.Parse()

	if *cpuprofile != "" {
		f, err := os.Create(*cpuprofile)
		if err != nil {
			log.Fatal(err)
		}
		pprof.StartCPUProfile(f)
		defer pprof.StopCPUProfile()
	}

	strings := make(chan string)
	go genAllStrings(*numLetters, strings)

	rotated := make(chan string)
	go rotate(strings, rotated)

	puzzles := make(chan puzzle)

	// Consume puzzles and write files.
	var wg2 sync.WaitGroup
	wg2.Add(1)
	go func() {
		defer wg2.Done()
		writePuzzles(puzzles)
	}()

	allWords := genAllWords()

	// Consume rotated words and generate puzzles.
	var wg sync.WaitGroup
	for i := 0; i < *parallel; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			matchWords(allWords, rotated, puzzles)
		}()
	}
	wg.Wait()
	// When puzzle generators are done, close puzzles. This will cause
	// writePuzzles to finish, and the program to exit.
	close(puzzles)

	wg2.Wait()
}

func genAllWords() []string {
	f, err := os.Open(*wordsFile)
	if err != nil {
		log.Fatalf("Open(%q): %v", *wordsFile, err)
	}
	r := bufio.NewReader(f)
	allWords := []string{}
	for {
		l, err := r.ReadBytes('\n')
		if err == io.EOF {
			break
		}
		if err != nil {
			log.Fatalf("ReadBytes: %v", err)
		}
		w := string(l)
		w = strings.TrimSpace(w)
		// Words must be >5 letters.
		if len(w) < 5 {
			continue
		}
		// Words must be lowercase, no punctuation.
		if !containsOnly(w, alphabet) {
			continue
		}
		// Words must contain <=N unique letters.
		if !hasAtMostLetters(w, *numLetters) {
			continue
		}

		allWords = append(allWords, w)
	}
	f.Close()
	fmt.Println("Matching", len(allWords), "words")
	return allWords
}

func hasAtMostLetters(s string, n int) bool {
	cs := map[rune]struct{}{}
	for _, c := range s {
		cs[c] = struct{}{}
		if len(cs) > n {
			return false
		}
	}
	return true
}

// genAllStrings generates all unique strings of length n and sends them to
// out.
func genAllStrings(n int, out chan<- string) {
	for _, c := range alphabet {
		if n == 1 {
			out <- string(c)
			continue
		}

		ch := make(chan string, 1000)
		go genAllStrings(n-1, ch)
		for rest := range ch {
			if rest[0] > byte(c) {
				out <- string(c) + rest
			}
		}
	}
	close(out)
}

// rotate emits rotated versions of the string.
//
// If s is "abcdefg", out will be sent:
// - abcdefg
// - bcdefga
// - cdefgab
// - defgabc
// - efgabcd
// - fgabcde
// - gabcdef
func rotate(in <-chan string, out chan<- string) {
	for s := range in {
		for i := 0; i < len(s); i++ {
			first, rest := s[:i], s[i:]
			out <- rest + first
		}
	}
	close(out)
}

type puzzle struct {
	letters string
	words   []string
	maxPts  int
}

func containsOnly(s, target string) bool {
	rs := map[rune]struct{}{}
	for _, r := range target {
		rs[r] = struct{}{}
	}
	for _, r := range s {
		if _, found := rs[r]; !found {
			return false
		}
	}
	return true
}

// matchWords emits all words that match in (with spelling bee semantics).
func matchWords(allWords []string, in <-chan string, out chan<- puzzle) {

	for s := range in {
		runes := map[rune]struct{}{}
		for _, c := range s {
			runes[c] = struct{}{}
		}

		words := []string{}
		for _, word := range allWords {
			// Words must contain the first character.
			if !strings.Contains(word, string(s[0])) {
				continue
			}

			// Words must contain only letters in this set.
			if containsOnly(word, s) {
				words = append(words, word)
			}
		}

		// This combination of letters doesn't produce enough answers.
		if len(words) < 10 {
			if *v {
				fmt.Print("1")
			}
			continue
		}

		// Score the puzzle and ensure at least one answer uses all letters.
		someContainsAll := false
		maxPts := 0
		for _, w := range words {
			containsAll := true
			for _, let := range s {
				if !strings.ContainsRune(w, let) {
					containsAll = false
				}
			}
			if containsAll {
				maxPts += 3
				someContainsAll = true
			} else {
				maxPts += 1
			}
		}
		if !someContainsAll {
			if *v {
				fmt.Print("2")
			}
			continue
		}

		out <- puzzle{
			letters: s,
			words:   words,
			maxPts:  maxPts,
		}
	}
}

func writePuzzles(in <-chan puzzle) {
	t := time.Tick(time.Second)
	for {
		select {
		case p, ok := <-in:
			if !ok {
				return
			}
			fn := p.letters + ".txt"
			f, err := os.Create(fn)
			if err != nil {
				log.Fatalf("Create(%q): %v", fn, err)
			}
			for _, w := range p.words {
				fmt.Fprintln(f, w)
			}
			fmt.Fprintln(f, p.maxPts)
			if *v {
				fmt.Println("wrote", p.letters)
			}
			f.Close()
		case <-t:
			if *v {
				fmt.Print("%")
			}
		}
	}
}
	Apache License
	Version 2.0, January 2004
	http://www.apache.org/licenses/

	TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION

	1. Definitions.

	"License" shall mean the terms and conditions for use, reproduction,
	and distribution as defined by Sections 1 through 9 of this document.

	"Licensor" shall mean the copyright owner or entity authorized by
	the copyright owner that is granting the License.

	"Legal Entity" shall mean the union of the acting entity and all
	other entities that control, are controlled by, or are under common
	control with that entity. For the purposes of this definition,
	"control" means (i) the power, direct or indirect, to cause the
	direction or management of such entity, whether by contract or
	otherwise, or (ii) ownership of fifty percent (50%) or more of the
	outstanding shares, or (iii) beneficial ownership of such entity.

	"You" (or "Your") shall mean an individual or Legal Entity
	exercising permissions granted by this License.

	"Source" form shall mean the preferred form for making modifications,
	including but not limited to software source code, documentation
	source, and configuration files.

	"Object" form shall mean any form resulting from mechanical
	transformation or translation of a Source form, including but
	not limited to compiled object code, generated documentation,
	and conversions to other media types.

	"Work" shall mean the work of authorship, whether in Source or
	Object form, made available under the License, as indicated by a
	copyright notice that is included in or attached to the work
	(an example is provided in the Appendix below).

	"Derivative Works" shall mean any work, whether in Source or Object
	form, that is based on (or derived from) the Work and for which the
	editorial revisions, annotations, elaborations, or other modifications
	represent, as a whole, an original work of authorship. For the purposes
	of this License, Derivative Works shall not include works that remain
	separable from, or merely link (or bind by name) to the interfaces of,
	the Work and Derivative Works thereof.

	"Contribution" shall mean any work of authorship, including
	the original version of the Work and any modifications or additions
	to that Work or Derivative Works thereof, that is intentionally
	submitted to Licensor for inclusion in the Work by the copyright owner
	or by an individual or Legal Entity authorized to submit on behalf of
	the copyright owner. For the purposes of this definition, "submitted"
	means any form of electronic, verbal, or written communication sent
	to the Licensor or its representatives, including but not limited to
	communication on electronic mailing lists, source code control systems,
	and issue tracking systems that are managed by, or on behalf of, the
	Licensor for the purpose of discussing and improving the Work, but
	excluding communication that is conspicuously marked or otherwise
	designated in writing by the copyright owner as "Not a Contribution."

	"Contributor" shall mean Licensor and any individual or Legal Entity
	on behalf of whom a Contribution has been received by Licensor and
	subsequently incorporated within the Work.

	2. Grant of Copyright License. Subject to the terms and conditions of
	this License, each Contributor hereby grants to You a perpetual,
	worldwide, non-exclusive, no-charge, royalty-free, irrevocable
	copyright license to reproduce, prepare Derivative Works of,
	publicly display, publicly perform, sublicense, and distribute the
	Work and such Derivative Works in Source or Object form.

	3. Grant of Patent License. Subject to the terms and conditions of
	this License, each Contributor hereby grants to You a perpetual,
	worldwide, non-exclusive, no-charge, royalty-free, irrevocable
	(except as stated in this section) patent license to make, have made,
	use, offer to sell, sell, import, and otherwise transfer the Work,
	where such license applies only to those patent claims licensable
	by such Contributor that are necessarily infringed by their
	Contribution(s) alone or by combination of their Contribution(s)
	with the Work to which such Contribution(s) was submitted. If You
	institute patent litigation against any entity (including a
	cross-claim or counterclaim in a lawsuit) alleging that the Work
	or a Contribution incorporated within the Work constitutes direct
	or contributory patent infringement, then any patent licenses
	granted to You under this License for that Work shall terminate
	as of the date such litigation is filed.

	4. Redistribution. You may reproduce and distribute copies of the
	Work or Derivative Works thereof in any medium, with or without
	modifications, and in Source or Object form, provided that You
	meet the following conditions:

	(a) You must give any other recipients of the Work or
	Derivative Works a copy of this License; and

	(b) You must cause any modified files to carry prominent notices
	stating that You changed the files; and

	(c) You must retain, in the Source form of any Derivative Works
	that You distribute, all copyright, patent, trademark, and
	attribution notices from the Source form of the Work,
	excluding those notices that do not pertain to any part of
	the Derivative Works; and

	(d) If the Work includes a "NOTICE" text file as part of its
	distribution, then any Derivative Works that You distribute must
	include a readable copy of the attribution notices contained
	within such NOTICE file, excluding those notices that do not
	pertain to any part of the Derivative Works, in at least one
	of the following places: within a NOTICE text file distributed
	as part of the Derivative Works; within the Source form or
	documentation, if provided along with the Derivative Works; or,
	within a display generated by the Derivative Works, if and
	wherever such third-party notices normally appear. The contents
	of the NOTICE file are for informational purposes only and
	do not modify the License. You may add Your own attribution
	notices within Derivative Works that You distribute, alongside
	or as an addendum to the NOTICE text from the Work, provided
	that such additional attribution notices cannot be construed
	as modifying the License.

	You may add Your own copyright statement to Your modifications and
	may provide additional or different license terms and conditions
	for use, reproduction, or distribution of Your modifications, or
	for any such Derivative Works as a whole, provided Your use,
	reproduction, and distribution of the Work otherwise complies with
	the conditions stated in this License.

	5. Submission of Contributions. Unless You explicitly state otherwise,
	any Contribution intentionally submitted for inclusion in the Work
	by You to the Licensor shall be under the terms and conditions of
	this License, without any additional terms or conditions.
	Notwithstanding the above, nothing herein shall supersede or modify
	the terms of any separate license agreement you may have executed
	with Licensor regarding such Contributions.

	6. Trademarks. This License does not grant permission to use the trade
	names, trademarks, service marks, or product names of the Licensor,
	except as required for reasonable and customary use in describing the
	origin of the Work and reproducing the content of the NOTICE file.

	7. Disclaimer of Warranty. Unless required by applicable law or
	agreed to in writing, Licensor provides the Work (and each
	Contributor provides its Contributions) on an "AS IS" BASIS,
	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
	implied, including, without limitation, any warranties or conditions
	of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
	PARTICULAR PURPOSE. You are solely responsible for determining the
	appropriateness of using or redistributing the Work and assume any
	risks associated with Your exercise of permissions under this License.

	8. Limitation of Liability. In no event and under no legal theory,
	whether in tort (including negligence), contract, or otherwise,
	unless required by applicable law (such as deliberate and grossly
	negligent acts) or agreed to in writing, shall any Contributor be
	liable to You for damages, including any direct, indirect, special,
	incidental, or consequential damages of any character arising as a
	result of this License or out of the use or inability to use the
	Work (including but not limited to damages for loss of goodwill,
	work stoppage, computer failure or malfunction, or any and all
	other commercial damages or losses), even if such Contributor
	has been advised of the possibility of such damages.

	9. Accepting Warranty or Additional Liability. While redistributing
	the Work or Derivative Works thereof, You may choose to offer,
	and charge a fee for, acceptance of support, warranty, indemnity,
	or other liability obligations and/or rights consistent with this
	License. However, in accepting such obligations, You may act only
	on Your own behalf and on Your sole responsibility, not on behalf
	of any other Contributor, and only if You agree to indemnify,
	defend, and hold each Contributor harmless for any liability
	incurred by, or claims asserted against, such Contributor by reason
	of your accepting any such warranty or additional liability.

	END OF TERMS AND CONDITIONS

	APPENDIX: How to apply the Apache License to your work.

	To apply the Apache License to your work, attach the following
	boilerplate notice, with the fields enclosed by brackets "{}"
	replaced with your own identifying information. (Don't include
	the brackets!) The text should be enclosed in the appropriate
	comment syntax for the file format. We also recommend that a
	file or class name and description of purpose be included on the
	same "printed page" as the copyright notice for easier
	identification within third-party archives.

	Copyright {yyyy} {name of copyright owner}

	Licensed under the Apache License, Version 2.0 (the "License");
	you may not use this file except in compliance with the License.
	You may obtain a copy of the License at

	http://www.apache.org/licenses/LICENSE-2.0

	Unless required by applicable law or agreed to in writing, software
	distributed under the License is distributed on an "AS IS" BASIS,
	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	See the License for the specific language governing permissions and
	limitations under the License.
	package main

	import (
	"bufio"
	"flag"
	"fmt"
	"io"
	"log"
	"os"
	"runtime/pprof"
	"strings"
	"sync"
	"time"
	)

	const alphabet = "abcdefghijklmnopqrstuvwxyz"

	var (
	wordsFile = flag.String("words_file", "/usr/share/dict/words", "File containing valid words")
	numLetters = flag.Int("num_letters", 3, "Number of letters in resulting puzzles")
	parallel = flag.Int("parallel", 3, "Number of goroutines to use to generate puzzles")
	v = flag.Bool("v", false, "verbose logging")

	cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
	)

	func main() {
	flag.Parse()

	if *cpuprofile != "" {
	f, err := os.Create(*cpuprofile)
	if err != nil {
	log.Fatal(err)
	}
	pprof.StartCPUProfile(f)
	defer pprof.StopCPUProfile()
	}

	strings := make(chan string)
	go genAllStrings(*numLetters, strings)

	rotated := make(chan string)
	go rotate(strings, rotated)

	puzzles := make(chan puzzle)

	// Consume puzzles and write files.
	var wg2 sync.WaitGroup
	wg2.Add(1)
	go func() {
	defer wg2.Done()
	writePuzzles(puzzles)
	}()

	allWords := genAllWords()

	// Consume rotated words and generate puzzles.
	var wg sync.WaitGroup
	for i := 0; i < *parallel; i++ {
	wg.Add(1)
	go func() {
	defer wg.Done()
	matchWords(allWords, rotated, puzzles)
	}()
	}
	wg.Wait()
	// When puzzle generators are done, close puzzles. This will cause
	// writePuzzles to finish, and the program to exit.
	close(puzzles)

	wg2.Wait()
	}

	func genAllWords() []string {
	f, err := os.Open(*wordsFile)
	if err != nil {
	log.Fatalf("Open(%q): %v", *wordsFile, err)
	}
	r := bufio.NewReader(f)
	allWords := []string{}
	for {
	l, err := r.ReadBytes('\n')
	if err == io.EOF {
	break
	}
	if err != nil {
	log.Fatalf("ReadBytes: %v", err)
	}
	w := string(l)
	w = strings.TrimSpace(w)
	// Words must be >5 letters.
	if len(w) < 5 {
	continue
	}
	// Words must be lowercase, no punctuation.
	if !containsOnly(w, alphabet) {
	continue
	}
	// Words must contain <=N unique letters.
	if !hasAtMostLetters(w, *numLetters) {
	continue
	}

	allWords = append(allWords, w)
	}
	f.Close()
	fmt.Println("Matching", len(allWords), "words")
	return allWords
	}

	func hasAtMostLetters(s string, n int) bool {
	cs := map[rune]struct{}{}
	for _, c := range s {
	cs[c] = struct{}{}
	if len(cs) > n {
	return false
	}
	}
	return true
	}

	// genAllStrings generates all unique strings of length n and sends them to
	// out.
	func genAllStrings(n int, out chan<- string) {
	for _, c := range alphabet {
	if n == 1 {
	out <- string(c)
	continue
	}

	ch := make(chan string, 1000)
	go genAllStrings(n-1, ch)
	for rest := range ch {
	if rest[0] > byte(c) {
	out <- string(c) + rest
	}
	}
	}
	close(out)
	}

	// rotate emits rotated versions of the string.
	//
	// If s is "abcdefg", out will be sent:
	// - abcdefg
	// - bcdefga
	// - cdefgab
	// - defgabc
	// - efgabcd
	// - fgabcde
	// - gabcdef
	func rotate(in <-chan string, out chan<- string) {
	for s := range in {
	for i := 0; i < len(s); i++ {
	first, rest := s[:i], s[i:]
	out <- rest + first
	}
	}
	close(out)
	}

	type puzzle struct {
	letters string
	words []string
	maxPts int
	}

	func containsOnly(s, target string) bool {
	rs := map[rune]struct{}{}
	for _, r := range target {
	rs[r] = struct{}{}
	}
	for _, r := range s {
	if _, found := rs[r]; !found {
	return false
	}
	}
	return true
	}

	// matchWords emits all words that match in (with spelling bee semantics).
	func matchWords(allWords []string, in <-chan string, out chan<- puzzle) {

	for s := range in {
	runes := map[rune]struct{}{}
	for _, c := range s {
	runes[c] = struct{}{}
	}

	words := []string{}
	for _, word := range allWords {
	// Words must contain the first character.
	if !strings.Contains(word, string(s[0])) {
	continue
	}

	// Words must contain only letters in this set.
	if containsOnly(word, s) {
	words = append(words, word)
	}
	}

	// This combination of letters doesn't produce enough answers.
	if len(words) < 10 {
	if *v {
	fmt.Print("1")
	}
	continue
	}

	// Score the puzzle and ensure at least one answer uses all letters.
	someContainsAll := false
	maxPts := 0
	for _, w := range words {
	containsAll := true
	for _, let := range s {
	if !strings.ContainsRune(w, let) {
	containsAll = false
	}
	}
	if containsAll {
	maxPts += 3
	someContainsAll = true
	} else {
	maxPts += 1
	}
	}
	if !someContainsAll {
	if *v {
	fmt.Print("2")
	}
	continue
	}

	out <- puzzle{
	letters: s,
	words: words,
	maxPts: maxPts,
	}
	}
	}

	func writePuzzles(in <-chan puzzle) {
	t := time.Tick(time.Second)
	for {
	select {
	case p, ok := <-in:
	if !ok {
	return
	}
	fn := p.letters + ".txt"
	f, err := os.Create(fn)
	if err != nil {
	log.Fatalf("Create(%q): %v", fn, err)
	}
	for _, w := range p.words {
	fmt.Fprintln(f, w)
	}
	fmt.Fprintln(f, p.maxPts)
	if *v {
	fmt.Println("wrote", p.letters)
	}
	f.Close()
	case <-t:
	if *v {
	fmt.Print("%")
	}
	}
	}
	}