public
Created

  • Download Gist
boggle-impossible.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
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)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.