631. Design Excel Sum Formula

Design the basic function of Excel and implement the function of the sum formula.

Implement the Excel class:

• Excel(int height, char width) Initializes the object with the height and the width of the sheet. The sheet is an integer matrix mat of size height x width with the row index in the range [1, height] and the column index in the range ['A', width]. All the values should be zero initially.

• void set(int row, char column, int val) Changes the value at mat[row][column] to be val.

• int get(int row, char column) Returns the value at mat[row][column].

• int sum(int row, char column, List<String> numbers) Sets the value at mat[row][column] to be the sum of cells represented by numbers and returns the value at mat[row][column]. This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers[i] could be on the format:

  • "ColRow" that represents a single cell.

    • For example, "F7" represents the cell mat[7]['F'].

  • "ColRow1:ColRow2" that represents a range of cells. The range will always be a rectangle where "ColRow1" represent the position of the top-left cell, and "ColRow2" represents the position of the bottom-right cell.

    • For example, "B3:F7" represents the cells mat[i][j] for 3 <= i <= 7 and 'B' <= j <= 'F'.

Note: You could assume that there will not be any circular sum reference.

• For example, mat[1]['A'] == sum(1, "B") and mat[1]['B'] == sum(1, "A").

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.

Solution

The key is to define a suitable Class Cell to handle formula dependency with other Cell.

The relationship is kept in a Map<Cell, Integer>

Which means the Cell of key has value times impact on the current Cell.

For example.

1. cell[i][j]'s sum has denendencies with cell[j][k]~cell[j][k+1]

2. cell[i][j]'s sum has denendencies with cell[j][k]~cell[j+1][k]

-> Cell[j][k] will impact 2 times on the current Cell value.

We should keep in Map as (cell[j][k], 2)

class Excel {

    Cell[][] table;
    public Excel(int height, char width) {
        table = new Cell[height+1][width-'A'+1];
    }
    
    public void set(int row, char column, int val) {
        //if(row < 0 || row >= table.length || col < 0 || col >= table[0].length) return;
        if(table[row][column-'A'] == null) table[row][column-'A'] = new Cell(val);
        else {
            table[row][column-'A'].set(val);
        }
    }
    
    public int get(int row, char column) {
        //if(row < 0 || row >= table.length || col < 0 || col >= table[0].length) return -1;
        if(table[row][column-'A'] != null) return table[row][column-'A'].get();
        return 0;
    }
    
    public int sum(int row, char column, String[] numbers) {
        //if(row < 0 || row >= table.length || col < 0 || col >= table[0].length) return -1;
        if(table[row][column-'A'] == null) {
            table[row][column-'A'] = new Cell(numbers);
        }
        else {
            table[row][column-'A'].setFormula(numbers);
        }
        return table[row][column-'A'].get();
    }
    
    class Cell {
        Map<Cell, Integer> dependecies = new HashMap<>();
        int val;
        public Cell(int val){
            this.val = val;
        }
        
        public Cell(String[] numbers){
            setFormula(numbers);
        }
        
        
        public void set(int val){
            dependecies.clear();
            this.val = val;
        }
        
        public int get(){
            if(dependecies.keySet().size() == 0){
                return val;
            }else{
                int sum = 0;
                for(Cell cell : dependecies.keySet()){
                    sum += cell.get() * dependecies.get(cell);
                }
                return sum;                
            }
        }
        
        
        
        private int[] getPos(String number){
            int row = Integer.parseInt(number.substring(1));
            int col = number.charAt(0) - 'A';
            return new int[]{row, col};
        }
        
        private void addFormula(int row, int col){
            if(table[row][col] == null) table[row][col] = new Cell(0);
            dependecies.put(table[row][col], dependecies.getOrDefault(table[row][col], 0) + 1);
        }
        
        public void setFormula(String[] numbers){
            dependecies.clear();
            for(String number : numbers){
                if(number.indexOf(":") < 0){
                    int[] pos = getPos(number);
                    addFormula(pos[0], pos[1]);
                }else {
                    String[] nums = number.split(":");
                    int[] startCell = getPos(nums[0]);
                    int[] endCell = getPos(nums[1]);
                    for(int i = startCell[0]; i <= endCell[0]; i++) {
                        for(int j = startCell[1]; j <= endCell[1]; j++) {
                            addFormula(i, j);
                        }
                    }
                }
            }
        }
        
        
    }
}