need help with c++ recursive function

[jianxu]

Hi, I am currently working on a homework assignment with the topic being a boggle game. We are creating the boggleboard class and one of the function that must be included is this:

bool playWord (string word, string player)
This method returns false if word does not appear in the dictionary, if it is not possible to form
word on the Boggle board, or if word has fewer than three letters. Otherwise it should return true.
The second parameter is the name of the player who is playing the word.

the problem I am currently having is this part: "if it is not possible to form
word on the Boggle board, or if word has fewer than three letters."

The professor suggested we use a recursive function that will backtrack to confirm the letters on the boggleboard is valid.
He also gave us an example:
Suppose you have a 4x4 array of characters called "board" that
represents the board. Imagine a method

bool matches (str, row, col, used)

that reports whether the string "str" matches the board configuration
beginning at the specified row and col when given an array "used" that
tells us which letters on the board have been used.

If str is empty, we return true.

Otherwise, if used[row][col] is true, we return return false.

Otherwise, if board[row][col] matches the first character of the
string, and (after making used[row][col] true), the recursive call

matches (rest of str, r, c, used)

returns true (where position r,c is adjacent to position row,col), we
return true

Otherwise, we set used[row][col] back to false and return false.

Despite this, I still don't understand how a string type and a letter on the board can relate to each other. For example, say our word is str, How do we tell the board side of things to analyze whether the letter is a "s" or not at that board space? I think for the part where it states "or if word has fewer than three letters." it is just a simple check on the used array to count up the letters we used to form the word.

I'm not looking for code, but rather comments on what thought processes I should perhaps take to reach a solution or perhaps I am missing a major concept? Thanks

[VernonDozier]

Hi, I am currently working on a homework assignment with the topic being a boggle game. We are creating the boggleboard class and one of the function that must be included is this:

bool playWord (string word, string player)
This method returns false if word does not appear in the dictionary, if it is not possible to form
word on the Boggle board, or if word has fewer than three letters. Otherwise it should return true.
The second parameter is the name of the player who is playing the word.

the problem I am currently having is this part: "if it is not possible to form
word on the Boggle board, or if word has fewer than three letters."

The professor suggested we use a recursive function that will backtrack to confirm the letters on the boggleboard is valid.
He also gave us an example:
Suppose you have a 4x4 array of characters called "board" that
represents the board. Imagine a method

bool matches (str, row, col, used)

that reports whether the string "str" matches the board configuration
beginning at the specified row and col when given an array "used" that
tells us which letters on the board have been used.

If str is empty, we return true.

Otherwise, if used[row][col] is true, we return return false.

Otherwise, if board[row][col] matches the first character of the
string, and (after making used[row][col] true), the recursive call

matches (rest of str, r, c, used)

returns true (where position r,c is adjacent to position row,col), we
return true

Otherwise, we set used[row][col] back to false and return false.

Despite this, I still don't understand how a string type and a letter on the board can relate to each other. For example, say our word is str, How do we tell the board side of things to analyze whether the letter is a "s" or not at that board space? I think for the part where it states "or if word has fewer than three letters." it is just a simple check on the used array to count up the letters we used to form the word.

I'm not looking for code, but rather comments on what thought processes I should perhaps take to reach a solution or perhaps I am missing a major concept? Thanks

This may be one of those problems where it'll probably take a few posts to nail things down.

Let's say the word is "car" and let's say the board is:

c a d g
h r k c
n b c s
k r w q

I think the "used" array starts as all false. Go through the array and find a 'c' at (0, 0). Flag used[0][0] equal to true. Then call the function again, only now the word to find is "ar", and you have to find your 'a' at a spot that is adjacent to (0,0), namely (0,1) or (1,0). Such an 'a' exists at (1,0), so mark used[1][0] as true, then call the function again, only this time the word to find is "r" and the coordinates are (1,0). Adjacent cells to (1,0) are (0,0), (0,2), and (1,1). (0,0) is flagged as "used", so that leaves (2,0) and (1,1). Are either of them 'r'? Yes. (1,1) is 'r', so the word has been found. Return true. When you hit a dead-end, "back-track" as your professor says. Work this out on paper before you try to code it, definitely. Try it for several examples. This is a semi-brute force method. For each failed attempt, one or more elements in the "used" array will likely have to be "reset" to false. When you have exhausted your possibilities with no solution, return false. When you've found a solution, return true.

Hope this helps.

[jianxu]

Hi Vernon,

Regarding what you said...I'm not sure I understand how the computer can take a string like car, and recognize that it needs to look for a c, then an a, then a r. Or...are you suggesting that we tell the computer to go through every single combination possible from a initial starting row,column on the board and then use a comparison statement to check if that possibility is the same until we get one of the two conclusions where 1) there are no such combination 2)there is a combination following the rule that the second letter have to be adjacent to the first, the third letter adjacent to the second, etc?

I think my main issue is trying to understand the jump from a string to individual characters because the computer doesn't realize that "car" string is made of individual letters and that the first letter starts from the left side....right? Or is there a way to tell the computer to look at the first letter of the string and use that to see if it matches with a letter on the board?

[VernonDozier]

Hi Vernon,

Regarding what you said...I'm not sure I understand how the computer can take a string like car, and recognize that it needs to look for a c, then an a, then a r. Or...are you suggesting that we tell the computer to go through every single combination possible from a initial starting row,column on the board and then use a comparison statement to check if that possibility is the same until we get one of the two conclusions where 1) there are no such combination 2)there is a combination following the rule that the second letter have to be adjacent to the first, the third letter adjacent to the second, etc?

I think my main issue is trying to understand the jump from a string to individual characters because the computer doesn't realize that "car" string is made of individual letters and that the first letter starts from the left side....right? Or is there a way to tell the computer to look at the first letter of the string and use that to see if it matches with a letter on the board?

Well, let's look at the string representing car. Let's say it's stored in a variable called aWord .

string aWord = "car";

aWord[0] is 'c'. aWord[1] is 'a'. aWord[2] is 'r'. aWord[3] can pose problems. Don't go past aWord[2] .

So if your question is how to isolate the characters, you would do it like above. To get the substring of everything but the the first letter of the word, use the substr function. To make sure you don't go "over the cliff" (i.e. past the end of the word), make use of the length function. Here's a program that may help you understand some string manipulation.

#include <iostream>
#include <string>
using namespace std;


int main ()
{
    string aWord = "cartoon";
    cout << aWord << " is made up of the following letters." << endl;
    for (int i = 0; i < aWord.length (); i++)
    {
        cout << "Letter " << i << " is " << aWord[i] << endl;
    }
    
    
    
    cout << "Entire word = " << aWord << endl;
    cout << "Here are increasingly smaller sub-words" << endl;
    string subWord = aWord.substr (1, aWord.length () - 1);

    while (subWord.length () > 0)
    {
          cout << subWord << endl;
          subWord = subWord.substr (1, subWord.length () - 1);
    }
    
    cout << "Press Enter to exit" << endl;
    cin.get ();   // pause so screen doesn't disappear
    return 0;
}

Is that what you are having difficulty with? How to isolate characters and sub-words? If not, please clarify.

http://www.cplusplus.com/reference/string/string/
http://www.cplusplus.com/reference/string/string/length.html
http://www.cplusplus.com/reference/string/string/substr.html

[jianxu]

Yes that made alot of sense. I never learned that I can apply that kind of syntax to isolate the characters in a string. So as you mentioned a couple posts above, I can take the first element of the string and test if it matches with the location on the board. I am curious if when we apply the test for adjacent letters, do we need to apply boundary conditions or will any rows/columns that lies outside the 4X4 array be automatically discarded? Because I can imagine all we have to say is if column/row is either less than zero or over 5, return false?

[Alex Edwards]

I'm not exactly sure how your professor wants this done, but...

Personally what I'd do is make a topic for each game of Boggle and implement a dictionary of words then map out specific words to a specific topic (using a map most likely).

A random topic is chosen (or generated) and the a double array of characters will be generated.

There will also be a class that maps paths for characters (for a given topic, there will be a class that iterates through the entire mapping of characters and checks for potential words on the board)).

All the user has to do is enter the row/column of the starting char and the string resembling the actual word possible.

I believe this topic may also be of some help-- Click! O_O

[jianxu]

Ah ok, as far as I know, for this assignment we only have to successfully code out a few functions and assume everything else will work out.

Thank you for explaining how that string to character part worked. I think I'll work on it tomorrow once I get some sleep =P
I'm sure I'll probably run into a few more problems so I'll post here again if I get stuck.

Thanks again!!! ^_^

[Alex Edwards]

I'm not exactly savvy with pulling information from a URL in C++ but I did make a program in Java that generates a dictionary and sorts it for you.

If you have a JDK and your paths set right to compile this, then it may help you get a little over a thousand real words for you to use as a small yet sufficient dictionary to use in your project.

import java.io.*;
import java.util.*;
import java.net.*;

/**
 * Goal - to retrieve information from URLs that are .txt files
 */
public class RetrieveInfo{

	public static void main(String... args){
		final String MY_DICTIONARY = "___MY_DICTIONARY.txt";
		RetrieveInfo ri = new RetrieveInfo();
		RetrieveInfo.Dictionary myD = ri.new Dictionary(MY_DICTIONARY, true);
		String urls[] = {
			"http://dictionary-thesaurus.com/wordlists/ActionWords(114).txt",
			"http://dictionary-thesaurus.com/wordlists/Adjectives(50).txt",
			"http://dictionary-thesaurus.com/wordlists/Consanants(120).txt",
			"http://dictionary-thesaurus.com/wordlists/DescriptiveWords(86).txt",
			"http://dictionary-thesaurus.com/wordlists/GRE_WordList(1264).txt"
		};

		RetrieveInfo.setDictionary(myD, urls);
		myD.printList();
		RetrieveInfo.sortDictionary(myD);
		System.out.println("Task Completed...?");
	}

	public class Dictionary{
		String fileName = "";
		boolean append = false;
		private ArrayList<String> wordList = new ArrayList<String>(0);

		public Dictionary(String fileName, boolean append){
			this.fileName = fileName;
			this.append = append;
		}

		public boolean appending(){
			return append;
		}

		public void store(String value){
			wordList.add(value);
		}

		public String[] getItems(){
			String arg[] = new String[wordList.size()];
			return wordList.toArray(arg);
		}

		public void setList(String... values){
			wordList.clear();

			for(String element : values){
				wordList.add(element);
			}
		}

		public void printList(){
			for(String element : wordList){
				System.out.println(element);
			}
		}

		@Override public String toString(){
			return fileName;
		}
	}

	public static void setDictionary(Dictionary d, String... urls){

		try{
			boolean existingFile = new File(d.toString()).exists();

			if(existingFile){
				System.out.println("File already exists! Enter yes to continue or anything else to exit the program.");
				String choice = new Scanner(System.in).nextLine();

				if(!choice.equalsIgnoreCase("YES"))
					System.exit(1);
			}

			InputStream is = null;
			InputStreamReader isr = null;
			BufferedReader br = null;
			FileOutputStream fos = null;
			PrintWriter pw = null;

			for(String element : urls){
				is = new URL(element).openStream();
				isr = new InputStreamReader(is);
				br = new BufferedReader(isr);
				fos = new FileOutputStream(d.toString(), d.appending());
				pw = new PrintWriter(fos);

				while(br.ready()){
					String word = br.readLine();
					d.store(word);
					pw.println(word);
					pw.flush();
				}
			}

			br.close();
			pw.close();
		}catch(Exception e){e.printStackTrace();}
	}

	public static void sortDictionary(Dictionary d){

		String meh[] = d.getItems();
		Arrays.sort(meh);
		d.setList(meh);

		FileOutputStream fos = null;
		PrintWriter pw = null;

		try{
			fos = new FileOutputStream(d.toString(), false); // Danger! will delete target file to sort it!
			pw = new PrintWriter(fos);

			for(String element : d.getItems()){
				pw.println(element);
				pw.flush();
			}

			pw.close();

		}catch(Exception e){
			e.printStackTrace();
		}
	}
}

--it's an incomplete project I worked on for the last 2 hours.

I'm sure this is doable in C++, I just felt more comfortable doing it in Java @_@.

To make things easier you could simply save the .txt files to a directory, store lines of characters in a vector and sort the vector and then send the sorted information in the same file.

[VernonDozier]

Yes that made alot of sense. I never learned that I can apply that kind of syntax to isolate the characters in a string. So as you mentioned a couple posts above, I can take the first element of the string and test if it matches with the location on the board. I am curious if when we apply the test for adjacent letters, do we need to apply boundary conditions or will any rows/columns that lies outside the 4X4 array be automatically discarded? Because I can imagine all we have to say is if column/row is either less than zero or over 5, return false?

There is more than one way to code this, so I can't visualize where you're headed on this. But in general, be careful not to return false too early, before you have exhausted all of your possibilities. And bounds-checking is almost certainly going to be required at several places. In particular, if you have a 4 x 4 grid and you are at (0,3) and you're looking for adjacent elements of the matrix, you certainly don't want to say "(0, 4) is out of bounds, so I'm going to return false." Because (0, 2) and (1,3) are not out of bounds and still must be checked. However, like I said, I can't really visualize where you're going, but that doesn't mean that there's anything wrong with your solution. I'd have to see some code/details.

Also, my Boggle is rusty. Are diagonals considered "adjacent"? Last night I was thinking they weren't.

[jianxu]

I think in my assignment, we can assume that diagonal ones are considered are valid choices as well. I will definitely post some code once I work to the point of getting stuck.

[jianxu]

So I have finished the assignment....I think....I have a feeling there's quite a bit of error lol

\

bool BoggleBoard::formable(string word, int row, int col, bool[][4] used)
{
	if(word.length() == 0)
	{
		return true;
	}
	else if(used[row][col] == true)
	{
		return false;
	}
	else if(word[1] == board[row][col])
	{
		used[row][col] = true;

		word = word.substr(1 , word.length()-1)

		if(formable(word,row - 1, col -1 , used) == true)
		{
			return true;
		}
		else if(formable(word,row , col -1 , used) == true)
		{
			return true;
		}
		else if(formable(word,row + 1, col -1 , used) == true)
		{
			return true;
		}
		else if(formable(word,row - 1, col  , used) == true)
		{
			return true;
		}
		else if(formable(word,row - 1, col +1 , used) == true)
		{
			return true;
		}
		else if(formable(word,row , col +1 , used) == true)
		{
			return true;
		}
		else if(formable(word,row + 1, col +1 , used) == true)
		{
			return true;
		}
		else if(formable(word,row + 1, col  , used) == true)
		{
			return true;
		}
		else
		{
			used[row][col] = false;
			return false;
		}
	}


}

this is of course, for the recursive portion of the code. The only problem I have is that most letter on the board cannot analyze all the different row/column combinations because they are on the edge of the board. Let me know what you guys think ^^ thanks for helping.

On a side note, homework 1

this is the link to our homework handout sheet. Perhaps this will help you better understand the requirements for this problem?

If it's no trouble, it would be much appreciated if someone can look over my overall code?
It would be nice to see what other people think/ what I can improve on, etc.
I have included them as attachments(They're not very large, and shouldn't be too complicated) Thanks again!

[Alex Edwards]

I glanced through your files ad noticed quite a few errors...

You initialize your "cube" char arrays in class-global scope (which, from what I understand is illegal in standard C++). You'll have to create temporary arrays in your constructor and copy their contents into your global arrays, or use a copy function in the STL if one's available, or better yet use a vector to prevent the headache of option a or b.

You need to separate your direction symbols when forming nested templates. >> will be parsed as the shift-bits right operation and not as the enclosing direction symbol for a nested template, so space it out!

Furthermore, your cube char arrays do not have characters stored in them. You need to wrap your char symbols inside ' ' so they will be read as characters.

The list goes on, but this should give you a reasonable start to get your program functional.

[VernonDozier]

I think I need to see your initial call to this function for it to make sense to me. I was thinking something a bit different, but like I said, there's more than one way to do it. I think you need a few lines of comments in there explaining exactly what the function does and what it requires. At the minimum, you have a problem with boundary checking. If your indexes are less than 0 or greater than three, you are in trouble. You need to check before trying to access those indexes. I'm not sure how much code you didn't post, but if it's not much more, post the whole project, especially the main function. But in particular, I think you need to provide the original call to this function, with the initial arguments, the board[][] array, and the initial used[][] array, which I'm assuming is all false. Basically I'm wondering if there is some helper function somewhere that does work, which then calls this function multiple times, or if this function is called only once non-recursively.