Bitmap matrix exercise

README.md

Bitmap Matrix

Un'immagine bitmap non è altro che una matrice NxM in cui ogni elemento contiene un valore RGBA, ovvero una quadrupla dove ogni elemento ha un valore tra 0 e 255 che rappresenta uno dei canali con cui identificare un colore.

In questo esercizio si richiede di generare delle bitmap randomiche e fare alcune operazioni su di esse.

Il cuore dell'esercizio è però quello di testare il codice (in TDD o a posteriori) utilizzando Jest. Suggerisco di generare a mano delle bitmap di esempio da utilizzare nei test come input per le funzioni che si andranno a realizzare.

Per semplificare l'esercizio ogni pixel è semplicemente un singolo valore tra 0 e 255.

Step 1

Generare randomicamente delle bitmap. La funzione che le genera deve prendere come input le dimensioni della bitmap e il numero di immagini da generare.

Step 2

Realizzare una funzione che, data un'immagine bitmap, identifichi se ci sono delle linee orizzontali di colore simile. La funzione deve prendere in input l'immagine, la lunghezza della linea da cercare e un indice (intero da 0 a 255) che determina come la funzione identifica il colore come "simile". Un valore 0 indica che il colore deve essere il medesimo, un numero superiore determina un insieme di colori simili. Ad esempio un valore di 30 applicato ad un colore 183, determina che tutti i colori tra 153 e 213 sono "simili".

index.js

/**
 * Returns an integer between 0 and 255
 * @returns {number} An integer between 0 and 255
 */
const getColor = () => Math.floor(Math.random() * 256);

exports.getColor = getColor;

/**
 * Generate a NxM matrix of "pixels" where each element, a pixel, has a value between 0 and 255
 * @param {number} N - Number of columns of the matrix
 * @param {number} M - Number of rows of the matrix
 * @returns {Array} - The Matrix (array of array)
 */
const generateBitmap = (N, M) => {
  const matrix = [];
  // Loop over columns
  for (let m = 0; m < M; m++) {
    const row = [];
    // Loop over rows
    for (let n = 0; n < N; n++) {
      row.push(getColor());
    }
    matrix.push(row);
  }
  return matrix;
};

exports.generateBitmap = generateBitmap;

/**
 * Generate multiple bitmaps
 * @param {number} I - Number of the bitmaps to generate
 * @param {number} N - Number of columns of the bitmaps
 * @param {number} M - Number of rows of the bitmaps
 * @returns {Array} - The bitmaps
 */
const generateBitmaps = (I, N, M) => {
  const bitmaps = [];
  for (let i = 0; i < I; i++) {
    bitmaps.push(generateBitmap(N, M));
  }
  return bitmaps;
};

exports.generateBitmaps = generateBitmaps;

/**
 * Identify horizontal lines in a bitmap
 * @param {Array} M - The bitmap matrix
 * @param {number} L - The length of the line
 * @param {number} r - The color range to identify a "similar" color
 * @returns {boolean} - Whether at least 1 horizontal line exists
 */
const findHorizontalLine = (M, L, r) => {
  for (let i = 0; i < M.length; i++) {
    let lastColor = null;
    let lineLength = 0;
    for (let j = 0; j < M[i].length; j++) {
      const color = M[i][j];
      // This is the first pixel of the row
      if (lastColor === null) {
        lastColor = color;
        lineLength++;
        continue;
      }
      if (color === lastColor) {
        lineLength++;
      } else if (
        (color > lastColor && color - r <= lastColor) ||
        (color < lastColor && color + r >= lastColor)
      ) {
        lineLength++;
      }
      if (lineLength >= L) {
        return true;
      }
      lastColor = color;
    }
  }
  return false;
};

exports.findHorizontalLine = findHorizontalLine;

index.test.js

const {
  findHorizontalLine,
  generateBitmap,
  generateBitmaps,
  getColor
} = require("./index");

test("can generate a valid color", () => {
  for (let i = 0; i < 10000; i++) {
    const v = getColor();
    expect(v).toBeGreaterThanOrEqual(0);
    expect(v).toBeLessThanOrEqual(255);
  }
});

test("can generate a bitmap", () => {
  const bitmap = generateBitmap(2, 3);
  expect(bitmap.length).toEqual(3);
  expect(bitmap[0].length).toEqual(2);
});

test("can generate multiple bitmaps", () => {
  expect(generateBitmaps(5, 1, 1).length).toEqual(5);
});

test("identifies horizontal lines", () => {
  const m1 = [[10, 59, 112, 20], [20, 33, 198, 1], [165, 43, 251, 72]];
  expect(findHorizontalLine(m1, 3, 20)).toBeFalsy();

  const m2 = [[10, 59, 112, 20], [20, 33, 42, 1], [165, 43, 251, 72]];
  expect(findHorizontalLine(m2, 3, 20)).toBeTruthy();

  const m3 = [[10, 59, 112, 20], [20, 20, 20, 20], [165, 43, 251, 72]];
  expect(findHorizontalLine(m3, 4, 0)).toBeTruthy();
});

package.json

{
  "name": "bitmap_matrix",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "dependencies": {},
  "devDependencies": {
    "jest": "^24.5.0"
  },
  "scripts": {
    "test": "jest"
  },
  "author": "Tommaso Visconti <tommaso@develer.com>",
  "license": "ISC"
}