No solution word search

generate-words.py

#!/usr/bin/env python3
# Here's the prompt:
#
#  Construct a "word search" N x M letter grid where:
#
# * There are NO possible words horizontal or vertical 
# * The letters appear random with no trivial patterns
# * The frequency distribution of letters is close to English prose
#
# This is a naive implementation
#
import random

# First we use the frequency distribution as grabbed from some
# website. ETA is near the top, good enough.
freqMap = {
  "E": 1,           "T": 0.757072,    "A": 0.675541,
  "O": 0.638935,    "I": 0.608153,    "N": 0.578203,
  "S": 0.522463,    "R": 0.500832,    "H": 0.492512,
  "D": 0.359401,    "L": 0.331115,    "U": 0.239601,
  "C": 0.225458,    "M": 0.217138,    "F": 0.191348,
  "Y": 0.175541,    "W": 0.173877,    "G": 0.168885,
  "P": 0.151414,    "B": 0.1239600,   "V": 0.0923461,
  "K": 0.0574043,   "X": 0.0141431,   "Q": 0.00915141,
  "J": 0.00831947,  "Z": 0.00582363,
}

# Now we declare the board size
rowCount = 30
colCount = 30

# This is how we do random selection. It uses a feature called random.choices
population = list(freqMap.keys())
weights = list(freqMap.values())

board = [ random.choices(population, weights, k=colCount) for row in range(0, rowCount) ]

# This is our definition of english words
mydict = set(map(lambda x: x.upper().strip(), open('/usr/share/dict/words', 'r').readlines()))

# The naive solution. We brute force looking for a word horizontally. 
# If we find one, we record that we did and then change the first letter with a new random letter.
# 
# Then we transpose the board and repeat the same process.
# At the end if our word count is greater than 0 we do it all again.
#
# Eventually, because our solution space of valid words is substantially smaller from our keyspace
# of possible letter combinations, we will tend towards having fewer words until eventually we
# get to 0 and then the loop exits and prints our board.
#
# Wildly inefficient.

while True:
  wordList = []

  for row in board:
    for i in range(0, colCount):
      for j in range(i+2, colCount):
        word = ''.join(row[i:j])
        if word in mydict:
          wordList.append(word)
          row[i] = random.choices(population, weights, k=1)[0]

  colList = [list(x) for x in zip(*board)]
  for x in range(0, len(colList)): 
    row = colList[x]
    for i in range(0, colCount):
      for j in range(i+2, colCount):
        word = ''.join(row[i:j])
        if word in mydict:
          wordList.append(word)
          board[i][x] = random.choices(population, weights, k=1)[0]

  if len(wordList) == 0:
    break

for row in board:
  print(' '.join(row))