#!/usr/bin/env python3
# coding: utf8

CIPHER =  [
        u'EKTAX', u'CEMEA', u'NVHEH', u'NEKLT', u'LUEEN', u'SAFUA', u'NTNTD', u'NDRDA',
        u'UBGES', u'IVLUR', u'UNTEA', u'IPPRN', u'TAEEE', u'RDROS', u'ILRRT', u'HNÄHA',
        u'BTNFV', u'BVETR', u'VLRDP', u'SUEUS', u'HIÄLI', u'GUAEO', u'HLVLE', u'TXFIE',
        u'HXDVD', u'NFNÄF', u'AX'
]

ALPHA_UC = u'ABCDEFGHIJKLMNOPQRSTUVWXYZÅÄÖ'

"""
EE = 3 (E = L | E = T)
PP = 1
RR = 1
"""

KEY = {
        u'E':u'S', # 17
        u'N':u'F', # 12
        u'A':u'L', # 10
        u'T':u'G', # 10
        u'R':u'P', # 9
        u'L':u'U', # 8
        u'U':u'E', # 8
        u'H':u'I', # 7
        u'V':u'L', # 7
        u'D':u'O', # 7
        u'I':u'A', # 6
        u'F':u'D', # 5
        u'X':u'K', # 4
        u'B':u'H', # 3
        u'Ä':u'T', # 3
        u'P':u'R', # 3
        u'K':u'M', # 2
        u'O':u'N', # 2
        u'G':u'C', # 2
        u'C':u'Ö', # 1
        u'M':u'Ä', # 1
        u'J':u'Å',
        u'Q':u'B',
        u'S':u'J',
        u'Y':u'Y',
        u'Z':u'X',
        u'Å':u'Z',
        u'Ö':u'Q',
}

def freqs(c,n=1) :
        fd={}
        for i in range(len(c)) :
                a = c[i:i+n]
                if len(a) < n : continue
                if a in fd.keys() :
                        fd[a] += 1
                else :
                        fd[a] = 1
        return fd

def substitute(k, c) :
        ns = u''
        for a in c :
                if a in k.keys() :
                        ns += k[a]
                else :
                        ns += a
        return ns

def rotate(k, c, alpha) :
        ns = u''
        for a in c :
                ns += alpha[ (alpha.index(a)+k) % len(alpha) ]
        return ns

def __idxs(s,v) :
        """ Gets the indicies in s where v occurs """
        idxs=[]
        for i in range(len(s)) :
                if s[i] == v : idxs.append(i)
        return idxs
def __matches(s,v,il) :
        """ Returns true if s[i] == v for i in il """
        for i in il :
                if s[i] != v : return False
        return True
def __matchpattern(a,b) :
        assert len(a) == len(b), 'Non-matching lengths'
        memA = []
        memB = []
        for i in range(len(a)) :
                if a[i] in memA :       # non-unique
                        il = __idxs(memA, a[i])
                        if not __matches(memB, b[i], il) :
                                return False
                else :                          # unique
                        if b[i] in memB :
                                return False
                memA.append(a[i])
                memB.append(b[i])
        return True

def wordfinder(c, w) :
        """ Extract all possible substrings """
        substrs=[]
        for i in range(len(c)) :
                if len(c[i:i+len(w)]) == len(w) :
                        substrs.append(c[i:i+len(w)])
        """ Match all substrings """
        matches=[]
        for substr in substrs :
                if __matchpattern(w, substr) :
                        matches.append(substr)
        return matches

ciphertext = ''.join(CIPHER)
print(wordfinder(ciphertext, 'UPPGIFT'))

#for i in range(len(ALPHA_UC)*2) :
#       print(rotate(i, ciphertext, list(ALPHA_UC)))
#       print('-----------------------------')
#ciphertext = substitute(KEY, ciphertext)
#print(ciphertext)

#print(wordfinder(ciphertext, 'LÖST'))
#fd = freqs(ciphertext, n=1)
#for k,v in zip(fd.keys(), fd.values()) :
#       print(u'%s => %d' % (k,v))