I am writing a Scrabble AI, and I want to handle blank tiles. Right now, I want to expand a string containing blank tiles into a list of strings composed of words created by all possible interpretations of the blanks.<p>So, "H_LLO" ==> ["HALLO", "HBLLO", ... "HZLLO"] (length is 26)<p>However, Scrabble has 2 blank tiles, so I can't just do a simple for loop and replace.<p>For example, "H_LL_" ==> ["HALLA", "HALLB", ... "HBLLA", ... "HZLLZ"] (length is 26x26 = 676)<p>What is the cleanest way to do this? The best I could come up with is the following, but I don't much like it:<p><pre><code> import re
from itertools import product
w = "H_LL_"
expanded = []
product_args = list()
for _ in xrange(w.count("_")):
product_args.append( map(chr, range(65, 91)) )
for repl_str in product(*tuple(product_args)):
wtemp = w
for c in repl_str:
wtemp = re.sub('_', c, wtemp)
expanded.append(wtemp)</code></pre>
Try this for when you need to fill 2 blank tiles:<p><pre><code> import string
from itertools import product
w = "H_LL_"
w_fmt = w.replace('_', '%s')
product_args = [list(string.uppercase)] * 2
expanded = [w_fmt % repl for repl in product(*product_args)]</code></pre>
Do you want to just find dictionary words based on board configuration and a bench? Typically they build a Directed Acyclic Word Graph from the dictionary and then you can just traverse the graph.<p>So for your example, you start at the H node and follow all paths. Then follow the L path if it exists. Then follow the next L path. Then follow all paths from that node. Then check if the word has ended.
Here's another way to do this in Python.<p><pre><code> lets = [chr(x) for x in range( ord('a'),ord('z')+1)]
def blankexpand( templates ):
expansion = []
for t in templates:
expansion = expansion + [t.replace('_',let,1) for let in lets]
return expansion
def expand( template ):
blanktiles = template.count('_')
if blanktiles == 0:
print 'nothing to expand'
elif blanktiles == 1:
print blankexpand( [template] )
elif blanktiles == 2:
print blankexpand( blankexpand( [template] ) )
else :
print 'too many blank tiles'
print
expand( 'abce' )
expand( 'a_')
expand( 'h_ll_')
expand( '___' )</code></pre>
I would simply use hyphen '-' as well as the underscore '_'.<p>Another almost as trivial solution would be to have a string with two blanks and permute away !
Well, do you really want ALL possibilities, or just valid ones (actual words - HZLLO is not a word)?<p>If you want all possibilities, I might suggest wrapping it in a function that can lazily return the possibilities one by one as needed (see the yield keyword).<p>If you want only valid entries, you will probably want something more sophisticated (e.g. a search tree)