| | |
need help with c++ recursive function
![]() |
•
•
Join Date: Aug 2008
Posts: 6
Reputation:
Solved Threads: 0
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
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
Last edited by jianxu; Aug 31st, 2008 at 12:38 am.
•
•
Join Date: Jan 2008
Posts: 3,955
Reputation:
Solved Threads: 515
•
•
•
•
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
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.
•
•
Join Date: Aug 2008
Posts: 6
Reputation:
Solved Threads: 0
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?
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?
Last edited by jianxu; Aug 31st, 2008 at 2:17 am.
•
•
Join Date: Jan 2008
Posts: 3,955
Reputation:
Solved Threads: 515
•
•
•
•
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 . C++ Syntax (Toggle Plain Text)
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. C++ Syntax (Toggle Plain Text)
#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/s...ng/length.html
http://www.cplusplus.com/reference/s...ng/substr.html
Last edited by VernonDozier; Aug 31st, 2008 at 2:52 am.
•
•
Join Date: Aug 2008
Posts: 6
Reputation:
Solved Threads: 0
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?
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
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
•
•
Join Date: Aug 2008
Posts: 6
Reputation:
Solved Threads: 0
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!!! ^_^
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!!! ^_^
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.
--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.
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.
java Syntax (Toggle Plain Text)
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.
•
•
Join Date: Jan 2008
Posts: 3,955
Reputation:
Solved Threads: 515
•
•
•
•
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?
Also, my Boggle is rusty. Are diagonals considered "adjacent"? Last night I was thinking they weren't.
![]() |
Similar Threads
- Recursive function - checking for palindromes (C)
- Order of a recursive function (C)
- Argorithm: palindromes, write recursive function. (Computer Science)
- recursive function (C)
- recursive function (C++)
Other Threads in the C++ Forum
- Previous Thread: Packet Filter
- Next Thread: File management
Views: 2006 | Replies: 12
| Thread Tools | Search this Thread |
Tag cloud for C++
algorithm api array arrays assignment beginner binary c++ c++borland c/c++ calculator char class classes code compile compiler constructor conversion convert count delete dll dynamic encryption error file files filestream forms fstream function functions game givemetehcodez graph graphics gui helpwithhomework homework http iamthwee input int lazy linker list loop loops map math matrix member memory multidimensional network newbie number object objects opengl output parameter pointer pointers problem program programming project qt random read reading recursion recursive reference server sort sorting spoonfeeding string strings struct student studio template templates text time tree variable vc++ vector video visual visualstudio win32 window windows winsock






