Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 06-19-2008, 02:08 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
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..
Reply With Quote
  #2  
Old 06-19-2008, 12:14 PM
Chompy Chompy is offline
¯\(º_o)/¯
Chompy's Avatar
Join Date: Sep 2006
Location: Norway
Posts: 2,815
Chompy is just really niceChompy is just really niceChompy is just really nice
Send a message via MSN to Chompy
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?
__________________
Reply With Quote
  #3  
Old 06-19-2008, 01:15 PM
zokemon zokemon is offline
That one guy...
zokemon's Avatar
Join Date: Mar 2001
Location: Sonoma County, California
Posts: 2,925
zokemon is a jewel in the roughzokemon is a jewel in the rough
Send a message via ICQ to zokemon Send a message via AIM to zokemon Send a message via MSN to zokemon Send a message via Yahoo to zokemon
Arguments please.
__________________
Do it with a DON!
Reply With Quote
  #4  
Old 06-19-2008, 03:10 PM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by zokemon View Post
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...
__________________
Reply With Quote
  #5  
Old 06-20-2008, 12:55 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
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 :/
Reply With Quote
  #6  
Old 06-20-2008, 10:19 AM
zokemon zokemon is offline
That one guy...
zokemon's Avatar
Join Date: Mar 2001
Location: Sonoma County, California
Posts: 2,925
zokemon is a jewel in the roughzokemon is a jewel in the rough
Send a message via ICQ to zokemon Send a message via AIM to zokemon Send a message via MSN to zokemon Send a message via Yahoo to zokemon
I'm asking what should be passed to the function .
__________________
Do it with a DON!
Reply With Quote
  #7  
Old 06-20-2008, 03:53 PM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by zokemon View Post
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.
__________________
Reply With Quote
  #8  
Old 06-20-2008, 06:08 PM
Dan Dan is offline
Daniel
Join Date: Oct 2007
Posts: 383
Dan is an unknown quantity at this point
Send a message via MSN to Dan
Do 2 letters have to link to form a word or can you pick any letter from any position to form a word?
__________________
Reply With Quote
  #9  
Old 06-20-2008, 06:12 PM
zokemon zokemon is offline
That one guy...
zokemon's Avatar
Join Date: Mar 2001
Location: Sonoma County, California
Posts: 2,925
zokemon is a jewel in the roughzokemon is a jewel in the rough
Send a message via ICQ to zokemon Send a message via AIM to zokemon Send a message via MSN to zokemon Send a message via Yahoo to zokemon
Ahh, didn't see that you added a wordlist above.
__________________
Do it with a DON!
Reply With Quote
  #10  
Old 06-20-2008, 06:15 PM
Rufus Rufus is offline
Registered User
Join Date: Jun 2004
Location: United Kingdom
Posts: 4,698
Rufus has much to be proud ofRufus has much to be proud ofRufus has much to be proud ofRufus has much to be proud ofRufus has much to be proud ofRufus has much to be proud of
Sudoku is better than Boggle!
__________________
Quote:
Originally Posted by Loriel View Post
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.
Reply With Quote
  #11  
Old 06-20-2008, 06:36 PM
Crow Crow is offline
ǝɔɐɹq ʎןɹnɔ
Crow's Avatar
Join Date: Dec 2006
Location: Germany
Posts: 5,153
Crow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond repute
Quote:
Originally Posted by Rufus View Post
Sudoku
Crosswords for dyslexic people.
__________________
Reply With Quote
  #12  
Old 06-20-2008, 07:30 PM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by Dan View Post
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.
__________________
Reply With Quote
  #13  
Old 08-02-2008, 11:39 AM
_Z3phyr_ _Z3phyr_ is offline
Banned
Join Date: Sep 2003
Location: Louisiane
Posts: 390
_Z3phyr_ is an unknown quantity at this point
Quote:
Originally Posted by Kristi View Post
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:
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;

string array containing all of the acceptable wordsone 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(rsp) {
  
p;
  for (
k=0;k<&& t==p;k++) { //8 because there are 8 directions to check
    
if (k==&& 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][sin 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-1sp); //start over
        
}
      }
    } else if (
k==&& r+1<=n-1) {//look below, if its not at the bottom
      
...
    } else if (
k==&& 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..
Reply With Quote
  #14  
Old 08-08-2008, 08:02 PM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by _Z3phyr_ View Post
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)
__________________
Reply With Quote
Reply

Tags
boggle, programming-exercise

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

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 Jump


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


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