Scrabble Solver Script

Keywords: power set, board, check, word, script, character, dictionary, element, code, scrabble, piece, ac, start, letter. Powered by TextRank.

I've been challenged by burcin at a game of scrabble - the Turkish version. She is quite crafty with words and can easily beat me and all of her friends. But I'm crafty with computers so I wrote a nice groovy script to play for me. I'm quite ok with making the strategical decisions, so the script just finds the best possible word for a given state. To make it play a good game of scrabble would involve far more than that. Here are some interesting parts of the script

  def permutations(letters) {
    def powerset = powerset(letters)
    def res = []
    powerset.each {
      def list = it.split("") - "" as List
      res << list.permutations().collect { it.join("") }
    }
    return res.flatten()
  }
 
  def powerset(letters) {
    def size = 2 ** letters.size()
    def res = []
    for (int i=0;i<size;i++) {
      def tmp = ""
      for (int j=0;j<letters.size();j++) {
        if ( (i & (1<<j)) > 0) {
          tmp += letters[j]
        }
      }
      res << tmp
    }
    return res - ""
  }

this piece of code generates all the possible permutations from your letters. First you need to generate the power set of the letters so if you have the letters [,b,c] you will need [,b,c,ab,ac,bc,abc]. The power set also includes the empty set which is pointless here. A nice way of generating the power set is used here. You know that there are 2^n elements in the power set, so you start from 0 and go up to 2 * n and for each number in the range the bits of the number will represent which elements to take from the letters. So say you are 4 in the range, which is 010 in base 2. This means that the 4th element in the power set is the 2 element from your letters. 5 is 011 which means the 5th element in the set is the first and second letters concatenated. Pretty cool way of doing it. Next we need all the permutations of all the elements in the power set. You want to check for the words

a, b, c
ab, ba
ac ,ca
bc, cb
abc,acb,bca, etc..

across the board.

def putWord(word, board, x, y) {
    if (board[y][x] != ASTERISK) return null
    //println "tryword: $word x/y $x $y"
    def clone = clone(board)
    def putat = x
    for(int i=0;i<word.size();i++) {
      while(putat < 14 && clone[y][putat] != "*") {
        putat++
      }
      if (putat > 14) {
        //putting the whole word would exceed board bounds
        return clone
      }
      clone[y][putat] = word[i]
      putat++
    }
 
    return clone
   
  }

this piece of code will put the given word on the board. The thing you need to careful about is that you may need to skip over exiting letters from words.

|   |   |   |   |   |   |
|---|---|---|---|---|---|
|*  |a  |*  |*  |*  |*  | 
|*  |b  |*  |*  |*  |*  | 
|*  |c  |*  |*  |*  |*  |

if you want to put the word "xyz" at position 0,0 you need to skip over the letter a and then continue putting the word so it looks like

| | | | | | |
|-|-|-|-|-|-|
|x|a|y|z|*|*| 
|*|b|*|*|*|*| 
|*|c|*|*|*|*|

if the starting location doesn't contain the * character you just just return as a word can't start there.

def isValidWords(board, dict) {
	def words = []
	  for (def line : board) {
		def wl = line.join("")
		def st = new StringTokenizer(wl, "*")
		while(st.hasMoreElements()) {
			def nt = st.nextToken()
			if (nt.size() > 1) words << nt
		}
     }
 
 
 
    for (String w : words) {
		if (!dict.containsKey(w)) return false
    }
    return true
  }

to check if the board is valid after you put a word you need to check that all the words on the board are in your dictionary, and that there are no extra islands on the board. The board is a 2D array like this

[
 [* * * * *],
 [* * * * *]
...
]

if you join each row of the board into a string and then tokenize on "*" you will get all the words in that row. Look them up in your dictionary and return false if a single words doesn't exists in the dictionary. What about vertical words? Just transpose the board (t_board[][] = board[][]) and run the same check.

def connected(board) {
    //dumpboard(board)
    def startx, starty
    outer:
    for(int i=0;i<15;i++) {
      for(int j=0;j<15;j++) {
                  if (board[i][j] != ASTERISK) {
                          startx = j
                          starty = i
                          break outer
                  }
      }
    }
    def clone = clone(board)
    floodfill(clone, startx, starty)
        for(int i=0;i<15;i++) for(int j=0;j<15;j++) if (clone[i][j] != ASTERISK && clone[i][j] != BANG) return false
        return true
    //return clone.flatten().findAll { it != ASTERISK && it != BANG }.size() == 0
  }
 
  def floodfill(board, x, y) {
    board[y][x] = BANG
    if (y < 14 && board[y+1][x] != ASTERISK && board[y+1][x] != BANG) {
      floodfill(board, x, y+1)
    }
    if (y > 0 && board[y-1][x] != ASTERISK && board[y-1][x] != BANG) {
      floodfill(board, x, y-1)
    }
    if (x < 14 && board[y][x+1] != ASTERISK && board[y][x+1] != BANG) {
      floodfill(board, x+1, y)
    }
    if (x>0 && board[y][x-1] != ASTERISK && board[y][x-1] != BANG) {
      floodfill(board, x-1, y)
    }
    //dumpboard(board)
  }

to check for islands just find the indices of the first letter on the board, and do a flood fill, replacing the letters with the bang character. Next check all locations for a character other than "!" or "*". If there are any it means there is an island and the board isn't valid. I have a more detailed write up on this method [ere][1]

The first iteration of the script ran on a single thread and would take about 6 to 7 minutes to calculate 13699 words. But it's a great candidate for parallelization which is very simple with groovy. With 6 threads it completes in about 2 minutes which is quite acceptable.

[]: /code/scrabble-island-detection/

Scrabble Solver Script

Metadata

Similar posts