## LeetCode 289. Game of Life

Problem:

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution:

boring

```public class Solution {
int[][] myBoard, newBoard;
public void gameOfLife(int[][] board) {
myBoard = board;
newBoard = new int[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
update(i, j);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
board[i][j] = newBoard[i][j];
}
}
}

private void update(int i, int j) {
int live = countNeighbors(i, j);
if (myBoard[i][j] > 0) {
if (live < 2) newBoard[i][j] = 0;
else if (live < 4) newBoard[i][j] = 1;
else newBoard[i][j] = 0;
}
else if (live == 3) newBoard[i][j] = 1;
}

private int countNeighbors(int i, int j) {
int count = 0;
if (i - 1 >= 0) {
if (myBoard[i-1][j] > 0) count++;
if (j - 1 >= 0) {
if (myBoard[i-1][j-1] > 0) count++;
}
if (j + 1 < myBoard[0].length) {
if (myBoard[i-1][j+1] > 0) count++;
}
}
if (i + 1 < myBoard.length) {
if (myBoard[i+1][j] > 0) count++;
if (j - 1 >= 0) {
if (myBoard[i+1][j-1] > 0) count++;
}
if (j + 1 < myBoard[0].length) {
if (myBoard[i+1][j+1] > 0) count++;
}
}
if (j - 1 >= 0) {
if (myBoard[i][j-1] > 0) count++;
}
if (j + 1 < myBoard[0].length) {
if (myBoard[i][j+1] > 0) count++;
}
return count;
}
}
```

## LeetCode 154. Find Minimum in Rotated Sorted Array II

Problem:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution:

At first I did not see the array may contain duplicates, which really bugged me.

```public class Solution {
int[] myNums;
public int findMin(int[] nums) {
myNums = nums;
if (nums.length < 10) {
// avoid trivial cases
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < min) min = nums[i];
}
return min;
}
return getMin(0, nums.length - 1);
}

private int getMin(int start, int end) {
int mid = (start + end) / 2;
int left = start + (end - start) / 4;
int right = end - (end - start) / 4;
if (start > myNums.length - 1) return myNums[myNums.length - 1];
if (end < 0) return myNums[0];
if (end - start < 1) return myNums[start];
if (myNums[left] <= myNums[mid] && myNums[mid] <= myNums[right]) {
int opt1 = getMin(start, left - 1);
int opt2 = getMin(right + 1, end);
return Math.min(opt1, opt2);
}
else if (myNums[left] > myNums[mid]) {
return getMin(left+1, mid);
}
else if (myNums[mid] > myNums[right]) {
return getMin(mid+1, right);
}
return 0;
}
}
```

## Day 5 Week 4 on JFLAP

Today has been a looooong day. I started by doing easy things: restructuring code in `grammarEditor.js` and fixed a minor user interface bug in `slrGoTo.html`. Then I read the ten pages of code for SLR Parsing and was able to alert if the grammar is not SLR(1). A conflict table is generated background to store all of conflict options. After another hour I managed to allow users to pass the “check” by the program if they fill in one of the options of the conflicts. At night I was finally able to add a menu for users to click in order to resolv conflicts. The entry in the matrix is highlighted if and only if 1)the user got it wrong and the entry has a conflict. 2)the user chose to finish automatically and the entry has a conflict.

For some reason the OpenDSA textbook was not working for FAEditor this afternoon when we tried showing it to professor Rodger. However, it recovered itself magically tonight. The failing reason was some 404 error on a JSON file. How weird.

Next week I hope to enable dragging of the nodes in FAEditor and other user interfaces. I will also test other html files in OpenDSA textbooks. If I have time, I will also look into grammar transforming to regular expressions, regular expressions transforming to NFA, and NPDA stuff.

## Day 4 Week 4 on JFLAP

Today morning I fixed a bug where the multiple-enabling button in the grammar editor appears at inappropriate times. Then I heard back from professor Shaffer who taught me to integrate `FAEditor` into the OpenDSA project. For a while I was unable to get the editor to appear on the page. The reason was that two parent divs that wrapped the editor had heights of 0 and the `iframe` itself had a top offset of -9999em. After around an hour of debugging I found that the reason lied in `module_origin`. Changing it fixed the problem perfectly.

Later I adjusted the width, height and some other appearances of the`FAEditor` in the texbook instance. I also found that files in resources folder were outdated, so I updated them from my earlier development directory. Before I finished work today I implemented the auto download `XML` feature in FAEditor. Now if you click on “save” the file will be downloaded automatically.

I printed out the thousands of lines of code for `SLR Parsing` from last year. Hoping that I can understand it tomorrow. Oh, here’s the link for the textbook-like FAEditor.

## Day 3 Week 4 on JFLAP

Today I added multiple grammar editing feature in grammar editor. Now users are able to edit many grammars and save them in an `XML` file that can be used in various exercises, but for now users are not granted access to the server so they cannot see their own grammars in exercises. In the afternoon I was added to OpenDSA Organization so from now on I can commit directly to the OpenDSA project! Hoooorayy for being part of an open-source project.

At night I did a little more work with user input experience in grammar editor. If you are editing one of the entry of the matrix, clicking on the entry itself triggers nothing, clicking on other entries in the matrix will save the current value in the entry and focus on the one you clicked, finally, clicking on empty places in the document will simply save the current value. So starting today professor Rodger will no longer need to press enter every time!

Oh, and in the afternoon professor Rodger gave us a lecture about SLR parsing and it really helped a lot.

## Day 2 Week 4 on JFLAP

Today I improved input experience of grammar editor. Before, when you press enter after filling in part of a production, you have to click on a cell in the table again in order to make further changes, and if you press enter after putting in left-side production, you will be taken of the power to continue putting in the right side and will be directed to the next row. This is highly inhumane so I fixed it today. Now, if you press enter, you will be directed to the natural “next one” of the input boxes. Arrow keys are also enabled to make the control easier. Tomorrow I plan to implement the function of clicking-and-save. Clicking on other parts of the page also saves current input.

I then fixed a bug of checking duplicate productions in the grammar editor. After that, I added stand-alone exercises just like `FAFixer`: LL Parse, Brute Force Parse, and SLR Parse. Multiple question feature is also implemented. Exercises are stores in `XML` format. I might also develop a grammar exercise generator to make instructors’ lives easier. All these three files are using the same JS file –grammarEditor.js, which saves thousands of lines of code. Before I finished work today I read another article. Summary and reference can be found here.

## Day 1 Week 4 on JFLAP

Today morning I officially moved my work to OpenDSA project, in `AV/FLA/billyu/` folder of the`NewKA` branch. I read the documentation about creating a stand-alone algorithm visualization but was still unable to integrate `FAEditor` into a book instance.

In the afternoon I created LL parsing exercise from `grammarEditor`. This exercise still uses the same JS file that the editor is using. The JS file judges the type of the exercise from the `id` attribute of the “h1” tag. For this LL parsing, the grammar is imported from an XML file. I plan to make this exercise with multiple questions tomorrow. I then added single file brute force parsing as well. It is also referencing `grammarEditor.js`, only using the brute force parsing function. Screenshots of these new functions are below.

LL Parsing interface

LL Parsing Tree

Brute Force Parsing

## Day 4 Week 3 on JFLAP

Today I spent the morning learning more about SLR parsing. In the afternoon I read more documentations of OpenDSA, specifically about how to create stand-alone visualizations. Then I perused the code of `grammerTest.js`, which is more than 3000 lines. I tried to disseminate the file into multiple single proof js files but FAILED. On Monday I’m going to create some example stand-alone visualizations and take care of `grammerTest`.

## Day 3 Week 3 on JFLAP

Today I did mostly reading. In the morning I read Compilers Chapter 1 and a little bit of Chapter 2. I learned about phases of a compiling process, which include syntactical phase and semantical phase etc. Although the book used many examples to illustrate these concepts, I still found it very hard to understand. I will spend more time tomorrow. Then I read a paper on action-based visualizations to broaden my recognition of software visualizations.

In the afternoon I explored more of OpenDSA. After some configuration steps I managed to compile a test textbook. I believe simple exercises, which use only JSAV libraries, can be implemented very easily, but for our exercises which depends on js libraries that we developed on our own, we would need more guidance. I learned about LL and SLR parsing before I left the office and after I came home. Both parsing algorithms need two functions `FIRST` and `FOLLOW`, which is basically what can be before a variable or after a variable in the language. Using these two functions, a parsing table can be made, and further parsing depends on this parsing table. LL parsing is relatively easier than SLR parsing because SLR requires that a DFA is made in order to obtain the parsing table. I have not looked into this DFA creation and usage yet. However, I realize that both parsing algorithms have limitations. It seems that the grammar has to be unambiguous for the algorithms to work.

## Day 2 Week 3 on JFLAP

Today I started by setting up a local development environment. I realize that no development should happen on the server, so I moved the folder to local directory and sync using the software cyberduck. Then I spent the rest of the morning restructuring the code of `FAEditor`, `FAFixer` and `FATester`. I added `type` variable in `FAEditor`. The editor modifies html content and initializes the graph according to this `type` variable. In this way I saved myself troubles copying changes across three similar files. I got to delete `FAFixer.js` and `FATester.js`.

In the afternoon I started looking at OpenDSA documentation. I got a grasp of how textbooks are compiled and how to configure their options, though I am confused how Canvas relates to OpenDSA. I now have the whole OpenDSA project running on my virtual machine. I will do some reading tomorrow instead of pure coding.