Eugene Tan

import caesar
import euclid

def determinant22(matrix):
    """Return determinant of a 2x2 matrix

    >>> determinant22([[2, 4], [-2, 1]])
    10
    """
    return (matrix[0][0] * matrix[1][1]) - (matrix[1][0] * matrix[0][1])

def determinant33(matrix):
    """Return determinant of a 3x3 matrix

    >>> determinant33([[2, 4, 3], [6, 1, 5], [-2, 1, 3]])
    -92
    """
    m = matrix
    return (m[0][0] * m[1][1] * m[2][2]) + (m[0][1] * m[1][2] * m[2][0]) + (m[0][2] * m[1][0] * m[2][1]) \
        - (m[2][0] * m[1][1] * m[0][2]) - (m[2][1] * m[1][2] * m[0][0]) - (m[2][2] * m[1][0] * m[0][1])

def determinant(matrix):
    """Returns the determinant of a nxn matrix

    Doesn't work for matrices above 3x3

    >>> matrix = [[3, 2, 0, 1], [4, 0, 1, 2], [3, 0, 2, 1], [9, 2, 3, 1]]
    >>> determinant(matrix)
    Traceback (most recent call last):
        ...
    NameError: unsupported

    Should be 24
    """
    if len(matrix) == 1:
        return matrix[0][0]
    if len(matrix) == 2:
        return determinant22(matrix)
    if len(matrix) == 3:
        return determinant33(matrix)
    # can't figure out how to solve for nxn matrix
    raise NameError('unsupported')

def cofactor(matrix, i, j):
    """Find cofactor of a matrix
    >>> matrix = [[2, 4, 3], [6, 1, 5], [-2, 1, 3]]
    >>> cofactor(matrix, 1, 2)
    -10
    >>> len(matrix)
    3
    >>> len(matrix[0])
    3
    """
    m = [x[:] for x in matrix]
    del m[i]
    for row in m:
        del row[j]
    sign = 1 if (i + j) % 2 == 0 else -1
    return determinant(m) * sign

def transpose(matrix):
    """Transpose a matrix

    >>> transpose([[17, 17, 5], [21, 18, 21], [2, 2, 19]])
    [[17, 21, 2], [17, 18, 2], [5, 21, 19]]
    """
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            if j > i:
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    return matrix

def inv(key):
    """Find the inverse of a hill cipher key

    >>> inv([[17, 17, 5], [21, 18, 21], [2, 2, 19]])
    [[4, 9, 15], [15, 17, 6], [24, 0, 17]]
    >>> inv([[5, 8], [17, 3]])
    [[9, 2], [1, 15]]
    """
    d = euclid.eeuclid1(determinant(key) % 26, 26, False)
    m = len(key)
    if key == 0:
        return None
    b = []
    for i in range(m):
        row = []
        for j in range(m):
            row.append(int(cofactor(key, j, i) * d) % 26)
        b.append(row)
    return b

def hill(text, key, decrypt=False):
    """Hill cipher

    >>> key = [[17, 17, 5], [21, 18, 21], [2, 2, 19]]
    >>> plaintext = "PAYMOREMONEY"
    >>> ciphertext = hill(plaintext, key)
    >>> ciphertext
    'LNSHDLEWMTRW'
    >>> hill(ciphertext, key, True)
    'PAYMOREMONEY'
    """
    m = len(key)
    if decrypt:
        key = inv(key)
    l = caesar.alpha_to_int(text.replace(' ', 'a'))
    result = []
    for k in range(len(text) / m):
        p = l[0:m]
        l = l[m:]
        for i in range(m):
            c = 0
            for j in range(m):
                c += p[j] * key[i][j]
            result.append(c % 26)
    return ''.join(caesar.int_to_alpha(result)).upper()

if __name__ == '__main__':
    import doctest
    doctest.testmod()