# Homework 14 February, 2022
1. **Single Cycle Check:**
You are given an array of integers, where each value represents a jump of its value. For example `3` means we jump forward three index. or `-2` means we jump backwards two index. If a jump goes outside the array's bounds, its wraps over to other side. Jump `-1` at index index `0` means going to last index. `1` at last index means going to index `0`. Starting the jump from a starting index, Write a program to verify if the input array conforms to the rule: Every element in the array is visited exactly once before landing back on **starting index**. You can assume starting index = `0`.
**Input and Output:**
- `[2, 3, 1, -4, -4, 2]` `true`
- `[3, 5, 6, -5, -2, -5, -12, -2, -1, 2, -6, 1, 1, 2, -5, 2]` `true`
- `[3, 5, 5, -5, -2, -5, -12, -2, -1, 2, -6, 1, 1, 2, -5, 2]` `false`
2. **Total Node Depth:**
Given a binary tree, write a program to calculate total of each node's depth. Depth is defined as distance between a node and root node. Node can have two children, `left` and `right`. They can be `null` to indicate node does not have corresponding child.
**Input and Output:**
1.
```php
[
'nodes' => [
[
'id' => '1',
'left' => null,
'right' => null,
'value' => 1,
],
],
'root' => '1',
]
```
```
0
```
2.
```php
[
'nodes' => [
[
'id' => '1',
'left' => '2',
'right' => null,
'value' => 1,
],
[
'id' => '2',
'left' => null,
'right' => null,
'value' => 2,
],
],
'root' => '1',
]
```
```
1
```
3.
```php
[
'nodes' => [
[
'id' => '1',
'left' => '2',
'right' => '3',
'value' => 1,
],
[
'id' => '2',
'left' => '4',
'right' => '5',
'value' => 2,
],
[
'id' => '3',
'left' => '6',
'right' => '7',
'value' => 3,
],
[
'id' => '4',
'left' => '8',
'right' => '9',
'value' => 4,
],
[
'id' => '5',
'left' => null,
'right' => null,
'value' => 5,
],
[
'id' => '6',
'left' => null,
'right' => null,
'value' => 6,
],
[
'id' => '7',
'left' => null,
'right' => null,
'value' => 7,
],
[
'id' => '8',
'left' => null,
'right' => null,
'value' => 8,
],
[
'id' => '9',
'left' => null,
'right' => null,
'value' => 9,
],
],
'root' => '1',
]
```
```
16
```
3. **Rivers:**
Imagine you have an aerial image of an area of potentially unequal weight and height. The area contains rivers and lands. The image is represented in a 2D array(matrix) of `1` and `0`. `1` means water and `0` means land. A river consists of water horizontally or vertically adjacent (but not diagonally adjacent). River is allowed to twist, for ex: like a `L` shape. Write a program that outputs an array of sizes of all rivers represented in the input (not mutable).
**Input and Output:**
1.
```php
[
[1, 0, 0, 1, 0],
[1, 0, 1, 0, 0],
[0, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 1, 0],
]
```
```
[1, 2, 2, 2, 5]
```
2.
```php
[
[1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0],
[1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0],
[0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1],
]
```
```
[2, 1, 21, 5, 2, 1]
```
3.
```php
[
[1, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 1]
]
```
```
[1, 1, 1, 1, 7, 1, 1, 1, 1]
```
4. **Islands:**
Similar to previous problem's input, imagine you have an aerial image of an area of potentially unequal weight and height. But `0` means water and `1` means land. We are looking for islands, island is defined as land horizontally or vertically adjacent (but not diagonally adjacent) **and** not touching the border of the image. Write a program to output modified version of the input image with valid islands removed. Removing island means replacing `1` with `0`.
**Input and Output:**
1.
```php
[
[1, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 0],
[1, 1, 0, 0, 1, 0],
[1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 1]
]
```
```php
[
[1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1]
]
```
2.
```php
[
[1, 0, 0, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[0, 1, 0, 1, 0],
[1, 0, 0, 0, 1]
]
```
```php
[
[1, 0, 0, 0, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1]
]
```
3.
```php
[
[1]
]
```
```php
[
[1]
]
```
5. **Youngest Common Ancestor:**
You are a family tree, where each person is represented as a node. Each node has a `ancestor` AKA parent pointing to another node. There will be another topAncestor who doesn't have any ancestor/parent. You will be given two input nodes of descendants. Write a program to output youngest common ancestor to the two descendants.
For example, given this family tree
```
topAncestor = node A
descendantOne = node E
descendantTwo = node I
A
/ \
B C
/ \ / \
D E F G
/ \
H I
```
Youngest common ancestor of `E` and `I` is `B`.
**Input and Output:**
1.
```php
[
'topAncestor' => 'A',
'descendantOne' => 'E',
'descendantTwo' => 'I',
'ancestralTree' => [
'nodes' => [
[
'ancestor' => null,
'id' => 'A',
'name' => 'A',
],
[
'ancestor' => 'A',
'id' => 'B',
'name' => 'B',
],
[
'ancestor' => 'A',
'id' => 'C',
'name' => 'C',
],
[
'ancestor' => 'B',
'id' => 'D',
'name' => 'D',
],
[
'ancestor' => 'B',
'id' => 'E',
'name' => 'E',
],
[
'ancestor' => 'C',
'id' => 'F',
'name' => 'F',
],
[
'ancestor' => 'C',
'id' => 'G',
'name' => 'G',
],
[
'ancestor' => 'D',
'id' => 'H',
'name' => 'H',
],
[
'ancestor' => 'D',
'id' => 'I',
'name' => 'I',
],
],
],
]
```
```
B
```
2.
```php
[
'topAncestor' => 'A',
'descendantOne' => 'A',
'descendantTwo' => 'B',
'ancestralTree' => [
'nodes' => [
[
'ancestor' => null,
'id' => 'A',
'name' => 'A',
],
[
'ancestor' => 'A',
'id' => 'B',
'name' => 'B',
],
[
'ancestor' => 'A',
'id' => 'C',
'name' => 'C',
],
[
'ancestor' => 'A',
'id' => 'D',
'name' => 'D',
],
[
'ancestor' => 'A',
'id' => 'E',
'name' => 'E',
],
[
'ancestor' => 'A',
'id' => 'F',
'name' => 'F',
],
[
'ancestor' => 'B',
'id' => 'G',
'name' => 'G',
],
[
'ancestor' => 'B',
'id' => 'H',
'name' => 'H',
],
[
'ancestor' => 'B',
'id' => 'I',
'name' => 'I',
],
[
'ancestor' => 'C',
'id' => 'J',
'name' => 'J',
],
[
'ancestor' => 'D',
'id' => 'K',
'name' => 'K',
],
[
'ancestor' => 'D',
'id' => 'L',
'name' => 'L',
],
[
'ancestor' => 'F',
'id' => 'M',
'name' => 'M',
],
[
'ancestor' => 'F',
'id' => 'N',
'name' => 'N',
],
[
'ancestor' => 'H',
'id' => 'O',
'name' => 'O',
],
[
'ancestor' => 'H',
'id' => 'P',
'name' => 'P',
],
[
'ancestor' => 'H',
'id' => 'Q',
'name' => 'Q',
],
[
'ancestor' => 'H',
'id' => 'R',
'name' => 'R',
],
[
'ancestor' => 'K',
'id' => 'S',
'name' => 'S',
],
[
'ancestor' => 'P',
'id' => 'T',
'name' => 'T',
],
[
'ancestor' => 'P',
'id' => 'U',
'name' => 'U',
],
[
'ancestor' => 'R',
'id' => 'V',
'name' => 'V',
],
[
'ancestor' => 'V',
'id' => 'W',
'name' => 'W',
],
[
'ancestor' => 'V',
'id' => 'X',
'name' => 'X',
],
[
'ancestor' => 'V',
'id' => 'Y',
'name' => 'Y',
],
[
'ancestor' => 'X',
'id' => 'Z',
'name' => 'Z',
],
],
],
]
```
```
A
```
3.
```php
[
'topAncestor' => 'A',
'descendantOne' => 'T',
'descendantTwo' => 'H',
'ancestralTree' => [
'nodes' => [
[
'ancestor' => null,
'id' => 'A',
'name' => 'A',
],
[
'ancestor' => 'A',
'id' => 'B',
'name' => 'B',
],
[
'ancestor' => 'A',
'id' => 'C',
'name' => 'C',
],
[
'ancestor' => 'A',
'id' => 'D',
'name' => 'D',
],
[
'ancestor' => 'A',
'id' => 'E',
'name' => 'E',
],
[
'ancestor' => 'A',
'id' => 'F',
'name' => 'F',
],
[
'ancestor' => 'B',
'id' => 'G',
'name' => 'G',
],
[
'ancestor' => 'B',
'id' => 'H',
'name' => 'H',
],
[
'ancestor' => 'B',
'id' => 'I',
'name' => 'I',
],
[
'ancestor' => 'C',
'id' => 'J',
'name' => 'J',
],
[
'ancestor' => 'D',
'id' => 'K',
'name' => 'K',
],
[
'ancestor' => 'D',
'id' => 'L',
'name' => 'L',
],
[
'ancestor' => 'F',
'id' => 'M',
'name' => 'M',
],
[
'ancestor' => 'F',
'id' => 'N',
'name' => 'N',
],
[
'ancestor' => 'H',
'id' => 'O',
'name' => 'O',
],
[
'ancestor' => 'H',
'id' => 'P',
'name' => 'P',
],
[
'ancestor' => 'H',
'id' => 'Q',
'name' => 'Q',
],
[
'ancestor' => 'H',
'id' => 'R',
'name' => 'R',
],
[
'ancestor' => 'K',
'id' => 'S',
'name' => 'S',
],
[
'ancestor' => 'P',
'id' => 'T',
'name' => 'T',
],
[
'ancestor' => 'P',
'id' => 'U',
'name' => 'U',
],
[
'ancestor' => 'R',
'id' => 'V',
'name' => 'V',
],
[
'ancestor' => 'V',
'id' => 'W',
'name' => 'W',
],
[
'ancestor' => 'V',
'id' => 'X',
'name' => 'X',
],
[
'ancestor' => 'V',
'id' => 'Y',
'name' => 'Y',
],
[
'ancestor' => 'X',
'id' => 'Z',
'name' => 'Z',
],
],
],
]
```
```
H
```
6. **Tic Tac Toe vs AI:**
Continue working on your previous code and try to implement the logic as discussed. Keep conscious track of the logic you come up with, you'll be asked about how and why.
Sign in with Wallet
Connect another wallet