Design Excel Sum Formula

Problem Statement

The task involves designing a basic version of an Excel-like program through an Excel class, in which users can set values to cells, retrieve values, and compute the sum of ranges of cells, similar to Excel's SUM function. The class initializes with dimensions specified by the user and simulates a spreadsheet. Each cell in this virtual spreadsheet can be accessed via a combination of column letter and row number.

Methods implemented in this class include:

1. Initialization: The spreadsheet (a 2D matrix) is initialized with default values of zero.
2. Setting a Value: Assigns a specific value to a cell.
3. Getting a Value: Retrieves the value of a specific cell.
4. Computing a Sum: Computes the sum of values within specified cells or ranges, where each range is a rectangle defined by its upper-left and bottom-right cells.

Note that the sum formula in a cell persists unless it is directly overridden by a new value or a new sum range.

Examples

Example 1

Input:

["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]

Output:

[null, null, 4, null, 6]

Explanation:

Excel excel = new Excel(3, "C");
// construct a 3*3 2D array with all zero.
// A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
excel.set(1, "A", 2);
// set mat[1]["A"] to be 2.
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
excel.sum(3, "C", ["A1", "A1:B2"]); // return 4
// set mat[3]["C"] to be the sum of value at mat[1]["A"] and the values sum of the rectangle range whose top-left cell is mat[1]["A"] and bottom-right cell is mat[2]["B"].
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
excel.set(2, "B", 2);
// set mat[2]["B"] to be 2. Note mat[3]["C"] should also be changed.
// A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6
excel.get(3, "C"); // return 6

Constraints

• 1 <= height <= 26
• 'A' <= width <= 'Z'
• 1 <= row <= height
• 'A' <= column <= width
• -100 <= val <= 100
• 1 <= numbers.length <= 5
• numbers[i] has the format "ColRow" or "ColRow1:ColRow2".
• At most 100 calls will be made to set, get, and sum.

Approach and Intuition

• Understanding Data Structure: The Excel sheet is internally represented as a 2D matrix with cells accessible through coordinates derived from column letters ('A' to width) and row numbers (1 to height). This matrix initializes with all cells set to zero.

• Handling Cell References in Methods:

  • For direct cell references like "F7", the method computes access by converting 'F' to its corresponding matrix index (5 if 'A' is 0-indexed) and uses the number directly minus one if 1-indexed (6 for '7').
  • For range references like "B3:F7", it decodes the starting and ending coordinates and iterates over the specified range to perform operations like sum calculations.

• Dynamic and Reactive Sum Calculation:

  • Method sum doesn’t just compute and forget. It assigns the computed sum to the target cell, making the sum formula reactive. When any cell within the range specified in a sum changes due to the set method, the sum should be recalculated and updated, though how this dynamic aspect is managed isn't specified in depth here but is crucial for a fully functional implementation.

• Design Considerations:

  • Ensuring the operations respect the boundaries of matrix dimensions.
  • Efficiently managing updates for dynamic sum ranges, possibly using additional data structures to monitor dependencies.

• Operational Constraints:

  • The task limits the height and width within typical Excel sheet bounds, ensuring operations are manageable.
  • The values and the operations are restricted, such as no more than 100 operations, which reduces the complexity concerning performance overhead.
  • No circular references are allowed for sum calculations which simplifies the dependency management and ensures that the sum calculations terminate.

By combining these strategies, the implementation of the Excel class effectively mirrors some of the basic functionalities of spreadsheet software, particularly focusing on cell management and dynamic sum calculations.

Solutions

public class Spreadsheet {
    SheetCell[][] sheetCells;
    class SheetCell {
        HashMap<String, Integer> dependentCells;
        int value;

        SheetCell(HashMap<String, Integer> references, int val) {
            value = val;
            dependentCells = references;
        }
    }

    Stack<int[]> updateStack = new Stack<>();

    public Spreadsheet(int height, char width) {
        sheetCells = new SheetCell[height][(width - 'A') + 1];
    }

    public int getValue(int row, char column) {
        if (sheetCells[row - 1][column - 'A'] == null)
            return 0;
        return sheetCells[row - 1][column - 'A'].value;
    }

    public void setValue(int row, char column, int value) {
        sheetCells[row - 1][column - 'A'] = new SheetCell(new HashMap<>(), value);
        sortDependencies(row - 1, column - 'A');
        processStack();
    }

    public int computeSum(int row, char column, String[] ranges) {
        HashMap<String, Integer> refs = parseRanges(ranges);
        int total = sumValues(row - 1, column - 'A', refs);
        setValue(row, column, total);
        sheetCells[row - 1][column - 'A'] = new SheetCell(refs, total);
        return total;
    }

    public void sortDependencies(int row, int col) {
        for (int i = 0; i < sheetCells.length; i++) {
            for (int j = 0; j < sheetCells[0].length; j++) {
                if (sheetCells[i][j] != null && sheetCells[i][j].dependentCells.containsKey("" + (char)('A' + col) + (row + 1))) {
                    sortDependencies(i, j);
                }
            }
        }
        updateStack.push(new int[]{row, col});
    }

    public void processStack() {
        while (!updateStack.isEmpty()) {
            int[] top = updateStack.pop();
            if (sheetCells[top[0]][top[1]].dependentCells.size() > 0)
                sumValues(top[0], top[1], sheetCells[top[0]][top[1]].dependentCells);
        }
    }

    public HashMap<String, Integer> parseRanges(String[] ranges) {
        HashMap<String, Integer> result = new HashMap<>();
        for (String range: ranges) {
            if (range.indexOf(":") < 0)
                result.put(range, result.getOrDefault(range, 0) + 1);
            else {
                String[] bounds = range.split(":");
                int startRow = Integer.parseInt(bounds[0].substring(1)), endRow = Integer.parseInt(bounds[1].substring(1));
                char startCol = bounds[0].charAt(0), endCol = bounds[1].charAt(0);
                for (int i = startRow; i <= endRow; i++) {
                    for (char j = startCol; j <= endCol; j++) {
                        result.put("" + j + i, result.getOrDefault("" + j + i, 0) + 1);
                    }
                }
            }
        }
        return result;
    }

    public int sumValues(int row, int col, HashMap<String, Integer> refs) {
        int sum = 0;
        for (String key: refs.keySet()) {
            int x = Integer.parseInt(key.substring(1)) - 1, y = key.charAt(0) - 'A';
            sum += (sheetCells[x][y] != null ? sheetCells[x][y].value : 0) * refs.get(key);
        }
        sheetCells[row][col] = new SheetCell(refs, sum);
        return sum;
    }
}