Skip to content
Create a gist now

Instantly share code, notes, and snippets.

Embed URL


Subversion checkout URL

You can clone with
Download ZIP
import collections
import datrie
import itertools
import math
import random
import string
Spot = collections.namedtuple('Spot', ['x', 'y'])
def create_board(cubes):
n = int(math.sqrt(len(cubes)))
letters = [random.choice(cube) for cube in cubes]
return [letters[i:i+n] for i in range(0, len(letters), n)]
def get_next_spots(board, spot, used_spots):
n = len(board)
a = (spot.x - 1, spot.x, spot.x + 1)
b = (spot.y - 1, spot.y, spot.y + 1)
spots = itertools.starmap(Spot, itertools.product(a, b))
return (s for s in spots if
0 <= s.x < n and 0 <= s.y < n and used_spots.count(s) == 0)
def check(board, spot, used_spots, index, word=u''):
if not index.has_keys_with_prefix(word):
return False
letter = board[spot.x][spot.y]
word += ('qu' if letter == 'q' else letter)
if word in index:
return True
used_spots = used_spots + [spot]
for next_spot in get_next_spots(board, spot, used_spots):
if check(board, next_spot, used_spots, index, word):
return True
return False
def build_trie(path):
trie = datrie.Trie(string.ascii_lowercase)
for word in file(path, 'r'):
trie[unicode(word.strip())] = True
return trie
def test_random_board(index, cubes):
board = create_board(cubes)
for x in range(0, 4):
for y in range(0, 4):
if check(board, Spot(x, y), [], index):
return True
return False
if __name__ == '__main__':
# Source: ( Note: q implies qu
cubes = """aaeegn elrtty aoottw abbjoo ehrtvw cimotu distty eiosst delrvy
achops himnqu eeinsu eeghnw affkps hlnnrz deilrx""".split()
trie = build_trie('ospd3.txt')
trials = 0
successes = 0
while True:
trials += 1
if not test_random_board(trie, cubes):
successes += 1
if trials % 10000 == 0:
print "Trials: {0}; Successes: {1}; Ratio: {2}".format(
trials, successes, float(successes)/trials)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.