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

Commit9641940

Browse files
jprasktrekhleb
andauthored
Add rail fence cipher (trekhleb#516)
* Add rail fence cipher encoder & decoder* Add functions to encode & decode strings using the rail fence cipher method* Add unit tests covering empty strings, pair & odd number of characters in the input string, n=3 & n=4* Add a README.md for the algorithm* Update root README.md to link to the new algorithm* Rename the CI workflow file.Co-authored-by: Oleksii Trekhleb <trehleb@gmail.com>
1 parentc755110 commit9641940

File tree

7 files changed

+262
-0
lines changed

7 files changed

+262
-0
lines changed
File renamed without changes.

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -143,6 +143,7 @@ a set of rules that precisely define a sequence of operations.
143143
*`A`[Travelling Salesman Problem](src/algorithms/graph/travelling-salesman) - shortest possible route that visits each city and returns to the origin city
144144
***Cryptography**
145145
*`B`[Polynomial Hash](src/algorithms/cryptography/polynomial-hash) - rolling hash function based on polynomial
146+
*`B`[Rail Fence Cypher](src/algorithms/cryptography/rail-fence-cipher) - a transposition cipher algorithm for encoding messages
146147
*`B`[Caesar Cipher](src/algorithms/cryptography/caesar-cipher) - simple substitution cipher
147148
*`B`[Hill Cipher](src/algorithms/cryptography/hill-cipher) - substitution cipher based on linear algebra
148149
***Machine Learning**
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
#Rail fence Cipher
2+
3+
This is a[transposition cipher](https://en.wikipedia.org/wiki/Transposition_cipher) in which the message is split accross a set of rails on a fence for encoding. The fence is populated with the message's characters, starting at the top left and adding a character on each position, traversing them diagonally to the bottom. Upon reaching the last rail, the direction should then turn diagonal and upwards up to the very first rail in a zig-zag motion. Rinse and repeat until the message is fully disposed across the fence. The encoded message is the result of concatenating the text in each rail, from top to bottom.
4+
5+
From[wikipedia](https://en.wikipedia.org/wiki/Rail_fence_cipher), this is what the message`WE ARE DISCOVERED. FLEE AT ONCE` looks like on a 3-rail fence:
6+
7+
```
8+
W . . . E . . . C . . . R . . . L . . . T . . . E
9+
. E . R . D . S . O . E . E . F . E . A . O . C .
10+
. . A . . . I . . . V . . . D . . . E . . . N . .
11+
-------------------------------------------------
12+
ECRLTEERDSOEEFEAOCAIVDEN
13+
```
14+
15+
The message can then be decoded by re-creating the encode fence, with the same traversal pattern, except characters should only be added on one rail at a time. To ilustrate that, a dash can be added on the rails that are not supposed to be poupated yet. This is what the fence would look like after populating the first rail, the dashes represent positions that were visited but not populated.
16+
17+
```
18+
W . . . E . . . C . . . R . . . L . . . T . . . E
19+
. - . - . - . - . - . - . - . - . - . - . - . - .
20+
. . - . . . - . . . - . . . - . . . - . . . - . .
21+
```
22+
23+
It's time to start populating the next rail once the number of visited fence positions is equal to the number of characters in the message.
24+
25+
[Learn more](https://crypto.interactive-maths.com/rail-fence-cipher.html)
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
importencodeRailFenceCipherfrom'../encodeRailFence';
2+
importdecodeRailFenceCipherfrom'../decodeRailFence';
3+
4+
describe('rail fence cipher',()=>{
5+
it('encodes a string correctly for base=3',()=>{
6+
expect(encodeRailFenceCipher('',3)).toBe('');
7+
expect(encodeRailFenceCipher('WEAREDISCOVEREDFLEEATONCE',3)).toBe('WECRLTEERDSOEEFEAOCAIVDEN');
8+
expect(encodeRailFenceCipher('Hello, World!',3)).toBe('Hoo!el,Wrdl l');
9+
});
10+
11+
it('decodes a string correctly for base=3',()=>{
12+
expect(decodeRailFenceCipher('',3)).toBe('');
13+
expect(decodeRailFenceCipher('WECRLTEERDSOEEFEAOCAIVDEN',3)).toBe('WEAREDISCOVEREDFLEEATONCE');
14+
expect(decodeRailFenceCipher('Hoo!el,Wrdl l',3)).toBe('Hello, World!');
15+
});
16+
17+
it('encodes a string correctly for base=4',()=>{
18+
expect(encodeRailFenceCipher('',4)).toBe('');
19+
expect(encodeRailFenceCipher('THEYAREATTACKINGFROMTHENORTH',4)).toBe('TEKOOHRACIRMNREATANFTETYTGHH');
20+
});
21+
22+
it('decodes a string correctly for base=4',()=>{
23+
expect(decodeRailFenceCipher('',4)).toBe('');
24+
expect(decodeRailFenceCipher('TEKOOHRACIRMNREATANFTETYTGHH',4)).toBe('THEYAREATTACKINGFROMTHENORTH');
25+
});
26+
});
Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
import{
2+
addChar,
3+
buildFence,
4+
DIRECTIONS,
5+
getNextDirection,
6+
}from'./railFenceCipher';
7+
8+
/**
9+
*@param {object} params
10+
*@param {number} params.railCount
11+
*@param {number} params.strLen
12+
*@param {Array} params.string
13+
*@param {Array} params.fence
14+
*@param {number} params.targetRail
15+
*@param {number} params.direction
16+
*@param {Array} params.coords
17+
*
18+
*@returns {Array}
19+
*/
20+
constfillDecodeFence=({
21+
railCount, strLen, string, fence, targetRail, direction, coords,
22+
})=>{
23+
if(string.length===0)returnfence;
24+
25+
const[currentRail,currentColumn]=coords;
26+
constshouldGoNextRail=currentColumn===strLen-1;
27+
constnextDirection=shouldGoNextRail
28+
?DIRECTIONS.DOWN
29+
:getNextDirection({ railCount, currentRail, direction});
30+
constnextRail=shouldGoNextRail ?targetRail+1 :targetRail;
31+
constnextCoords=[
32+
shouldGoNextRail ?0 :currentRail+nextDirection,
33+
shouldGoNextRail ?0 :currentColumn+1,
34+
];
35+
36+
constshouldAddChar=currentRail===targetRail;
37+
const[currentChar, ...remainderString]=string;
38+
constnextString=shouldAddChar ?remainderString :string;
39+
constnextFence=shouldAddChar ?fence.map(addChar(currentRail,currentChar)) :fence;
40+
41+
returnfillDecodeFence({
42+
railCount,
43+
strLen,
44+
string:nextString,
45+
fence:nextFence,
46+
targetRail:nextRail,
47+
direction:nextDirection,
48+
coords:nextCoords,
49+
});
50+
};
51+
52+
/**
53+
*@param {object} params
54+
*@param {number} params.railCount
55+
*@param {number} params.strLen
56+
*@param {Array} params.fence
57+
*@param {number} params.currentRail
58+
*@param {number} params.direction
59+
*@param {Array} params.code
60+
*
61+
*@returns {string}
62+
*/
63+
constdecodeFence=({
64+
railCount, strLen, fence, currentRail, direction, code,
65+
})=>{
66+
if(code.length===strLen)returncode.join('');
67+
68+
const[currentChar, ...nextRail]=fence[currentRail];
69+
constnextDirection=getNextDirection({ railCount, currentRail, direction});
70+
71+
returndecodeFence({
72+
railCount,
73+
strLen,
74+
currentRail:currentRail+nextDirection,
75+
direction:nextDirection,
76+
code:[...code,currentChar],
77+
fence:fence.map((rail,idx)=>(idx===currentRail ?nextRail :rail)),
78+
});
79+
};
80+
81+
/**
82+
*@param {string} string
83+
*@param {number} railCount
84+
*
85+
*@returns {string}
86+
*/
87+
exportdefaultfunctiondecodeRailFenceCipher(string,railCount){
88+
conststrLen=string.length;
89+
constemptyFence=buildFence(railCount);
90+
constfilledFence=fillDecodeFence({
91+
railCount,
92+
strLen,
93+
string:string.split(''),
94+
fence:emptyFence,
95+
targetRail:0,
96+
direction:DIRECTIONS.DOWN,
97+
coords:[0,0],
98+
});
99+
100+
returndecodeFence({
101+
railCount,
102+
strLen,
103+
fence:filledFence,
104+
currentRail:0,
105+
direction:DIRECTIONS.DOWN,
106+
code:[],
107+
});
108+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
import{
2+
addChar,
3+
buildFence,
4+
DIRECTIONS,
5+
getNextDirection,
6+
}from'./railFenceCipher';
7+
8+
/**
9+
*@param {object} params
10+
*@param {number} params.railCount
11+
*@param {number} params.currentRail
12+
*@param {number} params.direction
13+
*@param {Array} params.string
14+
*
15+
*@returns {Array}
16+
*/
17+
constfillEncodeFence=({
18+
railCount, fence, currentRail, direction, string,
19+
})=>{
20+
if(string.length===0)returnfence;
21+
22+
const[letter, ...nextString]=string;
23+
constnextDirection=getNextDirection({ railCount, currentRail, direction});
24+
25+
returnfillEncodeFence({
26+
railCount,
27+
fence:fence.map(addChar(currentRail,letter)),
28+
currentRail:currentRail+nextDirection,
29+
direction:nextDirection,
30+
string:nextString,
31+
});
32+
};
33+
34+
/**
35+
*@param {string} string
36+
*@param {number} railCount
37+
*
38+
*@returns {string}
39+
*/
40+
exportdefaultfunctionencodeRailFenceCipher(string,railCount){
41+
constfence=buildFence(railCount);
42+
43+
constfilledFence=fillEncodeFence({
44+
railCount,
45+
fence,
46+
currentRail:0,
47+
direction:DIRECTIONS.DOWN,
48+
string:string.split(''),
49+
});
50+
51+
returnfilledFence.flat().join('');
52+
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/**
2+
*@constant DIRECTIONS
3+
*@type {object}
4+
*@property {number} UP
5+
*@property {number} DOWN
6+
*/
7+
exportconstDIRECTIONS={UP:-1,DOWN:1};
8+
9+
/**
10+
*@param {number} rows
11+
*
12+
*@returns {Array}
13+
*/
14+
exportconstbuildFence=(rows)=>Array(rows)
15+
.fill()
16+
.map(()=>[]);
17+
18+
/**
19+
*@param {object} params
20+
*@param {number} params.railCount
21+
*@param {number} params.currentRail
22+
*@param {number} params.direction
23+
*
24+
*@returns {number}
25+
*/
26+
exportconstgetNextDirection=({ railCount, currentRail, direction})=>{
27+
switch(currentRail){
28+
case0:returnDIRECTIONS.DOWN;
29+
caserailCount-1:returnDIRECTIONS.UP;
30+
default:returndirection;
31+
}
32+
};
33+
34+
/**
35+
* Given a rail, adds a char to it
36+
* if it matches a targetIndex.
37+
*@callback charAdder
38+
*@param {number} rail
39+
*@param {currentRail} number
40+
*/
41+
42+
/**
43+
*@param {number} targetIndex
44+
*@param {string} letter
45+
*
46+
*@returns {charAdder}
47+
*/
48+
exportconstaddChar=(targetIndex,letter)=>(rail,currentRail)=>{
49+
return(currentRail===targetIndex ?[...rail,letter] :rail);
50+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp