Matrix

fast exponentiation

If we are doing b*(n-1), normally we think of multiplying b many many times. But in math,

if exponent is even
b^n= b^(2k) = (b^k)^2
and if its odd
b^n = (b^k)^2 * b.

Lets take
3^13 for example.

b^13 = b^8 b^4 b^1

if u notice, this can be represented in Binary (1101). At 1 bit, we need to multiply by b but if 0 bit, we dont multiply. But we still need to square the base at each step.

this is log n time, optimised from n time

def fast_pow(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        base *= base
        exponent //= 2
    return result

# Example usage
print(fast_pow(3, 13))  # Output: 1594323

matrix multiplication

Conditions for Multiplication:

For two matrices, A and B, to be multiplied (in the order A × B), the number of columns in the first matrix (A) must be equal to the number of rows in the second matrix (B).

• If matrix A has dimensions $m \times n$ (m rows and n columns)
• And matrix B has dimensions $p \times q$ (p rows and q columns)

Then, A can be multiplied by B if and only if $n = p$. The resulting matrix will have dimensions $m \times q$.

The Multiplication Process:

Let's say we have:

Matrix A (m x n):

Matrix B (n x q):

The resulting matrix C (m x q), where $C = A \times B$, will have elements $c_{ij}$ calculated as follows:

$c_{ij} = \sum_{k=1}^{n} a_{ik} \cdot b_{kj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}$

In simpler terms, to find the element in the $i$-th row and $j$-th column of the resulting matrix C, you take the $i$-th row of matrix A and the $j$-th column of matrix B, multiply their corresponding elements, and then sum up those products. This is the dot product of the row and the column.

Why do we need this?

Well When you perform the matrix multiplication, the count of the character at index j in the new vector will be the sum of the counts of all characters i in the original vector that can transform into j.

To perform t transformations, you need to apply this transformation represented by matrix M a total of t times. Instead of doing t separate matrix multiplications, which would be inefficient, the code uses matrix exponentiation.

    rows1 = len(mat1)
    cols1 = len(mat1[0]) if rows1 > 0 else 0
    rows2 = len(mat2)
    cols2 = len(mat2[0]) if rows2 > 0 else 0

    if cols1 != rows2:
        print(f"Error: Cannot multiply matrices with dimensions {rows1}x{cols1} and {rows2}x{cols2}. Number of columns in the first matrix must equal the number of rows in the second matrix.")
        return None

    result = [[0 for _ in range(cols2)] for _ in range(rows1)]

    for i in range(rows1):  # Iterate through rows of mat1
        for j in range(cols2):  # Iterate through columns of mat2
            for k in range(cols1):  # Iterate through columns of mat1 (and rows of mat2)
                result[i][j] += mat1[i][k] * mat2[k][j]
    return result

rightwise

imagine we are on the rightmost bit. Once we process it, we cross that bit off and the next digit on the left becomes our rightmost bit.

In every iteration of the loop, regardless of whether n was odd or even, we square the matrix.
If matrix initially holds M, then in the first iteration it becomes M^2 -> M^4 -> M^8 and so on. It is like multiplying base to the exponent.

90 degree clockwise

zip(*box[::-1])

90 degree anti clockwise

zip(*[row[::-1] for row in box])