# Homework 13 February 2022

1. **Construct Tree Hashmap from node list (children list)**:
Given a list of nodes, construct a php array (hash-map) using ID of the node as KEY.

**Input:**

    [
        'nodes' => [
            [
                'children' => [
                    'B',
                    'C',
                ],
                'id' => 'A',
                'value' => 'A',
            ],

            [
                'children' => [
                    'D',
                ],
                'id' => 'B',
                'value' => 'B',
            ],

            [
                'children' => [
                ],
                'id' => 'C',
                'value' => 'C',
            ],

            [
                'children' => [
                ],
                'id' => 'D',
                'value' => 'D',
            ],
        ],
        'startNode' => 'A',
    ]

**Output**:

    [
        'nodes' => [
            'A' => [
                'children' => [
                    'B',
                    'C',
                ],
                'id' => 'A',
                'value' => 'A',
            ],
            'B' => [
                'children' => [
                    'D',
                ],
                'id' => 'B',
                'value' => 'B',
            ],
            'C' => [
                'children' => [
                ],
                'id' => 'C',
                'value' => 'C',
            ],
            'D' => [
                'children' => [
                ],
                'id' => 'D',
                'value' => 'D',
            ],
        ],
        'startNode' => 'A',
    ]

2. **Construct Tree Hashmap from node list (parent reference)**:
Given a list of nodes, construct a php array (hash-map) using ID of the node as KEY. This data structure doesn't have children of nodes populated. Traverse the map and generate children of each node by the parent ID.

**Input:**

    [
        'nodes' => [
            [
                'id' => 'A',
                'value' => 'A',
                'parent' => null,
            ],

            [
                'id' => 'B',
                'value' => 'B',
                'parent' => 'A',
            ],

            [
                'id' => 'C',
                'value' => 'C',
                'parent' => 'A',
            ],

            [
                'id' => 'D',
                'value' => 'D',
                'parent' => 'B',
            ],
        ],
        'startNode' => 'A',
    ]

**Output:** Same as previous problem.

3. **Depth-first Search**:
Use the function implemented in *1* to construct Tree hashmap.
Given a Tree-like structure, stored in a flattened php array, Write a program to navigate the tree using *Depth-first Search* approach (left to right) and store the value of all nodes and print it.

***Input:***:

    [
        'nodes' => [
            [
                'children' => [
                    'B',
                    'C',
                    'D',
                ],
                'id' => 'A',
                'value' => 'A',
            ],

            [
                'children' => [
                    'E',
                    'F',
                ],
                'id' => 'B',
                'value' => 'B',
            ],

            [
                'children' => [
                ],
                'id' => 'C',
                'value' => 'C',
            ],

            [
                'children' => [
                    'G',
                    'H',
                ],
                'id' => 'D',
                'value' => 'D',
            ],

            [
                'children' => [
                ],
                'id' => 'E',
                'value' => 'E',
            ],

            [
                'children' => [
                    'I',
                    'J',
                ],
                'id' => 'F',
                'value' => 'F',
            ],

            [
                'children' => [
                    'K',
                ],
                'id' => 'G',
                'value' => 'G',
            ],

            [
                'children' => [
                ],
                'id' => 'H',
                'value' => 'H',
            ],

            [
                'children' => [
                ],
                'id' => 'I',
                'value' => 'I',
            ],

            [
                'children' => [
                ],
                'id' => 'J',
                'value' => 'J',
            ],

            [
                'children' => [
                ],
                'id' => 'K',
                'value' => 'K',
            ],
        ],
        'startNode' => 'A',
    ]

**Output:**

    ["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"]

4. **Breadth-first Search**:
Use the function implemented in *1* to construct Tree hashmap.
Given a Tree-like structure, stored in a flattened php array, Write a program to navigate the tree using *Breadth-first Search* approach (left to right) and store the value of all nodes and print it.

**Input**: Same as Depth-first Search.

**Output**:

    ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]

5. **Tic Tac Toe**:
Try to improve your previous implementation of tic tac toe. Ex: Optimizing check winner functions as discussed.
6. **Tic Tac Toe VS AI**:
Building upon the previous two player implementation. Implement a Player VS Computer Game. Your main goal is to conceive and implement the algorithm for computer player to place his marker on most likely place to win. Hint: Start by placing randomly, then actually work on finding winning algorithms.

7. **Optimized Fibonacci (Dynamic Programming)**:
Implement a recursive function to output N-th number of fibonacci sequence. Now Optimize it by applying the basic concept of dynamic programming. Ex: Saving result for a N input in a hashmap and retrieving it instead of recalculating again.