scrabble.py

#!/usr/bin/python
import itertools 
import networkx as nx
import random

class Node(object):
    def __key__(self):
        return str(self.line) + str(self.prev) + str(self.data) + str(self.next)

    def __init__(self, char, prev, next, line):
        self.data = char
        self.prev = prev
        self.next = next
        self.line = line
    
    def __repr__(self):
        #return "data:%s, prev:%s, next:%s, line:%d" % (self.data, str(self.prev), str(self.next), self.line)
        return "%s" % (self.data)
    
    def __eq__(self, other):
        return self.data == other.data

    def __ne__(self, other):
        return self.data <> other.data
    
    def __hash__(self):
        return hash(self.__key__())


scores = {'A':1,
          'B':3,
          'C':3,
          'D':2,
          'E':1,
          'F':4,
          'G':2,
          'H':4,
          'I':1,
          'J':8,
          'K':5,
          'L':1,
          'M':3,
          'N':1,
          'O':1,
          'P':3,
          'Q':10,
          'R':1,
          'S':1,
          'T':1,
          'U':1,
          'V':4,
          'W':4,
          'X':10,
          'Y':4,
          'Z':10,
          ' ':0
          }

tiles  = {'A':9,
          'B':2,
          'C':2,
          'D':4,
          'E':12,
          'F':2,
          'G':3,
          'H':2,
          'I':9,
          'J':1,
          'K':1,
          'L':1,
          'M':2,
          'N':6,
          'O':8,
          'P':2,
          'Q':1,
          'R':6,
          'S':4,
          'T':6,
          'U':4,
          'V':2,
          'W':2,
          'X':1,
          'Y':2,
          'Z':1,
          ' ':2
          }

bag = ''.join([x*tiles[x] for x in tiles])
bag_without_blank_tiles = ''.join([x*tiles[x] for x in tiles if tiles[x]!=' '])

board = [['.']*15 for i in xrange(15)]

rack = random.sample(bag_without_blank_tiles, 7)

x=7
y=7

square=(x,y)

def printBoard():
    for i in board:
        print ' '.join(i)

def nextRightSquare(square):
    return square[0]+1, square[1]

def nextLeftSquare(square):
    return square[0]-1, square[1]

def nextTopSquare(square):
    return square[0], square[1]-1

def nextTopSquare(square):
    return square[0], square[1]+1

def isVacant(square):
    return getLetter(square)=='.'

def getLetter(square):
    return board[square[0]][square[1]]

def windows(iterable, length=2, overlap=0): 
    it = iter(iterable) 
    results = list(itertools.islice(it, length)) 
    while len(results) == length: 
        yield results 
        results = results[length-overlap:] 
        results.extend(itertools.islice(it, length-overlap)) 
    if results: 
        yield results 

ngdawg = nx.DiGraph()

for each_word in open('sowpods.txt').read().strip().split('\n')[:10]:
    ngdawg.add_edge(1,each_word[0],char=each_word[0])
    for each_pair in windows(each_word, overlap=1):
        if len(each_pair)==2:
            ngdawg.add_edge(each_pair[0], each_pair[1],char=each_pair[1])
            if ngdawg.has_edge(each_pair[0], 0):
                ngdawg.add_edge(0, each_pair[1], char=each_pair[1])
    ngdawg.add_edge(each_word[-1],0,char=each_word[-1])    


'''    
print "nodes:"
print ngdawg.nodes()
print "edges:"
print ngdawg.edges(data=True)
'''

g = nx.DiGraph()
head = Node(1, None, None, 0)
tail = Node(0, None, None, 0)

for i,each_word in enumerate(open('list.txt').read().strip().split('\n')[:10]):
    first_letter = Node(each_word[0],1,each_word[1],0)
    g.add_edge(head, first_letter, char=each_word[0])
    second_letter = Node(each_word[1], each_word[0], each_word[2], 0)
    g.add_edge(first_letter, second_letter, char=each_word[1])    
    for each_pair in windows(each_word, overlap=3, length=4):
        if len(each_pair)==4:
            from_node = Node(each_pair[1], each_pair[0], each_pair[2], 0)
            to_node = Node(each_pair[2], each_pair[1], each_pair[3], 0)            
            g.add_edge(from_node, to_node,char=each_pair[1])
    print each_word
    from_node = Node(each_word[-2], each_word[-3], each_word[-1], 0)
    to_node = Node(each_word[-1], each_word[-2], 0, 0)            
    g.add_edge(from_node, to_node, char=each_word[-2])
    g.add_edge(to_node, tail, char=each_word[-1])

print "nodes:"
print g.nodes()
print "edges:"
print g.edges(data=True)


def extendRight(partialWord, node, square):
    if isVacant(square):
        if isTerminalNode(node):
            return partialWord
        for letter in get_next(node):
            if letter in rack:
                rack.remove(letter)
                square = nextRightSquare(square)
                partialWord += letter
                extendRight(partialWord, letter, square)
                rack.append(letter)
    else:
        letter = getLetter(square)
        letter = get_next(node)
        partialWord += letter
        square = nextRightSquare(square)
        extendRight(partialWord, letter, square)
        
def leftPart(partialWord, node, limit):
    extendRight(partialWord, node, anchorSquare)
    if limit > 0:
        for letter in get_next():
            if letter in rack:
                rack.remove(letter)
                partialWord += letter
                leftPart(partialWord, node, limit-1)
                rack.append(letter)
'''                
def get_next(node,L={}):
    edges = ngdawg.edges(node)
    if not node:
        return L
    if not edges:
        return L[node]
    else:        
        for i in sorted([x[1] for x in edges], reverse=True):
            for j in [x[1] for x in ngdawg.edges(node)]:
                L.setdefault(node, []).append(j)
                #print "node:"+ node + ",j:" + str(j)
            return get_next(i,L)

        
def edges(node):
    return sorted([x[1] for x in ngdawg.edges(node)], reverse=True)

print get_next('a')
print get_next('d',{})
'''
def find_all_paths(dawg, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if start == 0:
        return []
    if not dawg.has_node(start):
        return []
    paths = []
    for each_node in dawg.neighbors(start):
        if each_node not in path:
            newpaths = find_all_paths(dawg, each_node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths
            
print find_all_paths(ngdawg, 'A', 'E')
    
from networkx import DiGraph
gx = DiGraph()
gx.add_node(Node('A', 'C', 'R',1))
gx.add_node(Node('A', 'C', 'T',2))
print gx.nodes()
gx.has_node(Node('A', 'C', 'T',2))

from matplotlib import pyplot
nx.draw(g)
pyplot.savefig('path2.png')