matrix_traversal.py

# 2D array traversal
# These are not really for production use,
# they are more to demonstrate how to traverse 2-D arrays.
# Bruce Wernick
# 31 January 2022


from collections import deque
import itertools
from random import shuffle


def dfs(arr, start):
  """ depth first search.
  """
  rows = len(arr)
  cols = len(arr[0])
  steps = [(0,1), (-1,0), (0,-1), (1,0)]
  is_valid = lambda y,x: x >= 0 and x < cols and y >= 0 and y < rows
  def neighbors(cp):
    r, c = cp
    for step in steps:
      y = r + step[0]
      x = c + step[1]
      if is_valid(y, x):
        yield (y, x)
  result = []
  seen = []
  stack = deque()
  stack.append(start)
  while stack:
    cp = stack.pop()
    if cp in seen:
      continue
    r, c = cp
    result.append(arr[r][c])
    seen.append(cp)
    for np in neighbors(cp):
      if not np in seen:
        stack.append(np)
  return result


def flatten_array(arr):
  """ return 1D array in row order.
  """
  new_arr = []
  for row in arr:
    for cp in row:
      new_arr.append(cp)
  return new_arr


def reverse_array(arr):
  """ return 1D array in reversed row and col order.
  """
  new_arr = []
  for row in reversed(arr):
    for cp in reversed(row):
      new_arr.append(cp)
  return new_arr


def diag_pos_array(arr):
  """ return 1D array in positive diagonal order.
      a b c d
      e f g h   =>   a b e c f i d g j h k l
      i j k l
  """
  new_arr = []
  nr = len(arr)
  nc = len(arr[0])
  for k in range(nr+nc):
    for r in range(nr):
      for c in range(nc):
        if c + r == k - 1:
          new_arr.append(arr[r][c])
  return new_arr


def diag_neg_array(arr):
  """ return 1D array in negative diagonal order.
      a b c d
      e f g h   =>   d h c l g b k f a j e i
      i j k l
  """
  new_arr = []
  nr = len(arr)
  nc = len(arr[0])
  for k in range(nr+nc-1):
    for c in range(nc-1,-1,-1):
      for r in range(nr-1,-1,-1):
        if (r - c) + nc - 1 == k:
          new_arr.append(arr[r][c])
  return new_arr


def diag_back(arr):
  """ Traverse array diagonally.
      Starting from row=0, col=-1,
      Move diagonally from bottom-right to top-left
      Ending at row=-1, col=0
  """
  rows = len(arr)
  cols = len(arr[0])
  for k in range(rows + cols - 1):
    for c in range(cols-1, -1, -1):
      for r in range(rows-1, -1, -1):
        if (r - c) + cols - 1 == k:
          yield arr[r][c]


def shuffle_array(arr):
  """ return 1D array with shuffled elements.
  """
  new_arr = []
  for row in arr:
    for cp in row:
      new_arr.append(cp)
  shuffle(new_arr)
  return new_arr


# ---------------------------------------------------------------------

if __name__ == "__main__":

  arr = [['a', 'b', 'c', 'd'],
         ['e', 'f', 'g', 'h'],
         ['i', 'j', 'k', 'l']]


  a = dfs(arr, (0,0))
  print("dfs    : ", a)

  a = flatten_array(arr)
  print("flatten: ", a)

  a = reverse_array(arr)
  print("reverse: ", a)

  a = diag_pos_array(arr)
  print("diag + : ", a)

  a = diag_neg_array(arr)
  print("diag - : ", a)

  print("diagbak", end=":  [")
  for cp in diag_back(arr):
    print(cp, end=",")
  print("]")

  a = shuffle_array(arr)
  print("shuffle: ", a)