Skip to content

Commit 211c72d

Browse files
pertrai1pertrai1
committed
Merge branch 'master' into dp-abbrev
2 parents 6da05a2 + cafb343 commit 211c72d

25 files changed

+625
-86
lines changed

‎.github/workflows/Ci.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ jobs:
2525
run: npm run test
2626

2727
- name: 💄 Code style
28-
run: npm run style
28+
run: npm run check-style
2929

3030
codespell:
3131
name: Check for spelling errors

‎Backtracking/AllCombinationsOfSizeK.js

Lines changed: 23 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,28 @@
1-
/*
2-
Problem: Given two numbers, n and k, make all unique combinations of k numbers from 1 to n and in sorted order
3-
4-
What is combinations?
5-
- Combinations is selecting items from a collections without considering the order of selection
6-
7-
Example:
8-
- We have an apple, a banana, and a jackfruit
9-
- We have three objects, and need to choose two items, then combinations will be
10-
11-
1. Apple & Banana
12-
2. Apple & Jackfruit
13-
3. Banana & Jackfruit
14-
15-
To read more about combinations, you can visit the following link:
16-
- https://betterexplained.com/articles/easy-permutations-and-combinations/
17-
18-
Solution:
19-
- We will be using backtracking to solve this questions
20-
- Take one element, and make all them combinations for k-1 elements
21-
- Once we get all combinations of that element, pop it and do same for next element
22-
*/
23-
24-
class Combinations {
25-
constructor(n, k) {
26-
this.n = n
27-
this.k = k
28-
this.current = [] // will be used for storing current combination
29-
this.combinations = []
30-
}
31-
32-
findCombinations(high = this.n, total = this.k, low = 1) {
33-
if (total === 0) {
34-
this.combinations.push([...this.current])
35-
return this.combinations
1+
function generateCombinations(n, k) {
2+
let currentCombination = []
3+
let allCombinations = [] // will be used for storing all combinations
4+
let currentValue = 1
5+
6+
function findCombinations() {
7+
if (currentCombination.length === k) {
8+
// Add the array of size k to the allCombinations array
9+
allCombinations.push([...currentCombination])
10+
return
3611
}
37-
for (let i = low; i <= high; i++) {
38-
this.current.push(i)
39-
this.findCombinations(high, total - 1, i + 1)
40-
this.current.pop()
12+
if (currentValue > n) {
13+
// Check for exceeding the range
14+
return
4115
}
42-
return this.combinations
16+
currentCombination.push(currentValue++)
17+
findCombinations()
18+
currentCombination.pop()
19+
findCombinations()
20+
currentValue--
4321
}
22+
23+
findCombinations()
24+
25+
return allCombinations
4426
}
4527

46-
export { Combinations }
28+
export { generateCombinations }

‎Backtracking/KnightTour.js

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2,12 +2,13 @@
22

33
class OpenKnightTour {
44
constructor(size) {
5+
// Constructor to initialize the chessboard and size
56
this.board = new Array(size).fill(0).map(() => new Array(size).fill(0))
67
this.size = size
78
}
89

910
getMoves([i, j]) {
10-
// helper function to get the valid moves of the knight from the current position
11+
// Helper function to get the valid moves of the knight from the current position
1112
const moves = [
1213
[i + 2, j - 1],
1314
[i + 2, j + 1],
@@ -19,18 +20,19 @@ class OpenKnightTour {
1920
[i - 1, j + 2]
2021
]
2122

23+
// Filter out moves that are within the board boundaries
2224
return moves.filter(
2325
([y, x]) => y >= 0 && y < this.size && x >= 0 && x < this.size
2426
)
2527
}
2628

2729
isComplete() {
28-
// helper function to check if the board is complete
30+
// Helper function to check if the board is complete
2931
return !this.board.map((row) => row.includes(0)).includes(true)
3032
}
3133

3234
solve() {
33-
// function to find the solution for the given board
35+
// Function to find the solution for the given board
3436
for (let i = 0; i < this.size; i++) {
3537
for (let j = 0; j < this.size; j++) {
3638
if (this.solveHelper([i, j], 0)) return true
@@ -40,22 +42,23 @@ class OpenKnightTour {
4042
}
4143

4244
solveHelper([i, j], curr) {
43-
// helper function for the main computation
45+
// Helper function for the main computation
4446
if (this.isComplete()) return true
4547

48+
// Iterate through possible moves and attempt to fill the board
4649
for (const [y, x] of this.getMoves([i, j])) {
4750
if (this.board[y][x] === 0) {
4851
this.board[y][x] = curr + 1
4952
if (this.solveHelper([y, x], curr + 1)) return true
50-
// backtracking
53+
// Backtracking: If the solution is not found, reset the cell to 0
5154
this.board[y][x] = 0
5255
}
5356
}
5457
return false
5558
}
5659

5760
printBoard(output = (value) => console.log(value)) {
58-
// utility function to display the board
61+
// Utility function to display the board
5962
for (const row of this.board) {
6063
let string = ''
6164
for (const elem of row) {

‎Backtracking/MColoringProblem.js

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/**
2+
* Colors a graph using up to m colors such that no two adjacent vertices share the same color.
3+
* @param {number[][]} graph - Adjacency matrix of the graph, using 0 for no edge.
4+
* @param {number} m - The number of colors to use.
5+
* @returns {?Array.<number>} A valid M-coloring of the graph using colors 1 to m, or null if none exists.
6+
* @see https://en.wikipedia.org/wiki/Graph_coloring
7+
*/
8+
function mColoring(graph, m) {
9+
const colors = new Array(graph.length).fill(0)
10+
11+
// Check if it's safe to color a vertex with a given color.
12+
function isSafe(vertex, color) {
13+
for (let i = 0; i < graph.length; i++) {
14+
if (graph[vertex][i] && colors[i] === color) {
15+
return false
16+
}
17+
}
18+
return true
19+
}
20+
21+
// Use backtracking to try and color the graph.
22+
function solveColoring(vertex = 0) {
23+
if (vertex === graph.length) {
24+
return true
25+
}
26+
27+
for (let color = 1; color <= m; color++) {
28+
if (isSafe(vertex, color)) {
29+
colors[vertex] = color
30+
31+
if (solveColoring(vertex + 1)) {
32+
return true
33+
}
34+
35+
// If no solution, backtrack.
36+
colors[vertex] = 0
37+
}
38+
}
39+
return false
40+
}
41+
42+
// If coloring is possible, return the colors.
43+
if (solveColoring()) {
44+
return colors
45+
}
46+
return null
47+
}
48+
49+
export { mColoring }

‎Backtracking/tests/AllCombinationsOfSizeK.test.js

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,18 @@
1-
import { Combinations } from '../AllCombinationsOfSizeK'
1+
import { generateCombinations } from '../AllCombinationsOfSizeK'
22

33
describe('AllCombinationsOfSizeK', () => {
44
it('should return 3x2 matrix solution for n = 3 and k = 2', () => {
5-
const test1 = new Combinations(3, 2)
6-
expect(test1.findCombinations()).toEqual([
5+
const res = generateCombinations(3, 2)
6+
expect(res).toEqual([
77
[1, 2],
88
[1, 3],
99
[2, 3]
1010
])
1111
})
1212

1313
it('should return 6x2 matrix solution for n = 4 and k = 2', () => {
14-
const test2 = new Combinations(4, 2)
15-
expect(test2.findCombinations()).toEqual([
14+
const res = generateCombinations(4, 2)
15+
expect(res).toEqual([
1616
[1, 2],
1717
[1, 3],
1818
[1, 4],

‎Backtracking/tests/MColoringProblem.test.js

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
import { mColoring } from '../MColoringProblem'
2+
3+
describe('MColoringProblem', () => {
4+
it('should color a triangle with 3 colors', () => {
5+
const graph = [
6+
[0, 1, 1],
7+
[1, 0, 1],
8+
[1, 1, 0]
9+
]
10+
const solution = mColoring(graph, 3)
11+
expect(solution).not.toBeNull()
12+
})
13+
14+
it('should not color a triangle with 2 colors', () => {
15+
const graph = [
16+
[0, 1, 1],
17+
[1, 0, 1],
18+
[1, 1, 0]
19+
]
20+
const solution = mColoring(graph, 2)
21+
expect(solution).toBeNull()
22+
})
23+
})

‎Bit-Manipulation/BinaryCountSetBits.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@ function BinaryCountSetBits(a) {
1616

1717
let count = 0
1818
while (a) {
19-
a &= (a - 1)
19+
a &= a - 1
2020
count++
2121
}
2222

‎Bit-Manipulation/GenerateSubSets.js

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/**
2+
* @function generateSubSets
3+
* @param {Array} inputArray
4+
* @returns {Array}
5+
* @example [1,2] -> [[],[1],[2],[1,2]]
6+
*/
7+
8+
// The time complexity of this algorithm is BigO(2^n) where n is the length of array
9+
function generateSubSets(inputArray) {
10+
if (!Array.isArray(inputArray)) {
11+
throw new Error('Provided input is not an array')
12+
}
13+
if (inputArray.length > 32) {
14+
throw new RangeError('Error size should be less than equal to 32')
15+
}
16+
let arrayLength = inputArray.length
17+
let subSets = []
18+
// loop till (2^n) - 1
19+
for (let i = 0; i < 1 << arrayLength; i++) {
20+
let subSet = []
21+
for (let j = 0; j < arrayLength; j++) {
22+
// 1 << j it shifts binary digit 1 by j positions and then we perform
23+
// and by AND operation we are checking whetheer jth bit
24+
// in i is set to 1 if result is non zero just add into set
25+
if (i & (1 << j)) {
26+
subSet.push(inputArray[j])
27+
}
28+
}
29+
subSets.push(subSet)
30+
}
31+
return subSets
32+
}
33+
34+
export { generateSubSets }

‎Bit-Manipulation/test/GenerateSubSets.test.js

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
import { generateSubSets } from '../GenerateSubSets'
2+
3+
describe('subSets', () => {
4+
it('find the subsets', () => {
5+
expect(generateSubSets([1, 2, 3])).toEqual([
6+
[],
7+
[1],
8+
[2],
9+
[1, 2],
10+
[3],
11+
[1, 3],
12+
[2, 3],
13+
[1, 2, 3]
14+
])
15+
expect(generateSubSets([1, 2])).toEqual([[], [1], [2], [1, 2]])
16+
expect(generateSubSets([1, 2, 3])).toEqual([
17+
[],
18+
[1],
19+
[2],
20+
[1, 2],
21+
[3],
22+
[1, 3],
23+
[2, 3],
24+
[1, 2, 3]
25+
])
26+
expect(() => generateSubSets('invalid')).toThrow(
27+
'Provided input is not an array'
28+
)
29+
expect(() =>
30+
generateSubSets([
31+
1, 2, 2, 1, 2, 3, 4, 3, 2, 3, 4, 3, 2, 2, 2, 3, 12, 11, 4, 2, 2, 2, 2,
32+
1, 2, 3, 5, 6, 7, 7, 8, 6, 5, 6, 7, 8, 9, 8, 0, 6
33+
])
34+
).toThrow('Error size should be less than equal to 32')
35+
})
36+
})

‎DIRECTORY.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,12 +3,14 @@
33
* [generateParentheses](Backtracking/generateParentheses.js)
44
* [GeneratePermutations](Backtracking/GeneratePermutations.js)
55
* [KnightTour](Backtracking/KnightTour.js)
6+
* [MColoringProblem](Backtracking/MColoringProblem.js)
67
* [NQueens](Backtracking/NQueens.js)
78
* [RatInAMaze](Backtracking/RatInAMaze.js)
89
* [Sudoku](Backtracking/Sudoku.js)
910
* [SumOfSubset](Backtracking/SumOfSubset.js)
1011
* **Bit-Manipulation**
1112
* [BinaryCountSetBits](Bit-Manipulation/BinaryCountSetBits.js)
13+
* [GenerateSubSets](Bit-Manipulation/GenerateSubSets.js)
1214
* [GrayCodes](Bit-Manipulation/GrayCodes.js)
1315
* [IsPowerofFour](Bit-Manipulation/IsPowerofFour.js)
1416
* [IsPowerOfTwo](Bit-Manipulation/IsPowerOfTwo.js)
@@ -166,6 +168,7 @@
166168
* [Area](Maths/Area.js)
167169
* [ArithmeticGeometricMean](Maths/ArithmeticGeometricMean.js)
168170
* [ArmstrongNumber](Maths/ArmstrongNumber.js)
171+
* [AutomorphicNumber](Maths/AutomorphicNumber.js)
169172
* [AverageMean](Maths/AverageMean.js)
170173
* [AverageMedian](Maths/AverageMedian.js)
171174
* [BinaryConvert](Maths/BinaryConvert.js)
@@ -308,6 +311,7 @@
308311
* [LinearSearch](Search/LinearSearch.js)
309312
* [Minesweeper](Search/Minesweeper.js)
310313
* [QuickSelectSearch](Search/QuickSelectSearch.js)
314+
* [RabinKarp](Search/RabinKarp.js)
311315
* [SlidingWindow](Search/SlidingWindow.js)
312316
* [StringSearch](Search/StringSearch.js)
313317
* [TernarySearch](Search/TernarySearch.js)

‎Dynamic-Programming/ZeroOneKnapsack.js

Lines changed: 17 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,34 @@
11
/**
22
* A Dynamic Programming based solution for calculating Zero One Knapsack
33
* https://en.wikipedia.org/wiki/Knapsack_problem
4+
*
5+
* Time and Space Complexity: O(n*cap)
46
*/
5-
67
const zeroOneKnapsack = (arr, n, cap, cache) => {
8+
// Base Case: No capacity or no items
79
if (cap === 0 || n === 0) {
810
cache[n][cap] = 0
911
return cache[n][cap]
1012
}
13+
14+
// Lookup (value already calculated)
1115
if (cache[n][cap] !== -1) {
1216
return cache[n][cap]
1317
}
18+
19+
// Profit when excluding the nth item
20+
let notPick = zeroOneKnapsack(arr, n - 1, cap, cache)
21+
22+
// Profit when including the nth item
23+
let pick = 0
1424
if (arr[n - 1][0] <= cap) {
15-
cache[n][cap] = Math.max(
16-
arr[n - 1][1] + zeroOneKnapsack(arr, n - 1, cap - arr[n - 1][0], cache),
17-
zeroOneKnapsack(arr, n - 1, cap, cache)
18-
)
19-
return cache[n][cap]
20-
} else {
21-
cache[n][cap] = zeroOneKnapsack(arr, n - 1, cap, cache)
22-
return cache[n][cap]
25+
// If weight of the nth item is within the capacity
26+
pick =
27+
arr[n - 1][1] + zeroOneKnapsack(arr, n - 1, cap - arr[n - 1][0], cache)
2328
}
29+
30+
cache[n][cap] = Math.max(pick, notPick) // maximize profit
31+
return cache[n][cap]
2432
}
2533

2634
const example = () => {

0 commit comments

Comments
 (0)