Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Mar 12th, 2006, 4:10 PM   #1
HammerCat
Newbie
 
Join Date: Mar 2006
Posts: 7
Rep Power: 0 HammerCat is on a distinguished road
searching for 2D arrays within 2D arrays

Hi,

I'm working on a program to find a 2D array of characters (temp) in a larger 2D array of characters (map), and then output the coordinates of the upper left corner of the first occurrence. Temp and map are loaded from a file, and can be any size. For the purpose of this example, map is:
j2DikxdiLLI3j
aAxzZxxixxkw9
okxjzxxxnchnq
jmxmbkklmnsff

and temp is:
xx
xx

So my expected coordinates should be row 1, col 5, but I am getting row 0, col 5 back. Here is my searching code:
        bool found = 0;
	int row = 0, col = 0;
	for (int i = 0; ((i < (maphgt-(temphgt-1))) && !found); i++)
	{
		for (int j = 0; ((j < (mapwid-(tempwid-1))) && !found); j++)
		{
				for (int m = 0; ((m < temphgt) && !found); m++)
				{
					for (int n = 0; n < tempwid; n++)
					{
                              if (temp[m][n] != map[i+m][j+n])
						break;
						else if ((n == (tempwid - 1)) && (m == (temphgt - 1)))
						{
							found = 1;
							row = i;
							col = j;
						}
					}
					
				}
               	
		}
	}
	if (found)
		cout << "Found it at row " << row << ", col " << col << endl;
	else
		cout << "Not found." << endl;

Anyone have any ideas?

Thanks.
HammerCat is offline   Reply With Quote
Old Mar 12th, 2006, 4:18 PM   #2
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 DaWei is on a distinguished road
I'll look at your code (haven't yet). Meanwhile, here's a presentational tip: if you put your maps in code tags, as with your code, they'll use a fixed-width font and preserve their relationships.

2DikxdiLLI3j
aAxzZxxixxkw9
okxjzxxxnchnq
jmxmbkklmnsff

vs.

2DikxdiLLI3j
aAxzZxxixxkw9
okxjzxxxnchnq
jmxmbkklmnsff
Notice that your first row is one character short of the rest. You might want to investigate the effects of that on your algorithm.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers
DaWei is offline   Reply With Quote
Old Mar 12th, 2006, 7:59 PM   #3
HammerCat
Newbie
 
Join Date: Mar 2006
Posts: 7
Rep Power: 0 HammerCat is on a distinguished road
Thank you for the tip. Upon further investigation, my map.txt file is actually

j2DikxdiLLI3j
aAxzZxxixxkw9
okxjzxxxnchnq
jmxmbkklmnsff

which, in my code editor, are all 13 characters long. Must have made a typo earlier, I'm sorry.

Thanks,
Catherine
HammerCat is offline   Reply With Quote
Old Mar 12th, 2006, 10:22 PM   #4
nindoja
Programmer
 
Join Date: Jun 2005
Posts: 92
Rep Power: 4 nindoja is on a distinguished road
Where do you assign values to tempwid and temphgt and mapwid and maphgt? I think what is happening is that your tempwid and temphgt are set differently than your implemention of them in the search algorithm.
nindoja is offline   Reply With Quote
Old Mar 12th, 2006, 10:26 PM   #5
HammerCat
Newbie
 
Join Date: Mar 2006
Posts: 7
Rep Power: 0 HammerCat is on a distinguished road
This bit of code is an example for extracting info from map.txt. It is simply repeated with different variable names for template.txt.

	char mapbuff[100];
	ifstream instream;

	instream.open("map.txt");
	instream.getline(mapbuff, 100);

	int mapwid = strlen(mapbuff);
	int maphgt = 1;			// create the variable height and set it to 1.. since we just took in 1 line

	while(!instream.eof()) // while we haven't reached the end of the file yet..
	{
		instream.getline(mapbuff, 100);
		maphgt++;		// for every line we take in, increment height by 1
	}

	char ** map = new char*[maphgt];		// declares HEIGHT strings

	for (int i = 0; i < maphgt; i++)
		map[i] = new char [mapwid+1];		// initialize the ith row of the map to have width+1 characters

	instream.clear();
	instream.seekg(0);		// seek to the beginning of the file

	for (int i = 0; (i < maphgt) && (!instream.eof()); i++)
	{
		instream.getline(mapbuff, 100);	// get a line and store it in buffer
		strcpy(map[i], mapbuff);
	}
	instream.clear();
	instream.close();
HammerCat is offline   Reply With Quote
Old Mar 13th, 2006, 3:17 PM   #6
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 DaWei is on a distinguished road
Here is some sample code. You will note that the approach is not the same as yours. When I use C++, I use C++, not C compiled with a C++ compiler. The result is code produced in a shorter period of time that is generally more robust. This code has been compiled and tested, but it hasn't been tested thoroughly. Your warranty expired yesterday.
#include <iostream>     // Included for I/O stream operations
#include <fstream>      // Included for file stream operations
#include <vector>       // Included for easy 'arrays'
#include <string>       // Included for C++ string usage.
                        // They're easier to deal with than char arrays

using namespace std;    // To use the entire standard namespace,
                        // thus precluding the necessity of 
                        // using the scope resolution operator.
                        // Can introduce name conflicts if due
                        // care is not taken.
typedef vector <string> charMap;

class Point
{
public:
    int x;
    int y;
    Point () : x (0), y (0) {}
    Point (int X, int Y) : x (X), y (Y){}
};

class cMap
{
public:
    size_t width;
    size_t height;
    charMap map;
    cMap (size_t w, size_t h)
    {
        width = w;
        height = h;
        for (size_t i = 0; i < height; i++)
        {
            string temp = "";
            for (size_t j = 0; j < width; j++) temp += " ";
            map.push_back (temp);
        }
    }
    cMap (size_t w, size_t h, charMap& m)
    {
        width = w;
        height = h;
        for (size_t i = 0; i < m.size (); i++) map.push_back (m [i]);
    }
    void show ()
    {
        for (size_t i = 0; i < height; i++) cout << map [i] << endl;
        cout << endl;
    }
};
bool validateMap (charMap& m);
bool mapFind (cMap& main, cMap& sub, Point& loc);
bool mapMatch (cMap& m, cMap& s, size_t y, size_t x);

// Function to send error message to stderr stream
int uhOh (string trouble)
{
    cerr << trouble << endl;
    cin.get ();
    return 1;
}
// Main
int main (int argc, char *argv [])
{
    Point location;
    // Generate a test map
    charMap theMap;
    theMap.push_back ("asdfghjkl");
    theMap.push_back ("Now is th");
    theMap.push_back ("The quick");
    theMap.push_back ("quality o");
    theMap.push_back ("Out, damn");

    if (!validateMap (theMap)) return uhOh ("Map poorly defined");
    
    cMap mainMap = cMap (theMap [0].size (), theMap.size (), theMap);
    cout << "Main map:\n" << endl;
    mainMap.show ();

    // Generate a submap
    theMap.clear ();
    theMap.push_back ("qu");
    theMap.push_back ("it");
    if (!validateMap (theMap)) return uhOh ("submap poorly defined");

    cMap subMap = cMap (theMap [0].size (), theMap.size (), theMap);
    cout << "Sub map:\n" << endl;
    subMap.show ();

    if (mapFind (mainMap, subMap, location))
        cout << "Top: " << location.y << ", Left: " << location.x << endl;
    else cout << "Sub map not found within the target map" << endl;
    cout << endl;

    // Generate a different submap
    theMap.clear ();
    theMap.push_back ("Now");
    theMap.push_back ("The");
    theMap.push_back ("qua");
    if (!validateMap (theMap)) return uhOh ("Second submap poorly defined");

    subMap.height = theMap.size ();
    subMap.width = theMap [0].size ();
    subMap.map = theMap;
    cout << "New submap:\n" << endl;
    subMap.show ();

    if (mapFind (mainMap, subMap, location))
        cout << "Top: " << location.y << ", Left: " << location.x << endl;
    else cout << "Sub map not found within the target map" << endl;
    cout << endl;

    cout << "Press ENTER to exit (don't you love to say that?)";
    cin.sync ();
    cin.get ();
    return 0;
}

bool validateMap (charMap& m)
{
    size_t testSize = m [0].size ();
    for (size_t i = 1; i < m.size (); i++)
        if (m [i].size () != testSize) return false;
    return true;
}
bool mapFind (cMap& main, cMap& sub, Point& loc)
{
    loc.x = 0;
    loc.y = 0;
    size_t maxX = main.map [0].size () - sub.map [0].size ();
    size_t maxY = main.map.size () - sub.map.size ();
    int pos;
    // For all possible rows...
    for (size_t i = 0; i <= maxY; i++)
    {
        // For all possible columns
        for (size_t j = 0; j <= maxX; j++)
        {
            // If the submap string isn't on this main map row, try the next
            if ((pos = main.map [i].find (sub.map [0], 0)) == string::npos) continue;
            j = pos;
            loc.x = pos;
            loc.y = i;
            if (mapMatch (main, sub, i, j)) return true;
        }
    }
    return false;
}
bool mapMatch (cMap& m, cMap& s, size_t y, size_t x)
{
    size_t xBase = x;
    for (size_t i = 0; i < s.height; i++, y++, x = xBase)
        for (size_t j = 0; j < s.map [0].size (); j++, x++)
            if (m.map [y][x] != s.map [i][j]) return false; 
    return true;
}
Output looks like this:
Quote:
Originally Posted by Output
Main map:

asdfghjkl
Now is th
The quick
quality o
Out, damn

Sub map:

qu
it

Top: 2, Left: 4

New submap:

Now
The
qua

Top: 1, Left: 0

Press ENTER to exit (don't you love to say that?)
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers
DaWei is offline   Reply With Quote
Old Mar 13th, 2006, 3:39 PM   #7
HammerCat
Newbie
 
Join Date: Mar 2006
Posts: 7
Rep Power: 0 HammerCat is on a distinguished road
Thanks DaWei,
Although your methods are a little more advanced than my education at this point, I do appreciate your help. I'm going to keep playing with my code and see if I can get it to work.
HammerCat is offline   Reply With Quote
Old Mar 13th, 2006, 6:09 PM   #8
The Dark
Expert Programmer
 
Join Date: Jun 2005
Posts: 852
Rep Power: 4 The Dark is on a distinguished road
HammerCat: the problem is in these lines
if (temp[m][n] != map[i+m][j+n])
 break;
If this test finds an entry that does not match, it only breaks out of the inner (n) loop, the m loop still continues, so it will go on to the next line and check that.

You could either use another bool variable such as "noMatch" to control the inner two loops, or you could just set m to temphgt in the above if test before the break, so that the m loop stops.
The Dark is offline   Reply With Quote
Old Mar 13th, 2006, 7:03 PM   #9
HammerCat
Newbie
 
Join Date: Mar 2006
Posts: 7
Rep Power: 0 HammerCat is on a distinguished road
Thank you The Dark! That worked.. I actually did a combo.. first set m to temphgt, then break, so that it closes out of both inner loops. It works though. Thank you!
HammerCat is offline   Reply With Quote
Old Mar 14th, 2006, 9:16 AM   #10
nnxion
Programming Guru
 
nnxion's Avatar
 
Join Date: Jun 2005
Location: elemental plane
Posts: 1,429
Rep Power: 5 nnxion is on a distinguished road
That's a nice solution DaWei, I almost thought the CharMap was a map but it was a vector<string>.
__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates
nnxion is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 2:23 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC