Created
January 5, 2022 02:37
-
-
Save kristopolous/e6e2b2720160f2caaf1d9a833c45a7ba to your computer and use it in GitHub Desktop.
No solution word search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment