Download or view Boggle.frink in plain text format
// Program to generate and draw random Boggle boards.
// Thanks to Jenny Williams for the research.
class Boggle
{
// This will be a two-dimensional array that stores the possible cubes.
class var cubes = undef
// The list of available words. This will be a dictionary.
class var wordlist = undef
// Initialize the cubes.
class initCubes[] :=
{
// This is a list of the sides of the cubes, cut-n-pasted directly from
// an e-mail as one big multi-line string.
raw="""E A E A E E
E E E E A M
E O M T T T
N O L D D R
I I E I T T
S S S N E U
C T I L E I
H H R L O D
A R F S A A
F R Y S A I
H D T N H O
C C W N S T
R W G O V R
U G E E M A
F I Y P R S
U O T O N W
E I P C L T
N H L R D O
I A F A S R
N N E M A G
O O T O U T
H P R I Y R
N N E N D A
I P C E S T
B Z J QU K X"""
// Break the string on newlines
rawlines = split[%r/[\r\n]+/, raw]
cubes = new array
// Now split each line on whitespace. It would be more concise if the
// split function allowed an array of strings as the second argument, but
// that's no big deal. The trim is necessary because there is leading
// whitespace in each line. And we just sort the cubes for fun.
for line = rawlines
cubes.push[sort[split[%r/\s+/,trim[line]]]]
}
// Method to generate a random Boggle board. This board is returned as a
// simple 2-dimensional array which can be easily manipulated by other
// programs, or the board can be pretty-printed or drawn to a graphics
// window with the methods below.
class generateBoard[] :=
{
if (cubes == undef)
initCubes[]
// Figure out the size of the board.
cubeside = sqrt[length[cubes]]
index = 0
// Create a two-dimensional array
board = new array[[cubeside, cubeside]]
// Make a copy of the cubes so we can remove from them safely.
cubeCopy = deepCopy[cubes]
while length[cubeCopy] > 0
{
// Pick a random cube from those remaining
cube = cubeCopy.removeRandom[]
// Pick a random letter from that cube.
letter = random[cube]
row = index div cubeside
col = index mod cubeside
board@row@col = letter
index = index + 1
}
return board
}
// returns a text representation of a board as a string with newlines.
class textBoard[board] :=
{
result = ""
cubeside = length[board]
for row=0 to cubeside-1
{
for col=0 to cubeside-1
{
ch = board@row@col
// This is necessary because of the "Qu" piece
if length[ch] == 2
result = result + "$ch "
else
result = result + "$ch "
}
result = result + "\n"
}
return result
}
// Draws the specified boggle board into the graphics object with the
// specified upper left coordinate and size.
class drawBoard[g is graphics, board, x, y, size] :=
{
g.color[0,0,0]
sidelen = length[board]
cubedim = size / sidelen
g.font["SansSerif", "bold", cubedim]
for row=0 to sidelen-1
for col = 0 to sidelen-1
g.text[board@row@col,
x + col*cubedim + cubedim/2,
y + row*cubedim + cubedim/2]
}
// Draws a printable Boggle worksheet.
class drawWorksheet[g is graphics, board] :=
{
// First draw the board
g.drawBoard[g, board, -20, 0, 40]
// Then the lines.
g.color[.8,.8,.8]
for y = 50 to 110 step 4
{
g.line[-42,y,-15,y]
g.line[-13,y,13,y]
g.line[15,y,42,y]
}
}
class solveBoard[board] :=
{
if (wordlist == undef)
initializeWordlist[]
wordsFound = new set
cubeside = length[board]
for i=0 to cubeside-1
for j=0 to cubeside-1
solveBoardInternal[board, wordlist, wordsFound, "", i, j, cubeside]
return wordsFound
}
// Solve a board by finding all words
class solveBoardInternal[board, wordpart, wordsFound, currWord, i, j, cubeside] :=
{
nb = deepCopy[board]
nb@i@j = undef
if wordpart.isFinal[] // End of a valid word?
wordsFound.put[currWord]
for ii=max[0, i-1] to min[cubeside-1, i+1]
{
for ij=max[0, j-1] to min[cubeside-1, j+1]
{
if ii==i and ij==j
next
newLetter = nb@ii@ij
if (! newLetter)
next
// println["Starting at $ii, $ij, $newLetter, $currWord"]
nextpart = wordpart.getWordlist[newLetter]
if (nextpart != undef)
solveBoardInternal[nb, nextpart, wordsFound, "$currWord$newLetter", ii, ij, cubeside]
}
}
}
class initializeWordlist[] :=
{
wordlist = new Wordlist
// The wordlist files are part of the Moby wordlist project, available at:
// http://icon.shef.ac.uk/Moby/
for word = lines["file:///home/eliasen/prog/mobydict/mwords/singlewords.txt"]
if length[word] >= 4 and (word =~ %r/^[a-z]*$/)
wordlist.addWord[uc[word]]
}
}
class Wordlist
{
// This is a dictionary where the key is a letter in a word and
// the value is the next WordList in the tree.
var nextDict
var final
new[] :=
{
nextDict = undef
final = false
}
// Adds a "next letter" mapping for the specified letter and returns
// the Wordlist for the next letter. If the next letter already exists,
// this returns the existing Wordlist
addLetter[letter] :=
{
if nextDict == undef
nextDict = new dict
w = nextDict@letter
if w == undef
{
w = new Wordlist
nextDict@letter = w
}
return w
}
// Adds the specified word to the Wordlist
addWord[word] :=
{
letlen = 1
let = left[word, 1]
if let == "Q" // Annoying special case for Qu tile
if (left[word,2] == "QU")
{
letlen = 2
let = "QU"
}
wl = addLetter[let]
if (length[word] > letlen)
wl.addWord[right[word, length[word]-letlen]]
else
wl.setFinal[]
}
// Gets the next wordlist for the specified letter. If the following
// letter does not exist, this returns undef.
getWordlist[letter] :=
{
if nextDict != undef
return nextDict@letter
else
return undef
}
// Sets the final flag.
setFinal[] := final = true
// Returns the final flag.
isFinal[] := final
}
// Sample test routines. Note that these are outside the class specification.
// These routines will be moved to their own file someday.
for i = 1 to 8
{
// Generate a random board.
board = Boggle.generateBoard[]
// Print the board as plaintext.
println[]
println[Boggle.textBoard[board]]
// Draw the board in graphics mode.
g=new graphics
Boggle.drawBoard[g, board, 0, 0, 100]
//g.show[]
// Draw a worksheet in graphics mode.
g=new graphics
//Boggle.drawWorksheet[g, board]
// Change g.show[] to g.print[] to print this to a printer.
//g.show[]
println[sort[array[Boggle.solveBoard[board]]]]
}
Download or view Boggle.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen, eliasen@mindspring.com