Question

Develop a C++ PROGRAM which will find a hidden sentence in a list of random words using map function Open this text file named shuffled_words.txt in your program If it matters, you may presume there are an even number of words in the file Place the contents of the file into an appropriate data structure in the following manner: Grab a pair of strings from the file (unless end of file is reached) Each string is separated by a space The first string is the key The second string is the value So both the key and value are strings Place the key/value pair into your data structure Words are chained together such that a key will give its value like normal, but that value may also be a key in the map, which can find another value and so forth For example... If... map["why"] = "hello" map["hello"] = "there" map["there"] = "everyone" map["everyone"] does not exist This means if I start with "why" and concatenate the map values together I get the sentence "why hello there everyone" Here is what a graphical representation of what the data structure might look like: There is only one sentence chained together in the entire text file. All other map entries are immediate dead ends. Take the giant word list, find the longest word chain as described above, and print out the sentence that chain makes.

Answer 1

Solution -

Below is the required code in C++. The data structure used in this code is Vector along with pairing.

#include<bits/stdc++.h>

#include <iterator>

using namespace std;

int main(){

fstream file;

// declaring a vector of pairs

vector<pair<string,string>>v;

// opening the file named "input.txt"

file.open("input.txt",ios::in);

if(!file)

cout<<"No such file";

else {

string s,prev;

file >> s;                      // reading the first word of sentence

prev = s;

int i=0;

while (file >> s) {      // reading the rest of the words

v.push_back(make_pair(prev,s)); // making pair like ("why","hello") and storing in vector

prev = s;                        // storing the current word as prev for next coming word to map

}

}

// displaying the chain

for(int i=0;i<v.size();i++)

cout << "(" << v[i].first << "->" << v[i].second << ")"<<endl;

file.close();  

return 0;

}

Explanation -

In this vector of pairs if used to store the mapping of prev word with next word.

An object ifstream is created to open the file in read mode.

First we read the very first word of the sentence and store it as prev for the next word.

Now we read all the other words using while loop and keep pushing the pair in the vector. The first pair will be (prev, current word). Now the current word will become prev for next coming word in the file. This keep repeating for other words until the end of the file.

At last we display the longest chain from the vector and close the file.

Note - We could have used map but since map keeps the key-value pair in sorted order then our original order of the sentence would be lost and we would then need another data structure like vector to store the original order of words in the sentence. For this reason, vector of pairs is used which fulfills the requirement with less space.

Refer to the screenshot below for code and output -

Thanks