make word squares that have rotational symmetry

word-square.cpp

/*
Copyright (c) 2019 Thaddaeus Frogley

Word Square Finder

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#include <iostream>
#include <fstream>

#include <deque>
#include <list>
#include <map>
#include <set>

#include <algorithm>

#include <locale>
#include <cstdlib>
#include <assert.h>

using namespace std;

// Stuff to do with command line options 

const char* gOptions[256] = {};

deque< const char* > ParseArguments (int argc, const char * argv[])
{
    deque< const char* > filenames;
    
    // options & their defaults:
    gOptions['c'] = "4"; // c=count, char or wchar_t
    gOptions['x'] = ",";
    gOptions['p'] = "a"; // (P)erfect => t=true, must be perfect, f=false, must not be perfect, a=any (either)
    gOptions['d'] = "t"; // (D)uplicates => t=true, same word allowed on two different rows
    gOptions['v'] = "g"; // (V)erbose logging to std::err
    
    for (int i=1;i!=argc;++i)
    {
        const char * arg = argv[i];
        if (*arg=='-')
        {
            if (arg[1]!=0 && arg[2]=='=')
            {
                gOptions[tolower(arg[1])] = arg+3;
            }
            else
            {
                cerr << "Error: Command line argument format not recognised:" << endl;
                cerr << "\t" << arg << endl;
                exit(-1);
            }
        }
        else
        {
            filenames.push_back(argv[i]);
        }
    }
    
    return filenames;
}

bool Enabled(char option)
{
    return *gOptions[option] == 't' || *gOptions[option] == 'T';
}

bool Verbose()
{
    return Enabled('v');
}

bool AllowDupes()
{
    return Enabled('d');
}

bool RequirePerfection()
{
    return Enabled('p');
}

bool RejectPerfection()
{
    return *gOptions['p'] == 'f' || *gOptions['p'] == 'F';
}

bool EvaluatePerfection(bool match)
{
    if (RequirePerfection())
        return match;
    if (RejectPerfection())
        return !match;
    return true;
}

// Stuff to read in a dictionary / word list
// does some extra lifting to support multiple words per line with a separator
// if your word list is well formed and large, you can speed this up a lot!

typedef deque<string> StringList;
typedef void(*AlgorithmPtr)(const StringList*);

struct IsSeperator : unary_function<int,bool> {
    bool operator() (const int& c) const {return isspace(c) || strchr( gOptions['x'], c );}
};


// trim from start
static inline string ltrim(string s) {
    s.erase(s.begin(), find_if(s.begin(), s.end(), not1(IsSeperator())));
    return s;
}

// trim from end
static inline string rtrim(string s) {
    string::reverse_iterator r = find_if(s.rbegin(), s.rend(), not1(IsSeperator()));
    
    if (r==s.rend())
        return string("");
    
    s.erase(r.base(), s.end());
    return s;
}

// trim from both ends
static inline string trim(string s) {
    return ltrim(rtrim(s));
}

typedef pair< string, string > StringPair;

static inline StringPair split_string( const string& s )
{
    string::const_iterator mid1 = find_if(s.begin(), s.end(), IsSeperator());
    string::const_iterator mid2 = find_if(mid1, s.end(), not1(IsSeperator()));
    
    return StringPair( string(s.begin(), mid1), string(mid2, s.end()) );
}
                  
StringList* BuildStringList(istream& myfile, int word_size)
{
    StringList* result=0;
    
    if (Verbose())
        cerr << "Loading." << endl;
    
    string line, word;
    result = new StringList();
        
    while ( myfile.good() )
    {
        getline (myfile,line);
        
        while (!line.empty())
        {
            StringPair split = split_string( line );
            word = trim(split.first);
            if (word.size()==word_size)
            {
                result->push_back(word);
            }
            line = split.second;
        }
    }
        
    sort( result->begin(), result->end() );

    return result;
}

// class for word square / grid 

class WordGrid
{
    public:
    
    WordGrid(int size)
    {
        w = size;
        data = (string::value_type*)calloc(size*size,sizeof(string::value_type));
    }
    
    ~WordGrid()
    {
        free(data);
    }
    
    string::value_type Get(int x, int y)
    {
        return data[y*w+x];
    }
    
    void Set(int x, int y, string::value_type c)
    {
        data[y*w+x] = c;
    }

    void Set(int y, string s)
    {
        for(int x=0;x!=w;++x)
            data[y*w+x] = s[x];
    }
    
    void Clear(int y)
    {
        for(int x=0;x!=w;++x)
            data[y*w+x] = 0;
    }

    string Get(int y) const
    {
        string result;
        result.reserve(w);
        for(int x=0;x!=w;++x)
             result.push_back(data[y*w+x]);
        return result;
    }
    
    string GetV(int x) const
    {
        string result;
        result.reserve(w);
        for(int y=0;y!=w;++y)
        {
            auto c = data[y*w+x];
            if (!c) break;
            result.push_back(c);
        }
        return result;
    }
    
    bool Contains( const string& rhs ) const
    {
        for(int x=0;x!=w;++x)
        {
            if (Get(x)==rhs) return true;
            if (GetV(x)==rhs) return true;
        }
        return false;
    }
    
    int Width() const { return w; };
    
    private:
    int w;
    string::value_type* data;
};

ostream& operator<<(ostream& os, const WordGrid& grid)
{
    cout << endl;
    for (int n=0;n!=grid.Width();++n)
        cout << grid.Get(n) << endl;
        
    return os;
}

// data structure that lets me quickly check if a partial word is valid

struct Words
{
    map< string::value_type, Words > data;
    
    size_t size() const {return data.size();}
    size_t rsize() const 
    {
        size_t t = 0;
        for (auto it = data.begin(); it != data.end(); ++it)
            t += it->second.size();
        return t;
    }
    
    void Insert(const string& word, int i=0)
    {
        if (i<word.size())
        {
            data[word[i]].Insert(word,i+1);
        }
    }
    
    bool Find(const string& word) const
    {
        int i=0;
        auto* head=this;
        
        while(i<word.size())
        {
            auto itr = head->data.find(word[i]);
            if (itr==head->data.end()) return false;
            head = &itr->second;
            i++;
        }
        return true;
    }
};

// our dictionary
Words words;
set< string > quick_words;
    
bool RollForward(WordGrid& grid, int c)
{
    auto witr = quick_words.begin();
    while (witr!=quick_words.end() && c<grid.Width())
    {
        const string& s = *witr;
        
        // no duplicates
        if (AllowDupes()==false && grid.Contains(s))
        {
            witr++;
            continue;
        }
        
        // add a row
        grid.Set(c,s);
        
        // check if all columns can still make valid words
        int n=0;
        for (;n!=grid.Width();++n)
        {
            if (words.Find(grid.GetV(n))==false) break;
        }
        
        if (n==grid.Width())
        {
            // recurse
            RollForward(grid,c+1);
            
            // roll back
            for (int n=c;n!=grid.Width();++n)
                grid.Clear(n);
        }
                
        witr++;
    }

    // final check, against perfection requirements
    // a "perfect" word square has the same words vertically and horizontally
    // ie: row(1) == column(1)
    bool okay = (c==grid.Width());
    for (int n=0; n!=grid.Width() && okay; ++n)
        okay = okay && EvaluatePerfection (grid.Get(n)==grid.GetV(n));
        
    if (okay)
        cout << grid << endl;
    
    return okay;
}

// reversible word
bool Reversable(const StringList* source, const string& s) 
{
    // todo: better to compare reverse in the search than copy, reverse and search
    string r(s);
    reverse(r.begin(), r.end());
    return binary_search(source->begin(), source->end(), r);
}

// entry point to word squares search
void WordSquare( const StringList* source, int sz )
{   
    if (Verbose())
        cerr << "Filtering." << endl;

    // copy only correct length words
    for_each(
        source->begin(), source->end(), 
        [&](const string& s){
            assert(s.size()==sz);

            // this is the constraint that results in word squares that can be rotated
            if (Reversable(source, s))
            {
                quick_words.insert(s);
                words.Insert(s);
            }            
        } 
    );

    if (Verbose())
        cerr << "Searching " << quick_words.size() << " / " << source->size() << " words." << endl;
        
    WordGrid grid(sz);
    
    auto witr = quick_words.begin();
    while (witr!=quick_words.end())
    {
        grid.Set(0, *witr);
        
        RollForward(grid, 1);
        witr++;
    } 
}

// entry point to application
int main (int argc, const char * argv[])
{
    auto filenames = ParseArguments(argc, argv);
    
    int width = atoi((gOptions['c']));
            
    // read word list in, 
    StringList* words = 0;
    if (filenames.empty())
    {
        // from std input if no filenames on commandline
        words = BuildStringList(cin, width);
    }
    else
    {
        // from first filename on commandline if one is given
        ifstream myfile (filenames[0]);
        if (myfile.is_open())
        {
            words = BuildStringList(myfile, width);
            myfile.close();
        }    
    }
    
    // find word squares
    if (words && !words->empty())
    {   
        WordSquare( words, width );
        
        delete words;
    }
    else
    {
        cerr << "Error: word list empty or missing." << endl;
        return -1;
    }
    
    return 0;
}