Last active
January 21, 2019 14:36
-
-
Save 6502/26552858e93ce4d4ec3a8ef46100df79 to your computer and use it in GitHub Desktop.
A solution for https://stackoverflow.com/questions/54271178/build-a-plinko-board-of-words-from-a-dictionary
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
import sys | |
L0 = sys.argv[1] | |
N = int(sys.argv[2]) | |
alpha = set("abcdefghijklmnopqrstuvwxyz") | |
words = set() | |
for L in open("words_alpha.txt"): | |
L = L.strip() | |
if len(L) == N and L[0] == L0: | |
words.add(L) | |
print("%i acceptable words" % len(words)) | |
wsets = {} | |
for i in range(1, N): | |
for c in alpha: | |
wsets[(i, c)] = set(w for w in words if w[i] == c) | |
# | |
# playing board | |
# | |
# x | |
# x x | |
# x x x | |
# x x x x | |
# x x x x x | |
# | |
M = [["?"] * (i+1) for i in range(N)] | |
wtab = [] | |
for i in range(1<<(N-1)): | |
j = 0 | |
w = [(0, 0)] | |
for k in range(N-1): | |
j += (i>>k)&1 | |
w.append((k+1, j)) | |
wtab.append(w) | |
def show(): | |
for i, L in enumerate(M): | |
print(" " * (N-i) + (" ".join(L))) | |
def solve(): | |
if M[0][0] == "?": | |
# First word, write it down on left side | |
for w in words: | |
for i in range(N): | |
M[i][0] = w[i] | |
if solve(): | |
return True | |
for i in range(N): | |
M[i][0] = "?" | |
return False | |
elif M[1][1] == "?": | |
# Second word; consider words where the | |
# second character is bigger than the second | |
# character of first word and write them down | |
# on the right side. | |
for w in words: | |
if (w[1] > M[1][0]): | |
for i in range(1, N): | |
M[i][i] = w[i] | |
if solve(): | |
return True | |
for i in range(1, N): | |
M[i][i] = "?" | |
return False | |
else: | |
# General case; find a free cell and try every compatible | |
# letter that covers it. | |
free = None | |
for i in range(2, N): | |
for j in range(i): | |
if M[i][j] == "?": | |
free = (i, j) | |
break | |
if free: break | |
if free is None: | |
# No free cells, we solved the puzzle | |
return True | |
i, j = free | |
checks = [w for w in wtab if (i, j) in w] | |
for x in alpha - set(M[i]): | |
M[i][j] = x | |
for w in checks: | |
if (i, j) in w: | |
word = "".join(M[ii][jj] for (ii, jj) in w) | |
if "?" not in word: | |
if word not in words: | |
break | |
else: | |
ws = None | |
for ii in range(1, N): | |
if word[ii] != "?": | |
if ws is None: | |
ws = wsets[ii, word[ii]] | |
else: | |
ws = ws & wsets[ii, word[ii]] | |
if not ws: break | |
if not ws: break | |
else: | |
# Acceptable assignment, recurse | |
if solve(): | |
return True | |
M[i][j] = "?" | |
return False | |
def score(debug = False): | |
miss = 0 | |
for w in wtab: | |
word = "".join(M[i][j] for (i, j) in w) | |
if word not in words: | |
miss += 1 | |
if debug: | |
print("Checking " + word) | |
return miss | |
if solve(): | |
show() | |
score(True) | |
else: | |
print("No solution") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment