# Homework Description

1. A 20x20 2d array with random 0s and 100000s. This is to represent an

area of terrain with 400 blocks of space. A 0 means the block is free; a

100000 means it is occupied by an obstacle. This array can also be used

to mark blocks that have been visited (looked at during the search).

2. One of the 0s (free blocks) will be designated as the start position

and one as the goal position (marked as -1). What we will be doing is

finding if there is a path from the start to the finish. If so, what

blocks are part of the path?

3. A function (block-status B) that will return -1, 0, or 100000 for

block B. Block B will be designated by a list of 2 elements (x y)

designating the x and y coordinates of the box with the top left block

being (0 0); x increases from left to right, y increases from top to

bottom.

4. A function (adjacent B) that returns a list of blocks adjacent (one

step vertical or horizontal) to block B.

5. A function (stepo B C) that returns C if a step from B to C is a legal

move (neither B or C are obstacles and C is adjacent to B). It returns #f

if B->C is not a legal move.

6. A function (stepv B C) that returns C if a step from B to C is a new

move (neither B or C are obstacles, C is not marked as visited, and C is

adjacent to B). It returns #f if not.

## Problem

> Assuming you know were the start is, using only horizontal and vertical movements, find a path to the goal if one exists. Does your algorithm find the path quickly? How much storage space does it require? Does it find the shortest possible path?

## Available functions

`(adjacent B)` -> list of blocks adjacent to the block B

`(stepo B C)` -> returns C if a step from B to C is a legal move (neither B or C are obstacles and C is adjacent to B). It returns #f if B->C is not a legal move.

`(stepv B C)` -> returns C if a step from B to C is a new move (neither B or C are obstacles, C is not marked as visited, and C is adjacent to B). It returns #f if not.

`(block-status B)` -> return -1, 0, or 100000 for block B.

# Solution

## Pseudocode

From the given points, we can visualize the 20x20 2D array as a graph, where each block of space represents a node. Assume that we know the starting position, the purpose of the algorithm is to find a path from the starting coordinate to a desingated goal coordinate. High-level pseudo code, using given functions, can be described as below:

visited = empty 2-D array same size as grid

dfs(start-block, target-block, grid):
    dfs-helper(null, start-block, grid, [start-block])

dfs-helper(prev-block, curr-block, grid, curr-path):

        # mark curr-block as visited
        visited.add(curr-block)

        # check if current block is the GOAL or not
        if block-status(curr-block) == 1:
            return curr-path

        # get all the block
        adjacent-blocks = adjacent(curr-block)
        
        # check all posible paths from current block
        iterate each adjacent-block in adjacent-blocks:
            # check validity of current move with given functions:
            #   - is the move from prev-block to curr-block a legal move? does it go out of the grid? is curr-block an obstacle (= 0)?
            #   - this must be a new move, where curr-block has never been visited before.
            if (stepo(prev-block, curr-block) AND stepv(prev-block, curr-block)):
                # add valid adjacent node to recorded path
                curr-path.add-item(adjacent-block)
                path = dfs-helper(curr-block, adjacent-block, curr-path)

                if size(path) != 0:
                    return path 
        
        # invalid path -> Remove latest added item to path
        remove-latest-added-item(path)

        return []

## Explanation

The process can be summarized in following steps:

0. Initialized a global list, `visited`, to record the visited nodes.

1. In the main function, `dfs`, we start calling the `dfs-helper` function with default parameters, where:

- `prev-block = null` as no block been visited before

- `curr-block = start-block` as we start from a given starting block on the grid

- `grid = grid`: the provided 20x20 2d array with random 0s and 100000s

- `curr-path = []`: initally, the recorded path starts with a list with a single element, the starting node.

2. Recursive function `dfs-helper`

a. We mark current block as visited.

b. If current block is the target block? The search completes and returns the recorded path, `curr-path`

c. Using the given function, `adjacent-blocks`, to find all surrounding blocks of the `curr-block`. There are maximumly 4 possible adjacent nodes to the left, right, up, down coordinates of `curr-block`.

d. Loop through each of the surrounding block:

- We check an adjacent block a valid move, where that block must **NOT** be an obstacle and be within the boundary of the grid. Also, this must not be **VISITED** before.

- If the conditions are passed, the following actions can be performed:

- Add that adjacent block to the path being recorded

- Recursively call `dfs-helper` on that adjacent-block

- If the recursive `dfs-helper` returns a path, return it.

e. If the function reaches `remove-lastest-added-item` function, it means that there is no path from `curr-block` to target. We should remove the latest item added to `path` list - `curr-block`.

f. An empty list is returned eventually

## Conclusion

- **Depth-first-search** doesn't not GURANTEE to return a optimal/shortest path as it will return the first path it finds. There are chances that this will be a shortest path (e.g: in the case there is an only single way from starting point to the goal).

- As we represents the grid as a graph, the runtime for this algorithm is approximately `O(M * N)`, where `M` and `N`represents the number of columns and total rows respectively.

- This algorithm uses extra space to record the visited nodes and path. In the worst case scenario, the space complexity can be up to approximately `O(M * N)`.