word_ladder.cpp

#include <iostream>
#include "../../SRC/lstd/filesystemutil.hpp"
#include "../../SRC/lstd/Timer.hpp"

class Node
{
public:
    Node* parent;
    std::string value;
    std::vector< Node* > children;
    Node( Node* parent , const std::string& value ) : parent(parent) , value(value) {}
    ~Node()
    {
        for ( uint i = 0 ; i < this->children.size() ; ++i ) delete this->children[i];
    }
};

void expand( const std::vector< std::string >& words , Node* node , int depth )
{
    if ( depth == 0 ) return;

    std::string startingWord = node->value;
    // find all words that only differ in one letter
    for ( uint i = 0 ; i < words.size() ; ++i )
    {
        int dif = 0;
        for ( uint j = 0 ; j < startingWord.length() ; ++j )
        {
            if ( words[i][j] != startingWord[j] )
            {
                ++dif;
                if ( dif >= 2 ) break;
            }
        }
        if ( dif == 1 )
        {
            // only add if not in list already
            bool inList = false;
            for ( uint j = 0 ; j < node->children.size() ; ++j )
            {
                if ( words[i] == node->children[j]->value )
                {
                    inList = true;
                    break;
                }
            }
            if ( !inList ) node->children.push_back( new Node( node , words[i] ) );
        }
    }

    // expand children
    for ( uint i = 0 ; i < node->children.size() ; ++i )
    {
        expand( words , node->children[i] , depth-1 );
    }
}

void search( std::vector< std::vector< std::string > >& solutions , Node* node , const std::string& str )
{
    if ( str == node->value )
    {
        Node* counter = node;
        std::vector< std::string > solution;
        while ( counter->parent != nullptr )
        {
            solution.push_back( counter->value );
            counter = counter->parent;
        }
        solution.push_back( counter->value );
        solutions.push_back( solution );
        return;
    }
    for ( uint i = 0 ; i < node->children.size() ; ++i )
    {
        search( solutions , node->children[i] , str );
    }
}

int main()
{
    std::string filename = "PATH/TO/DICTIONARY_FILENAME";
    std::string startingWord = "Kerzen";
    std::string endingWord = "Vetter";
    int depth = 6;
    bool removeNames = false;

    std::vector< std::string > lines;
    if ( readFile( lines , filename ) )
    {
        // find all six letter words
        std::vector< std::string > sixLetterWords;
        for ( uint i = 1 ; i < lines.size() ; ++i )
        {
            if ( !startsWith( lines[i] , "#" ) )
            {
                std::vector< std::string > parts;
                split( parts , lines[i] , '/' );
                if ( parts.size() == 2 )
                {
                    if ( parts[0].length() == startingWord.length() )
                    {
                        if ( removeNames )
                        {
                            // names have only an S in the second part, so don't add them
                            if ( parts[1] != "S" )
                            {
                                sixLetterWords.push_back( parts[0] );
                            }
                        }
                        else sixLetterWords.push_back( parts[0] );
                    }
                }
            }
        }
        std::cout << sixLetterWords.size() << " six letter words found" << std::endl;
        // yeet the umlauts
        std::vector< std::string > cleanWords;
        for ( uint i = 0 ; i < sixLetterWords.size() ; ++i )
        {
            bool clean = true;
            for ( uint j = 0 ; j < startingWord.length() ; ++j )
            {
                if ( sixLetterWords[i][j] < 65 || sixLetterWords[i][j] > 122 )
                {
                    clean = false;
                    break;
                }
            }
            if ( clean ) cleanWords.push_back( sixLetterWords[i] );
        }
        std::cout << cleanWords.size() << " clean words found" << std::endl << std::endl;

        Node* root = new Node( nullptr , startingWord );

        Timer timer;
        timer.start();
        expand( cleanWords , root , depth );

        std::vector< std::vector< std::string > > solutions;
        search( solutions , root , endingWord );
        timer.stop();

        std::cout << "There are " << solutions.size() << " solutions:" << std::endl << std::endl;
        for ( uint i = 0 ; i < solutions.size() ; ++i )
        {
            std::cout << i << ": ";
            for ( int j = (int)solutions[i].size()-1 ; j >= 0 ; --j )
            {
                std::cout << solutions[i][j];
                if ( j != 0 ) std::cout << " > ";
            }
            std::cout << std::endl << std::endl;
        }
        std::cout << "Time: " << timer.getTime() << "ms" << std::endl;

        delete root;
    }
    else std::cout << "failed to open file" << std::endl;
    return 0;
}