|
'use strict' |
|
|
|
/** |
|
* Process matrix and calculates parts per section |
|
* |
|
* @param {number[[]]} data - A square matrix as a list of lists. Each list contains integers |
|
* @return {Map[]} |
|
*/ |
|
function processData(data) { |
|
const parts = [] |
|
const candidates = [] |
|
let identicalParts |
|
let processed = new Set() |
|
let part |
|
let key |
|
|
|
data.forEach((row, i) => { |
|
row.forEach((partSetId, j) => { |
|
if (!isPartProcessed(processed, getKey(i, j))) { |
|
identicalParts = new Map([['setId', partSetId], ['parts', 0]]) |
|
parts.push(identicalParts) |
|
|
|
candidates.push(createPart(partSetId, i, j)) |
|
|
|
while (candidates.length) { |
|
part = candidates.pop() |
|
key = getKey(part.get('i'), part.get('j')) |
|
if (!isPartProcessed(processed, key)) { |
|
identicalParts.set('parts', identicalParts.get('parts') + 1) |
|
processed.add(key) |
|
candidates.push(...adjacentParts(data, part)) |
|
} |
|
} |
|
} |
|
}) |
|
}) |
|
|
|
return parts |
|
} |
|
|
|
/** |
|
* Creates part information |
|
* |
|
* @param {number} partSetId - set id that part belongs to |
|
* @param {number} i - part position in first dimension of the matrix |
|
* @param {number} j - part position in second dimension of the matrix |
|
* @return {Map.<string, number, number>} - part information |
|
*/ |
|
function createPart(partSetId, i, j) { |
|
return new Map([['setId', partSetId], ['i', i], ['j', j]]) |
|
} |
|
|
|
/** |
|
* Finds adjacent parts to part that is passed. |
|
* It checks if part exist to the left, right, bellow and above |
|
* |
|
* @param {number[[]]} data - A square matrix as a list of lists. Each list contains integers |
|
* @param {Map.<string, number, number>} part - part that will be used to check for neighbors |
|
* @return {Map.<string, number, number>[]} - list of adjacent items in the same set |
|
*/ |
|
function adjacentParts(data, part) { |
|
let adjacent = []; |
|
let i = part.get('i'); |
|
let j = part.get('j'); |
|
let setId = part.get('setId') |
|
|
|
adjacent.pushIfNotNull(candidate(data, i, j + 1, setId)) |
|
adjacent.pushIfNotNull(candidate(data, i, j - 1, setId)) |
|
adjacent.pushIfNotNull(candidate(data, i + 1, j, setId)) |
|
adjacent.pushIfNotNull(candidate(data, i - 1, j, setId)) |
|
|
|
return adjacent |
|
} |
|
|
|
/** |
|
* Adds item to the array only if item is truthy |
|
* |
|
* @param {object} item - item that has to be added to the array |
|
*/ |
|
Array.prototype.pushIfNotNull = function(item) { |
|
if (item) { |
|
this.push(item) |
|
} |
|
} |
|
|
|
/** |
|
* Checks if item at [i][j] position is part of the same set |
|
* |
|
* @param {number[[]]} data - A square matrix as a list of lists. Each list contains integers |
|
* @param {number} i - part position in first dimension of the matrix |
|
* @param {number} j - part position in second dimension of the matrix |
|
* @param {number} setId - set number of identical parts |
|
* @return {Map.<string, number, number>} - adjacent item in the same set |
|
*/ |
|
function candidate(data, i, j, setId) { |
|
let matrixSize = data.length - 1 |
|
|
|
if (i >= 0 |
|
&& j >= 0 |
|
&& i <= matrixSize |
|
&& j <= matrixSize |
|
&& data[i][j] === setId) { |
|
return createPart(setId, i, j) |
|
} |
|
} |
|
|
|
/** |
|
* Generates part's key so it can be used in search item in the set |
|
* |
|
* @param {number} i - part position in first dimension of the matrix |
|
* @param {number} j - part position in second dimension of the matrix |
|
* @return {string} - unique key for each part |
|
*/ |
|
function getKey(i, j) { |
|
return `${i}${j}` |
|
} |
|
|
|
/** |
|
* Checks if part is processed |
|
* |
|
* @param {Set.<string>} processed - set of processed parts that item has to be checked in |
|
* @param {string} part - part key to be checked in processed set |
|
* @return {boolean} - true if part is processed otherwise false |
|
*/ |
|
function isPartProcessed(processed, part) { |
|
return processed.has(part) |
|
} |
|
|
|
/** |
|
* Main driver of the program. |
|
* |
|
* @param {number[[]]} data - a square matrix as a list of lists. Each list contains integers |
|
* @return {[number, number]} - the size and marking of the largest group as a list of two integers. |
|
*/ |
|
function radiationSearch(data) { |
|
return processData(data).reduce((p, c) => (p = p[0] < c.get('parts') |
|
? [c.get('parts'), c.get('setId')] |
|
: p, p), [0, 0]) |
|
} |
|
|
|
mocha.setup('bdd') |
|
const assert = chai.assert |
|
|
|
describe('Assertions', () => { |
|
it('14 of 1', () => |
|
assert.deepEqual(radiationSearch([ |
|
[1, 2, 3, 4, 5], |
|
[1, 1, 1, 2, 3], |
|
[1, 1, 1, 2, 2], |
|
[1, 2, 2, 2, 1], |
|
[1, 1, 1, 1, 1] |
|
]), [14, 1])) |
|
|
|
it('19 of 2', () => |
|
assert.deepEqual(radiationSearch([ |
|
[2, 1, 2, 2, 2, 4], |
|
[2, 5, 2, 2, 2, 2], |
|
[2, 5, 4, 2, 2, 2], |
|
[2, 5, 2, 2, 4, 2], |
|
[2, 4, 2, 2, 2, 2], |
|
[2, 2, 4, 4, 2, 2] |
|
]), [19, 2])) |
|
}) |
|
|
|
mocha.run() |
