Databases
StackOverflow2013
Postsdbo
POBoggle - Implementing Recursion
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBoggle - Implementing Recursion
    primarykey
    data
    text
    <p>So, I'm trying to figure out how to implement the recursive calls for a simulation of Boggle. There are two players: human and computer. When the human goes, s/he finds a words on the board (which was randomly shuffled), and the recursive call is supposed to check the validity. Basically, I have to loop through adjacent letters starting from index 0 of the word input, and crawl that way, checking each time to make sure the word exists or not. The problem is I don't exactly know how to do this. Here's my code thus far, and I've provided some pseudocode to further explain my intentions. Can anyone help?</p> <pre><code>#include &lt;iostream&gt; #include &lt;cctype&gt; #include &lt;cmath&gt; #include "strlib.h" #include "gboggle.h" #include "graphics.h" #include "grid.h" #include "lexicon.h" #include "random.h" #include "simpio.h" #include "Board.h" using namespace std; /* Constants */ const int MIN_WORD_COUNT = 4; const int boardSize = 16; const int BOGGLE_WINDOW_WIDTH = 650; const int BOGGLE_WINDOW_HEIGHT = 350; const string STANDARD_CUBES[16] = { "AAEEGN", "ABBJOO", "ACHOPS", "AFFKPS", "AOOTTW", "CIMOTU", "DEILRX", "DELRVY", "DISTTY", "EEGHNW", "EEINSU", "EHRTVW", "EIOSST", "ELRTTY", "HIMNQU", "HLNNRZ" }; const string BIG_BOGGLE_CUBES[25] = { "AAAFRS", "AAEEEE", "AAFIRS", "ADENNN", "AEEEEM", "AEEGMU", "AEGMNN", "AFIRSY", "BJKQXZ", "CCNSTW", "CEIILT", "CEILPT", "CEIPST", "DDLNOR", "DDHNOT", "DHHLOR", "DHLNOR", "EIIITT", "EMOTTT", "ENSSSU", "FIPRSY", "GORRVW", "HIPRRY", "NOOTUW", "OOOTTU" }; /* Function prototypes */ void welcome(); void giveInstructions(); void checkBoard( Vector&lt;string&gt; ); void shakeCubes( int, int, Vector&lt;string&gt; &amp;, Grid&lt;char&gt; &amp; ); void checkBoardLetters( Grid&lt;char&gt; ); void checkHumanWords( Set&lt;string&gt; ); void findHumanWordsOnBoard( Set&lt;string&gt; &amp;, Grid&lt;char&gt; ); bool boardContainsHumanWord( Grid&lt;char&gt;, string ); void toupper(string&amp; word); bool askQuestion(string question); void customConfiguration(int boardSize); void shuffleBoard(int boardSize, const string cubes[]); void humanTurn(Grid&lt;char&gt;&amp; cubeLetters, Set&lt;string&gt; &amp;alreadyUsedWords, Lexicon &amp;dictionary); /* Main program */ int main() { initGraphics(BOGGLE_WINDOW_WIDTH, BOGGLE_WINDOW_HEIGHT); welcome(); giveInstructions(); int rows = 4; int cols = 4; int boardSize = rows*cols; Vector&lt;string&gt; vec; Set&lt;string&gt; humanWords; Grid&lt;char&gt; cubeLetters( rows, cols ); Lexicon dictionary("EnglishWords.dat"); // Task 1: Copy constant array into a vector vec for( int i = 0; i &lt; rows * cols; i++ ) { vec.add( STANDARD_CUBES[ i ] ); } string instructions = "Do you need instructions?"; if (askQuestion(instructions)) giveInstructions(); string customConfig = "Do you want a custom configuration?"; drawBoard( rows, cols ); if (askQuestion(customConfig)){ customConfiguration(boardSize); } else { shakeCubes( rows, cols, vec, cubeLetters ); } // Task 2 humanTurn( cubeLetters, humanWords, dictionary ); // debug //checkHumanWords( humanWords ); // Task 3 findHumanWordsOnBoard( humanWords, cubeLetters ); // debug //checkHumanWords( humanWords ); //else { // shuffleBoard(boardSize,STANDARD_CUBES); //} return 0; } /* * Function: shakeCubes * Usage: shakeCubes( int, int, Vector&lt;string&gt; &amp; ); * ----------------- * Randomize cubes and their sides. */ void shakeCubes( int rows, int cols, Vector&lt;string&gt; &amp;vec, Grid&lt;char&gt; &amp;cubeLetters ) { // Shuffle cubes srand ( time(NULL) ); random_shuffle( vec.begin(), vec.end() ); char c; int i = 0, j = 0; // Shuffle cube sides foreach( string s in vec ) { c = s[ rand() % 6 ]; labelCube( i, j, c ); cubeLetters[ i ][ j ] = c; if( j == 3 ) { i++; j = 0; } else j++; } } void humanTurn(Grid&lt;char&gt;&amp; cubeLetters, Set&lt;string&gt; &amp;alreadyUsedWords, Lexicon &amp;dictionary) { cout &lt;&lt; endl &lt;&lt; "Find all the words you can." &lt;&lt; endl &lt;&lt; "Signal that you're finished by entering an empty line." &lt;&lt; endl &lt;&lt; endl; do { cout &lt;&lt; "Enter a word: "; string word = getLine(); if(word.empty()) break; // the only way out of the do-while loop toupper(word); if(word.length() &lt; MIN_WORD_COUNT) // word &lt; min word length { cout &lt;&lt; "I'm sorry, but we have our standards." &lt;&lt; endl &lt;&lt; "That word doesn't meet the minimum word length." &lt;&lt; endl; } else if(alreadyUsedWords.contains(word)) // word has already been entered { cout &lt;&lt; "You've already found that word!" &lt;&lt; endl; } else if( dictionary.contains( word ) ) // word not in lexicon { alreadyUsedWords.add(word); recordWordForPlayer( word, HUMAN ); } else { cout &lt;&lt; "You can't make that word!" &lt;&lt; endl; } } while(true); } /* * Function: checkBoard * Usage: checkBoard( Vector&lt;string&gt; ); * ----------------- * Print out current state of Boggle board. */ void checkBoard( Vector&lt;string&gt; vec ) { cout &lt;&lt; endl; foreach(string s in vec) { cout &lt;&lt; s &lt;&lt; endl; } } void checkBoardLetters( Grid&lt;char&gt; cubeLetters ) { cout &lt;&lt; endl; for( int i = 0; i &lt; 4; i ++ ) { for( int j = 0; j &lt; 4; j++ ) { cout &lt;&lt; cubeLetters[i][j] &lt;&lt; endl; } } } void checkHumanWords( Set&lt;string&gt; humanWords ) { cout &lt;&lt; endl; foreach( string s in humanWords ) { cout &lt;&lt; s &lt;&lt; endl; } if( humanWords.isEmpty() ) cout &lt;&lt; "human word set is empty" &lt;&lt; endl; } // Does board contain word? RECURSIVE bool boardContainsWord( Grid&lt;char&gt; cubeLetters, string word ) { foreach( char c in cubeLetters ) for( int i = 0; i &lt; cubeLetters.numRows(); i++ ) { for( int j = 0; j &lt; cubeLetters.numCols(); j++ ) { if( cubeLetters[i][j] == word[0] ) { if( word.length() == 1 ) return true; else return boardContainsWord( cubeLetters, word.substr(1) ); } } } return false; } /* bool boardContainsLetter( Grid&lt;char&gt; cubeLetters, char letter ) { return false; } // Task 3: Reduce set of HumanWords to those that exist on board void findHumanWordsOnBoard( Set&lt;string&gt; &amp;humanWords, Grid&lt;char&gt; cubeLetters ) { foreach( string word in humanWords ) { if( !boardContainsWord( cubeLetters, word ) ) humanWords.remove( word ); } } */ /* *** Brainstorming and Under Construction *** I need to save (x,y) coordinates and store in a Set collection class to describe path. I need a recursive, boolean function that takes in string word, Grid board, and Set path to check valid words. This recursion will check each adjacent letter (and can start from top left [row-1][col-1], and move around the chosen letter); It also has to check whether it's inBounds before proceeding. /* * Function: welcome * Usage: welcome(); * ----------------- * Print out a cheery welcome message. */ void welcome() { cout &lt;&lt; "Welcome! You're about to play an intense game "; cout &lt;&lt; "of mind-numbing Boggle. The good news is that "; cout &lt;&lt; "you might improve your vocabulary a bit. The "; cout &lt;&lt; "bad news is that you're probably going to lose "; cout &lt;&lt; "miserably to this little dictionary-toting hunk "; cout &lt;&lt; "of silicon. If only YOU had a gig of RAM..." &lt;&lt; endl &lt;&lt; endl; } /* * Function: giveInstructions * Usage: giveInstructions(); * -------------------------- * Print out the instructions for the user. */ void giveInstructions() { cout &lt;&lt; endl; cout &lt;&lt; endl &lt;&lt; "The boggle board is a grid onto which I will randomly distribute" &lt;&lt; endl &lt;&lt; "dice. These 6-sided dice have letters rather than numbers on the faces, " &lt;&lt; endl &lt;&lt; "creating a grid of letters on which you try to form words. You go first, " &lt;&lt; endl &lt;&lt; "entering the words you find that are formed by tracing adjoining " &lt;&lt; endl &lt;&lt; "letters. Two letters adjoin if they are next to each other horizontally, " &lt;&lt; endl &lt;&lt; "vertically, or diagonally. A letter can only be used once in the word. Words" &lt;&lt; endl &lt;&lt; "must be at least 4 letters long and can only be counted once. You score points" &lt;&lt; endl &lt;&lt; "based on word length, a 4-letter word is worth one, 5-letters two, etc. After your " &lt;&lt; endl &lt;&lt; "tiny brain is exhausted, I, the brilliant computer, will find all the remaining " &lt;&lt; endl &lt;&lt; "words in the puzzle and double or triple your paltry score." &lt;&lt; endl &lt;&lt; endl; cout &lt;&lt; "Hit return when you're ready..."; getLine(); } //Function call to capitalize every letter in a string void toupper(string&amp; word) { for(int i = 0; i &lt; word.size(); i++) { word[i] = toupper(word[i]); } } // A do-while loop to keep asking for a YES/NO answer to a given question bool askQuestion(string question) { do { cout &lt;&lt; question &lt;&lt; " "; string answer = getLine(); if(toupper(answer[0]) == 'N') return false; else if(toupper(answer[0]) == 'Y') return true; } while (cout &lt;&lt; "Please answer yes or no." &lt;&lt; endl); return 1; } // Requests user for a board configuration input for the given size board // and labels the cubes with the corresponding input string void customConfiguration(int boardSize) { cout &lt;&lt; endl &lt;&lt; "Enter a " &lt;&lt; boardSize &lt;&lt; "-character string to identify which letters you want on the cubes." &lt;&lt; endl &lt;&lt; "The first " &lt;&lt; sqrt(double(boardSize)) &lt;&lt; " letters are the cubes on the top row from left to right " &lt;&lt; endl &lt;&lt; "next " &lt;&lt; sqrt(double(boardSize)) &lt;&lt; " letters are the second row, etc." &lt;&lt; endl &lt;&lt; "Enter the string: "; string answer; do { answer = getLine(); if(answer.size() &gt;= double(boardSize)) break; } while (cout &lt;&lt; "String must include " &lt;&lt; boardSize &lt;&lt; " characters! Try again: "); toupper(answer); int strIndex = 0; for (int row = 0; row &lt; sqrt(double(boardSize)); row++){ for (int col = 0; col &lt; sqrt(double(boardSize)); col++){ char answerSubStr = answer[strIndex]; labelCube(row, col, answerSubStr); strIndex++; } } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USGuy Coder
    1. USCon Antonakos
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POBoggle - Implementing Recursion
      1. USCon Antonakos
      1. VTFavorite
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload