sequences.py

def adj(A):
    labels = [[-1 for i in A[0]] for j in A]
    next_label = 0
    linked = {}

    for row in range(len(A)):
        for col in range(len(A[0])):
            nbrs = []
            not_nbrs=[]
            if row >= 1:
                if A[row-1][col] == A[row][col]:
                    nbrs.append(labels[row-1][col])
                else:
                    not_nbrs.append(labels[row-1][col])
            if col >= 1:
                if A[row][col-1] == A[row][col]:
                    nbrs.append(labels[row][col-1])
                else:
                    not_nbrs.append(labels[row-1][col])
            if len(nbrs) == 0:
                linked[next_label] = set([next_label])
                labels[row][col] = next_label
                next_label += 1
            else:
                labels[row][col] = min(nbrs)
                for label in nbrs:
                    linked[label] = linked[label].union( set(nbrs) )
    for row in range(len(A)):
        for col in range(len(A[0])):
            labels[row][col] = min(linked[labels[row][col]])
    adjs = {}
    def adj_connect(l1, l2, color1, color2):
        if l1 in adjs:
            adjs[l1].add((l2, color2))
        else:
            adjs[l1] = set([(l2, color2)])
        if l2 in adjs:
            adjs[l2].add((l1,color1))
        else:
            adjs[l2] = set([(l1,color1)])
    for row in range(len(A)):
        for col in range(len(A[0])):
            if row >= 1:
                if A[row-1][col] != A[row][col]:
                    adj_connect(labels[row-1][col], labels[row][col], A[row-1][col], A[row][col])
            if col >= 1:
                if A[row][col-1] != A[row][col]:
                    adj_connect(labels[row][col-1], labels[row][col], A[row][col-1], A[row][col])
    return adjs

class Queue:
    def __init__(self):
        self.__values = []
    def enqueue(self, value):
        self.__values.append(value)
    def dequeue(self):
        return self.__values.pop(0)
    def __len__(self):
        return len(self.__values)

def find_words(A):
    links = adj(A)
    nodes = {}
    nodes[0] = {"word":[],"alternatives":[]}
    visits = Queue()
    visits.enqueue(0)
    while len(visits)>0:
        current = visits.dequeue()
        prefix = nodes[current]["word"]
        children = links[current]
        for child in children:
            if not child[0] in nodes:
                visits.enqueue(child[0])
                nodes[child[0]] = {"word":prefix+[child[1]], "alternatives":[]}
            else:
                nodes[child[0]]["alternatives"].append(prefix+[child[1]])
    return nodes

def does_dominate(w1, w2):
    if len(w1) < len(w2):
        return False
    if len(w2) == 0:
        return True
    copy2 = w2
    for c in w1:
        if copy2[0] == c:
            copy2 = copy2[1:]
            if len(copy2) == 0:
                return True
    return False

def simple_sequences(nodes):
    sequences = []
    for id  in nodes:
        sequences.append(reduce(lambda x,y: str(x)+str(y), nodes[id]["word"],"" ))
    sequences.sort(cmp=lambda x,y: -cmp(len(x), len(y)))
    for i in range(len(sequences)):
        j = i
        while j < len(sequences)-1:
            j+=1
            w1 = sequences[i]
            w2 = sequences[j]
            if does_dominate(w1, w2):
                sequences.remove(w2)
    return sequences

A = [[1,3,2,4,1,1,0,2,1,0,0,0,3,3,1,0,0],[1,1,2,0,1,2,0,2,2,1,2,4,3,3,3,0,3],[4,4,1,2,1,3,0,3,2,1,4,0,2,0,2,3,0],[0,1,1,1,0,4,1,2,3,2,3,3,1,2,4,0,4],[0,0,3,4,1,4,2,0,3,1,0,3,3,2,0,1,0],[0,0,2,1,0,0,4,4,3,4,1,1,4,1,0,1,0],[1,2,1,3,3,2,2,2,0,4,2,1,2,2,4,0,4],[0,4,0,1,0,4,3,4,2,1,3,4,0,2,2,1,3],[3,0,4,4,3,2,4,3,3,4,4,1,1,0,1,4,1]]
nodes = find_words(A)
sequences = simple_sequences(nodes)
print sequences