mini gen

This is a project that generates mini cross word puzzles.

style guide

Keep things simple. Do them the easy way first. Write tests in each file. Run tests after each change. Prefer to do things yourself or use the standard library. Once there are no errors, also fix all warnings.

All modules are defined in src/lib.rs. src/main.rs uses the modules defined in src/lib.rs. All assets are kept in the assets directory.

There should be no tests in main.rs or lib.rs -- move them closer to the code, or define an integration test in tests/integration.rs.

All errors are named after the form ErrorModule or ErrorFunction.

If you notice a minor violation of this style guide, just fix it as you work. If you need to refactor something larger, however, make note of it and let us know so we can do it together.

puzzle format

Each day has a fixed puzzle format. All puzzles are 5x5. The format looks like this:

. _ _ _ _
. _ _ _ _
_ _ _ _ _
_ _ _ _ .
_ _ _ _ .

Where . is a black square, _ is a blank square.

These puzzles are stored in the assets directory, in 0-monday.txt .. 6-sunday.txt

The puzzle parser is located in src/parse.rs. It contains a function that takes a file path, and creates a Board object, or returns a Result with a ErrorParse enum variant.

A Board object is an array of 25 Tiles. Tile is an repr(u8) enum that can be all the letters in the alphabet, Black, or Blank. These objects are defined in src/board.rs.

command line interface

We expose a simple command-line interface. It is implemented in src/cli.rs, and used in src/main.rs. The API is minimal and simple:

minicross path/to/file.txt

If there is something wrong with the passed CLI arguments, an ErrorCli is returned.

Running the CLI will parse the puzzle, then generate a puzzle matching the board configfuration, and print the result.

solver

Given a Dict of words, and board configuration with blanks, the solver generates a puzzle matching this board with no blank tiles remaining. (All black tiles are the same.) It is defined in src/solver.rs, as a function that takes a Board and produces a new Board. If the board can't be solved, an ErrorSolve will be returned.

There is an integration test in tests/integration.rs that takes the parsed board, and the solved board, and ensures that (1) there are no non-blank tiles in the solved board and (2) all the black tiles are in the same place.

loading words

There is a list of good 3-to-5 letter crossword words in assets/words.txt. Each word is on its own line.

We can load these words into a Dict. In src/dict.rs, There is a function that takes a path, and produces a Dict. A Dict is just a set of strings. If there is an issue with words.txt, a ErrorDict is returned.

matching words

To solve a partial puzzle, we need a way to match words in the dictionary. We call this the matching function, and it is defined in src/matcher.rs.

The matcher takes a Dict and a partial Word, defined as a Vec of Tiles. It returns all matching words. The matcher is defined in src/matcher.rs. The matcher does not accept black tiles, or partial words not of length 3 to 5 inclusive. If these invariants are violated, an ErrorMatch is returned.

To illustrate, when given C O L _, the matcher will produce a list beginning [cola, cold, ...]. (There may be multiple blanks) If no words match, an empty list is returned.

Note that Word is defined in src/board.rs.

adding words to the dictionary

There is a script in scripts/add_word.py, which you can use to add words to assets/words.txt. Just run it, and type words, one per line, when prompted. When done, just leave an empty line. The script will normalize all words to lowercase, remove any words that have punctuation, add the words to words.txt, and sort the result.

how solving works

The solver is a backtracking solver. Here is how it works, at a high level:

• First, we pick a random unsolved row/column from a partially solved Board. We ignore black tiles, and extract a partial Word.

• We use the Dict to get all matches for that word. If there are no matches, we give up and backtrack.

• If there are matches, we generate a new board for each match. We then check that the board is solvable (meaning all rows and columns still have a solution). If the board is no longer solvable, we backtrack.

• The solver guarantees that all words in the puzzle are unique. If a word has already appeared in the puzzle, the solver will backtrack.

• We do this recursively, using an implicit stack of boards.

• Once there are no blanks (solved) or we have exhausted all boards (unsolvable) we return to the caller. If the board is unsolvable, this is a ErrorSolve.

validating solving

There is an integration test in src/integration.rs that generates many random boards using all daily formats, and solves them. In then checks that all words are valid words in the dictionary. If the solver produces nonsensical words, this test fails.

extracting a word list

Once we have a solved board, we can call a function defined in src/list.rs to get the list of words. This function will error if there are blanks, or duplicate words. It will list all the across words in order, then all of the down words in order.