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))) | |
random.shuffle(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: (http://goo.gl/PMfwS). 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