LeetCode 631 - Design Excel Sum Formula

https://leetcode.com/problems/design-excel-sum-formula

Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:

Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from 'A' to 'Z'. It represents that the width is the number of characters from 'A' to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from 'A'.

void Set(int row, char column, int val): Change the value at C(row, column) to be val.

int Get(int row, char column): Return the value at C(row, column).

int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.

numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, "F7" represents the cell at (7, F).

If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.

Example 1:

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

Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0

Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4. 
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4

Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6

Note:

1. You could assume that there won't be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
2. The test cases are using double-quotes to represent a character.
3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

/**
 * Your Excel object will be instantiated and called as such:
 * Excel obj = new Excel(H, W);
 * obj.set(r,c,v);
 * int param_2 = obj.get(r,c);
 * int param_3 = obj.sum(r,c,strs);
 */

https://leetcode.com/articles/design-excel-sum-formula/

Firstly, we can note that once a formula is applied to any cell in excel, let's say $C1 = C2 + C3$, if any change is made to $C2$ or $C3$, the result to be put into $C1$ needs to be evaluated again based on the new values of $C2$ and $C3$. Further, suppose some other cell, say $D2$ is also dependent on $C1$ due to some prior formula applied to $D2$. Then, when any change is made to, say, $C2$, we re-evaluate $C1$'s value. Furhter, since $D2$ is dependent on $C1$, we need to re-evaluate $D2$'s value as well.

Thus, whenver, we make any change to any cell, $x$, we need to determine the cells which are dependent on $x$, and update these cells, and further determine the cells which are dependent on the changed cells and so on. We can assume that no cycles are present in the formulas, i.e. Any cell's value won't directly or indirectly be dependent on its own value.

But, while doing these set of evaluations of the cells to determine their updated values, we need to update the cells in such an order that the cell on which some other cell is dependent is always evaluated prior to the cell which is dependent on the former cell. In order to do so, we can view the dependence between the cells in the form of a dependency graph, which can be a Directed Graph. Since, no cycles are allowed between the formulas, the graph reduces to a Directed Acyclic Graph. Now, to solve the problem of evaluating the cells in the required order, we can make use of a very well known method specifically used for such problems in Directed Acyclic Graphs, known as the Topological Sorting.

in the case of a topological sort, we can't print a node until all the nodes on which it is dependent have already been printed. To solve this problem, we make use of a temporary stack. We do the traversals in the same manner as in DFS, but we don’t print the current vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Note that a vertex is pushed to stack only when all of its adjacent(dependent) vertices (and their adjacent(dependent) vertices and so on) are already in stack. At the end, we print the contents of the stack. Thus, we obtain the correct ordering of the vertices

• set takes $O\big((r*c)^2\big)$ time. Here, $r$ and $c$ refer to the number of rows and columns in the current Excel Form. There can be a maximum of $O(r*c)$formulas for an Excel Form with $r$ rows and $c$ columns. For each formula, $r*c$ time will be needed to find the dependent nodes. Thus, in the worst case, a total of $O\big((r*c)^2\big)$ will be needed.
• sum takes $O\big((r*c)^2 + 2*r*c*l\big)$ time. Here, $l$ refers to the number of elements in the the list of strings used for obtaining the cells required for the current sum. In the worst case, the expansion of each such element requires $O(r*c)$ time, leading to $O(l*r*c)$ time for expanding $l$ such elements. After doing the expansion, calculate_sum itself requires $O(l*r*c)$ time for traversing over the required elements for obtaining the sum. After this, we need to update all the dependent cells, which requires the use of set which itself requires $O\big((r*c)^2\big)$ time.
• get takes $O(1)$ time.
• The space required will be $O\big((r*c)^2\big)$ in the worst case. $O(r*c)$ space will be required for the Excel Form itself. For each cell in this form, the $cells$list can contain $O(r*c)$ cells.

    Formula[][] Formulas;
    class Formula {
        Formula(HashMap < String, Integer > c, int v) {
            val = v;
            cells = c;
        }
        HashMap < String, Integer > cells;
        int val;
    }
    Stack < int[] > stack = new Stack < > ();
    public Excel(int H, char W) {
        Formulas = new Formula[H][(W - 'A') + 1];
    }

    public int get(int r, char c) {
        if (Formulas[r - 1][c - 'A'] == null)
            return 0;
        return Formulas[r - 1][c - 'A'].val;
    }
    public void set(int r, char c, int v) {
        Formulas[r - 1][c - 'A'] = new Formula(new HashMap < String, Integer > (), v);
        topologicalSort(r - 1, c - 'A');
        execute_stack();
    }

    public int sum(int r, char c, String[] strs) {
        HashMap < String, Integer > cells = convert(strs);
        int summ = calculate_sum(r - 1, c - 'A', cells);
        set(r, c, summ);
        Formulas[r - 1][c - 'A'] = new Formula(cells, summ);
        return summ;
    }

    public void topologicalSort(int r, int c) {
        for (int i = 0; i < Formulas.length; i++)
            for (int j = 0; j < Formulas[0].length; j++)
                if (Formulas[i][j] != null && Formulas[i][j].cells.containsKey("" + (char)('A' + c) + (r + 1))) {
                    topologicalSort(i, j);
                }
        stack.push(new int[] {r,c});
    }

    public void execute_stack() {
        while (!stack.isEmpty()) {
            int[] top = stack.pop();
            if (Formulas[top[0]][top[1]].cells.size() > 0)
                calculate_sum(top[0], top[1], Formulas[top[0]][top[1]].cells);
        }
    }

    public HashMap < String, Integer > convert(String[] strs) {
        HashMap < String, Integer > res = new HashMap < > ();
        for (String st: strs) {
            if (st.indexOf(":") < 0)
                res.put(st, res.getOrDefault(st, 0) + 1);
            else {
                String[] cells = st.split(":");
                int si = Integer.parseInt(cells[0].substring(1)), ei = Integer.parseInt(cells[1].substring(1));
                char sj = cells[0].charAt(0), ej = cells[1].charAt(0);
                for (int i = si; i <= ei; i++) {
                    for (char j = sj; j <= ej; j++) {
                        res.put("" + j + i, res.getOrDefault("" + j + i, 0) + 1);
                    }
                }
            }
        }
        return res;
    }

    public int calculate_sum(int r, int c, HashMap < String, Integer > cells) {
        int sum = 0;
        for (String s: cells.keySet()) {
            int x = Integer.parseInt(s.substring(1)) - 1, y = s.charAt(0) - 'A';
            sum += (Formulas[x][y] != null ? Formulas[x][y].val : 0) * cells.get(s);
        }
        Formulas[r][c] = new Formula(cells, sum);
        return sum;
    }

http://code.bitjoy.net/2017/06/25/leetcode-design-excel-sum-formula/

本题要求设计一个简单的Excel表格求和功能。主要实现三个接口：

• Get(int row, char column)，获取坐标为(row,column)的cell的值
• Set(int row, char column, int val)，把坐标为(row,column)的值设置为val
• Sum(int row, char column, List of Strings : numbers)，numbers表示一系列求和公式，把公式计算结果填入坐标(row,column)中，并且当公式中的格子更新时，该公式计算出来的值也要更新。

本题的难点是，如果C3=A1+B2，如果更新了B2，下次get(C3)时，得到的结果也必须是用更新过的B2的值。而且还有可能A1的值也是用某个公式计算出来的。

当时比赛的时候，有一些思路，但是逻辑不是很清晰，后来参考这个题解，逻辑很清楚。

Excel包含两个成员，二维矩阵matrix表示一个excel表格，hashmap formula的key为某个格子，value为该格子对应的求和公式。如果某个格子的值是实实在在的值，不是用公式计算出来的，则不在这个hashmap中。

• 对于get，如果坐标不在formula中，说明该格子是实实在在的值，直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
• 对于set，直接把matrix对应坐标设置为value就好，注意的是，因为set之后就变成了实实在在的值，所以要清空formula中该格子的公式（如果有的话）。
• 对于sum，计算字符串公式的值，把结果填入对应的格子，然后在formula中设置该格子的公式。

问题的难点是怎样对一个公式求值。说穿了其实就是不停的递归调用get函数，因为get函数如果该cell没有在formula中，则返回实实在在的值，否则递归计算formula的值。想象一下，就是不停的对一个坐标递归求值，直到不能递归时，返回matrix中的值，然后递归累加起来。想明白了其实很简单，代码注意把公共的计算部分抽象出来

http://www.cnblogs.com/grandyang/p/7170238.html

这道题让我们设计Excel表格的求和公式，Excel表格想必大家都用过，还是比较熟悉的，这里让我们对单元格进行求和运算。由于这道题里要求二维数组的局部和，而且又会经常更新数组的值，博主第一反应觉得应该用之前那题Range Sum Query 2D - Mutable中的树状数组来做，结果哼哼哧哧的写完后，发现下面这个test case没通过：

["Excel","sum","set","get"]
[[3,"C"],[1,"A",["A2"]],[2,"A",1],[1,"A"]]
Expected:
[null,0,null,1]

仔细分析一下发现，这个case先把A2的值赋给了A1，此时A1和A2都是0，然后给A2赋值为1，求A1的值。大家的第一印象肯定是觉得A1还是0啊，其实在Excel中，相当于已经把A1和A2关联起来了，只要A2点值发生了改变，A1的值也会跟着变，所以A1的值此时也为1。而树状数组的主要功能的优化区域和的计算速度，并没有建立关联的步骤，难怪不能通过OJ呢。这道题标记为Hard还是有道理的，我们要模拟出Excel表中的这种关联方式，这里参考的是yupinglu大神的帖子，首先我们肯定需要一个二维数组mat来保存数据，然后需要一个map来建立单元格和区域和之间的映射，这里的区域和就是sum函数中的字符串数组表示的内容，可参见题目中的例子，有可能单个单元格或者多个。

我们来看set函数，如果我们改变了某个单元格的内容，那么如果作为结果单元格，那么对应的链接就会断开。比如我们有三个单元格A1, B1, C1，我们设置的关联是A1 + B1 = C1，那么我们改变A1和B1的值都是OK的，C1的值会自动更新。但如果我们改变了C1的值，那么这个关联就不复存在了，Excel中也是这样的。所以我们在改变某个单元格的时候，要将其的关联删除。

我们再来看get函数，我们在获取某个单元格的值的时候，一定要先看其有没有和其他单元格关联，如果有的话，要重新计算一下关联，有可能关联的单元格的值已经发生改变了，那么当前作为结果单元格的值也需要改变；如果该单元格没有任何关联，那么就直接从数组mat中取值即可。

最后看本题的难点sum函数，要根据关联格求出结果格的值，首先这个字符串数组可能有多个字符串，每个字符串有两个可能，一种是单个的单元格，一种是两个单元格中间用冒号隔开。那么我们需要分情况讨论，区别这两种情况的方法就是看冒号是否存在，如果不存在，就说明只有一个单元格，我们将其数字和字母都提取出来，调用get函数，将该位置的值加入结果res中；如果冒号存在，我们根据冒号的位置，分别将两个单元格的字母和数字提取出来，然后遍历这两个单元格之间所有的单元格，调用get函数并将返回值加入结果res中。这个遍历相加的过程可能可以用树状数组来优化，但由于这不是此题的考察重点，所以直接遍历就OK。最后别忘了建立目标单元格和区域字符串数组之间的映射，并返回结果res即可。

http://blog.csdn.net/u014688145/article/details/73718744
set的时候需要把当前的公式清零，而在get的时候，map中存在它的求和公式，则先更新，再返回。接着在sum中记录所有的公式即可。

int[][] table; Map<String, String[]> mem = new HashMap<>(); public Excel(int H, char W) { table = new int[H][W - 'A' + 1]; } public void set(int r, char c, int v) { table[r-1][c - 'A'] = v; if (mem.containsKey(""+c+r)) mem.remove(""+c+r); } public int get(int r, char c) { if(mem.containsKey(""+r+c)) sum(r,c,mem.get(""+r+c)); return table[r - 1][c - 'A']; } public int sum(int r, char c, String[] strs) { mem.put(""+c+r,strs); int sum = 0; for (int i = 0; i < strs.length; ++i){ String cell = strs[i]; if (cell.contains(":")){ String[] cells = cell.split(":"); char topC = cells[0].charAt(0); char botC = cells[1].charAt(0); int topR = 0; for (int j = 1; j < cells[0].length(); ++j) topR = topR * 10 + cells[0].charAt(j) - '0'; int botR = 0; for (int j = 1; j < cells[1].length(); ++j) botR = botR * 10 + cells[1].charAt(j) - '0'; for (int k = topR; k <= botR; ++k){ for (char l = topC; l <= botC; ++l){ sum += get(k, l); } } } else{ char col = cell.charAt(0); int row = 0; for (int j = 1; j < cell.length(); ++j) row = row * 10 + cell.charAt(j) - '0'; sum += get(row, col); } } return table[r-1][c - 'A'] = sum; }
https://discuss.leetcode.com/topic/93812/c-3-ms-concise-and-easy-to-understand


1 Sum(1, "A", ["A1","B1"]);
2 Sum(1, "A", ["B1","C1"]);
Sum(1, "B", ["A1"]);
I think this shoud be illegal and need to defend it.

X. https://discuss.leetcode.com/topic/94526/a-different-solution-in-java-beats-80

http://bookshadow.com/weblog/2017/06/25/leetcode-design-excel-sum-formula/

观察者模式（Observer Pattern）

为单元格cell注册观察者列表target（关心cell变化的单元格），被观察者列表source（变化会影响到cell的单元格）

利用字典values存储每个单元格的值

单元格之间的观察者关系为图结构，当某一单元格发生变化时，其所有观察者节点均会依次发生变化

对于某单元格触发的观察者单元格更新操作，可以利用BFS实现

当执行set操作时，清除单元格的被观察者列表，然后更新其观察者列表的值

当执行sum操作时，清除单元格的被观察者列表，然后重新注册其被观察者，并更新其被观察者的观察关系，最后更新其观察者列表的值

https://discuss.leetcode.com/topic/93738/java-oop-style-easy-to-understand

It could be optimized by

• caching Expressions results
• marking Expressions as dirty on 'set' operations
• not recalculating cached results if expression is not dirty (doesn't depend on dirty expressions)