The problem is this: You have a two dimensional grid, and you need to scan the entire thing. Sure, but what does this ambiguous “scan” do? Well this particular post is about a word search puzzle, so the scans need to create strings to be used as search areas for the puzzle words. Scan the puzzle, and it compiles a list of all the columns, rows, and diagonals.

Now, there are a total of 8 directions you can scan a two dimensional grid by. { N, NE, E, SE, S, SW, W, NW – Exactly eight.} Wouldn’t it be nice if we didn’t need to scan all those directions. Well, if you think about it ‘E’ is a reflection of ‘W’ the same as ‘NE’ is a reflection of ‘SW’. Since the thing I just said, we don’t actually need to scan all 8 directions up front. We do need to look at all 8 directions, but we certainly don’t need to create strings for all 8.

Example:
We have a row in the puzzle that reads as.. “123456789”
If we scan East we get that exact string: “123456789”
If we scan West we get the exact reverse: “987654321”
Why bother doing both, since the data is all there no matter which we choose?

A: There is no reason to bother, not for a word search puzzle at the very least..

Alright so how do we actually perform the scans? First we need to define the scan parameters: starting location, ending location, direction, incrementation details, and a check for string completion. Let’s take a simple example (ie. Scan East).

Starting location: 0,0 – We could start at the bottom, but.. from the top feels right.
Ending Location: Puzzle Width – 1, Puzzle Height – 1 – Again, this just feels right
Direction: 1, 0 – We can define the direction as a 2d vector {x,y}
Incrementation Details: y++ – Every time we complete a string, we need to increment so we can get the next row.
Is String Incomplete: string_x != (Ending Location).x – You might have wondered why the end location has a non zero x component.. this is why.

In code that looks like this:

void WordSearch::Scan_Horizontal()
{
	short V[] = { 1, 0 }; //Right
	auto increment_F = []( WordBox* data, position& c )
//c = Cursor - ie. beginning of each string
	{
		c.y++;
	};
	auto word_Incomplete = []( path& p, position& t )
//t = Text Position - ie. current position
//p.E.x = End X Position
	{
		return t.x - 1 != p.E.x;
	};
	Scan_AlongVector( 
					path( 0, 0, data->width - 1, data->height - 1 )
					, V
					, increment_F
					, word_Incomplete );
}

Horizontal, and Vertical scans are easy though, all the strings are the same length, not like diagonals! Yea, that’s right the diagonals are different; diagonals have two strings of matching length for everything but the single longest. So to do the diagonals you need to start in one of the two corners perpendicular to the diagonal you want to scan. Then there is the matter of incrementing the cursor position around the edge of the puzzle (2d array). After that, you’ve got to consider how to determine incomplete strings. I’ll jump straight to the code this time, here it is:

void WordSearch::Scan_DiagonalDown()
{//Start Bottom Left
	short V[] = { 1, 1 }; //Right + Down
	auto increment_F = []( WordBox* data, position& c )
	{
		static ushort last_cx = c.x;
		c.x = c.y == 0 ? ++c.x : 0; //move right, once at the top
		c.y = c.y == 0 ? ( c.x == last_cx ? -42 : 0 ) : --c.y; //move up, until at the top
		last_cx = c.x;
	};
	auto word_Incomplete = []( path& p, position& t )
	{
		return ( t.y - 1 != p.S.y && t.x - 1 != p.E.x );
	};
	Scan_AlongVector( path( 0, data->height - 1, data->width, -42 ), V, increment_F, word_Incomplete );
}

That deals with a lot, but so far there is one unanswered question. How the heck does “Scan_AlongVector()” do its job? Well here’s the code for that too. Put any of your questions about the code in this post down in the comments section.

//It performs multiple scans on the word box along any lines that are parrallel to the vector V, requires a thought out function to increment the starting coordinates for each scan
int WordSearch::Scan_AlongVector( path search_path, short Dir[], void( *increment )( WordBox* data, position& c ), bool( *word_Incomplete )( path& p, position& t ) )
{
	ushort count = 0;
	position c;
	c.x = search_path.S.x;
	c.y = search_path.S.y;
	position T;
	//Top is assumed zero

	//Loop until goal coordinates are reached
	while ( true )
	{
		T.x = c.x;
		T.y = c.y;

		WordBoxWord WBW;
		WBW.start = T;
		WBW.Dir[0] = Dir[0];
		WBW.Dir[1] = Dir[1];
		
		//Continues to scan letters until either TX or TY reach the perimeter
		do
		{
			char letter = data->Get_Letter( T.x, T.y );
			if ( letter == 0 ) break; // The defined end must have been out of bounds
			WBW.word += letter;
			T.x += Dir[0];
			T.y += Dir[1];
			//repeat if Y isn't going back past the starting axis AND X isn't at the end yet
		} while ( word_Incomplete( search_path, T ) );
		
		if ( WBW.word.empty() ) break;

		int length = WBW.word.length();
		if ( length > largest_search_area )
			largest_search_area = length;

		auto List_ITER = Search_Areas.find( length );


		//We searched the word list for words of equal length
		if ( List_ITER != Search_Areas.end() )
		{
			// If-> We found a list of words matching the length provided
			List_ITER->second.push_back( WBW );
			count++;
		}
		else
		{
			//There are no words of this size at all
			std::vector<WordBoxWord> new_list;
			new_list.push_back( WBW );

			Search_Areas.emplace( length, new_list );
			count++;
		}
		increment( data, c );
	}
	return count;
}