# 04.17.2022 - Data Structures/Introduction to Bitboard

[Bitboard](https://www.chessprogramming.org/Bitboards) is a widely-used technique in many computer chess programs for efficiently representing and extracting information on the chessboard. It seems to be simultaneously invented by the computer engineers from the Soviet, Britain, and America.

We'll get into chess in the next few articles, but for now, let's examine this interesting technique in a more straightforward example: The tic-tac-toe game.

---

Let's say we have a Tic-tac-toe game with the size of 3x3, it's common sense to represent this board as a 3x3 integer array, with some notation. For example, a 3x3 array with 0 represents empty squares, 1 for X, and 2 for O:

$$
\\text{board} = \\def\\arraystretch{1.5}
\\begin{array}{c:c:c}    1 & 0 & 0 \\\\
\\hdashline 0 & 2 & 1 \\\\
\\hdashline 2 & 0 & 1
\\end{array}
$$

Using the smallest possible number type — a byte (8-bit), the space required to maintain this board in the memory would be 9 bytes. And the same algorithm on the board, for example, evaluate the board to see who's the winner, would be something like:

![](_meta/bitboard-algo-01.png)

With bitboard, we can save both the space complexity and time complexity for representing the board in memory and the algorithm to evaluate the game.

Instead of using 9 bytes (or 72 bits) of memory for the board, we could maintain two different boards, one for X and one for O, and we only need to use 9 bits per board, with every 0-bit for empty squares and 1-bit for the occupied squares.

For example, the same board as described at the beginning of the article can be represented using just two 9-bits numbers:

$$
\\begin{align}
\\text{board\_x} = \\def\\arraystretch{1.5}
\\begin{array}{c:c:c:c:c:c:c:c:c} \\hline 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\\\
\\hline
\\end{array} \\\\
\\text{board\_o} = \\def\\arraystretch{1.5}
\\begin{array}{c:c:c:c:c:c:c:c:c} \\hline 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\\\
\\hline \\end{array}
\\end{align}
$$

In reality, there's no 9-bits number type on any computer, we could use two 16-bits numbers instead, that sums up to 4 bytes, or we can even use just use 3 bytes (this would be a great exercise for the readers).

Now, how can we perform the board evaluation algorithm?

There are 9 squares on the board, indexing from 0 to 8, and this is how we read the value at the nth bit:

$$
\\def\\arraystretch{1.5}
\\begin{array}{c:c:c}    6 & 7 & 8 \\\\ \\hdashline    3 & 4 & 5 \\\\
\\hdashline    0 & 1 & 2 \\end{array}
\\ \\ \\ \\ n^\\text{th}\\ \\text{bit} = (\\text{board} \\gg n)\\ \\&\\ 1
$$

To print the board, we could write something like:

![](_meta/bitboard-algo-02.png)

Now, let's say we want to check if it's X or O is winning the 2nd row of the board. We can check if every bit at the second row of each board is equal to 1. To do this, we apply the bitwise `AND` operator between each board and a mask board of `0b000111000`:

$$
\\def\\arraystretch{1.5}    \\begin{array}{c:c:c}    0 & 1 & 0 \\\\ \\hdashline    1 & 0 & 1 \\\\
\\hdashline    0 & 0 & 1 \\end{array}\\
\text{ AND }\\ \\def\\arraystretch{1.5}    \\begin{array}{c:c:c}    0 & 0 & 0 \\\\ \\hdashline    1 & 1 & 1 \\\\
\\hdashline    0 & 0 & 0 \\end{array}\ = \ \\def\\arraystretch{1.5}
\\begin{array}{c:c:c}    0 & 0 & 0 \\\\ \\hdashline    1 & 0 & 1 \\\\
\\hdashline    0 & 0 & 0 \\end{array}
$$

In case we do have a winner, the result of the `AND` operation between two boards would be the mask board itself.

$$
\\def\\arraystretch{1.5}    \\begin{array}{c:c:c}    0 & 1 & 0 \\\\ \\hdashline    1 & 1 & 1 \\\\
\\hdashline    0 & 0 & 1 \\end{array}\\ \text{ AND }\\
\\def\\arraystretch{1.5}    \\begin{array}{c:c:c}    0 & 0 & 0 \\\\
\\hdashline    1 & 1 & 1 \\\\    \\hdashline    0 & 0 & 0 \\end{array}\\ = \\
\\def\\arraystretch{1.5}    \\begin{array}{c:c:c}    0 & 0 & 0 \\\\ \\hdashline    1 & 1 & 1 \\\\
\\hdashline    0 & 0 & 0 \\end{array}
$$

Using this method, we can check if X or O is winning any of the 3 rows by defining 3 mask boards for each row:

$$
\\begin{align}
\\text{win\_row[1]} = \\def\\arraystretch{1.5}    \\begin{array}{c:c:c:c:c:c:c:c:c} \\hline 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\
\\hline \\end{array} \\\\
\text{win\_row[2]} = \\def\\arraystretch{1.5}    \\begin{array}{c:c:c:c:c:c:c:c:c} \\hline 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\\\
\\hline \\end{array} \\\\ \\text{win\_row[3]} = \\def\\arraystretch{1.5}    \\begin{array}{c:c:c:c:c:c:c:c:c} \\hline 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\\\
\\hline \\end{array} \\end{align}
$$

And the check algorithm:

![](_meta/bitboard-algo-03.png)

To fully scan and check if X or O is winning any of the rows, columns and diagonals, we can define the mask board for each rows, columns and diagonal lines. Here's the example implementation in JavaScript:

```jsx
const WIN_COLS = [0b100100100, 0b010010010, 0b001001001];
const WIN_ROWS = [0b111000000, 0b000111000, 0b000000111];
const WIN_DIAG = [0b100010001, 0b001010100];

const isWinner = (p) => {
    for (let col of WIN_COLS) {
        if ((col & p) == col) return true;
    }
    for (let row of WIN_ROWS) {
        if ((row & p) == row) return true;
    }
    for (let dg of WIN_DIAG) {
        if ((dg & p) == dg) return true;
    }
    return false;
};

// Call isWinner(p) to check if X or O is winner
// with p is board_x or board_y
```


Structures Bitboard Tic Tac Toe

# 02.17.2022 - Data Structures/Representing Graphs

There are two ways to represent a graph data structure, each come with its own pros and cons.

## Using adjacency matrix

An adjacency matrix is a square matrix, each element in the matrix indicate whether pairs of vertices are connected in the graph or not.

![](_meta/adjacency-matrix-representation.png)

For weighted graph, the matrix's element could be some number other than 1.

The drawbacks of using adjacency matrix is its memory usage. No matter how many edges are there, we always need $N \times N$ sized matrix, where $N$ is the number of nodes.

If there are 10000 nodes, then the matrix size will be $4 \times 10000 \times 10000$, that's around 381MB, a huge waste of memory if the graph only have a few edges.

Another point is, if we want to find out which node we can go from a node $u$, we'll need to check the whole row of $u$, which cost a lot of time.

## Using adjacency list

Adjacency list is a collection of unordered lists, each list define the set of vertices that connected to a vertex in a graph.

![](_meta/adjacency-list-representation.png)

For the same graph, adjacency list takes less memory than using adjacency matrix.

But if we want to find out if there's an edge between two vertices $u$ and $v$, we would need to traversal the lists twice $O(2n)$. While using adjacency matrix only takes 1 lookup $O(1)$.

Structures Graph Represent

# 12.30.2021 - Data Structures/Binary Search Tree/Delete node

Algorithm to delete a node from a BST:
- Find the node to delete
- Find the deepest right most (DRM) node of the tree
- Replace the node to delete with the DRM
- Continue find and delete the DRM in the tree

Implementation:

```javascript
delete(value: number) {
  this.root = this.deleteAt(value, this.root);
}

private deleteAt(value: number, node?: TreeNode): TreeNode | undefined {
  if (node) {
    if (value < node.value) {
      node.left = this.deleteAt(value, node.left);
    } else if (value > node.value) {
      node.right = this.deleteAt(value, node.right);
    } else {
      if (!node.left && !node.right) {
        // case 1: node has no child
        node = undefined;
      } else if (node.left && node.right) {
        // case 2: node has two child
        let rightMost = this.deepestRightMost();
        if (rightMost) {
          node.value = rightMost.value;
          node.left = this.deleteAt(rightMost.value, node.left);
          node.right = this.deleteAt(rightMost.value, node.right);
        }
      } else {
        // case 3: node has 1 child
        node = node.left || node.right;
      }
    }
  }
  return node;
}

```



Structures Binary Search Tree Delete node

# 12.28.2021 - Data Structures/Binary Tree/In-order Traversal with Stack

This one is a bit more compex than the pre-order (in term of using stack).

Algorithm:
- Create an empty stack
- Create a temporary reference called curr, set it as root
- Repeat while curr still not null, or the stack still not empty
    - For each tree starting from node curr, we want to push every left nodes in that tree to the stack. To do this, repeat while curr still has a left child, push its left node to the stack and set curr as its left.
    - Start popping out the stack and set it as curr, visit that node and set curr to its right node.

Implementation:

```javascript
let stack = [];
let curr = root;
while (curr !== null || stack.length) {
  while (curr !== null) {
    stack.push(curr);
    curr = curr.left;
  }
  curr = stack.pop();
  curr.visit();
  curr = curr.right;
}
```

