Matrices

Definition

Definition

The Matrices Algorithm involves operations on matrices, typically for tasks such as multiplication, addition, or finding determinants

Explanation

It works by iterating through corresponding elements of matrices, applying the defined operation to each pair, and storing the result in a new matrix. The process may involve nested loops for efficient traversal of matrix elements and appropriate mathematical operations based on the desired outcome

Guidance

• Matrix Addition
  • Iterate through each element of both matrices
  • Add corresponding elements and store the result in a new matrix
  • Ensure matrices have the same dimensions
• Matrix Multiplication
  • Iterate through rows of the first matrix
  • Iterate through columns of the second matrix
  • Multiply corresponding elements and sum them up for each resulting element of the new matrix
  • Ensure the number of columns in the first matrix matches the number of rows in the second matrix
• Finding Determinant
  • Implement the appropriate determinant calculation method (e.g., cofactor expansion, LU decomposition)
  • Ensure the matrix is square (i.e., same number of rows and columns)
  • Handle special cases like 2x2 matrices separately for efficiency

Tips

• ensure that the dimensions of the matrices are compatible for the intended operation
• optimize the algorithm by minimizing unnecessary iterations and operations
• implement error handling for invalid operations or incompatible matrix dimensions

Practice

Practice

matrix_addition(matrix1, matrix2):
  // Check if matrices have the same dimensions
  if dimensions of matrix1 != dimensions of matrix2:
    return "Matrices must have the same dimensions"
  else:
    // Initialize an empty matrix for the result
    result_matrix = empty matrix with dimensions of matrix1
    // Iterate through each element of the matrices
    for i from 0 to number of rows in matrix1:
      for j from 0 to number of columns in matrix1:
        // Add corresponding elements and store the result in the result matrix
        result_matrix[i][j] = matrix1[i][j] + matrix2[i][j]
    return result_matrix

matrix_multiplication(matrix1, matrix2):
  // Check if matrices can be multiplied (number of columns in matrix1 == number of rows in matrix2)
  if number of columns in matrix1 != number of rows in matrix2:
    return "Number of columns in matrix1 must be equal to number of rows in matrix2"
  else:
    // Initialize an empty matrix for the result
    result_matrix = empty matrix with dimensions (rows of matrix1) x (columns of matrix2)
    // Iterate through each row of matrix1
    for i from 0 to number of rows in matrix1:
      // Iterate through each column of matrix2
      for j from 0 to number of columns in matrix2:
        // Initialize the sum for the current element of the result matrix
        sum = 0
        // Iterate through each column of matrix1 (or each row of matrix2)
        for k from 0 to number of columns in matrix1:
          // Multiply corresponding elements and accumulate the sum
          sum += matrix1[i][k] * matrix2[k][j]
        // Store the sum as the resulting element in the result matrix
        result_matrix[i][j] = sum
    return result_matrix

find_determinant(matrix):
  // Check if the matrix is square
  if number of rows != number of columns:
    return "Matrix must be square"
  else if matrix is 2x2:
    // Calculate determinant for 2x2 matrix using the formula ad - bc
    return (matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0])
  else:
    // Implement determinant calculation method (e.g., cofactor expansion)

find_determinant(matrix):
  // Check if the matrix is square
  if number of rows != number of columns:
    return "Matrix must be square"
  else if matrix is 2x2:
    // Calculate determinant for 2x2 matrix using the formula ad - bc
    return (matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0])
  else:
    // Initialize determinant variable
    determinant = 0
    // Iterate through each column of the matrix
    for col from 0 to number of columns in matrix:
      // Calculate cofactor (submatrix) for the current element
      cofactor = submatrix obtained by removing the first row and current column
      // Calculate the sign of the current element's contribution to the determinant
      sign = (-1)^(row + col)  // Alternating signs for each element
      // Recursively calculate determinant using cofactor expansion
      determinant += sign * matrix[0][col] * find_determinant(cofactor)
    return determinant

Solution

function shape(m) {
  const shapes = [];
  let dimension = m;
  while (dimension && Array.isArray(dimension)) {
    shapes.push(dimension.length);
    dimension = (dimension.length && [...dimension][0]) || null;
  }
  return shapes;
}

func validateType(m [][]int) error {
	if m == nil || len(m) == 0 || len(m[0]) == 0 {
		return errors.New("Invalid matrix format")
	}
	return nil
}

func validate2D(m [][]int) error {
	if err := validateType(m); err != nil {
		return err
	}
	if len(m) != 2 {
		return errors.New("Matrix is not of 2D shape")
	}
	return nil
}

function validateSameShape(a, b) {
  validateType(a);
  validateType(b);

  const aShape = shape(a);
  const bShape = shape(b);

  if (aShape.length !== bShape.length) {
    throw new Error("Matrices have different dimensions");
  }

  while (aShape.length && bShape.length) {
    if (aShape.pop() !== bShape.pop()) {
      throw new Error("Matrices have different shapes");
    }
  }
}

function generate(mShape, fill) {
  const generateRecursively = (recShape, recIndices) => {
    if (recShape.length === 1) {
      return Array(recShape[0])
        .fill(null)
        .map((cellValue, cellIndex) => fill([...recIndices, cellIndex]));
    }
    const m = [];
    for (let i = 0; i < recShape[0]; i += 1) {
      m.push(generateRecursively(recShape.slice(1), [...recIndices, i]));
    }
    return m;
  };

  return generateRecursively(mShape, []);
}

function zeros(mShape) {
  return generate(mShape, () => 0);
}

const dot = (a, b) => {
  validate2D(a);
  validate2D(b);

  const aShape = shape(a);
  const bShape = shape(b);
  if (aShape[1] !== bShape[0]) {
    throw new Error("Matrices have incompatible shape for multiplication");
  }

  const outputShape = [aShape[0], bShape[1]];
  const c = zeros(outputShape);

  for (let bCol = 0; bCol < b[0].length; bCol += 1) {
    for (let aRow = 0; aRow < a.length; aRow += 1) {
      let cellSum = 0;
      for (let aCol = 0; aCol < a[aRow].length; aCol += 1) {
        cellSum += a[aRow][aCol] * b[aCol][bCol];
      }
      c[aRow][bCol] = cellSum;
    }
  }

  return c;
};

function walk(m, visit) {
  const recWalk = (recM, cellIndices) => {
    const recMShape = shape(recM);

    if (recMShape.length === 1) {
      for (let i = 0; i < recM.length; i += 1) {
        visit([...cellIndices, i], recM[i]);
      }
    }
    for (let i = 0; i < recM.length; i += 1) {
      recWalk(recM[i], [...cellIndices, i]);
    }
  };

  recWalk(m, []);
}

function getCellAtIndex(m, cellIndices) {
  let cell = m[cellIndices[0]];
  for (let dimIdx = 1; dimIdx < cellIndices.length - 1; dimIdx += 1) {
    cell = cell[cellIndices[dimIdx]];
  }
  return cell[cellIndices[cellIndices.length - 1]];
}

const updateCellAtIndex = (m, cellIndices, cellValue) => {
  let cell = m[cellIndices[0]];
  for (let dimIdx = 1; dimIdx < cellIndices.length - 1; dimIdx += 1) {
    cell = cell[cellIndices[dimIdx]];
  }
  cell[cellIndices[cellIndices.length - 1]] = cellValue;
};

function add(a, b) {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue + cellValue);
  });

  return result;
}

function mul(a, b) {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue * cellValue);
  });

  return result;
}

function sub(a, b) {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue - cellValue);
  });

  return result;
}

import java.util.ArrayList;
import java.util.List;

public class MatrixOperations {

  public static List<Integer> shape(Object m) {
    List<Integer> shapes = new ArrayList<>();
    Object dimension = m;
    while (dimension != null && dimension instanceof Object[]) {
      shapes.add(((Object[]) dimension).length);
      dimension = (((Object[]) dimension).length > 0) ? ((Object[]) dimension)[0] : null;
    }
    return shapes;
  }

  public static void validateType(Object[] m) {
    if (m == null || m.length == 0 || !(m[0] instanceof Object[])) {
      throw new IllegalArgumentException("Invalid matrix format");
    }
  }

  public static void validate2D(Object[] m) {
    validateType(m);
    int[] aShape = shape(m);
    if (aShape.length != 2) {
      throw new IllegalArgumentException("Matrix is not of 2D shape");
    }
  }

  public static void validateSameShape(Object a, Object b) {
    validateType(a);
    validateType(b);

    List<Integer> aShape = shape(a);
    List<Integer> bShape = shape(b);

    if (aShape.size() != bShape.size()) {
      throw new IllegalArgumentException("Matrices have different dimensions");
    }

    while (!aShape.isEmpty() && !bShape.isEmpty()) {
      if (!aShape.remove(aShape.size() - 1).equals(bShape.remove(bShape.size() - 1))) {
        throw new IllegalArgumentException("Matrices have different shapes");
      }
    }
  }

  public static Object generate(List<Integer> mShape, FillFunction fill) {
    return generateRecursively(mShape, new ArrayList<>(), fill);
  }

  private static Object generateRecursively(List<Integer> recShape, List<Integer> recIndices, FillFunction fill) {
    if (recShape.size() == 1) {
      Object[] array = new Object[recShape.get(0)];
      for (int i = 0; i < recShape.get(0); i++) {
        array[i] = fill.apply(recIndices, i);
      }
      return array;
    }

    List<Object> m = new ArrayList<>();
    for (int i = 0; i < recShape.get(0); i++) {
      m.add(generateRecursively(new ArrayList<>(recShape.subList(1, recShape.size())), appendToList(recIndices, i), fill));
    }
    return m.toArray();
  }

  private static List<Integer> appendToList(List<Integer> list, Integer element) {
    List<Integer> newList = new ArrayList<>(list);
    newList.add(element);
    return newList;
  }

  public static Object zeros(List<Integer> mShape) {
    return generate(mShape, (indices, cellIndex) -> 0);
  }

  public static Object dot(Object a, Object b) {
    validate2D(a);
    validate2D(b);

    List<Integer> aShape = shape(a);
    List<Integer> bShape = shape(b);
    if (!aShape.get(1).equals(bShape.get(0))) {
      throw new IllegalArgumentException("Matrices have incompatible shape for multiplication");
    }

    List<Integer> outputShape = new ArrayList<>();
    outputShape.add(aShape.get(0));
    outputShape.add(bShape.get(1));
    Object c = zeros(outputShape);

    for (int bCol = 0; bCol < ((Object[]) b)[0].length; bCol++) {
      for (int aRow = 0; aRow < ((Object[]) a).length; aRow++) {
        int cellSum = 0;
        for (int aCol = 0; aCol < ((Object[]) a)[aRow].length; aCol++) {
          cellSum += (int) (((Object[]) a)[aRow][aCol]) * ((int[][]) b)[aCol][bCol];
        }
        ((int[][]) c)[aRow][bCol] = cellSum;
      }
    }
    return c;
  }

  public static void walk(Object m, VisitFunction visit) {
    recWalk(m, new ArrayList<>(), visit);
  }

  private static void recWalk(Object recM, List<Integer> cellIndices, VisitFunction visit) {
    List<Integer> recMShape = shape(recM);

    if (recMShape.size() == 1) {
      for (int i = 0; i < ((Object[]) recM).length; i++) {
        visit.apply(appendToList(cellIndices, i), ((Object[]) recM)[i]);
      }
    }

    for (int i = 0; i < ((Object[]) recM).length; i++) {
      recWalk(((Object[]) recM)[i], appendToList(cellIndices, i), visit);
    }
  }

  public static Object getCellAtIndex(Object m, List<Integer> cellIndices) {
    Object cell = ((Object[]) m)[cellIndices.get(0)];
    for (int dimIdx = 1; dimIdx < cellIndices.size() - 1; dimIdx++) {
      cell = ((Object[]) cell)[cellIndices.get(dimIdx)];
    }
    return ((Object[]) cell)[cellIndices.get(cellIndices.size() - 1)];
  }

  public static void updateCellAtIndex(Object m, List<Integer> cellIndices, Object cellValue) {
    Object cell = ((Object[]) m)[cellIndices.get(0)];
    for (int dimIdx = 1; dimIdx < cellIndices.size() - 1; dimIdx++) {
      cell = ((Object[]) cell)[cellIndices.get(dimIdx)];
    }
    ((Object[]) cell)[cellIndices.get(cellIndices.size() - 1)] = cellValue;
  }

  public static Object add(Object a, Object b) {
    validateSameShape(a, b);
    Object result = zeros(shape(a));

    walk(a, (cellIndices, cellValue) -> {
      updateCellAtIndex(result, cellIndices, cellValue);
    });

    walk(b, (cellIndices, cellValue) -> {
      Object currentCellValue = getCellAtIndex(result, cellIndices);
      updateCellAtIndex(result, cellIndices, (int) currentCellValue + (int) cellValue);
    });

    return result;
  }

  public static Object mul(Object a, Object b) {
    validateSameShape(a, b);
    Object result = zeros(shape(a));

    walk(a, (cellIndices, cellValue) -> {
      updateCellAtIndex(result, cellIndices, cellValue);
    });

    walk(b, (cellIndices, cellValue) -> {
      Object currentCellValue = getCellAtIndex(result, cellIndices);
      updateCellAtIndex(result, cellIndices, (int) currentCellValue * (int) cellValue);
    });

    return result;
  }

  public static Object sub(Object a, Object b) {
    validateSameShape(a, b);
    Object result = zeros(shape(a));

    walk(a, (cellIndices, cellValue) -> {
      updateCellAtIndex(result, cellIndices, cellValue);
    });

    walk(b, (cellIndices, cellValue) -> {
      Object currentCellValue = getCellAtIndex(result, cellIndices);
      updateCellAtIndex(result, cellIndices, (int) currentCellValue - (int) cellValue);
    });

    return result;
  }

  private static void validateType(Object matrix) {
    if (!(matrix instanceof Object[])) {
      throw new IllegalArgumentException("Input is not a matrix");
    }
  }

  private static void validate2D(Object matrix) {
    if (!(matrix instanceof Object[]) || !(((Object[]) matrix)[0] instanceof Object[])) {
      throw new IllegalArgumentException("Input is not a 2D matrix");
    }
  }

  interface FillFunction {

    Object apply(List<Integer> indices, int cellIndex);
  }

  interface VisitFunction {

    void apply(List<Integer> cellIndices, Object cellValue);
  }
}

function shape(m) {
  const shapes = [];
  let dimension = m;
  while (dimension && Array.isArray(dimension)) {
    shapes.push(dimension.length);
    dimension = (dimension.length && [...dimension][0]) || null;
  }
  return shapes;
}

function validateType(m) {
  if (!m || !Array.isArray(m) || !Array.isArray(m[0])) {
    throw new Error("Invalid matrix format");
  }
}

function validate2D(m) {
  validateType(m);
  const aShape = shape(m);
  if (aShape.length !== 2) {
    throw new Error("Matrix is not of 2D shape");
  }
}

function validateSameShape(a, b) {
  validateType(a);
  validateType(b);

  const aShape = shape(a);
  const bShape = shape(b);

  if (aShape.length !== bShape.length) {
    throw new Error("Matrices have different dimensions");
  }

  while (aShape.length && bShape.length) {
    if (aShape.pop() !== bShape.pop()) {
      throw new Error("Matrices have different shapes");
    }
  }
}

function generate(mShape, fill) {
  const generateRecursively = (recShape, recIndices) => {
    if (recShape.length === 1) {
      return Array(recShape[0])
        .fill(null)
        .map((cellValue, cellIndex) => fill([...recIndices, cellIndex]));
    }
    const m = [];
    for (let i = 0; i < recShape[0]; i += 1) {
      m.push(generateRecursively(recShape.slice(1), [...recIndices, i]));
    }
    return m;
  };

  return generateRecursively(mShape, []);
}

function zeros(mShape) {
  return generate(mShape, () => 0);
}

const dot = (a, b) => {
  validate2D(a);
  validate2D(b);

  const aShape = shape(a);
  const bShape = shape(b);
  if (aShape[1] !== bShape[0]) {
    throw new Error("Matrices have incompatible shape for multiplication");
  }

  const outputShape = [aShape[0], bShape[1]];
  const c = zeros(outputShape);

  for (let bCol = 0; bCol < b[0].length; bCol += 1) {
    for (let aRow = 0; aRow < a.length; aRow += 1) {
      let cellSum = 0;
      for (let aCol = 0; aCol < a[aRow].length; aCol += 1) {
        cellSum += a[aRow][aCol] * b[aCol][bCol];
      }
      c[aRow][bCol] = cellSum;
    }
  }

  return c;
};

function walk(m, visit) {
  const recWalk = (recM, cellIndices) => {
    const recMShape = shape(recM);

    if (recMShape.length === 1) {
      for (let i = 0; i < recM.length; i += 1) {
        visit([...cellIndices, i], recM[i]);
      }
    }
    for (let i = 0; i < recM.length; i += 1) {
      recWalk(recM[i], [...cellIndices, i]);
    }
  };

  recWalk(m, []);
}

function getCellAtIndex(m, cellIndices) {
  let cell = m[cellIndices[0]];
  for (let dimIdx = 1; dimIdx < cellIndices.length - 1; dimIdx += 1) {
    cell = cell[cellIndices[dimIdx]];
  }
  return cell[cellIndices[cellIndices.length - 1]];
}

const updateCellAtIndex = (m, cellIndices, cellValue) => {
  let cell = m[cellIndices[0]];
  for (let dimIdx = 1; dimIdx < cellIndices.length - 1; dimIdx += 1) {
    cell = cell[cellIndices[dimIdx]];
  }
  cell[cellIndices[cellIndices.length - 1]] = cellValue;
};

function add(a, b) {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue + cellValue);
  });

  return result;
}

function mul(a, b) {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue * cellValue);
  });

  return result;
}

function sub(a, b) {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue - cellValue);
  });

  return result;
}

import kotlin.math.pow

fun shape(m: Any): List<Int> {
    val shapes = mutableListOf<Int>()
    var dimension: Any? = m
    while (dimension != null && dimension is Array<*>) {
        shapes.add((dimension as Array<*>).size)
        dimension = if ((dimension as Array<*>).isNotEmpty()) (dimension as Array<*>)[0] else null
    }
    return shapes
}

fun validateType(m: Array<*>?) {
    if (m == null || !m.isArray() || !m[0].isArray()) {
        throw IllegalArgumentException("Invalid matrix format")
    }
}

fun validate2D(m: Array<*>) {
    validateType(m)
    val aShape = shape(m)
    if (aShape.size != 2) {
        throw IllegalArgumentException("Matrix is not of 2D shape")
    }
}

fun validateSameShape(a: Any, b: Any) {
    validateType(a)
    validateType(b)

    val aShape = shape(a)
    val bShape = shape(b)

    if (aShape.size != bShape.size) {
        throw IllegalArgumentException("Matrices have different dimensions")
    }

    while (aShape.isNotEmpty() && bShape.isNotEmpty()) {
        if (aShape.removeAt(aShape.size - 1) != bShape.removeAt(bShape.size - 1)) {
            throw IllegalArgumentException("Matrices have different shapes")
        }
    }
}

fun generate(mShape: List<Int>, fill: (List<Int>) -> Any): Any {
    fun generateRecursively(recShape: List<Int>, recIndices: List<Int>): Any {
        return if (recShape.size == 1) {
            Array(recShape[0]) { cellIndex ->
                fill(recIndices + cellIndex)
            }
        } else {
            val m = mutableListOf<Any>()
            for (i in 0 until recShape[0]) {
                m.add(generateRecursively(recShape.slice(1 until recShape.size), recIndices + i))
            }
            m.toTypedArray()
        }
    }

    return generateRecursively(mShape, emptyList())
}

fun zeros(mShape: List<Int>): Any {
    return generate(mShape) { 0 }
}

fun dot(a: Any, b: Any): Any {
    validate2D(a)
    validate2D(b)

    val aShape = shape(a)
    val bShape = shape(b)
    if (aShape[1] != bShape[0]) {
        throw IllegalArgumentException("Matrices have incompatible shape for multiplication")
    }

    val outputShape = listOf(aShape[0], bShape[1])
    val c = zeros(outputShape)

    for (bCol in 0 until (b as Array<*>)[0].size) {
        for (aRow in (a as Array<*>).indices) {
            var cellSum = 0
            for (aCol in (a[aRow] as Array<*>).indices) {
                cellSum += (a[aRow] as Array<*>)[aCol] as Int * (b[aCol] as IntArray)[bCol]
            }
            (c as Array<*>)[aRow][bCol] = cellSum
        }
    }

    return c
}

fun walk(m: Any, visit: (List<Int>, Any) -> Unit) {
    fun recWalk(recM: Any, cellIndices: List<Int>) {
        val recMShape = shape(recM)

        if (recMShape.size == 1) {
            for (i in (recM as Array<*>).indices) {
                visit(cellIndices + i, recM[i]!!)
            }
        }
        for (i in (recM as Array<*>).indices) {
            recWalk(recM[i]!!, cellIndices + i)
        }
    }

    recWalk(m, emptyList())
}

fun getCellAtIndex(m: Any, cellIndices: List<Int>): Any {
    var cell: Any = (m as Array<*>)[cellIndices[0]]!!
    for (dimIdx in 1 until cellIndices.size - 1) {
        cell = (cell as Array<*>)[cellIndices[dimIdx]]!!
    }
    return (cell as Array<*>)[cellIndices.last()]!!
}

fun updateCellAtIndex(m: Any, cellIndices: List<Int>, cellValue: Any) {
    var cell: Any = (m as Array<*>)[cellIndices[0]]!!
    for (dimIdx in 1 until cellIndices.size - 1) {
        cell = (cell as Array<*>)[cellIndices[dimIdx]]!!
    }
    (cell as Array<*>)[cellIndices.last()] = cellValue
}

fun add(a: Any, b: Any): Any {
    validateSameShape(a, b)
    val result = zeros(shape(a))

    walk(a) { cellIndices, cellValue ->
        updateCellAtIndex(result, cellIndices, cellValue)
    }

    walk(b) { cellIndices, cellValue ->
        val currentCellValue = getCellAtIndex(result, cellIndices) as Int
        updateCellAtIndex(result, cellIndices, currentCellValue + cellValue as Int)
    }

    return result
}

fun mul(a: Any, b: Any): Any {
    validateSameShape(a, b)
    val result = zeros(shape(a))

    walk(a) { cellIndices, cellValue ->
        updateCellAtIndex(result, cellIndices, cellValue)
    }

    walk(b) { cellIndices, cellValue ->
        val currentCellValue = getCellAtIndex(result, cellIndices) as Int
        updateCellAtIndex(result, cellIndices, currentCellValue * cellValue as Int)
    }

    return result
}

fun sub(a: Any, b: Any): Any {
    validateSameShape(a, b)
    val result = zeros(shape(a))

    walk(a) { cellIndices, cellValue ->
        updateCellAtIndex(result, cellIndices, cellValue)
    }

    walk(b) { cellIndices, cellValue ->
        val currentCellValue = getCellAtIndex(result, cellIndices) as Int
        updateCellAtIndex(result, cellIndices, currentCellValue - cellValue as Int)
    }

    return result
}

private fun validateType(matrix: Any) {
    if (matrix !is Array<*>) {
        throw IllegalArgumentException("Input is not a matrix")
    }
}

private fun validate2D(matrix: Any) {
    if (!(matrix is Array<*>) || !(matrix[0] is Array<*>)) {
        throw IllegalArgumentException("Input is not a 2D matrix")
    }
}

def shape(m):
    shapes = []
    dimension = m
    while dimension and isinstance(dimension, list):
        shapes.append(len(dimension))
        dimension = dimension[0] if len(dimension) else None
    return shapes

def validate_type(m):
    if m is None or not isinstance(m, list) or not isinstance(m[0], list):
        raise ValueError("Invalid matrix format")


def validate_2d(m):
    validate_type(m)
    a_shape = shape(m)
    if len(a_shape) != 2:
        raise ValueError("Matrix is not of 2D shape")

def validateSameShape(a, b):
    validateType(a)
    validateType(b)

    aShape = shape(a)
    bShape = shape(b)

    if len(aShape) != len(bShape):
        raise ValueError("Matrices have different dimensions")

    while aShape and bShape:
        if aShape.pop() != bShape.pop():
            raise ValueError("Matrices have different shapes")


def generate(mShape, fill):
    def generateRecursively(recShape, recIndices):
        if len(recShape) == 1:
            return [fill(recIndices + [cellIndex]) for cellIndex in range(recShape[0])]
        m = []
        for i in range(recShape[0]):
            m.append(generateRecursively(recShape[1:], recIndices + [i]))
        return m

    return generateRecursively(mShape, [])


def zeros(mShape):
    return generate(mShape, lambda _: 0)


def dot(a, b):
    validate2D(a)
    validate2D(b)

    aShape = shape(a)
    bShape = shape(b)
    if aShape[1] != bShape[0]:
        raise ValueError("Matrices have incompatible shape for multiplication")

    outputShape = [aShape[0], bShape[1]]
    c = zeros(outputShape)

    for bCol in range(len(b[0])):
        for aRow in range(len(a)):
            cellSum = 0
            for aCol in range(len(a[aRow])):
                cellSum += a[aRow][aCol] * b[aCol][bCol]
            c[aRow][bCol] = cellSum

    return c


def walk(m, visit):
    def recWalk(recM, cellIndices):
        recMShape = shape(recM)

        if len(recMShape) == 1:
            for i in range(len(recM)):
                visit(cellIndices + [i], recM[i])
        for i in range(len(recM)):
            recWalk(recM[i], cellIndices + [i])

    recWalk(m, [])


def getCellAtIndex(m, cellIndices):
    cell = m[cellIndices[0]]
    for dimIdx in range(1, len(cellIndices) - 1):
        cell = cell[cellIndices[dimIdx]]
    return cell[cellIndices[-1]]


def updateCellAtIndex(m, cellIndices, cellValue):
    cell = m[cellIndices[0]]
    for dimIdx in range(1, len(cellIndices) - 1):
        cell = cell[cellIndices[dimIdx]]
    cell[cellIndices[-1]] = cellValue


def add(a, b):
    validateSameShape(a, b)
    result = zeros(shape(a))

    def update(result, cellIndices, cellValue):
        updateCellAtIndex(result, cellIndices, cellValue)

    walk(a, lambda cellIndices, cellValue: update(result, cellIndices, cellValue))
    walk(b, lambda cellIndices, cellValue: update(result, cellIndices, cellValue + getCellAtIndex(result, cellIndices)))

    return result


def mul(a, b):
    validateSameShape(a, b)
    result = zeros(shape(a))

    def update(result, cellIndices, cellValue):
        updateCellAtIndex(result, cellIndices, cellValue)

    walk(a, lambda cellIndices, cellValue: update(result, cellIndices, cellValue))
    walk(b, lambda cellIndices, cellValue: update(result, cellIndices, cellValue * getCellAtIndex(result, cellIndices)))

    return result


def sub(a, b):
    validateSameShape(a, b)
    result = zeros(shape(a))

    def update(result, cellIndices, cellValue):
        updateCellAtIndex(result, cellIndices, cellValue)

    walk(a, lambda cellIndices, cellValue: update(result, cellIndices, cellValue))
    walk(b, lambda cellIndices, cellValue: update(result, cellIndices, getCellAtIndex(result, cellIndices) - cellValue))

    return result

use std::error::Error;

fn shape(m: &Vec<Vec<i32>>) -> Vec<usize> {
    let mut shapes = Vec::new();
    let mut dimension = m;
    while let Some(inner) = dimension.first() {
        shapes.push(inner.len());
        if let Some(inner_dim) = inner.get(0) {
            dimension = inner;
        } else {
            dimension = &vec![];
        }
    }
    shapes
}

fn validate_type<T>(m: &Vec<Vec<T>>) {
    if m.is_empty() || m[0].is_empty() {
        panic!("Invalid matrix format");
    }
}

fn validate_2d<T>(m: &Vec<Vec<T>>) {
    validate_type(m);
    let a_shape = shape(m);
    if a_shape.len() != 2 {
        panic!("Matrix is not of 2D shape");
    }
}

fn validate_same_shape(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Result<(), Box<dyn Error>> {
    validate_type(a)?;
    validate_type(b)?;

    let a_shape = shape(a);
    let b_shape = shape(b);

    if a_shape.len() != b_shape.len() {
        return Err("Matrices have different dimensions".into());
    }

    for (a_dim, b_dim) in a_shape.iter().zip(b_shape.iter()) {
        if a_dim != b_dim {
            return Err("Matrices have different shapes".into());
        }
    }

    Ok(())
}

fn generate<F>(m_shape: &[usize], fill: F) -> Vec<Vec<i32>>
where
    F: Fn(Vec<usize>) -> i32,
{
    fn generate_recursively<F>(
        rec_shape: &[usize],
        rec_indices: Vec<usize>,
        fill: F,
    ) -> Vec<Vec<i32>>
    where
        F: Fn(Vec<usize>) -> i32,
    {
        if rec_shape.len() == 1 {
            return (0..rec_shape[0])
                .map(|cell_index| fill([&rec_indices[..], &[cell_index]].concat()))
                .collect();
        }
        let mut m = Vec::new();
        for i in 0..rec_shape[0] {
            m.push(generate_recursively(
                &rec_shape[1..],
                [&rec_indices[..], &[i]].concat(),
                &fill,
            ));
        }
        m
    }

    generate_recursively(m_shape, Vec::new(), fill)
}

fn zeros(m_shape: &[usize]) -> Vec<Vec<i32>> {
    generate(m_shape, |_| 0)
}

fn dot(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Result<Vec<Vec<i32>>, Box<dyn Error>> {
    validate_2d(a)?;
    validate_2d(b)?;

    let a_shape = shape(a);
    let b_shape = shape(b);

    if a_shape[1] != b_shape[0] {
        return Err("Matrices have incompatible shape for multiplication".into());
    }

    let output_shape = vec![a_shape[0], b_shape[1]];
    let c = zeros(&output_shape);

    for b_col in 0..b[0].len() {
        for a_row in 0..a.len() {
            let mut cell_sum = 0;
            for a_col in 0..a[a_row].len() {
                cell_sum += a[a_row][a_col] * b[a_col][b_col];
            }
            c[a_row][b_col] = cell_sum;
        }
    }

    Ok(c)
}

fn walk<F>(m: &Vec<Vec<i32>>, visit: F)
where
    F: Fn(Vec<usize>, i32),
{
    fn rec_walk<F>(rec_m: &Vec<Vec<i32>>, cell_indices: Vec<usize>, visit: F)
    where
        F: Fn(Vec<usize>, i32),
    {
        let rec_m_shape = shape(rec_m);

        if rec_m_shape.len() == 1 {
            for i in 0..rec_m.len() {
                visit([cell_indices.clone(), vec![i]].concat(), rec_m[i][0]);
            }
        }
        for i in 0..rec_m.len() {
            rec_walk(&rec_m[i], [cell_indices.clone(), vec![i]].concat(), &visit);
        }
    }

    rec_walk(m, Vec::new(), visit);
}

fn get_cell_at_index(m: &Vec<Vec<i32>>, cell_indices: &[usize]) -> i32 {
    let mut cell = &m[cell_indices[0]];
    for dim_idx in 1..cell_indices.len() - 1 {
        cell = &cell[cell_indices[dim_idx]];
    }
    cell[cell_indices[cell_indices.len() - 1]]
}

fn update_cell_at_index(m: &mut Vec<Vec<i32>>, cell_indices: &[usize], cell_value: i32) {
    let mut cell = &mut m[cell_indices[0]];
    for dim_idx in 1..cell_indices.len() - 1 {
        cell = &mut cell[cell_indices[dim_idx]];
    }
    cell[cell_indices[cell_indices.len() - 1]] = cell_value;
}

fn add(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Result<Vec<Vec<i32>>, Box<dyn Error>> {
    validate_same_shape(a, b)?;

    let mut result = zeros(&shape(a));

    walk(a, |cell_indices, cell_value| {
        update_cell_at_index(&mut result, &cell_indices, cell_value);
    });

    walk(b, |cell_indices, cell_value| {
        let current_cell_value = get_cell_at_index(&result, &cell_indices);
        update_cell_at_index(&mut result, &cell_indices, current_cell_value + cell_value);
    });

    Ok(result)
}

fn mul(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Result<Vec<Vec<i32>>, Box<dyn Error>> {
    validate_same_shape(a, b)?;

    let mut result = zeros(&shape(a));

    walk(a, |cell_indices, cell_value| {
        update_cell_at_index(&mut result, &cell_indices, cell_value);
    });

    walk(b, |cell_indices, cell_value| {
        let current_cell_value = get_cell_at_index(&result, &cell_indices);
        update_cell_at_index(&mut result, &cell_indices, current_cell_value * cell_value);
    });

    Ok(result)
}

fn sub(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Result<Vec<Vec<i32>>, Box<dyn Error>> {
    validate_same_shape(a, b)?;

    let mut result = zeros(&shape(a));

    walk(a, |cell_indices, cell_value| {
        update_cell_at_index(&mut result, &cell_indices, cell_value);
    });

    walk(b, |cell_indices, cell_value| {
        let current_cell_value = get_cell_at_index(&result, &cell_indices);
        update_cell_at_index(&mut result, &cell_indices, current_cell_value - cell_value);
    });

    Ok(result)
}

fn validate_type(a: &Vec<Vec<i32>>) -> Result<(), Box<dyn Error>> {
    if !a.iter().all(|inner| inner.iter().all(|&x| x == 0 || x == 1)) {
        return Err("Matrix contains invalid elements".into());
    }
    Ok(())
}

fn validate_2d(a: &Vec<Vec<i32>>) -> Result<(), Box<dyn Error>> {
    if a.iter().any(|inner| inner.len() != a[0].len()) {
        return Err("Matrix rows have different lengths".into());
    }
    Ok(())
}

function shape(m: any): number[] {
  const shapes: number[] = [];
  let dimension = m;
  while (dimension && Array.isArray(dimension)) {
    shapes.push(dimension.length);
    dimension = (dimension.length && [...dimension][0]) || null;
  }
  return shapes;
}

function validateType<T>(m: T[][]): void {
  if (!m || !Array.isArray(m) || !Array.isArray(m[0])) {
    throw new Error("Invalid matrix format");
  }
}

function validate2D<T>(m: T[][]): void {
  validateType(m);
  const aShape = shape(m);
  if (aShape.length !== 2) {
    throw new Error("Matrix is not of 2D shape");
  }
}

function validateSameShape(a: any, b: any): void {
  validateType(a);
  validateType(b);

  const aShape = shape(a);
  const bShape = shape(b);

  if (aShape.length !== bShape.length) {
    throw new Error("Matrices have different dimensions");
  }

  while (aShape.length && bShape.length) {
    if (aShape.pop() !== bShape.pop()) {
      throw new Error("Matrices have different shapes");
    }
  }
}

function generate(mShape: number[], fill: () => number): any {
  const generateRecursively = (
    recShape: number[],
    recIndices: number[],
  ): any => {
    if (recShape.length === 1) {
      return Array(recShape[0])
        .fill(null)
        .map((cellValue, cellIndex) => fill([...recIndices, cellIndex]));
    }
    const m: any[] = [];
    for (let i = 0; i < recShape[0]; i += 1) {
      m.push(generateRecursively(recShape.slice(1), [...recIndices, i]));
    }
    return m;
  };

  return generateRecursively(mShape, []);
}

function zeros(mShape: number[]): any {
  return generate(mShape, () => 0);
}

const dot = (a: any, b: any): any => {
  validate2D(a);
  validate2D(b);

  const aShape = shape(a);
  const bShape = shape(b);
  if (aShape[1] !== bShape[0]) {
    throw new Error("Matrices have incompatible shape for multiplication");
  }

  const outputShape = [aShape[0], bShape[1]];
  const c = zeros(outputShape);

  for (let bCol = 0; bCol < b[0].length; bCol += 1) {
    for (let aRow = 0; aRow < a.length; aRow += 1) {
      let cellSum = 0;
      for (let aCol = 0; aCol < a[aRow].length; aCol += 1) {
        cellSum += a[aRow][aCol] * b[aCol][bCol];
      }
      c[aRow][bCol] = cellSum;
    }
  }

  return c;
};

function walk(
  m: any,
  visit: (cellIndices: number[], cellValue: number) => void,
): void {
  const recWalk = (recM: any, cellIndices: number[]): void => {
    const recMShape = shape(recM);

    if (recMShape.length === 1) {
      for (let i = 0; i < recM.length; i += 1) {
        visit([...cellIndices, i], recM[i]);
      }
    }
    for (let i = 0; i < recM.length; i += 1) {
      recWalk(recM[i], [...cellIndices, i]);
    }
  };

  recWalk(m, []);
}

function getCellAtIndex(m: any, cellIndices: number[]): number {
  let cell = m[cellIndices[0]];
  for (let dimIdx = 1; dimIdx < cellIndices.length - 1; dimIdx += 1) {
    cell = cell[cellIndices[dimIdx]];
  }
  return cell[cellIndices[cellIndices.length - 1]];
}

const updateCellAtIndex = (
  m: any,
  cellIndices: number[],
  cellValue: number,
): void => {
  let cell = m[cellIndices[0]];
  for (let dimIdx = 1; dimIdx < cellIndices.length - 1; dimIdx += 1) {
    cell = cell[cellIndices[dimIdx]];
  }
  cell[cellIndices[cellIndices.length - 1]] = cellValue;
};

function add(a: any, b: any): any {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue + cellValue);
  });

  return result;
}

function mul(a: any, b: any): any {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue * cellValue);
  });

  return result;
}

function sub(a: any, b: any): any {
  validateSameShape(a, b);
  const result = zeros(shape(a));

  walk(a, (cellIndices, cellValue) => {
    updateCellAtIndex(result, cellIndices, cellValue);
  });

  walk(b, (cellIndices, cellValue) => {
    const currentCellValue = getCellAtIndex(result, cellIndices);
    updateCellAtIndex(result, cellIndices, currentCellValue - cellValue);
  });

  return result;
}