Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

UniquePaths2 and HornerScheme#1240

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
Saimon398 wants to merge5 commits intoTheAlgorithms:master
base:master
Choose a base branch
Loading
fromSaimon398:master
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
80 changes: 80 additions & 0 deletionsDynamic-Programming/UniquePaths2.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
/*
* 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 += 1) {
const submatrix = []
for (let k = 0; k < columns; k += 1) {
submatrix[k] = filler
}
matrix[i] = submatrix
}
return matrix
}

/**
* @description Return number of unique paths
* @param {Object []} obstacles Obstacles grid
* @returns {Number}
*/
const uniquePaths2 = (obstacles) => {
if (!(obstacles instanceof Object)) {
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 += 1) {
// If robot encounters an obstacle in these cells,
// he cannot continue movind in that direction
if (obstacles[i][0]) {
break
}
grid[i][0] = 1
}
for (let j = 0; j < columns; j += 1) {
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 += 1) {
for (let j = 1; j < columns; j += 1) {
if (obstacles[i][j]) {
grid[i][j] = 0
} else {
grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
}
}
}
return grid[rows - 1][columns - 1]
}

export { uniquePaths2 }
19 changes: 19 additions & 0 deletionsDynamic-Programming/tests/UniquePaths2.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
import { uniquePaths2 } from '../UniquePaths2'

describe('Unique Paths2', () => {
// Should return number of ways, taken into account the obstacles
test('Case 1: 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('Case 2: 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('Case 3: there are wrong type of input data', () => {
expect(() => uniquePaths2('wrong input')).toThrow()
expect(() => uniquePaths2(100)).toThrow()
})
})
38 changes: 38 additions & 0 deletionsMaths/HornerScheme.js
View file
Open in desktop
Original file line numberDiff line numberDiff 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 }
25 changes: 25 additions & 0 deletionsMaths/test/HornerScheme.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff 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()
})
})
[8]ページ先頭
©2009-2025 Movatter.jp