Boggle.frink

View or download 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]]]]
}


View or download 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 17591 days, 17 hours, 48 minutes ago.