Oct 29, 2022 · Oct 29, 2022 · Oct 29, 2022 · Oct 29, 2022 · Oct 29, 2022 · Oct 29, 2022
diff --git a/Dynamic-Programming/UniquePaths2.js b/Dynamic-Programming/UniquePaths2.js
 /*
 * Unique Paths 2
 *
 * There is a robot on an `m x n` grid.
 * The robot is initially located at the top-left corner
 * The robot tries to move to the bottom-right corner.
 * The robot can only move either down or right at any point in time.
 *
 * Given grid with obstacles
 * An obstacle and space are marked as 1 or 0 respectively in grid.
 * A path that the robot takes cannot include any square that is an obstacle.
 * Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
 *
 * More info: https://leetcode.com/problems/unique-paths-ii/
 */

 /**
 * @description Return 'rows x columns' grid with cells filled by 'filler'
 * @param {Number} rows Number of rows in the grid
 * @param {Number} columns Number of columns in the grid
 * @param {String | Number | Boolean} filler The value to fill cells
 * @returns {Object []}
 */
 const generateMatrix = (rows, columns, filler = 0) => {
  const matrix = []
  for (let i = 0; i < rows; i++) {
    const submatrix = []
    for (let k = 0; k < columns; k++) {
      submatrix[k] = filler
    }
    matrix[i] = submatrix
  }
  return matrix
 }

 /**
 * @description Return number of unique paths
 * @param {Array [][]} obstacles Obstacles grid
 * @returns {Number}
 */
 const uniquePaths2 = (obstacles) => {
  if (!Array.isArray(obstacles)) {
    throw new Error('Input data must be type of Array')
  }
  // Create grid for calculating number of unique ways
  const rows = obstacles.length
  const columns = obstacles[0].length
  const grid = generateMatrix(rows, columns)
  // Fill the outermost cell with 1 b/c it has
  // the only way to reach neighbor
  for (let i = 0; i < rows; i++) {
    // If robot encounters an obstacle in these cells,
    // he cannot continue moving in that direction
    if (obstacles[i][0]) {
      break
    }
    grid[i][0] = 1
  }
  for (let j = 0; j < columns; j++) {
    if (obstacles[0][j]) {
      break
    }
    grid[0][j] = 1
  }
  // Fill the rest of grid by dynamic programming
  // using following reccurent formula:
  // K[i][j] = K[i - 1][j] + K[i][j - 1]
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < columns; j++) {
      grid[i][j] = obstacles[i][j] ? 0 : grid[i - 1][j] + grid[i][j - 1]
    }
  }
  return grid[rows - 1][columns - 1]
 }

 export { uniquePaths2 }
diff --git a/Dynamic-Programming/tests/UniquePaths2.test.js b/Dynamic-Programming/tests/UniquePaths2.test.js
 import { uniquePaths2 } from '../UniquePaths2'

 describe('Unique Paths2', () => {
  // Should return number of ways, taken into account the obstacles
  test('There are obstacles in the way', () => {
    expect(uniquePaths2([[0, 0, 0], [0, 1, 0], [0, 0, 0]])).toEqual(2)
    expect(uniquePaths2([[0, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0]])).toEqual(3)
  })
  // Should return number of all possible ways to reach right-bottom corner
  test('There are no obstacles in the way', () => {
    expect(uniquePaths2([[0, 0, 0], [0, 0, 0], [0, 0, 0]])).toEqual(6)
    expect(uniquePaths2([[0, 0, 0], [0, 0, 0]])).toEqual(3)
  })
  // Should throw an exception b/c input data has wrong type
  test('There are wrong type of input data', () => {
    expect(() => uniquePaths2('wrong input')).toThrow()
    expect(() => uniquePaths2(100)).toThrow()
  })
 })
diff --git a/Maths/HornerScheme.js b/Maths/HornerScheme.js
 /**
 * @function hornerScheme
 * @description Convert a number from decimal system to another (till decimal)
 * @param {Number} number Number to be converted
 * @param {Number} base Base of new number system
 * @returns {String} Converted Number
 * @see [HornerMethod](https://en.wikipedia.org/wiki/Horner%27s_method)
 * @example
 * const num1 = 125 // Needs to be converted to the binary number system
 * gornerScheme(num, 2); // ===> 1111101
 * @example
 * const num2 = 125 // Needs to be converted to the octal number system
 * gornerScheme(num, 8); // ===> 175
 */
 const hornerScheme = (number, base) => {
  if (typeof number !== 'number' || typeof base !== 'number') {
    throw new Error('Input data must be numbers')
  }
  // Zero in any number system is zero
  if (number === 0) {
    return `${number}`
  }
  let absoluteValue = Math.abs(number)
  let convertedNumber = ''
  while (absoluteValue > 0) {
    // Every iteration last digit is taken away
    // and added to the previois one
    const lastDigit = absoluteValue % base
    convertedNumber = lastDigit + convertedNumber
    absoluteValue = Math.trunc(absoluteValue / base)
  }
  // Result is whether negative or positive,
  // depending on the original value
  const result = number < 0 ? `-${convertedNumber}` : convertedNumber
  return result
 }

 export { hornerScheme }
diff --git a/Maths/test/HornerScheme.test.js b/Maths/test/HornerScheme.test.js
 import { hornerScheme } from '../HornerScheme'

 describe('Horner Scheme', () => {
  test('Case 1: testing conversion to the binary system', () => {
    expect(hornerScheme(210, 2)).toEqual('11010010')
    expect(hornerScheme(-210, 2)).toEqual('-11010010')
  })
  test('Case 2: testing conversion to the system with base 5', () => {
    expect(hornerScheme(210, 5)).toEqual('1320')
    expect(hornerScheme(-210, 5)).toEqual('-1320')
  })
  test('Case 3: testing conversion to the octal system', () => {
    expect(hornerScheme(210, 8)).toEqual('322')
    expect(hornerScheme(-210, 8)).toEqual('-322')
  })
  test('Case 4: testing 0', () => {
    expect(hornerScheme(0, 8)).toEqual('0')
    expect(hornerScheme(0, 8)).toEqual('0')
  })
  test('Case 5: testing throwing an exception', () => {
    expect(() => hornerScheme('string', 2)).toThrow()
    expect(() => hornerScheme(10, 'base')).toThrow()
    expect(() => hornerScheme(true, false)).toThrow()
  })
 })
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,76 @@
		/*
		* Unique Paths 2
		*
		* There is a robot on an `m x n` grid.
		* The robot is initially located at the top-left corner
		* The robot tries to move to the bottom-right corner.
		* The robot can only move either down or right at any point in time.
		*
		* Given grid with obstacles
		* An obstacle and space are marked as 1 or 0 respectively in grid.
		* A path that the robot takes cannot include any square that is an obstacle.
		* Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
		*
		* More info: https://leetcode.com/problems/unique-paths-ii/
		*/

		/**
		* @description Return 'rows x columns' grid with cells filled by 'filler'
		* @param {Number} rows Number of rows in the grid
		* @param {Number} columns Number of columns in the grid
		* @param {String \| Number \| Boolean} filler The value to fill cells
		* @returns {Object []}
		*/
		const generateMatrix = (rows, columns, filler = 0) => {
		const matrix = []
		for (let i = 0; i < rows; i++) {
		const submatrix = []
		for (let k = 0; k < columns; k++) {
		submatrix[k] = filler
		}
		matrix[i] = submatrix
		}
		return matrix
		}

		/**
		* @description Return number of unique paths
		* @param {Array [][]} obstacles Obstacles grid
		* @returns {Number}
		*/
		const uniquePaths2 = (obstacles) => {
		if (!Array.isArray(obstacles)) {
		throw new Error('Input data must be type of Array')
		}
		// Create grid for calculating number of unique ways
		const rows = obstacles.length
		const columns = obstacles[0].length
		const grid = generateMatrix(rows, columns)
		// Fill the outermost cell with 1 b/c it has
		// the only way to reach neighbor
		for (let i = 0; i < rows; i++) {
		// If robot encounters an obstacle in these cells,
		// he cannot continue moving in that direction
		if (obstacles[i][0]) {
		break
		}
		grid[i][0] = 1
		}
		for (let j = 0; j < columns; j++) {
		if (obstacles[0][j]) {
		break
		}
		grid[0][j] = 1
		}
		// Fill the rest of grid by dynamic programming
		// using following reccurent formula:
		// K[i][j] = K[i - 1][j] + K[i][j - 1]
		for (let i = 1; i < rows; i++) {
		for (let j = 1; j < columns; j++) {
		grid[i][j] = obstacles[i][j] ? 0 : grid[i - 1][j] + grid[i][j - 1]
		}
		}
		return grid[rows - 1][columns - 1]
		}

		export { uniquePaths2 }
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,19 @@
		import { uniquePaths2 } from '../UniquePaths2'

		describe('Unique Paths2', () => {
		// Should return number of ways, taken into account the obstacles
		test('There are obstacles in the way', () => {
		expect(uniquePaths2([[0, 0, 0], [0, 1, 0], [0, 0, 0]])).toEqual(2)
		expect(uniquePaths2([[0, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0]])).toEqual(3)
		})
		// Should return number of all possible ways to reach right-bottom corner
		test('There are no obstacles in the way', () => {
		expect(uniquePaths2([[0, 0, 0], [0, 0, 0], [0, 0, 0]])).toEqual(6)
		expect(uniquePaths2([[0, 0, 0], [0, 0, 0]])).toEqual(3)
		})
		// Should throw an exception b/c input data has wrong type
		test('There are wrong type of input data', () => {
		expect(() => uniquePaths2('wrong input')).toThrow()
		expect(() => uniquePaths2(100)).toThrow()
		})
		})
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,38 @@
		/**
		* @function hornerScheme
		* @description Convert a number from decimal system to another (till decimal)
		* @param {Number} number Number to be converted
		* @param {Number} base Base of new number system
		* @returns {String} Converted Number
		* @see [HornerMethod](https://en.wikipedia.org/wiki/Horner%27s_method)
		* @example
		* const num1 = 125 // Needs to be converted to the binary number system
		* gornerScheme(num, 2); // ===> 1111101
		* @example
		* const num2 = 125 // Needs to be converted to the octal number system
		* gornerScheme(num, 8); // ===> 175
		*/
		const hornerScheme = (number, base) => {
		if (typeof number !== 'number' \|\| typeof base !== 'number') {
		throw new Error('Input data must be numbers')
		}
		// Zero in any number system is zero
		if (number === 0) {
		return `${number}`
		}
		let absoluteValue = Math.abs(number)
		let convertedNumber = ''
		while (absoluteValue > 0) {
		// Every iteration last digit is taken away
		// and added to the previois one
		const lastDigit = absoluteValue % base
		convertedNumber = lastDigit + convertedNumber
		absoluteValue = Math.trunc(absoluteValue / base)
		}
		// Result is whether negative or positive,
		// depending on the original value
		const result = number < 0 ? `-${convertedNumber}` : convertedNumber
		return result
		}

		export { hornerScheme }
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,25 @@
		import { hornerScheme } from '../HornerScheme'

		describe('Horner Scheme', () => {
		test('Case 1: testing conversion to the binary system', () => {
		expect(hornerScheme(210, 2)).toEqual('11010010')
		expect(hornerScheme(-210, 2)).toEqual('-11010010')
		})
		test('Case 2: testing conversion to the system with base 5', () => {
		expect(hornerScheme(210, 5)).toEqual('1320')
		expect(hornerScheme(-210, 5)).toEqual('-1320')
		})
		test('Case 3: testing conversion to the octal system', () => {
		expect(hornerScheme(210, 8)).toEqual('322')
		expect(hornerScheme(-210, 8)).toEqual('-322')
		})
		test('Case 4: testing 0', () => {
		expect(hornerScheme(0, 8)).toEqual('0')
		expect(hornerScheme(0, 8)).toEqual('0')
		})
		test('Case 5: testing throwing an exception', () => {
		expect(() => hornerScheme('string', 2)).toThrow()
		expect(() => hornerScheme(10, 'base')).toThrow()
		expect(() => hornerScheme(true, false)).toThrow()
		})
		})