You have been assigned to work with an undersea explorer who is attempting to

identify and map undersea trenches. The explorer has provided you with several

data sets of sonar readings in this format:

```js

// Example 1

sonar = [

[-5,-5,-5,-5,-5],

[-5,-8,-8,-9,-7],

[-5,-5,-5,-5,-8],

[-5,-5,-5,-5,-5]

]

```

Depending on the scan, the provided matrix may be larger or smaller, but it will

always be rectangular. Your task is to determine if a given data set contains a

trench by comparing each node and their neighbors and determining if there is a

pattern that matches the defined properties of a trench.

Neighbors are considered to be nodes that are directly above, below, or to

the side. **No diagonals**!

A trench has the following three properties:

1. It has a length of **three or more** nodes.

1. Each node in the trench must be **deeper than -5**.

1. Trenches may **not** branch into (any form of) a "T" shape. A node with more than **two neighbors** will result in branching "T" shape.

![valid-invalid-trenches]

This problem literally has edge cases! After discussing the matter with the

explorer, you have agreed that potential trenches that otherwise meet the rules

as a trench are valid, even if part of it is on the edge of the data set, and it

can't be fully determined if those nodes follow the rules.

A few examples:

```js

// Example 1

sonar_1 = [

[-5,-5,-5,-5,-5],

[-5,-8,-8,-9,-7],

[-5,-5,-5,-5,-8],

[-5,-5,-5,-5,-5]

]

```

**Example 1 has a trench**. The nodes containing -8, -8, -9, -7, -8 meet the rules.

This is an edge case trench, because the nodes containing -7 and -8 are on the

edge of the data set.

```js

// Example 2

sonar_2 = [

[-5,-5,-5,-7,-5],

[-5,-8,-8,-9,-5],

[-5,-5,-5,-7,-5],

[-5,-5,-5,-5,-5]

]

```

**Example 2 does not have a trench**. The node containing -9 has three neighbors with a

depth below -5. This would create a "T" shaped trench, which is not valid.

```js

// Example 3

sonar_3 = [

[-5,-5,-5,-5,-5],

[-5,-5,-5,-5,-5],

[-5,-9,-9,-5,-5],

[-5,-5,-5,-5,-5]

]

```

**Example 3 does not have a trench**. There are two nodes that are next to one

another and are deeper than -5, but a trench must have at least 3 total nodes to

be a trench.

*************** test specs ****************

const { expect } = require('chai');

const [identifyTrench, findNeighbors, trenchTraversal] = require('../identifying-trenches.js');

describe('findNeighbors', () => {

const sonar_data = [

[-8, -5, -9],

[-6, -5, -8],

[-7, -7, -8]

];

it('Only returns NSEW neighbors depth < -5', () => {

const neighbors = findNeighbors([1, 1], sonar_data);

expect(neighbors.length).to.equal(3);

expect(neighbors).to.deep.include.members([[2, 1], [1, 0], [1, 2]]);

});

it('Can find the correct neighbors in a corner', () => {

const NWNeighbors = findNeighbors([0, 0], sonar_data);

const SENeighbors = findNeighbors([2, 2], sonar_data);

expect(NWNeighbors.length).to.equal(1);

expect(NWNeighbors).to.deep.include.members([[1, 0]]);

expect(SENeighbors.length).to.equal(2);

expect(SENeighbors).to.deep.include.members([[2, 1], [1, 2]]);

});

});

describe('trenchTraversal', () => {

const sonar_1 = [

[-5, -5, -5, -5, -5],

[-5, -8, -8, -9, -7],

[-5, -5, -5, -5, -8],

[-5, -5, -5, -5, -5]

];

const sonar_2 = [

[-5, -5, -5, -6, -5],

[-5, -7, -8, -9, -5],

[-5, -5, -5, -8, -5],

[-5, -5, -5, -5, -5]

];

const sonar_3 = [

[-5, -5, -5, -5, -5],

[-5, -5, -5, -5, -5],

[-5, -9, -9, -5, -5],

[-5, -5, -5, -5, -5]

];

it('Can traverse a valid trench and return true, but returns false if the start is too shallow', () => {

let visited1 = new Set();

const shallowStart = trenchTraversal([0, 0], sonar_1, visited1);

let visited2 = new Set();

const validTrench = trenchTraversal([1, 1], sonar_1, visited2);

expect(shallowStart).to.equal(false);

expect(validTrench).to.equal(true);

});

it('Can traverse a valid trench and return true, but traversing a trench with a "T" returns false', () => {

let visited1 = new Set();

const validTrench = trenchTraversal([1, 3], sonar_1, visited1);

let visited2 = new Set();

const tTrench = trenchTraversal([1, 1], sonar_2, visited2)

expect(validTrench).to.equal(true);

expect(tTrench).to.equal(false)

});

it('Can traverse a valid trench and return true, but a trench that is too short returns false', () => {

let visited = new Set();

const shortTrench = trenchTraversal([2, 3], sonar_3, visited)

expect(shortTrench).to.equal(false)

});

});

describe('identifyTrench', () => {

const sonar_1 = [

[-5, -5, -5, -5, -5],

[-5, -8, -8, -9, -7],

[-5, -5, -5, -5, -8],

[-5, -5, -5, -5, -5]

];

const sonar_2 = [

[-5, -5, -5, -6, -5],

[-5, -7, -8, -9, -5],

[-5, -5, -5, -8, -5],

[-5, -5, -5, -5, -5]

];

const sonar_3 = [

[-5, -5, -5, -5, -5],

[-5, -5, -5, -5, -5],

[-5, -9, -9, -5, -5],

[-5, -5, -5, -5, -5]

];

const sonar_4 = [

[-5, -5, -5, -5, -5],

[-5, -5, -5, -5, -5],

[-5, -3, -3, -5, -5],

[-5, -5, -5, -5, -5]

];

const sonar_5 = [

[-7, -8, -5, -5, -5],

[-5, -5, -5, -5, -5],

[-5, -3, -9, -8, -5],

[-5, -5, -5, -7, -5]

];

it('Finds and identifies a valid trench, but rejects trenches that have a T', () => {

const validResult = identifyTrench(sonar_1);

const rejectT = identifyTrench(sonar_2);

expect(validResult).to.equal(true);

expect(rejectT).to.equal(false);

});

it('Rejects trenches that are too short', () => {

const rejectShort = identifyTrench(sonar_3);

expect(rejectShort).to.equal(false);

});

it('Can find a valid trench after rejecting an invalid one, and can handle data with no trenches', () => {

const noTrench = identifyTrench(sonar_4);

const secondTrench = identifyTrench(sonar_5);

expect(noTrench).to.equal(false);

expect(secondTrench).to.equal(true);

});

});

************** code below *************

// function findNeighbors(node, matrix) {

// // Only consider N, S, E, W nodes

// // North

// // South

// // East

// // West

// // Your code here

// }

// function trenchTraversal(node, matrix, visited) {

// // Don't bother traversing if it is to shallow

// // Traverse the potential trench to count it's length

// // Your code here

// }

// function identifyTrench(trenchMatrix) {

// // Start at 0,0 and attempt to traverse any unvisited nodes

// // Your code here

// }

module.exports = [identifyTrench, findNeighbors, trenchTraversal];