Scrabble :Assume that you are trying to complete a crossword puzzle

Question

In a crossword puzzle, some letters are given and we have to figure out which complete word can we make out of it. For example, given letters "cwd"in the same order, we can make the word "crossword" or "crowd" with it. But if "dw" is given in that order, we cannot make "crossword" out of it because d and w are in the opposite order here.

We have to find an efficient method and write a code for this process. The code will take two strings as input in two lines. The first string will contain letters on the crossword("cwd"), and the second string will contain a word that we want to check.(i.e. we want to check whether the word can be made out of given letters in the same order). The output should say "yes" if the word can be formed, else it should say "no"

I have written a code:

x = re.search(letters, guess)
if (x):
  print("yes")
else:
  print("no")

but I am not getting the correct output.

where,

letters = ccwd #letters already in the crossword

guess = crossword #word to check for fit

Answer 1

If you are looking for a generic solution, try this- Suppose you have a list, let's call it lst, of dictionary words and you are given a pattern, let's say pat and you want to find out which of the words from the list match the pattern. This can be done by constructing a regular expression while separating each of the pattern characters by .* to allow inserting 0 or more characters between them. Following program achieves that-

pattern = "xyz"                     # can be replaced to have the desired pattern
lst =["crossword", "crowd"]         # this can be replaced to contain the words of your choice
pattern = '.*'.join(list(pattern))  # modifies the pattern to include .* between each of the characters of the pattern
obj = re.compile(pattern)          # create compiled regex object to use it again and again
for word in lst:
    if obj.search(word):
        print "Yes"
    else:
        print "No"

Answer 2

As mentioned, adding special chars b/w letters in the input and finding that pattern

---

x=re.findall(".*".join(list(letters)),guess)

if (x):
    print("yes")
else:
    print("no")

Answer 3

In your first example, you want to find a word that contains c, followed by anything (or nothing), followed by w, followed by anything (or nothing), followed by d.

The regular expression for "anything (or nothing)" is .*.

So, you want to to look for this regular expression:

c.*w.*d

Answer 4

lets=input()

guess=input()

i = 0

for x in guess:
    if x == lets[i]: 
          i += 1
          if i >= len(lets): break

if (i == len(lets)):
    print("Yes")
else:
    print("No")

Answer 5

This code will work for your question.

### import Library for using re.compile() method
import re

### letters already in the crossword
letters=input() 

### word to check for fit
guess=input() 

### modify letters to include .* between each character 
x=re.findall(".*".join(list(letters)),guess) 

if (x):
    print("yes")
else:
    print("no")
        

Answer 6

For the problem as defined, you can use a regular expression but you should cover cases where a prefix or suffix is added (not just letters in between):

print(["yes","no"][not re.match(".*".join("^"+letters+"$"),guess)])

letters = "cwd"

guess = "crossword"   --> yes
guess = "crowd"       --> yes
guess = "crowded"     --> yes
guess = "overcrowded" --> yes
guess = "wicked"      --> no

If you're not allowed to use libraries, you can do it with a recursive function:

def match(letters,guess):
    if not letters: return True         # stop recursion
    if not guess:   return False        # exhausted guess but not letters
    s = int(letters[0]==guess[0])       # next letter? (s=1)
    return match(letters[s:],guess[1:]) # recurse for rest

match("cwd","crossword")   --> True
match("cwd","crowd")       --> True
match("cwd","crowded")     --> True
match("cwd","overcrowded") --> True
match("cwd","wicked")      --> False

For a real crossword, a very efficient method would be to build an index of word sets for each length-positon-letter. You can then combine the sets for the known letter positions of your incomplete word:

For example:

with open("/usr/share/dict/words") as wf:
    words = [w.lower() for w in wf.read().split("\n") if len(w)>=2]

cIndex = dict()  # { (length,position,letter): set of words }
for word in words:
    for i,c in enumerate(word):
        cIndex.setdefault((len(word),i,c),set()).add(word)


def findwords(placed):
    result = None
    s = len(placed)
    for i,c in enumerate(placed):  #Run through known letters/positions
        if c=="." : continue
        if result is None:
            result  = cIndex.get((s,i,c),set()).copy()
        else:
            result &= cIndex.get((s,i,c),set())  # combine word sets
    return result or set()

Loading the index may take a few seconds but, after that, response time is instantaneous.

output:

print(findwords(".l.p..n."))

# {'slapping', 'aleppine', 'clipping', 'slipband', 'oliphant', 'elephant', 'clupeine', 'slipping', 'flippant', 'elaphine', 'clepsine', 'clapping', 'flopwing', 'slopping'}

You could also use the function to solve scrabble problems by feeding it various lengths and filtering on available letters:

from collections import Counter
def fitWord(placed,letters,maxLen=None):
    if maxLen is None:
        maxLen = len(placed)-placed.count(".")+len(letters)
    result = findwords(placed)
    if len(placed)<maxLen:
        result |= fitWord("."+placed,letters,maxLen)
        result |= fitWord(placed+".",letters,maxLen)
    letterCounts = Counter(letters)+Counter(placed.replace(".",""))
    return {w for w in result if not Counter(w)-letterCounts}
        
    
print(fitWord("l.p..n","eehatoi"))

# {'elaphine', 'elephant', 'lophine', 'lepton', 'oliphant'}

A variant of this could be made for hangman.

Answer 7

letters=input() #letters already in the crossword
guess=input() #word to check for fit
l1 = list(letters)
l2 = list(guess)
all_match = 0
for c in l1:
    for i in range(0, len(l2)):
        if c == l2[i]:
            l2 = l2[i+1:]
            all_match = all_match + 1
            break
        
if all_match == len(l1):
    print('yes')
else:
    print('no')