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 was born 20145 days, 11 hours, 41 minutes ago.