A Quick and Dirty Words With Friends Solver: Part 2
2.1 The Solver class
We are now going to create a solver class to perform the next calculations. This needs to intake the current state of the board and the letters you have in your rack. I'm not very experienced with OOP and I suspect there's a more 'proper' way to do this with inheritance. But I'm just going to pass an instance of the board class as an argument to the solver class.
class Solver:
def __init__(self, Board, rack):
'''Simple init. Add variables'''
self.rack = rack
self.Board = Board
2.1 Where am I allowed to place letters?
At this point, how do we proceed? The most basic possible brute force solver might do something like this: There are 11x11 = 121 (minus the number of occupied squares) possible places to put tiles. We could just find every single possbile configuration (of which there are around 100 trillion) that we could drop the \(n\) tiles from our rack and see which ones happen to form lined up, valid words.
But this is clearly very inefficient. We already have some knowledge about where we can legally place tiles based on the rules, so what's the point in trying tiles in illegal configurations. What we need is a way of listing every single possible place we could legally place tiles, even if it makes an invalid word.
The rules about where you can place tiles can be summarised by the following:
- Tiles must all be placed in a single row or column.
- Apart from the first move, tiles must be connected to a word already on the board .
- Tiles do not have to all be adjacent, however they must form one and only one fully connected word per row/column.
To find the full set of valid tile placements we need two functions:
find_valid_placements
and
identify_starters
. For the function
find_valid_placements
, you must pass an index ranging from 0 to 10, and either 'row' or 'col'. This identifies a single row or column on the board. It then seeks to return the set of indicies where one
could
place letters in that particular row or column.
The algorithm goes something like this:
- Find all the squares in the row that are adjacent to an occupieid square.
- For each of these squares, start here and keep stepping right. If you find a square that is unoccupied add all the unoccupied squares from your starting square to this one to a master list.
- If there are unconnected, unoccupied squares to the left of the starting square, then for each of the set of indices you've just added, add each one again including these squares.
That's kind of hard to explain, so here's a pictorial representation of what's happening there:
The other function,
identify_starters
just finds which squares are occupied, next to an occupied square, and other. Note that it also has to be passed the two adjacent columns in order to know whether a square is adjacent to an occupied square.
def identify_starters(self, row, adjacent1, adjacent2):
'''
given a row, in the form of a list, identify the indicies
where you can 'start' the algorithm below (which amounts
to finding the indicies where one can place a single
letter) and also return the occupied indicies and the non-
starters (everthing that is not a starter or occupied)
'''
if adjacent1 == None:
adjacent1 = [''] * 11
if adjacent2 == None:
adjacent2 = [''] * 11
non_starters = []
occupied = [index for index in range(len(row)) if row[index] != '']
for index, item in enumerate(row):
if index == 0:
if item == '' and row[1] == '':
non_starters.append(index)
elif index == 10:
if item == '' and row[9] == '':
non_starters.append(index)
else:
if item == '' and row[index - 1] == '' and row[index + 1] == '':
non_starters.append(index)
starters = [index for index in range(
len(row)) if index not in occupied and index not in non_starters]
for index in non_starters:
if adjacent1[index] != '' or adjacent2[index] != '':
non_starters.remove(index)
starters.append(index)
return starters, non_starters, occupied
def find_valid_placements(self, index, rtype='row'):
'''
Find the set of sets of indices where letters can possibly
be placed
'''
board = self.Board.letters
if rtype == 'col':
row = list(board[index, :][::-1])
if index == 0:
adjacent1 = None
adjacent2 = list(board[index + 1, :][::-1])
elif index == 10:
adjacent1 = list(board[index - 1, :][::-1])
adjacent2 = None
else:
adjacent1 = list(board[index - 1, :][::-1])
adjacent2 = list(board[index + 1, :][::-1])
elif rtype == 'row':
row = list(board[:, index])
if index == 0:
adjacent1 = None
adjacent2 = list(board[:, index + 1])
elif index == 10:
adjacent1 = list(board[:, index - 1])
adjacent2 = None
else:
adjacent1 = list(board[:, index - 1])
adjacent2 = list(board[:, index + 1])
starters, non_starters, occupied = self.identify_starters(row, adjacent1, adjacent2)
master_poss = []
for starter in starters:
poss = []
next_nums = list(range(starter + 1, 11))
next_nums = [num for num in next_nums if num not in occupied]
for i in range(len(next_nums) + 1):
poss.append([starter] + next_nums[:i])
for p in poss:
master_poss.append(p)
if starter - 1 in non_starters:
c = 1
if starter - 2 in non_starters:
c += 1
if starter - 3 in non_starters:
c += 1
if starter - 4 in non_starters:
c += 1
if starter - 5 in non_starters:
c += 1
if starter - 6 in non_starters:
c += 1
if starter - 7 in non_starters:
c += 1
if starter - 8 in non_starters:
c += 1
if starter - 9 in non_starters:
c += 1
if starter - 10 in non_starters:
c += 1
news = []
for i in range(c):
news.append(list(reversed(range(starter - 1, starter - 1 - (i + 1), -1))))
for new in news:
for old_poss in poss:
master_poss.append(new + old_poss)
grouped = {}
for item in master_poss:
try:
grouped[len(item)].append(item)
except KeyError:
grouped[len(item)] = [item]
return grouped
Granted, these two functions are UGLY. Especially that nested if statement. Yuk. In fact just looking at them now is making me feel sick. Think I'll have to come back and improve this at some point. They do work but please let me know if you can find a neater way. I'm very certain there is one.
Here's a simple helper function that extracts the words from a given column or row.
def extract_words(self, row):
'''Extracts the words from a given row '''
row = [' ' if letter == '' else letter for letter in row]
return [word for word in ''.join(row).split(' ') if len(word) > 1]
This next function is the final complex one. It seeks to find every valid placement of letters in a single row. I.e, the previous functions show the set of indicies letters could collectively be placed in that are consistent with the rules of the game; and this function runs through every permutation and combination of your letters and returns those which form valid words for that row. This does not guarantee that this will be valid however, as we still need to check for conflicts in the perpendicular direction.
Perhaps at this point, it is best explained by an example. Let's say you're looking at the following row
row = ['','','','','w','o','r','d','s','','']
for which the two adjacent parallel rows are empty and you have the following letters in your hand
letters = 'sdafkso'
The function find_valid_placements acting on this row will return the following set of indicies
possible_placements =[[3], [3, 9], [3, 9, 10],
[2, 3], [2, 3, 9], [2, 3, 9, 10],
[1, 2, 3], [1, 2, 3, 9], [1, 2, 3, 9, 10],
[0, 1, 2, 3], [0, 1, 2, 3, 9], [0, 1, 2, 3, 9, 10],
[9], [9, 10]]
The function
find_words
will then sort these possible placements into groups based on length. It will also list every possible permutation of you letters and group them by length
placements_grouped = {1: [[3], [9]],
2: [[3, 9], [2, 3], [9, 10]],
...}
letters_grouped = {1: ['s', 'd', 'a', 'f', 'k', 's', 'o'],
2: ['sd', 'sa', 'sf', 'sk', 'ss', ...],
...}
Then for each length, the function matches each set of letters with each set of indicies, inserts them into the row, and uses the extract words function to check if this is a valid word in the dictionary. It then passes all of these valid rows on to the next function to check that they do not cause conflicts in the other direction.
def find_words(self, index, rtype='row'):
'''Find the placements which give valid words
on that row'''
board = self.Board.letters
if rtype == 'col':
row = list(board[index, :][::-1])
elif rtype == 'row':
row = list(board[:, index])
valid_placements = self.find_valid_placements(index, rtype=rtype)
if valid_placements == {}:
return []
big = min([len(self.rack), max(valid_placements.keys())])
small = min(valid_placements.keys())
valid_placements = {key: item for key, item in valid_placements.items() if key <= big}
all_combs = {}
all_perms = {}
new_rows = []
for n in range(small, big + 1):
all_combs[n] = [''.join(p) for p in combinations(self.rack, n)]
for key, item in all_combs.items():
all_perms[key] = list(set([''.join(p) for comb in item for p in permutations(comb)]))
for n in range(small, big + 1):
placements = valid_placements[n]
perms = all_perms[n]
for placement in placements:
for perm in perms:
new_row = row[:]
for i, index in enumerate(placement):
new_row[index] = perm[i]
words = self.extract_words(new_row)
for word in words:
if not exists(word):
break
new_rows.append(new_row)
return new_rows
The next function then does this validation process. If we just suggested some word placements for a row, it will then check all 11 columns to see whether the placement creates invalid words in that direction.
def validate(self, index, new_row, rtype='row'):
'''Check whether a new row insertion creates
confilcts with other rows/columns'''
test_board = self.Board.letters.copy()
if rtype == 'row':
test_board[:, index] = new_row
for col_num in range(11):
test_col = list(test_board[col_num, :][::-1])
words = self.extract_words(test_col)
for word in words:
if not exists(word):
return False, None
return True, test_board
elif rtype == 'col':
test_board[index, :] = list(reversed(new_row))
for row_num in range(11):
test_row = list(test_board[:, row_num])
words = self.extract_words(test_row)
for word in words:
if not exists(word):
return False, None
return True, test_board
So now we are left with a set of truly valid placements. Notice that this function returns the whole board if it is valid. Now we need to score the word.
def extract_word_positions(self, board):
'''Find every word on the board, listing the word,
it's starting square and whether it's in a row or column'''
words = []
for row_num in range(11):
row = list(board[:, row_num])
word = ''
starting_square = (0, 0)
first_letter = True
for i, letter in enumerate(row):
if letter == '' or i == 10:
if i == 10 and letter == '':
if len(word) > 1:
words.append((word, starting_square, 'row'))
elif i == 10 and word != '':
if len(word) > 0:
word += letter
words.append((word, starting_square, 'row'))
else:
if len(word) > 1:
words.append((word, starting_square, 'row'))
word = ''
first_letter = True
else:
word += letter
if first_letter:
starting_square = (i, row_num)
first_letter = False
for col_num in range(11):
col = list(board[col_num, :][::-1])
word = ''
starting_square = (0, 0)
first_letter = True
for i, letter in enumerate(col):
if letter == '' or i == 10:
if i == 10 and letter == '':
if len(word) > 1:
words.append((word, starting_square, 'col'))
elif i == 10 and word != '':
if len(word) > 0:
word += letter
words.append((word, starting_square, 'col'))
else:
if len(word) > 1:
words.append((word, starting_square, 'col'))
word = ''
first_letter = True
else:
word += letter
if first_letter:
starting_square = (col_num, i)
first_letter = False
return words
def score(self, old_board, new_board):
'''Find out what a placement is worth given the
old state of the board and the new'''
old_words = self.extract_word_positions(old_board)
new_words = self.extract_word_positions(new_board)
new_words = [word for word in new_words if word not in old_words]
total_score = 0
for word in new_words:
letters, (x, y), rtype = word
l = len(letters)
if rtype == 'col':
powers = list(reversed(list(MyBoard.powers[x, :])))[y:y + l]
elif rtype == 'row':
powers = list(MyBoard.powers[x:x + l, y])
word_score = 0
multiplier = 1
for l, p in zip(letters, powers):
s = points[l]
if p != '':
if p[1] == 'l':
if p[0] == 't':
s *= 3
elif p[0] == 'd':
s *= 2
elif p[1] == 'w':
if p[0] == 't':
multiplier *= 3
if p[0] == 'd':
multiplier *= 2
word_score += s
word_score *= multiplier
total_score += word_score
return total_score
Finally we put all of these together into a solve and print function
def solve(self, n_solutions=10):
board = self.Board.letters
options = []
counter = 0
poss = []
for col_num in range(11):
rows = self.find_words(col_num, rtype='col')
for row in rows:
valid, new_board = self.validate(col_num, row, rtype='col')
if valid:
poss.append(('col', row, col_num, self.score(board, new_board)))
for row_num in range(11):
rows = self.find_words(row_num, rtype='row')
for row in rows:
valid, new_board = self.validate(row_num, row, rtype='row')
if valid:
poss.append(('row', row, row_num, self.score(board, new_board)))
poss = sorted(poss, key=lambda x: -x[3])
return poss[:n_solutions]
def print_solutions(self, n_solutions=10):
solutions = self.solve(n_solutions=n_solutions)
for i, solution in enumerate(reversed(solutions)):
new_board = self.Board.letters.copy()
rtype, new_row, index, score = solution
if rtype == 'row':
key_word = 'across'
old_row = list(new_board[:, index])
old_words = self.extract_words(old_row)
new_words = self.extract_words(new_row)
new_word = [word for word in new_words if word not in old_words][0]
new_board[:, index] = new_row
elif rtype == 'col':
key_word = 'down'
old_col = list(new_board[index, :][::-1])
old_words = self.extract_words(old_col)
new_words = self.extract_words(new_row)
new_word = [word for word in new_words if word not in old_words][0]
new_board[index, :] = list(reversed(new_row))
print('Solution {0}: play "{1}" {2} for {3} points'.format(
n_solutions - i, new_word, key_word, score))
to_print = Board()
to_print.letters = new_board
to_print.print_board()
Done! Let's take it for a test drive
board_string = '''
A B C D E F G H I J K
--------------------------------------------
| | | | | | | | | | | | 1
--------------------------------------------
| | | | | | | | | | | | 2
--------------------------------------------
| | | | | | | | | s | | | 3
--------------------------------------------
| | | | | | t | | | p | | | 4
--------------------------------------------
| | | f | i | n | o | | | a | | | 5
--------------------------------------------
| | | | | | w | o | r | d | s | | 6
--------------------------------------------
| | | | | | n | | a | e | | | 7
--------------------------------------------
| | | | | | | | g | | | | 8
--------------------------------------------
| | | | | | | | s | | | | 9
--------------------------------------------
| | | | | | | | | | | | 10
--------------------------------------------
| | | | | | | | | | | | 11
--------------------------------------------
'''
my_letters = 'ajfpeys'
MyBoard = Board()
MyBoard.ingest(board_string)
solver = Solver(MyBoard, my_letters)
solver.print_solutions(n_solutions=3)
Solution 10: play "spay" across for 51 points
A B C D E F G H I J K
--------------------------------------------
| | | | | | | | | | | | 1
--------------------------------------------
| | | | | | | | | | | | 2
--------------------------------------------
| | | | | | | | | s | | | 3
--------------------------------------------
| | | | | | t | | | p | | | 4
--------------------------------------------
| | | f | i | n | o | | | a | | | 5
--------------------------------------------
| | | | | | w | o | r | d | s | | 6
--------------------------------------------
| | | | | | n | | a | e | | | 7
--------------------------------------------
| | | | | | | | g | | | | 8
--------------------------------------------
| | | | | | | | s | p | a | y | 9
--------------------------------------------
| | | | | | | | | | | | 10
--------------------------------------------
| | | | | | | | | | | | 11
--------------------------------------------
Solution 9: play "spas" across for 45 points
A B C D E F G H I J K
--------------------------------------------
| | | | | | | | | | | | 1
--------------------------------------------
| | | | | | | | | | | | 2
--------------------------------------------
| | | | | | | | | s | | | 3
--------------------------------------------
| | | | | | t | | | p | | | 4
--------------------------------------------
| | | f | i | n | o | | | a | | | 5
--------------------------------------------
| | | | | | w | o | r | d | s | | 6
--------------------------------------------
| | | | | | n | | a | e | | | 7
--------------------------------------------
| | | | | | | | g | | | | 8
--------------------------------------------
| | | | | | | | s | p | a | s | 9
--------------------------------------------
| | | | | | | | | | | | 10
--------------------------------------------
| | | | | | | | | | | | 11
--------------------------------------------
Solution 8: play "spae" across for 45 points
A B C D E F G H I J K
--------------------------------------------
| | | | | | | | | | | | 1
--------------------------------------------
| | | | | | | | | | | | 2
--------------------------------------------
| | | | | | | | | s | | | 3
--------------------------------------------
| | | | | | t | | | p | | | 4
--------------------------------------------
| | | f | i | n | o | | | a | | | 5
--------------------------------------------
| | | | | | w | o | r | d | s | | 6
--------------------------------------------
| | | | | | n | | a | e | | | 7
--------------------------------------------
| | | | | | | | g | | | | 8
--------------------------------------------
| | | | | | | | s | p | a | e | 9
--------------------------------------------
| | | | | | | | | | | | 10
--------------------------------------------
| | | | | | | | | | | | 11
--------------------------------------------