Skip to content

Instantly share code, notes, and snippets.

@reyou

reyou/find the size of the largest shape.js

Created May 24, 2018 02:25
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save reyou/203537b23b38425212f45b50c0f4a8a3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save reyou/203537b23b38425212f45b50c0f4a8a3 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. reyou created this gist May 24, 2018.
    53 changes: 53 additions & 0 deletions find the size of the largest shape.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,53 @@
    /** Algorithm: given a collection (matrix) of
    pixels you must find the size of the largest shape.
    Shapes were defined as pixels touching each other orthogonality. */
    var input = [
    [1, 1, 1, 1, 0],
    [1, 1, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
    ];
    var input2 = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]
    ];

    console.log(findMax(input));
    console.log(findMax(input2));
    function findMax(input) {
    var count = 0;
    let rowCount = input.length;
    let colCount = input[0].length;
    for (let i = 0; i < rowCount; i++) {
    for (let j = 0; j < colCount; j++) {
    var currentCount = search(input, i, j, 0);
    if (currentCount > count) {
    count = currentCount;
    }
    }
    }
    return count;
    }

    function search(input, row, col, counter) {
    if (
    row < 0 ||
    col < 0 ||
    row > input.length - 1 ||
    col > input[0].length - 1 ||
    input[row][col] === 0
    ) {
    return counter;
    } else {
    input[row][col] = 0;
    counter = counter + 1;
    }
    // top, right, bottom, left
    counter = search(input, row - 1, col, counter);
    counter = search(input, row, col + 1, counter);
    counter = search(input, row + 1, col, counter);
    counter = search(input, row, col - 1, counter);
    return counter;
    }