X Tutup
Skip to content

Commit 11b4bb8

Browse files
TornjVTornjV
committed
Merge branch 'gh-pages' of https://github.com/parkjs814/AlgorithmVisualizer into feature/chartTracer
2 parents 5b5361f + d97a778 commit 11b4bb8

File tree

29 files changed

+583
-80
lines changed

29 files changed

+583
-80
lines changed

‎algorithm/category.json‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,13 @@
1111
"bridges": "Find-Bridges"
1212
}
1313
},
14+
"cryptography": {
15+
"name": "Cryptography",
16+
"list": {
17+
"caesar_cipher": "Caesar Cipher",
18+
"affine_cipher": "Affine Cipher"
19+
}
20+
},
1421
"mst": {
1522
"name": "Minimum Spanning Tree",
1623
"list": {

‎algorithm/cryptography/affine_cipher/basic/code.js‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
/*
2+
code assumes that plainText contains ONLY LOWER CASE ALPHABETS
3+
*/
4+
5+
Number.prototype.mod = function (n) {
6+
return ((this%n)+n)%n;
7+
};
8+
9+
var keys = {a: 5, b: 7},
10+
N = 26;
11+
12+
function encrypt (plainText) {
13+
var cypherText = '';
14+
function cryptAlpha (alpha) {
15+
var index = alpha.charCodeAt (0) - 'a'.charCodeAt (0);
16+
var result = ((keys.a * index) + keys.b).mod (N);
17+
18+
logger._print ('Index of ' + alpha + ' = ' + index);
19+
20+
result += 'a'.charCodeAt (0);
21+
return String.fromCharCode (result);
22+
}
23+
24+
logger._print ('Beginning Affine Encryption');
25+
logger._print ('Encryption formula: <b>((keys.a * index_of_alphabet) + keys.b) % N</b>');
26+
logger._print ('keys.a=' + keys.a + ', keys.b=' + keys.b + ', N=' + N);
27+
28+
for (var i in plainText) {
29+
ptTracer._select (i)._wait ();
30+
ptTracer._deselect (i)._wait ();
31+
32+
cypherText += cryptAlpha (plainText [i]);
33+
34+
ptTracer._notify (i, cypherText.slice (-1))._wait ();
35+
ptTracer._denotify (i)._wait ();
36+
}
37+
38+
return cypherText;
39+
}
40+
41+
function decrypt (cypherText) {
42+
var plainText = '';
43+
var aInverse = (function () {
44+
for (var i = 1; i < N; i++) {
45+
if ( ((keys.a * i).mod (N)) == 1 ) {
46+
return i;
47+
}
48+
}
49+
}) ();
50+
51+
logger._print ('a<sup>-1</sup> = ' + aInverse);
52+
53+
function decryptAlpha (alpha) {
54+
var index = alpha.charCodeAt (0) - 'a'.charCodeAt (0);
55+
var result = (aInverse * (index - keys.b)).mod (N);
56+
57+
logger._print ('Index of ' + alpha + ' = ' + index);
58+
59+
result += 'a'.charCodeAt (0);
60+
return String.fromCharCode (result);
61+
}
62+
63+
logger._print ('Beginning Affine Decryption');
64+
logger._print ('Decryption formula: <b>(a<sup>-1</sup> * (index - keys.b)) % N</b>');
65+
logger._print ('keys.b=' + keys.b + ', N=' + N);
66+
67+
for (var i in cypherText) {
68+
ctTracer._select (i)._wait ();
69+
ctTracer._deselect (i)._wait ();
70+
71+
plainText += decryptAlpha (cypherText [i]);
72+
73+
ctTracer._notify (i, plainText.slice (-1))._wait ();
74+
ctTracer._denotify (i)._wait ();
75+
}
76+
77+
return plainText;
78+
}
79+
80+
var cipherText = encrypt (plainText);
81+
ctTracer._setData (cipherText);
82+
decrypt (cipherText);

‎algorithm/cryptography/affine_cipher/basic/data.js‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
function randString (length) {
2+
var choices = 'abcdefghijklmnopqrstuvwxyz';
3+
var text = '';
4+
5+
for (var i = 0; i < length; i++) {
6+
text += choices [Math.floor (Math.random () * choices.length)];
7+
}
8+
9+
return text;
10+
}
11+
12+
//var plainText = randString (5);
13+
var plainText = 'secret';
14+
var ptTracer = new Array1DTracer ('Encryption');
15+
var ctTracer = new Array1DTracer ('Decryption');
16+
var logger = new LogTracer ();
17+
18+
ptTracer._setData (plainText);

‎algorithm/cryptography/affine_cipher/desc.json‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
{
2+
"Affine Cipher": "The affine cipher is a type of monoalphabetic substitution cipher, wherein each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter.",
3+
"Applications": [
4+
"Cryptanalysis",
5+
"More complex Variations of Affine Cipher are used in practical cryptography"
6+
],
7+
"Complexity": {
8+
"time": "worst O(N), N = length of plain/cipher text",
9+
"space": "worst O(N), to create the new mapping (plain->cipher, cipher->plain)"
10+
},
11+
"References": [
12+
"<a href='http://practicalcryptography.com/ciphers/affine-cipher/'>Practicalcryptography</a>"
13+
],
14+
"files": {
15+
"basic": "Encrypting and Decrypting a string using affine functions"
16+
}
17+
}

‎algorithm/cryptography/caesar_cipher/basic/code.js‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
function getPosUp(pos) {
2+
return (pos === alphabet.length - 1) ? 0 : pos + 1;
3+
}
4+
5+
function getPosDown(pos) {
6+
return (pos === 0) ? alphabet.length - 1 : pos - 1;
7+
}
8+
9+
function getNextChar(currChar, direction) {
10+
var pos = alphabetMap[currChar];
11+
var nextPos = direction === 'up' ? getPosUp(pos) : getPosDown(pos);
12+
var nextChar = alphabet.charAt(nextPos);
13+
14+
logger._print(currChar + ' -> ' + nextChar);
15+
return nextChar;
16+
}
17+
18+
function cipher(str, rotation, direction, cipherTracer) {
19+
if (!str) return '';
20+
21+
for (var i = 0; i < str.length; i++) {
22+
23+
cipherTracer._wait();
24+
25+
var currChar = str.charAt(i);
26+
var r = rotation;
27+
28+
logger._print('Rotating ' + currChar + ' ' + direction + ' ' + rotation + ' times');
29+
cipherTracer._select(i)._wait();
30+
31+
// perform given amount of rotations in the given direction
32+
while (r-- > 0) {
33+
currChar = getNextChar(currChar, direction);
34+
cipherTracer._notify(i, currChar)._wait();
35+
}
36+
37+
str = str.substring(0, i) + currChar + str.substring(i + 1);
38+
logger._print('Current result: ' + str);
39+
}
40+
41+
return str;
42+
}
43+
44+
function encrypt(str, rotation) {
45+
logger._print('Encrypting: ' + str);
46+
return cipher(str, rotation, 'down', encryptTracer);
47+
}
48+
49+
function decrypt(str, rotation) {
50+
logger._print('Decrypting: ' + str);
51+
return cipher(str, rotation, 'up', decryptTracer);
52+
}
53+
54+
var encrypted = encrypt(string, rotation);
55+
logger._print('Encrypted result: ' + encrypted);
56+
57+
decryptTracer._setData(encrypted);
58+
var decrypted = decrypt(encrypted, rotation);
59+
logger._print('Decrypted result: ' + decrypted);

‎algorithm/cryptography/caesar_cipher/basic/data.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
var string = 'secret';
2+
var rotation = 5;
3+
var alphabet = 'abcdefghijklmnopqrstuvwxyz';
4+
// create a map of char -> position to improve run time
5+
// otherwise we would have to search the alphabet each
6+
// time to find the character position
7+
var alphabetMap = alphabet.split('').reduce(function(map, curr, idx) {
8+
map[curr] = idx;
9+
return map;
10+
}, {});
11+
12+
var logger = new LogTracer();
13+
var encryptTracer = new Array1DTracer('Encryption');
14+
var decryptTracer = new Array1DTracer('Decryption');
15+
16+
encryptTracer._setData(string);

‎algorithm/cryptography/caesar_cipher/desc.json‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
{
2+
"Caesar Cipher": "In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.",
3+
"Applications": [
4+
"Often incorporated as part of more complex schemes, such as the Vigenère cipher"
5+
],
6+
"Complexity": {
7+
"time": "best O(N * #ofRotations), worst O(N * #ofRotations * alphabetSize)",
8+
"space": "best O(1), worst O(alphabetSize)"
9+
},
10+
"References": [
11+
"<a href='https://en.wikipedia.org/wiki/Caesar_cipher'>Wikipedia</a>"
12+
],
13+
"files": {
14+
"basic": "Encrypting and Decrypting a string using character rotation"
15+
}
16+
}

‎algorithm/dp/fibonacci/basic/data.js‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
1-
var tracer = new Array1DTracer();
1+
var tracer = new Array1DTracer('Sequence');
22
var index = 15;
33
var D = [1, 1];
44
for (var i = 2; i < index; i++) {
55
D.push(0);
66
}
7-
tracer._setData(D);
7+
tracer._setData(D);

‎algorithm/dp/knapsack_problem/basic/data.js‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ for (var i = 0; i < N + 1; i++) {
1111
}
1212
}
1313

14-
var tracer = new Array2DTracer()._setData(DP);
15-
var dataViewer1 = new Array1DTracer()._setData(val);
16-
var dataViewer2 = new Array1DTracer()._setData(wt);
17-
var logger = new LogTracer();
14+
var tracer = new Array2DTracer('Knapsack Table')._setData(DP);
15+
var dataViewer1 = new Array1DTracer('Values')._setData(val);
16+
var dataViewer2 = new Array1DTracer('Weights')._setData(wt);
17+
var logger = new LogTracer();

‎algorithm/dp/knapsack_problem/desc.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,4 +10,4 @@
1010
"files": {
1111
"basic": "Knapsack problem"
1212
}
13-
}
13+
}

0 commit comments

Comments
 (0)
X Tutup