Instantly share code, notes, and snippets.

# RoboTeddy/boggle-impossible.py Created Apr 18, 2013

 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)