RoboTeddy / boggle-impossible.py

Created April 18, 2013


    
    View boggle-impossible.py 
  
  
      boggle-impossible.py
    
    
        Raw
      
    
    File suppressed. Click to show.
  
  
            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)