# problem2solution.py
#
# ICS H32 Fall 2025
# Exercise Set 6
# INSTRUCTOR SOLUTION


# This solution to reverse_transpose builds up a new list
# and returns it.  Because we need columns within rows,
# we build the new list's rows and then, within them, each
# row's columns.

def reverse_transpose(a: list[list[object]]) -> list[list[object]]:
    result = []

    rows = len(a)
    columns = len(a[0])

    for i in range(columns):
        result.append([])
        
        for j in range(rows):
            result[i].append(a[-j - 1][-i - 1])

    return result


# There are two ways to solve the calculate_sums problem.
# One is to calculate the sums at each step, i.e., when
# decided what the value of a[i][j] should be, add up all
# of the cells a[m][n] where m >= i and n >= j, then do all
# of that again for some other cell.
#
# Another way to solve the problem is to recognize that we
# can actually calculate it backward.  In other words, if
# we're trying to get the answer for a[i][j], it's a lot easier
# if we already have the answers for a[m][n] where m > i and
# n > j.  In that case, we can start with a[i][j], add
# a[i + 1][j] and a[i][j + 1] to that, then subtract
# a[i + 1][j + 1] (since we're counting it twice, in both
# a[i + 1][j] and a[i][j + 1]).
#
# The tricky part is that we need to consider that the cells
# a[i + 1][j] and a[i + 1][j + 1] may not always exist, but
# there may be cells in later "rows" that do, in which case
# we need to consider those instead.  That's the job of safe_index.

def calculate_sums(a: list[list[int]]) -> None:
    def safe_index(a: list[list[int]], i: int, j: int) -> int:
        while i < len(a):
            if j >= len(a[i]):
                i += 1
            else:
                return a[i][j]

        return 0
        
    for i in reversed(range(0, len(a))):
        for j in reversed(range(0, len(a[i]))):
            a[i][j] += safe_index(a, i + 1, j) + safe_index(a, i, j + 1) - safe_index(a, i + 1, j + 1)