Graal Forums Programming Exercise #5: Solving Boggle?!
 User Name Remember Me? Password
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

 Thread Tools Search this Thread Display Modes
#1
06-19-2008, 02:08 AM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Programming Exercise #5: Solving Boggle?!

 For those of you who know not what Boggle is: http://en.wikipedia.org/wiki/Boggle So today boys and... boys, our task is to make a word finder in Boggle. Given a word list, find all the words from that list you can make on an x by x Boggle board (the game itsself is a 4x4 board, but we can do better ) Expert Level: Do the above task with recursion Addeum: We can use the TWL06 as our word list. http://www.cs.bu.edu/fac/byers/cours...ndouts/TWL.txt
 __________________

Last edited by Kristi; 06-19-2008 at 03:09 PM..
#2
06-19-2008, 12:14 PM
 Chompy ¯\(º_o)/¯ Join Date: Sep 2006 Location: Norway Posts: 2,815
 So, the algorithm to find all words in a Boggle board in the most efficient way? And, just pick random letters and find words by them? Are there any rules (Hard letters like K (2 or more), U, X, Z etc.) of letters that can be used to produce the board?
 __________________
#3
06-19-2008, 01:15 PM
 zokemon That one guy... Join Date: Mar 2001 Location: Sonoma County, California Posts: 2,925
 Arguments please.
 __________________ Do it with a DON!
#4
06-19-2008, 03:10 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by zokemon Arguments please.
If someone wants to go grab a boggle board and put up a random example, feel free to do so.

As for the rules, that is the reason I linked the wiki...
 __________________
#5
06-20-2008, 12:55 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
 try:
 __________________ ◕‿‿◕ · pfa · check yer syntax! · src Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
#6
06-20-2008, 10:19 AM
 zokemon That one guy... Join Date: Mar 2001 Location: Sonoma County, California Posts: 2,925
 I'm asking what should be passed to the function .
 __________________ Do it with a DON!
#7
06-20-2008, 03:53 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by zokemon I'm asking what should be passed to the function .
I left that up to you guys since the answer was obvious i thought.

You pass the board its self. That is the only thing you would ever need. If you want to give it pointers to different word lists too that is your choice.
 __________________
#8
06-20-2008, 06:08 PM
 Dan Daniel Join Date: Oct 2007 Posts: 383
 Do 2 letters have to link to form a word or can you pick any letter from any position to form a word?
 __________________ Email: [email protected]
#9
06-20-2008, 06:12 PM
 zokemon That one guy... Join Date: Mar 2001 Location: Sonoma County, California Posts: 2,925
 Ahh, didn't see that you added a wordlist above.
 __________________ Do it with a DON!
#10
06-20-2008, 06:15 PM
 Rufus Registered User Join Date: Jun 2004 Location: United Kingdom Posts: 4,698
 Sudoku is better than Boggle!
__________________
Quote:
 Originally Posted by Loriel Seriously, you have ****-all for content and you're not exactly pulling in new developer talent, angling for prestigious titles should be your last concern.
#11
06-20-2008, 06:36 PM
 Crow ǝɔɐɹq ʎןɹnɔ Join Date: Dec 2006 Location: Germany Posts: 5,153
Quote:
 Originally Posted by Rufus Sudoku
Crosswords for dyslexic people.
 __________________
#12
06-20-2008, 07:30 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by Dan Do 2 letters have to link to form a word or can you pick any letter from any position to form a word?
have to link, and you can't reuse letters.
 __________________
#13
08-02-2008, 11:39 AM
 _Z3phyr_ Banned Join Date: Sep 2003 Location: Louisiane Posts: 390
Quote:
 Originally Posted by Kristi Given a word list, find all the words from that list you can make on an x by x Boggle board (the game itsself is a 4x4 board, but we can do better ) Addeum: We can use the TWL06 as our word list. http://www.cs.bu.edu/fac/byers/cours...ndouts/TWL.txt Expert Level: Do the above task with recursion
you can find all of the words on an x by x boggle board, as long as you can find all of the words on an x by x boggle board.

edit- answer:

Let M be an n x n matrix. (meaning, let M be an n-1 x n-1 array)
Let W be the set of accepted words.

if a set of entries of M, called X, where each entry of M in X is adjacent to the one both preceding and following, is an element of W, then there is a word in the matrix.

Problem: define the set of all possible values for X
(note: the maximum length of X is n*n)

how to do this:

loop through all entries of M sub 'i,j', (we don't need to check if it is apart of the alphabet because this is a boggle board) then check for each entry that:
• M sub 'i+1,j' is an element of W.substring(0,1)
• M sub 'i-1,j' is an element of W.substring(0,1)
• M sub 'i,j+1' is an element of W.substring(0,1)
• M sub 'i,j-1' is an element of W.substring(0,1)
• M sub 'i+1,j+1' is an element of W.substring(0,1)
• M sub 'i-1,j-1' is an element of W.substring(0,1)
• M sub 'i+1,j-1' is an element of W.substring(0,1)
• M sub 'i-1,j+1' is an element of W.substring(0,1)

if any of those are true (and if not then move onto the next entry in the matrix), repeat the process with the new entry and see if it is an element of W.substring(1,2). if that is true, do it again with W.substring(2,3), then (3,4), and so on.

how all of that looks in code talk
PHP Code:
``` M = 2-dimensional string array of length n-1 by n-1 containing only letters of the alphabet because arrays start at index 0 and not 1;W = string array containing all of the acceptable words, one word per entry;for (i=0;i<n-1;i++) { //row # of the matrix  for (j=0;j<n-1;j++) { //column # of the matrix    check(i,j,0);  }}check(r, s, p) {  t = p;  for (k=0;k<8 && t==p;k++) { //8 because there are 8 directions to check    if (k==0 && r-1>=0) { //look above the entry, if its not at the top      for (l=0;l<W.length();l++) { //for each word in W        if (M[r][s] in W[l].substring(p,p+1)) {           //p is used to check the pth letter of the lth string in W.          p++; //<--move onto the next letter and...          check(r-1, s, p); //start over        }      }    } else if (k==1 && r+1<=n-1) {//look below, if its not at the bottom      ...    } else if (k==2 && s-1>=0) {//look left, if its not at the left edge      ...    }    //dot dot dot  }}  ```
since i'm being asked to show what words can be found:

add the string W[l] to a separate array every time
M[r][s] in W[l].substring(p,p+1) && p == W[l].size(), and then break; so that the search can continue.

Last edited by _Z3phyr_; 08-02-2008 at 05:17 PM..
#14
08-08-2008, 08:02 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by _Z3phyr_ stuffs
I just quickly glanced this over because I am at work but two things...

I don't see a return value.

I don't see handling of already used letters (you can't use the same letter/piece twice in boggle)
 __________________

 Tags boggle, programming-exercise

 Thread Tools Search this Thread Search this Thread: Advanced Search Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General Forums     Graal Main Forum (English)         Hello and Goodbyes         Birthday Forum         Guild Life         Job Forum             Global Scripting Team             Playerworld Administration Team             Forum moderation Team             Graal Kingdoms Team             Graal Zone Team             Wiki Administration Team         Server Maintenance         Discussions en Francais (Français)         Diskussionsforum (Deutsch)     Forum Rules and documentation     Non-Graal-related threads Graal V6 forums     Announcements     Your opinion     Questions about V6     Feature request     Bug Report Gold Servers     Graal Kingdoms         Markets         Kingdoms             Dustari             Forest             Crescent Pirates             Samurai             Zormite Republic         Graal Kingdoms Events         Information             Gods         GK Suggestions         GK Bugs     Zone         Gfx submissions         Information         Zone Suggestions.         Zone Bugs         Zone News         Zone PC PlayerWorlds     PlayerWorlds Main Forum         Playerworld Related Information     Playerworld Staff Openings     Bomy Island Main Forum         Kingdoms Main Forum         Events and Activities         Bugs and Future Improvements             New Races     Classic Main Forum         Classic News         Classic Bugs and suggestions         Hiring for Classic     Delteria Main Forum         Delteria News         Delteria Bugs and suggestions         Hiring for Delteria     Era Main Forum         Era News         Era Bugs and improvements         Hiring for Era         Era Wiki     N-Pulse Main Forum         N-Pulse News         N-Pulse Bugs and suggestions         Hiring for N-Pulse     Unholy Nation Main Forum         Unholy Nation News         Unholy Nation Bugs and improvements         Hiring for Unholy Nation     Valikorlia Main Forum         Valikorlia News         Valikorlia Bugs and suggestions         Hiring for Valikorlia     Zodiac Main Forum         Zodiac News         Zodiac Bugs and suggestions         Hiring for Zodiac Development Forums     Level Design     Graphic Design     Sounds & Music     Gani Construction     Videos     NPC Scripting         New Scripting Engine (GS2)         Old Scripting Engine (GS1)         Code Gallery     Tech Support         Bug Reports (No posting)     Future Improvements Private forums

All times are GMT +2. The time now is 04:04 PM.

 -- Graal Forums - Author on top -- Mobile -- Graal Forums - Old Layout Contact Us - Graal - Archive - Privacy Statement - Top

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.