Skip to content

Commit c7b203f

Browse files
trekhlebtrekhleb
authored
Merge branch 'master' into master
2 parents dc7e20a + adda5c5 commit c7b203f

10 files changed

Lines changed: 945 additions & 43 deletions

File tree

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,8 @@ a set of rules that precisely define a sequence of operations.
7777
* `B` [Radian & Degree](src/algorithms/math/radian) - radians to degree and backwards conversion
7878
* `B` [Fast Powering](src/algorithms/math/fast-powering)
7979
* `B` [Horner's method](src/algorithms/math/horner-method) - polynomial evaluation
80+
* `B` [Matrices](src/algorithms/math/matrix) - matrices and basic matrix operations (multiplication, transposition, etc.)
81+
* `B` [Euclidean Distance](src/algorithms/math/euclidean-distance) - distance between two points/vectors/matrices
8082
* `A` [Integer Partition](src/algorithms/math/integer-partition)
8183
* `A` [Square Root](src/algorithms/math/square-root) - Newton's method
8284
* `A` [Liu Hui π Algorithm](src/algorithms/math/liu-hui) - approximate π calculations based on N-gons

‎src/algorithms/cryptography/hill-cipher/hillCipher.js‎

Lines changed: 24 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
import * as mtrx from '../../math/matrix/Matrix';
2+
13
// The code of an 'A' character (equals to 65).
24
const alphabetCodeShift = 'A'.codePointAt(0);
35
const englishAlphabetSize = 26;
@@ -15,33 +17,36 @@ const generateKeyMatrix = (keyString) => {
1517
'Invalid key string length. The square root of the key string must be an integer',
1618
);
1719
}
18-
const keyMatrix = [];
1920
let keyStringIndex = 0;
20-
for (let i = 0; i < matrixSize; i += 1) {
21-
const keyMatrixRow = [];
22-
for (let j = 0; j < matrixSize; j += 1) {
21+
return mtrx.generate(
22+
[matrixSize, matrixSize],
23+
// Callback to get a value of each matrix cell.
24+
// The order the matrix is being filled in is from left to right, from top to bottom.
25+
() => {
2326
// A → 0, B → 1, ..., a → 32, b → 33, ...
2427
const charCodeShifted = (keyString.codePointAt(keyStringIndex)) % alphabetCodeShift;
25-
keyMatrixRow.push(charCodeShifted);
2628
keyStringIndex += 1;
27-
}
28-
keyMatrix.push(keyMatrixRow);
29-
}
30-
return keyMatrix;
29+
return charCodeShifted;
30+
},
31+
);
3132
};
3233

3334
/**
3435
* Generates a message vector from a given message.
3536
*
3637
* @param {string} message - the message to encrypt.
37-
* @return {number[]} messageVector
38+
* @return {number[][]} messageVector
3839
*/
3940
const generateMessageVector = (message) => {
40-
const messageVector = [];
41-
for (let i = 0; i < message.length; i += 1) {
42-
messageVector.push(message.codePointAt(i) % alphabetCodeShift);
43-
}
44-
return messageVector;
41+
return mtrx.generate(
42+
[message.length, 1],
43+
// Callback to get a value of each matrix cell.
44+
// The order the matrix is being filled in is from left to right, from top to bottom.
45+
(cellIndices) => {
46+
const rowIndex = cellIndices[0];
47+
return message.codePointAt(rowIndex) % alphabetCodeShift;
48+
},
49+
);
4550
};
4651

4752
/**
@@ -59,19 +64,17 @@ export function hillCipherEncrypt(message, keyString) {
5964
}
6065

6166
const keyMatrix = generateKeyMatrix(keyString);
67+
const messageVector = generateMessageVector(message);
6268

6369
// keyString.length must equal to square of message.length
6470
if (keyMatrix.length !== message.length) {
6571
throw new Error('Invalid key string length. The key length must be a square of message length');
6672
}
6773

68-
const messageVector = generateMessageVector(message);
74+
const cipherVector = mtrx.dot(keyMatrix, messageVector);
6975
let cipherString = '';
70-
for (let row = 0; row < keyMatrix.length; row += 1) {
71-
let item = 0;
72-
for (let column = 0; column < keyMatrix.length; column += 1) {
73-
item += keyMatrix[row][column] * messageVector[column];
74-
}
76+
for (let row = 0; row < cipherVector.length; row += 1) {
77+
const item = cipherVector[row];
7578
cipherString += String.fromCharCode((item % englishAlphabetSize) + alphabetCodeShift);
7679
}
7780

‎src/algorithms/math/euclidean-distance/README.md‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
# Euclidean Distance
2+
3+
In mathematics, the **Euclidean distance** between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore occasionally being called the Pythagorean distance.
4+
5+
![Euclidean distance between two points](https://upload.wikimedia.org/wikipedia/commons/5/55/Euclidean_distance_2d.svg)
6+
7+
## Distance formulas
8+
9+
### One dimension
10+
11+
The distance between any two points on the real line is the absolute value of the numerical difference of their coordinates
12+
13+
![One dimension formula](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d75418dbec9482dbcb70f9063ad66e9cf7b5db9)
14+
15+
### Two dimensions
16+
17+
![Two dimensions formula](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c0157084fd89f5f3d462efeedc47d3d7aa0b773)
18+
19+
### Higher dimensions
20+
21+
In three dimensions, for points given by their Cartesian coordinates, the distance is
22+
23+
![Three dimensions formula](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1d13a40a7b203b455ae6d4be8b3cce898bda625)
24+
25+
Example: the distance between the two points `(8,2,6)` and `(3,5,7)`:
26+
27+
![3-dimension example](https://www.mathsisfun.com/algebra/images/dist-2-points-3d.svg)
28+
29+
In general, for points given by Cartesian coordinates in `n`-dimensional Euclidean space, the distance is
30+
31+
![n-dimensional formula](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0ef4fe055b2a51b4cca43a05e5d1cd93f758dcc)
32+
33+
## References
34+
35+
- [Euclidean Distance on MathIsFun](https://www.mathsisfun.com/algebra/distance-2-points.html)
36+
- [Euclidean Distance on Wikipedia](https://en.wikipedia.org/wiki/Euclidean_distance)

‎src/algorithms/math/euclidean-distance/__tests__/euclideanDistance.test.js‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
import euclideanDistance from '../euclideanDistance';
2+
3+
describe('euclideanDistance', () => {
4+
it('should calculate euclidean distance between vectors', () => {
5+
expect(euclideanDistance([[1]], [[2]])).toEqual(1);
6+
expect(euclideanDistance([[2]], [[1]])).toEqual(1);
7+
expect(euclideanDistance([[5, 8]], [[7, 3]])).toEqual(5.39);
8+
expect(euclideanDistance([[5], [8]], [[7], [3]])).toEqual(5.39);
9+
expect(euclideanDistance([[8, 2, 6]], [[3, 5, 7]])).toEqual(5.92);
10+
expect(euclideanDistance([[8], [2], [6]], [[3], [5], [7]])).toEqual(5.92);
11+
expect(euclideanDistance([[[8]], [[2]], [[6]]], [[[3]], [[5]], [[7]]])).toEqual(5.92);
12+
});
13+
14+
it('should throw an error in case if two matrices are of different shapes', () => {
15+
expect(() => euclideanDistance([[1]], [[[2]]])).toThrowError(
16+
'Matrices have different dimensions',
17+
);
18+
19+
expect(() => euclideanDistance([[1]], [[2, 3]])).toThrowError(
20+
'Matrices have different shapes',
21+
);
22+
});
23+
});

‎src/algorithms/math/euclidean-distance/euclideanDistance.js‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* @typedef {import('../matrix/Matrix.js').Matrix} Matrix
3+
*/
4+
5+
import * as mtrx from '../matrix/Matrix';
6+
7+
/**
8+
* Calculates the euclidean distance between 2 matrices.
9+
*
10+
* @param {Matrix} a
11+
* @param {Matrix} b
12+
* @returns {number}
13+
* @trows {Error}
14+
*/
15+
const euclideanDistance = (a, b) => {
16+
mtrx.validateSameShape(a, b);
17+
18+
let squaresTotal = 0;
19+
20+
mtrx.walk(a, (indices, aCellValue) => {
21+
const bCellValue = mtrx.getCellAtIndex(b, indices);
22+
squaresTotal += (aCellValue - bCellValue) ** 2;
23+
});
24+
25+
return Number(Math.sqrt(squaresTotal).toFixed(2));
26+
};
27+
28+
export default euclideanDistance;

0 commit comments

Comments
 (0)