//***********************************************************************
// Author: Mark Bates
// File: map.cpp
// Date: 9-12-02
// Purpose: Reads in a file supplied by the user of 5 letter words,
// if the words are 1 letter off the two words connect.
// The words are placed in a ''words'' vector and a ''graph''
// is created, the index of the word is used in the graph.
// If the words connect, the graph should contain the index
// of the word in it''s position on the graph. The user is
// asked for 2 words, the program then tells if the 2nd word
// can be reached from the first word.
//
//***********************************************************************
#include <iostream.h>
#include <stdlib.h>
#include <vector>
#include <fstream.h>
#include <string>
#include <list>
#include <algorithm>
#include <stack>
//********************************************************************
// Compare funtion to determine if words are one character off
//********************************************************************
bool comp(string a, string b)
{
int notmatch = 0;
for( int i = 0; i < 5; i++)
{
if( a[i] != b[i] )
notmatch++;
}
if( notmatch > 1 )
return false;
else
return true;
}
//********************************************************************
// Requires a file name paramter containing 5 letter words
//********************************************************************
int main(int argc, char* argv[])
{
if(argc != 2)
{
cerr << "Incorrect number of parameters passed" << endl;
return EXIT_FAILURE;
}
ifstream inf( argv[1] );
if( !inf )
{
cerr << "File " << argv[1] << " could not be opened" << endl;
return EXIT_FAILURE;
}
vector<string> words;
vector<vector<int> > graph;
string str;
int index = 0;
while( inf >> str )
{
words.push_back(str);
graph.push_back();
for( int i = index -1; i >= 0; i-- )
{
if( comp(words[index], words[i]) )
{
graph[i].push_back(index);
graph[index].push_back(i);
}
}
index++;
}
inf.close();
ostream_iterator<string> ot(cout, "\n" );
copy(words.begin(), words.end(), ot);
cout << graph[0][0] << endl;
cout << graph[1][0] << graph[1][1] << graph[1][2] << graph[1][3] << endl;
cout << graph[2][0] << graph[2][1] << graph[2][2] << endl;
cout << graph[3][0] << endl;
cout << graph[4][0] << graph[4][1] << endl;
cout << graph[5][0] << endl;
string from;
string to;
string starting;
string target;
int atposition = 0;
cout << "From where? " << endl;
cin >> from;
cout << "To where? " << endl;
cin >> to;
for(int i = 0; i <= index; i++)
{
if(words[i] == from)
{
starting = from;
target = to;
atposition = i;
break;
}
else if(words[i] == to)
{
starting = to;
target = from;
atposition = i;
break;
}
cout << "Inside for loop" << endl;
}
if(starting == target)
{
cout << "You are already there!" << endl;
return EXIT_FAILURE;
}
// My troubles start here!!!!
// Help me!!!!
vector<bool> visited;
cout << "Vector visited made" << endl;
stack<int> cango;
cout << "stack cango made" << endl;
cout << "Before while counter" << endl;
int counter = graph[atposition].size();
while(counter > 0)
{
cango.push(graph[atposition][counter]);
counter--;
}
cout << "After while counter" << endl;
visited[atposition] = true;
cout << "atposition made" << endl;
while( !cango.empty() )
{
cout << "Inside while cango ! empty" << endl;
atposition = cango.top();
cango.pop();
visited[atposition] = true;
if( target == words[atposition])
{
cout << "You can get there" << endl;
return EXIT_SUCCESS;
}
while( visited[atposition] && !cango.empty() )
{
atposition = cango.top();
cango.pop();
visited[atposition] = true;
}
}
cout << "You can not go from " << from << " to " << to << endl;
system("PAUSE");
return 0;
}
learning STL
Currently learning the STL in my college C++ class.
Having trouble determing wether I can get from ''starting'' to ''target''...The two main problems I am having is putting all the places one word goes to into the stack (trying to push() vector[0][0] through vector[0][end]). I also get a core dump when I try setting bool vector[0] to true.
any help in simple form is greatly appreciated
I know the code after my "need help here" comment probaly isn''t correct...but the program doesn''t make it that far where I can iron out the bugs.
It is recommended not to use a vector of bools, but a std::bitset instead. I forget why exactly.
You appear to be a victim of the infamous "off-by-one" bug:
The largest index you can use is actually
But in general, you are also using the
Unlike your C arrays, vectors can grow dynamically. However, this means that nothing exists when the vector is first creatd besides the container itself - in a C array, the memory is allocated statically all at once.
To populate your
However the
I think this might possibly be why
[edited by - Zipster on September 12, 2002 12:08:52 AM]
int counter = graph[atposition].size();while(counter > 0){ cango.push(graph[atposition][counter]); counter--;}
The largest index you can use is actually
counter-1
.But in general, you are also using the
vector
class wrong. In the case of visited
, you try to access an element of the vector, yet the vector is empty. The only way you can access an element of a vector is if was already created via push_front
or push_back
, or populated by some other means.Unlike your C arrays, vectors can grow dynamically. However, this means that nothing exists when the vector is first creatd besides the container itself - in a C array, the memory is allocated statically all at once.
To populate your
visited
vector so you can use it, you can use the resize
function like so:visited.resize(index, false);
However the
index
variable doesn't exactly indicate that it's also the size of the words
vector, so if you want to use words.size()
instead of index
, go right ahead quote:I forget why exactly.
I think this might possibly be why
[edited by - Zipster on September 12, 2002 12:08:52 AM]
quote:Original post by Oluseyi
It is recommended not to use a vector of bools, but a std::bitset instead. I forget why exactly.
vector is a specialization that is, in fact, not an STL compatible container. It''s was a first attempt at making a bit container that compressed 8 bool''s into a byte (as opposed to one bool per byte).
quote:Original post by RegaRIP
I also get a core dump when I try setting bool vector[0] to true.
0.o That''s impressive - what OS are you using? (Perhaps you meant seg-fault?)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement