Boggle

Last week read an article that covered the Azure Kinect DK camera. It seems that up to recently you could only get on a list and wait for the hardware and software to become available. It appears that has recently changed and Microsoft is starting to ship the camera.

About two years ago I purchased the AWS DeepLens camera. The camera in combination with an AWS account allows you to experiment with Machine Learning. My free AWS account has expired and I am ready to start experimenting with Azure and Microsoft’s new camera. I will check later today if I can purchase the new camera and will start experimenting with it on the Azure cloud.

I was looking at a recursive problem / challenge which did not have a solution. The challenge is to find the count of instances of a specified word on a Boggle 4 x 4 matrix of words. To be honest I have never before heard or played this game. If you are interested and would like to learn more about Boggle you can do it here.

The requirement for this exercise is to find the count of occurrences of the specified string “LEGAL” in the specified character array which is illustrated by the following:

If you start at location [0,1] we can find the word “LEGAL”. If we start at location [2,1] we can find the second instance of the same word. Note that locations [0,3] and [1,3] have two letters. The first instance is to locate the string twice. By using the red letters we should be able to find three instances of the word.

The test scaffolding follows:

	/*
	 * Test scaffolding
	 */
	public static void main(String[] args) {

		// **** matrix holding the boggle letters ****
		char boggle[][]	= 	{
							{ 'P', 'L', 'E', 'Y'},
							{ 'G', 'A', 'G', 'S'},
							{ 'E', 'L', 'I', 'O'},
							{ 'M', 'C', 'F', 'J'}
							};
		
		// **** string to search for ****
		String str	= "LEGAL";
		
		// **** count number of occurrences of the specified string ****
		int count = countInstances(boggle, str);
		System.out.println("main <<< count: " + count);
	}

We define the matrix with the letters to match the diagram, define the string and count the number of instances by calling the method countInstances().

	/*
	 * 
	 */
	static int countInstances(char[][] boggle, String str) {
		
		int count	= 0;
		
		int rows = boggle.length;
		int cols = boggle[0].length;
		
		// ???? ????
//		System.out.println("countInstances <<< rows: " + rows + " cols: " + cols);
		
		// **** search starting at the specified location ****
		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < cols; c++) {
				
				// ???? ????
//				System.out.println("countInstances <<< r: " + r + " c: " + c);
				
				// **** ****
				if (boggle[r] == str.charAt(0))
					count += search(boggle, str.substring(1,  str.length()), r, c);
			}
		}
		
		// **** ****
		return count;
	}

We first figure out the number of rows and columns in the matrix. We could have used the BOGGLE_LEN variable instead. This was done to verify that either approach would work.

We then traverse the matrix from left to right and from top to bottom. To reduce time we check the first character in the string to see if it matches the current character in the matrix. If so we proceed; otherwise we skip the character.

	/*
	 * Search for the string starting at the specified location.
	 */
	static int	search(char[][] boggle, String str, int row, int col) {
		
		int count = 0;
		
		// ???? ????
//		System.out.println("search <<< str ==>" + str + "<== row: " + row + " col: " + col);
		
		// **** end condition ****
		if (str.length() == 0) {
			return 1;
		}
		
		// **** check right ****
		if (row < BOGGLE_LEN) {
			count = search(boggle, str.substring(1, str.length()), row + 1, col);
		}
		
		// **** check down down ****
		if (col < BOGGLE_LEN) { count = search(boggle, str.substring(1, str.length()), row, col + 1); } // **** check left **** if (col > 0) {
			count = search(boggle, str.substring(1, str.length()), row, col - 1);
		}
		
		// **** check up ****
		if (row > 0) {
			count = search(boggle, str.substring(1, str.length()), row - 1, col);			
		}
		
		// **** ****
		return count;
	}

This recursive method checks if we are done and return a value of 1.

If we are not done and found the word, we attempt to go right, down, left and up. If the word is found the count will be set to 1.

Finally we return the count.

A console capture of the Eclipse IDE follows:

main <<< count: 2

Now, let’s change the matrix as illustrated by the following code:

	/*
	 * Test scaffolding
	 */
	public static void main(String[] args) {

		// **** matrix holding the boggle letters ****
		char boggle[][]	= 	{
							{ 'P', 'L', 'E', 'L'},
							{ 'G', 'A', 'G', 'E'},
							{ 'E', 'L', 'I', 'O'},
							{ 'M', 'C', 'F', 'J'}
							};
		
		// **** string to search for ****
		String str	= "LEGAL";
				
		// **** count number of occurrences of the specified string ****
		int count = countInstances(boggle, str);
		System.out.println("main <<< count: " + count);
	}

The console capture follows:

main <<< count: 3

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.

Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.