// 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]]]]
}