README WordSquare Solver and Generator
Copyright 2024, Robert Ryan McCune <robertryanmccune@gmail.com>

TABLE OF CONTENTS
1. ABOUT WORDSQUARE
2. CONTENTS
3. COMPILATION
4. RUNNING THE PROGRAM
5. USAGE
6. FILES AND FORMATS
7. IMPLEMENTATION DETAILS
8. PRELIMINARY EXPERIMENTS
9. CONCLUSION


1.	ABOUT WORDSQUARE 

A wordsquare is a square grid of letters where
words are formed both across and down.  The dimensions of a 
typical wordsquare, e.g. wordsquares that appear 
in news publications, are 
5 letters by 5 letters.  An example is below:

	utah-
	meme-
	petal
	-todo
	-hoys
	
There are 5 words to be read across, like petal and utah,
but there are also 5 words down, like ump and teeth.
Some words may not be familiar, but are included in open source
word lists.  Words in this program must be at least 3 letters,
with spaces/empty characters represented by hyphens '-'.

This program takes as input seed words, then generates
the remaining words to create a wordsquare.  Empirically,
at least 3 words are required to compute a wordsquare,
any fewer will take too long.  Multiple valid 
wordsquares can be found.  This implementation 
uses preprocessing to significantly improve runtime.


2.  CONTENTS	
	
	README - this software manual document file
	LICENSE - the BSD license for this software
	Makefile - commands for compilation
	main.cpp - the main program
	input/ - directory for input files to wordsquare program
		location to put output from preprocessing
		includes sample input files
	lib/ - directory for the common header file
	objects/ - directory for the 5 objects used
		in the main program
	preprocessing/ - directory for the preprocessing file
	wordlist/ - directory for a wordlist
		sample wordlist and license is included
	

3.	COMPILATION

To compile, from the home directory, 
enter from the command line:

	make all
	
Which will compile both the main program
and the preprocessing program.
The default output directory is the home directory

To compile only the main program, enter:

	make wordsquares
	
To compile only the preprocessing program, enter:

	make preproc
	
To remove all binaries, enter:

	make clean	
	
The program was compiled with Apple clang version 14.0.3
and GNU Make 3.81
	

4.  RUNNING THE PROGRAM

	4.1	PREPROCESSING
	
The main program for generating wordsquares 
requires 3 different input files.  These 3 different input files
are all generated from a wordlist.  The preprocessing 
program takes as input a wordlist and outputs the 3 files.  
See Section 6 for details on file formats, including the
reasoning behind the file names

To execute the preprocessing program, run:
	
	./preproc [wl_in] [di_out] [re_out] [ma_out]
	
Where:
	- wl_in = wordlist input file
	- di_out = dictionary output file
	- re_out = regular expressions output file
	- ma_out = matches output file

A sample open-source wordlist is included in package,
and the sample output files generated from the sample wordlist
are provided in the input directory.  The output of the
preprocessing program is placed in the input folder
because the files are input for the main wordsquare program.

To re-generate the sample files provided in the input directory,
after compiling, execute:

	./preproc wordlist/wordlist-20210729.txt  input/dict.sample  input/regs.sample  input/matches.sample	
	
The reason for the  3 input files is explained in
Section 7 Implementation Details
	
	4.2 MAIN PROGRAM
	
The main program requires 4 input files to execute: 
the 3 input files generated by preprocessing, as well
as the seeds file that includes the seed words to the wordsquare.
A sample seed file is included in the input folder.  
See Section 5 for details on seed word usage.

To run the program, include the 4 input files 
as well as an output file location to write
the resultant wordsquares

	./wordsquares [di_in] [re_in] [ma_in] [seeds_in] [squares_out]
	
Where:
	- di_in, re_in, and ma_in = di_out, re_out, and ma_out from the preprocessing program
	- seeds_in = a list of seed words
	- squares_out = the output file where complete wordsquares are written
	
To run the main wordsquare program with the provided sample files, run:

	./wordsquares  input/dict.sample  input/regs.sample  input/matches.sample  input/seeds.txt  wordsquares.txt

	
5.	USAGE

Running the wordsquare program requires the 4 input files,
3 files from preprocessing as well as the seeds file.
The seeds file is a list of words to include in wordsquare.
The minimum number of seed words allowed is 3 (any less would take 
days to compute).  The maximum is 10, in which case the program
would see if a wordsquare can be formed exclusively with
the input words.  Less than 3 seed words or more than 10
seed words will cause the program to exit.

A word in the seed file must be 5 characters.  To include
a word with less than 5 alphabet characters, add a hyphen
where the space should be. For example, "the" could be 
represented as: the--, -the-, or --the, it's up to the user.
Any word with less than or more than 5 characters will
cause the program to exit.

While the user must explicitly enter where the space/hyphen
goes for a seed word, the program will test all possible
configurations while solving, i.e. the program will 
try "the--", "-the-", and "--the" from dictionary words.

	
6.	FILES AND FORMATS

	6.1	Wordlist
	
The wordlist is simply a newline separated list of words.  
The words may or may not be words that can be found in 
a Webster's Dictionary, a word in the wordlist may
be seen as just a collection of letters.

In the example wordlist, all words are enclosed in quotes.
This is okay because words get sanitized before added
to the wordlist used by the program.  Words may contain
punctuation, numbers, upper and lower case letters, ect.
because they all get taken out (sans hyphens) when converted to a 
Dict wordlist.
	
	6.2	Dict
	
A Dict in this program is synonymous with a wordlist.  
On Linux systems a file is included called dict that's a wordlist.  
Here, a Dict is like a sanitized wordlist, where
words from the original wordlist have punctuation 
and numbers removed, all characters converted
to lower case, and only words with between 
3 and 5 letters are kept.

The first line of a Dict is the number of words
in the Dict.  After the header, each 
sanitized word in the Dict is newline-delimited.
	
	6.3	Regs
	
Regs is short for regular expressions.  This object contains
all possible regular expressions that could match an 
entry in the Dict wordlist.  An asterisk stands for a wildcard
character.  For example, if a word in Dict was "state", then
there would be entries in Regs that include "s****", "*t***",
"st*te", etc., for all possible combinations for all words in Dict.
For each 5-letter word, there are  31 possible Regular expressions 
to represent it using this asterisk notation.

There would be some overlap, for example "state" and "taste" 
could both be represented by "***te", but 
the regex is only entered once.

The regs object stores both an array of regexes,
as well as a map of regexes to their index in the array.
This object is used in junction with Matches and Dict to 
perform faster searches through the wordlist.  
For these Implementation Details, see Section 7.
	
	6.4	Matches

	
Matches is a large binary matrix stored in 
Compressed Sparse Column (CSC) format.  Before converting
the matrix to CSC, the number of rows in the matrix
is equal to the number of entries in the Dict wordlist, 
and the number of columns is equal to the number of entries in
Regs.  The corresponding cell is '1' if the word can be
represented, or "matched", by the regular expression.  e.g.
	
...     | s**te | ta*** | ***te |...
...     |       |       |       |...
state   |     1 |     0 |     1 |...
taste   |     0 |     1 |     1 |...
...

In the above table, "state" can be represented by "s**te"", 
so it's entry is 1.  "taste" can be represented by "ta***",
so it's cell entry is 1.  Both "state" and "taste" can be 
represented by "***te", so both entries are 1.

The number of cells in the Matrix is equal to the size of the
Dict wordlist by the number of regular expressions in the 
Regs list.  In the sample files, there are 27068 words and
147,656 possible RegExes. That means there are 3,996,752,608
cells in the matrix.  However, since each word can be 
represented by 31 entries, the total number of '1's in the 
matrix is only 839,108.  That is quite sparse.  

Instead of maintaining a true sparse matrix, the matrix is stored
in the Compressed Sparse Column (CSC) format (see below).
In addition to saving space, this will help with 
efficiently finding words for the wordsquare.  This will
be further explained in Implementation Details in Section 7.

A matrix stored in the CSC format is represented by 2 arrays.
To store these arrays in the matches file, the first line of
the file is the size of array 1, followed by each entry in the array, 
all newline delimited.  Then the size of the second array
is listed in the matches file, followed by each entry 
in the second array, again newline delimited. 

For details on Compressed Sparse Row (CSR) and
Compressed Sparse Column (CSC) format, see:

Buluç, Aydın, John Gilbert, and Viral B. Shah. 
"Implementing sparse matrices for graph algorithms." 
Graph Algorithms in the Language of Linear Algebra (2011): 287-313.
	
	6.5	Seeds
	
The seed file provides words that must be included 
in the wordsquare.  At least 3 words must be provided,
any less would cause the program to take too long.
The maximum allowed number of words is 10.

Words in the seeds file are new line delimited.
No header is required, just list each word on
it's own line.

Words must be exactly 5 characters long.
Words can be as few as 3 letters long,
but hyphens, '-', must be included to 
indicate empty spaces.  For example, if you
wanted to include the word 'cat' as a seed word,
then it must be listed in the seed word file as 
either 'cat--', '-cat-', or 'cat--'.
	
	6.6	Output
	
The output file lists all wordsquares found 
from the given seedwords and wordlist.  The first line
lists how many wordsquares were found, followed
by the words found in each square.  Each square 
is listed along with its index.  All 10 words in the
square are listed, even though only the first 5 words
are needed to complete the square.
	
7.	IMPLEMENTATION DETAILS

The program uses the Dict, Regs, and Matches objects
to perform faster word searches.

Consider a simple approach to computing a wordsquare.
Say the current state of the wordsquare is:
	
	***ts
	stare
	***en
	***ad
	torts

And the program wants to find a word that fits 
the third column.  We can see the regex pattern for the 
third column is "*a**r".  A simple approach 
would be to iterate through the entire wordlist
(in the Dict object) and check every word 
to see if it matches the regex.  But with a
wordlist of 27,000 words, this may be
excessive.

Instead, we make use of the Dict, Regs, and
Matches objects to find words that fit the
given pattern more quickly.

Reconsider the situation where we are trying to
find words that fit the pattern of the 
third column.  The regex pattern is "*a**r."
Using the map in Regs, we can find the index of
the regex in the regex array.  

With this index, we can find the
column of the regex in the Matches matrix.
We then traverse down the column, and every time
there is a '1' we add the index of that row to an array.
Since the matrix is stored in Compressed Sparse Column 
(CSC) format, all the 0's are eliminated, and we can 
easily and efficiently find all the rows indices
that match the regex.

Finally, we iterate through the array of row indices,
and for each row index we look up the actual word
using the wordlist array in Dict.  Each word
will match with the given regex.

This approach demonstrates a trade-off 
of space for faster run time.


8.  PRELIMINARY EXPERIMENTS

Two wordsquare implementations were tested.  
The first is simple - when trying to test if a 
word would fit a given entry in the word square,
the program iterates over every word in the dict
and tests for a match.  The second implementation
is described in Section 7, utilizing
preprocessing, auxiliary data structures and
Compressed Sparse Column.

For the simple implementation:

# seed words | runtime (in s) 
6            | 0.085
5            | 6.3
4            | 3062
3            | --

For the approach withe preprocessing and CSC

# seed words  | runtime (in s)
6             | 0.13
5             | 0.13
4             | 1.50
3             | 2327

Preprocessing: 21.5s, which only needs 
to be computed once, and can be used to
find multiple word squares

9.  CONCLUSION

This program computes wordsquares from given seedwords.
It does so by using auxiliary data structures for faster
identification of words to fit in the wordsquare. 
At least 3 words are required to complete the square.

In the future, it would be interesting to adjust
the program to allow for different sizes of wordsquares,
e.g. wordsquares of size 4x4 or 6x6.  It would also
be useful to allow for words of less than 5 characters
as seed words, like allowing the word 'cat' as input without
specifying the spaces/empty characters.  Lastly, it would
be interesting to explore how to parallelize the program.
