need help with c++ recursive function

Reply

Join Date: Aug 2008
Posts: 6
Reputation: jianxu is an unknown quantity at this point 
Solved Threads: 0
jianxu jianxu is offline Offline
Newbie Poster

need help with c++ recursive function

 
0
  #1
Aug 31st, 2008
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
Last edited by jianxu; Aug 31st, 2008 at 12:38 am.
Reply With Quote Quick reply to this message  
Join Date: Jan 2008
Posts: 3,955
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 515
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster

Re: need help with c++ recursive function

 
0
  #2
Aug 31st, 2008
Originally Posted by jianxu View Post
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.
Reply With Quote Quick reply to this message  
Join Date: Aug 2008
Posts: 6
Reputation: jianxu is an unknown quantity at this point 
Solved Threads: 0
jianxu jianxu is offline Offline
Newbie Poster

Re: need help with c++ recursive function

 
0
  #3
Aug 31st, 2008
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?
Last edited by jianxu; Aug 31st, 2008 at 2:17 am.
Reply With Quote Quick reply to this message  
Join Date: Jan 2008
Posts: 3,955
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 515
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster

Re: need help with c++ recursive function

 
1
  #4
Aug 31st, 2008
Originally Posted by jianxu View Post
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 .
  1. 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.

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5.  
  6. int main ()
  7. {
  8. string aWord = "cartoon";
  9. cout << aWord << " is made up of the following letters." << endl;
  10. for (int i = 0; i < aWord.length (); i++)
  11. {
  12. cout << "Letter " << i << " is " << aWord[i] << endl;
  13. }
  14.  
  15.  
  16.  
  17. cout << "Entire word = " << aWord << endl;
  18. cout << "Here are increasingly smaller sub-words" << endl;
  19. string subWord = aWord.substr (1, aWord.length () - 1);
  20.  
  21. while (subWord.length () > 0)
  22. {
  23. cout << subWord << endl;
  24. subWord = subWord.substr (1, subWord.length () - 1);
  25. }
  26.  
  27. cout << "Press Enter to exit" << endl;
  28. cin.get (); // pause so screen doesn't disappear
  29. return 0;
  30. }

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.
Reply With Quote Quick reply to this message  
Join Date: Aug 2008
Posts: 6
Reputation: jianxu is an unknown quantity at this point 
Solved Threads: 0
jianxu jianxu is offline Offline
Newbie Poster

Re: need help with c++ recursive function

 
0
  #5
Aug 31st, 2008
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?
Reply With Quote Quick reply to this message  
Join Date: Jun 2008
Posts: 973
Reputation: Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough 
Solved Threads: 108
Alex Edwards's Avatar
Alex Edwards Alex Edwards is offline Offline
Posting Shark

Re: need help with c++ recursive function

 
1
  #6
Aug 31st, 2008
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
Reply With Quote Quick reply to this message  
Join Date: Aug 2008
Posts: 6
Reputation: jianxu is an unknown quantity at this point 
Solved Threads: 0
jianxu jianxu is offline Offline
Newbie Poster

Re: need help with c++ recursive function

 
0
  #7
Aug 31st, 2008
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!!! ^_^
Reply With Quote Quick reply to this message  
Join Date: Jun 2008
Posts: 973
Reputation: Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough 
Solved Threads: 108
Alex Edwards's Avatar
Alex Edwards Alex Edwards is offline Offline
Posting Shark

Re: need help with c++ recursive function

 
0
  #8
Aug 31st, 2008
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.

  1.  
  2. import java.io.*;
  3. import java.util.*;
  4. import java.net.*;
  5.  
  6. /**
  7.  * Goal - to retrieve information from URLs that are .txt files
  8.  */
  9. public class RetrieveInfo{
  10.  
  11. public static void main(String... args){
  12. final String MY_DICTIONARY = "___MY_DICTIONARY.txt";
  13. RetrieveInfo ri = new RetrieveInfo();
  14. RetrieveInfo.Dictionary myD = ri.new Dictionary(MY_DICTIONARY, true);
  15. String urls[] = {
  16. "http://dictionary-thesaurus.com/wordlists/ActionWords(114).txt",
  17. "http://dictionary-thesaurus.com/wordlists/Adjectives(50).txt",
  18. "http://dictionary-thesaurus.com/wordlists/Consanants(120).txt",
  19. "http://dictionary-thesaurus.com/wordlists/DescriptiveWords(86).txt",
  20. "http://dictionary-thesaurus.com/wordlists/GRE_WordList(1264).txt"
  21. };
  22.  
  23. RetrieveInfo.setDictionary(myD, urls);
  24. myD.printList();
  25. RetrieveInfo.sortDictionary(myD);
  26. System.out.println("Task Completed...?");
  27. }
  28.  
  29. public class Dictionary{
  30. String fileName = "";
  31. boolean append = false;
  32. private ArrayList<String> wordList = new ArrayList<String>(0);
  33.  
  34. public Dictionary(String fileName, boolean append){
  35. this.fileName = fileName;
  36. this.append = append;
  37. }
  38.  
  39. public boolean appending(){
  40. return append;
  41. }
  42.  
  43. public void store(String value){
  44. wordList.add(value);
  45. }
  46.  
  47. public String[] getItems(){
  48. String arg[] = new String[wordList.size()];
  49. return wordList.toArray(arg);
  50. }
  51.  
  52. public void setList(String... values){
  53. wordList.clear();
  54.  
  55. for(String element : values){
  56. wordList.add(element);
  57. }
  58. }
  59.  
  60. public void printList(){
  61. for(String element : wordList){
  62. System.out.println(element);
  63. }
  64. }
  65.  
  66. @Override public String toString(){
  67. return fileName;
  68. }
  69. }
  70.  
  71. public static void setDictionary(Dictionary d, String... urls){
  72.  
  73. try{
  74. boolean existingFile = new File(d.toString()).exists();
  75.  
  76. if(existingFile){
  77. System.out.println("File already exists! Enter yes to continue or anything else to exit the program.");
  78. String choice = new Scanner(System.in).nextLine();
  79.  
  80. if(!choice.equalsIgnoreCase("YES"))
  81. System.exit(1);
  82. }
  83.  
  84. InputStream is = null;
  85. InputStreamReader isr = null;
  86. BufferedReader br = null;
  87. FileOutputStream fos = null;
  88. PrintWriter pw = null;
  89.  
  90. for(String element : urls){
  91. is = new URL(element).openStream();
  92. isr = new InputStreamReader(is);
  93. br = new BufferedReader(isr);
  94. fos = new FileOutputStream(d.toString(), d.appending());
  95. pw = new PrintWriter(fos);
  96.  
  97. while(br.ready()){
  98. String word = br.readLine();
  99. d.store(word);
  100. pw.println(word);
  101. pw.flush();
  102. }
  103. }
  104.  
  105. br.close();
  106. pw.close();
  107. }catch(Exception e){e.printStackTrace();}
  108. }
  109.  
  110. public static void sortDictionary(Dictionary d){
  111.  
  112. String meh[] = d.getItems();
  113. Arrays.sort(meh);
  114. d.setList(meh);
  115.  
  116. FileOutputStream fos = null;
  117. PrintWriter pw = null;
  118.  
  119. try{
  120. fos = new FileOutputStream(d.toString(), false); // Danger! will delete target file to sort it!
  121. pw = new PrintWriter(fos);
  122.  
  123. for(String element : d.getItems()){
  124. pw.println(element);
  125. pw.flush();
  126. }
  127.  
  128. pw.close();
  129.  
  130. }catch(Exception e){
  131. e.printStackTrace();
  132. }
  133. }
  134. }

--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.
Reply With Quote Quick reply to this message  
Join Date: Jan 2008
Posts: 3,955
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 515
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster

Re: need help with c++ recursive function

 
0
  #9
Aug 31st, 2008
Originally Posted by jianxu View Post
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.
Reply With Quote Quick reply to this message  
Join Date: Aug 2008
Posts: 6
Reputation: jianxu is an unknown quantity at this point 
Solved Threads: 0
jianxu jianxu is offline Offline
Newbie Poster

Re: need help with c++ recursive function

 
0
  #10
Aug 31st, 2008
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.
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:




Views: 2006 | Replies: 12
Thread Tools Search this Thread



Tag cloud for C++
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2010 DaniWeb® LLC