0

I'm trying to create a word ladder, by using a linked list as a dictionary of words, and a queue to hold the word to be changed.

In the while loop of the queue, it reaches the first word in the dictionary (the word "toon" and changed to "poon") and stops. How can I make it continue until it reaches the targeted word?

Here is the code:

#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

struct Node
{
    string data;
    Node* next;
};

void insert(string ele, Node*& head)
{
    Node* newnode = new Node;
    newnode->data = ele;
    newnode->next = head;
    head = newnode;
}

void del(string key, Node*& head)
{
    Node* temp = head;
    Node* prev = NULL;

    if (temp != NULL && temp->data == key)
    {
        head = temp->next; 
        delete temp;            
        return;
    }
    else
    {
        while (temp != NULL && temp->data != key)
        {
            prev = temp;
            temp = temp->next;
        }
        if (temp == NULL)
            return;

        prev->next = temp->next;

        delete temp;
    }
}

bool find(string key,Node *&head)
{
    Node* p = head;
    while (p != NULL)
    {
        if (p->data == key)
        {
            return true;
        }
        else
        {
            p = p->next;
        }
    }
    if (p == NULL)
        return false;
}

void print(Node*& head)
{
    Node* p = head;
    while (p != NULL)
    {
        cout << p->data;
        p = p->next;
    }
}

void WordLadder(string start, string target, Node*& head)
{
    if (start == target)
        cout << "They are the same";

    if (find(target, head) != true)
        cout << "Target Not found in dicionary";
    //start word size
    int wordlength = start.size();
    //counter
    int level = 0;
    queue<string> q;
    //push word in queue
    q.push(start);
    int len = 0;
    while (!q.empty())
    {
        int wordlength = start.size();
        int sizeofq = q.size();
       
        string word = q.front();
        q.pop();
        for (int i = 0; i < wordlength ; i++)
        {
            for (char c = 'a'; c <= 'z'; c++)
            {
                word[i] = c;
                   
                if (word == target)
                {
                    q.pop();
                }
                if (find(word, head) == true)
                {
                    del(word, head);
                    q.push(word);
                    break;
                }
            }
        }
    }
    cout << len;
}

int main()
{
    Node* head = NULL;
    insert("poon", head);
    insert("plee", head);
    insert("same", head);
    insert("poie", head);
    insert("plie", head);
    insert("poin", head);
    insert("plea", head);
    string start = "toon";
    string target = "plea";
    
    WordLadder(start, target, head);
   
    return 0;
}
Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Crossplayer
  • 43
  • 7
  • It looks like you're trying to use an algorithm very simillar to BFS. You can try search how that's built. I'll try to fix your code. – Misty May 07 '21 at 20:36
  • Your code looks like an hybrid between C and C++. Are you sure a. you should reimplement a linked list (there's already `std::list` in the STL, which you are using for `std::string` and `std::queue`), b. Why are you using stuff like `NULL`, `operator new` and bare pointers instead of smart pointers and move semantics and c. why are you using a linked list in the first place? Linked lists are extremely inefficient on modern machines, and almost never make sense compared to stuff like `vector` and `deque`. Also I would stay away from pointer references (i.e. T*&) - things can get very messy. – mcilloni May 07 '21 at 20:37
  • @mcilloni im using a basic linked list because that how i took it in university if there is any method better than linked list please tell me about it,plus i think linked list works fine my problem lies in the wordladder function – Crossplayer May 07 '21 at 20:41
  • @Misty thanks i will search for BFS ,but if you can fix it without it that will very good for me – Crossplayer May 07 '21 at 20:44
  • 1
    _if there is any method better than linked list please tell me about it_ - just use `std::vector` or `std::list` if you _really_ need a linked list (hint: you don't). Reinventing the wheel without a very good reason often leads to poorer quality code that's harder to understand. – mcilloni May 07 '21 at 20:48
  • 1
    Here, I'd recommend using some data structure with a good "find" function (though you could just keep an `std::vector` sorted). I would use an `std::set` – Misty May 07 '21 at 21:00
  • 1
    [List of and documentation for the containers offered out of the box by modern C++](https://en.cppreference.com/w/cpp/container). Read up on the recommended usages for each one and pick the best one for the job. But don't be surprised if `std::vector` outperforms even the best fit when fed a small data set. The smarter the algorithm, generally the more the overhead to overcome before you start reaping the rewards, and `vector` is so "stupid" it's pretty much the king for small-to-medium amounts of data. – user4581301 May 07 '21 at 21:04
  • That said... If you MUST write a linked list, [see the community addition to this answer](https://stackoverflow.com/a/22122095/4581301) for a really good way to simplify your linked list code. If you keep a pointer to the `next` pointer, you have both the `next` pointer, and the insertion point you're currently tracking with the `prev` pointer and since a `head` pointer is a `next` pointer that points to the first item, the different name is abstracted away by using a pointer to pointer. – user4581301 May 07 '21 at 21:08

2 Answers2

1

Algorithm

It seems you were on the right track, trying to implement something like BFS, so I'm not going to explain the algorithm for a "Word Ladder" in detail. But a high-level overview is:

  1. Push the start word in the queue
  2. Run a loop until the queue is empty
  3. Traverse all words that differ by only one character to the current word and push the word in the queue (for BFS)
  4. Repeat until we find the target word or go through all words

The errors you made and how I fixed them:

Before the "wordlength" loop you need a loop to go through all the elements on the queue. While it seems the while loop is doing that, it's not. I think you realise this, as you created a sizeofq variable and never used it. The loop looks like this:

for(int j = 0; j < sizeofq; j++) {

And encapsulates the next two loops. You also need to add a temporary variable to store the initial state of word[i]. You also made a few mistakes where you used the wrong variable.

As discussed in the comments I switched from using the custom linked list you made to an std::set, but you can easily switch back onto it if you need to, as it seems like it wasn't the one causing problems. Here's the full code:

#include <iostream>
#include <queue>
#include <string>
#include <set>
using namespace std;

void WordLadder(string start, string target, set<string>& myset)
{
    if(start == target) {
        cout << "They are the same" << "\n";
        return;
    }

    if(myset.find(target) == myset.end()) {
        cout<<"Target Not found in dicionary" << "\n";
        return;
    }
    
    int wordlength = start.size();
    int level = 0;

    queue<string> q;
    q.push(start);

    while (!q.empty())
    {
        level++;
        int sizeofq = q.size();
        for(int j = 0; j < sizeofq; j++) {
            string word = q.front();
            q.pop();
            for(int i = 0; i < wordlength; ++i) 
            {
                char temp_ch = word[i];
                for (char c = 'a'; c <= 'z'; c++)
                {
                    word[i] = c;
                    if (word == target) 
                    {            
                        cout << level + 1 << endl;
                        return;
                    }
                    if (myset.find(word) == myset.end())
                    {
                        continue;
                    }
                    myset.erase(word);
                    q.push(word);
                }

                 word[i] = temp_ch;
            }
            
        }      
    }

    return;   
}


int main()
{
   
    std::set<string> myset;
    myset.insert("poon");
    myset.insert("plee");
    myset.insert("same");
    myset.insert("poie");
    myset.insert("plie");
    myset.insert("poin");
    myset.insert("plea");
    string start = "toon";
    string target = "plea";
    
    WordLadder(start, target, myset);
    return 0;
}

Stylistic suggestions

You seem to be a new C++ programmer, so I thought I'd leave my thoughts about the code here.

It's considered good practice to have the function return the result, not print it. It makes your code much more flexible.

You implemented your own container to make this work, which is kind of like reinventing the wheel. The C++ STL nearly always includes something you can use to make your life easier, so search for it before you get to work.

If you're writing a bigger project do not use using namespace, but for a small toy like this one it's fine.

Misty
  • 416
  • 3
  • 8
0

As I already said in one of my answers, rolling your own containers in C++ often leads to confusing and hard to read code, which doesn't help at all while modelling a problem.

In modern C++ (i.e. after C++11, and nowadays ideally you should be using C++17 or even start timidly dabbling with C++20) you almost never need stuff like operator new, NULL and often pointers at all (they are still useful as a stopgap solution for the lack of std::optional<T&> though).

By the way, I don't think using a queue is needed to solve your problem; a single "current item" variable suffices; you can then find the next element by searching the list for what string has an Hamming distance of one from the current element. It will not work in a general case due to the likelihood of loops, but it is enough if you are only working on a limited list of words such as yours where there is really only one single possible ladder.

This is how I would quickly model your problem in C++20:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <ranges>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>

using namespace std::literals;

// Simple implementation of Hamming's distance (see https://en.wikipedia.org/wiki/Hamming_distance)
std::size_t hamming_distance(const std::string_view s1, const std::string_view s2) {
    std::size_t dist {};

    if (s1.size() != s2.size()) {
        throw std::runtime_error { "strings have different lengths, which is unsupported" };
    }

    auto it1 { s1.begin() };
    auto it2 { s2.begin() };

    const auto end1 { s1.end() };

    while (it1 != end1) {
        dist += *it1++ != *it2++;
    }

    return dist;
}

bool word_ladder(std::string_view start, const std::string_view target, std::vector<std::string> words) {
    if (start == target) {
        std::cout << "noop: start and target are the same\n";
        
        return true;
    }

    // C++20's ranges - use std::find(std::begin(words), std::end(words), target) in older revisions
    if (std::ranges::find(words, target) == std::end(words)) {
        std::cerr << "error: target Not found in dictionary\n";

        return false;
    }

    std::size_t len { 1U };

    // Current word in the ladder - must be string because we are deleting them from the vector,
    // so we must copy them
    std::string word { start };

    std::cout << word;

    while (word != target) {
        std::cout << "->";

        // find an element in the dictionary has hamming(el, word) == 1 (i.e. 'cord' and 'core').
        // this won't work if there's more than one match, because it will cause a loop.
        // This is also based on C++20's ranges, and it can be replaced with std::find_if
        const auto next_it { std::ranges::find_if(words, [word] (const auto el) { return hamming_distance(el, word) == 1; }) };

        // no match, it means the chain can't be completed
        if (next_it == std::end(words)) {
            std::cout << "X (no result)\n";

            return false;
        }

        // print the next element
        std::cout << *next_it;
      
        // set the next word as the newly found item
        word = *next_it;

        // remove it from the vector
        // while this is O(n), it's empirically as fast as using a more "optimized" container
        // due to how hecking fast vectors and memcpy are on modern CPUs
        words.erase(next_it); 

        ++len; // chain length counter
    }

    std::cout << "\nChain was " << len << " elements long\n";

    return true;
}

int main() {
    std::vector<std::string> words {
        "poon",
        "plee",
        "same",
        "poie",
        "plie",
        "poin",
        "plea",
    };

    const auto start { "toon"sv };
    const auto target { "plea"sv };
    
    const bool success { word_ladder(start, target, std::move(words)) };
   
    return success ? EXIT_SUCCESS : EXIT_FAILURE;
}

The output is:

toon->poon->poin->poie->plie->plee->plea
Chain was 7 elements long

I have used std::vector instead of a more "optimal" container because it is often the best all-around choice, even on severely limited systems, due to how fast modern CPUs are. Linked lists are especially terrible and should be (almost) always avoided due to their massive overhead from pointer indirections, which offsets any theoretic gain you might get from them.

In general, you should generally use vectors and hashmaps (i.e. std::unordered_map) by default, and only consider the other containers when you really need them.

mcilloni
  • 693
  • 5
  • 9