We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Recursion
  4. Crossword Puzzle
  5. Discussions

Crossword Puzzle

  • amourayuba
     + 0 comments

    Looks more like a dp problem to me. Here is my long and ugly solution.

    The main idea is, first find all the available spots where to put words. Then, find their length. Then, sort them by how many of each lengths there are. Start with the smallest numbers. If there is only one spot of length 5. The put the apppropriate word in that spot. Move to the next smallest number of words of that length, saving the possible configurations of the crossword that you found.

    Then loop over each spot/word length. For each set word/spot lengths, try all possiblities, store all possible configurations at that stage. Repeat, by the end, only one possible solution works.

    I think the functions ishstart/isvstart/findend/findspots and putword are reasonably nice. The function match can probably be writtend much better, in a recursive or nicer dp way.

    from collections import defaultdict
from copy import deepcopy


#
# Complete the 'crosswordPuzzle' function below.
#
# The function is expected to return a STRING_ARRAY.
# The function accepts following parameters:
#  1. STRING_ARRAY crossword
#  2. STRING words
#

def ishstart(crossword, i, j):
    if i == 9 or crossword[i + 1][j] == '+':
        return False
    if i == 0 or crossword[i - 1][j] == '+':
        return True
    return False


def isvstart(crossword, i, j):
    if j == 9 or crossword[i][j + 1] == '+':
        return False
    if j == 0 or crossword[i][j - 1] == '+':
        return True
    return False


def findend(crossword, i, j, wordtype):
    if wordtype == 'Horizontal':
        start = i
        while start < 10 and crossword[start][j] == '-':
            start += 1
        return (start - 1, j)
    if wordtype == 'Vertical':
        start = j
        while start < 10 and crossword[i][start] == '-':
            start += 1
        return (i, start - 1)


def findspots(crossword):
    spots = defaultdict(list)
    for i in range(10):
        for j in range(10):
            if crossword[i][j] == '-':
                if ishstart(crossword, i, j):
                    end = findend(crossword, i, j, 'Horizontal')
                    spots[end[0] - i + 1].append(((i, j), end))
                if isvstart(crossword, i, j):
                    end = findend(crossword, i, j, 'Vertical')
                    spots[end[1] - j + 1].append(((i, j), end))
    return spots


def putword(cs, spot, word):
    xi, yi = spot[0]
    xf, yf = spot[1]
    l = 0
    cross = deepcopy(cs)
    for i in range(xi, xf + 1):
        for j in range(yi, yf + 1):
            if cs[i][j] == '-' or cs[i][j] == word[l]:
                cross[i][j] = word[l]
                l += 1
            else:
                return False
    return cross


def match(words, spots, crossword):
    wlengths = defaultdict(list)
    for word in words:
        wlengths[len(word)].append(word)
    nwords = []
    for wlength, words in wlengths.items():
        nwords.append([len(words), wlength])
    nwords.sort()

    dp = None
    for nword in nwords:
        npossib, word_length = nword
        if npossib == 1:
            word_toput = wlengths[word_length][0]
            spot_toput = spots[word_length][0]
            if dp:
                crossword = dp[0]
            newcross = putword(crossword, spot_toput, word_toput)
            dp = [newcross]
        else:
            words_toput = wlengths[word_length]
            spots_toput = spots[word_length]
            sols = []
            if dp:
                for cross in dp:
                    poss = [cross]
                    for wd in words_toput:
                        newposs = []
                        for cross in poss:
                            for sp in spots_toput:
                                newcross = putword(cross, sp, wd)
                                if newcross:
                                    newposs.append(newcross)
                        poss = newposs
                        if not poss:
                            break
                    for sol in poss:
                        sols.append(sol)
            else:
                for wd in words_toput:
                    for sp in spots_toput:
                        newcross = putword(crossword, sp, wd)
                        if newcross:
                            sols.append(newcross)
            dp = sols

    return dp


def crosswordPuzzle(crossword, words):
    crossword = [list(el) for el in crossword]

    spots = findspots(crossword)
    # print(spots)
    words = words.split(';')'
		

    sol = match(words, spots, crossword)[-1][0]
    # pprint(sol)
    return [''.join(el) for el in sol]