[UVA] 795 - Sandorf's Cipher
Sandorf's Cipher
| Sandorf's Cipher |
Count Mathias Sandorf, a hero of Jules Verne, encrypted the secret
messages of the Trieste conspirators by using a cipher key a
6
6 hard paper square with some holes in it. In figure 1
the holes are marked white.
One edge of the cipher key has a
pinch-mark. Empty messages are coded as empty strings. For
encrypting a non empty message follow the Sandorf's algorithm
below.
Figure 1: Sandorf's cipher key
- 1.
- Extend the message, by appending trailing `#'
characters, until its length equals a multiple of 36, and then
reverse the extended message. By convention, original messages
do not end with # but, however, they can contain #. For
example, the message:
Real Programmers use Fortran. Quiche Eaters use Pascal.
is 55 characters long and has to be extended by appending 17 trailing #. Right after step 1, the message is:
#################.lacsaP esu sretaE ehciuQ .nartroF esu sremmargorP laeR
- 2.
- Position the cipher key on a sheet of paper, the pinch-mark facing upwards.
- 3.
- Copy the next 9 characters from the message (initially the first 9 characters) onto the paper through the holes of the cipher key, one character per hole, from left to right and top to bottom.
- 4.
- Turn the cipher key 90 degrees
clockwise and repeat from step 3 until the key gets to its
initial position, with the pinch-mark up. The result is a 66
matrix of characters, called a coded group.
- 5.
- Repeat from step 2 until all characters of the message are copied into coded groups, then append the rows of the coded groups from the first row of the first generated coded group to the last row of the last generated coded group, following the order of rows in each group and the order of groups. For the given message there are two coded groups, shown below,
u#l# # geuhoc
as#r## raPir
ec##st sutrl
##aa## rQae o
EP# ## emFR .
#e#s. meanrs
which, when appended, yield the final encrypted message:
u#l# #as#r##ec##st##aa##EP# ## #e#s.geuhoc raPir sutrlrQae oemFR .meanrs
Input and Output
Write a program that decrypts messages encrypted by using the Sandorf's algorithm. The encrypted messages are read from a text file, one message per line ending with a line-break. Lines can be of different length. All characters of a line (except the line-break) are part of the encrypted message which cannot exceed 108 characters. The decrypted messages are printed on the standard output file. Each output line contains a message in its original form, starting from the beginning of the line. Decoding the above encrypted message yields the result:
Real Programmers use Fortran. Quiche Eaters use
Pascal.
Sample Input
irdetn ihtoteao pesms soiaCet snaoi #e#r# edt#aasdrtltn ca reyor feneiv o#kginasksoaemlt f odatrnip as ene w#lerhiomfte t rSp se ntt.is id,raal o#r#i#etbanagvareioml nbfooheo lny e# #s#holp#lpt#iiok# w#so ts.tiis h H### ##d#l##a####n##o)##Dg#(##i#n#o#
Sample Output
Competition is a disease that sooner or later infects every trade and profession and makes it take a long step forward. Still, it remains the obligation of every honorable man to oppose it with his skills. (Donald Honig)
Miguel Revilla
2001-01-05
題目描述：
根據那個盤面，加密過程每次順時針轉一次，將依序將文字塞入方格。
填的時候，由上而下由左而右填入空白的格子中(填在背後的紙)，上方只是板子
最後填滿一個表格，再依序按照每行每列將文字讀出，即為加密後的。
現在要反解析回去。
題目解法：
保證輸入每一行長度都為 36 的倍數，既然加密是順時針，解密就是逆時針。
並且顛倒由下而上，由右而左把東西讀出，因此解出來會是反的。
輸出時在整理一下，要反著輸出。
不過原本的加密訊息中可能會有 '#'，只需要濾掉尾端的 '#' 即可。
#include <stdio.h>
#include <string.h>
char pattern[10][10] = {
"#_#_#_",
"####_#",
"##_###",
"#_##_#",
"#####_",
"###_##"
};// encrypted clockwise, decode counter-clockwise
char ret[1005];
int retidx;
void counterclockwise() {
char p[10][10];
int i, j;
for(i = 0; i < 6; i++)
for(j = 0; j < 6; j++)
p[i][j] = pattern[j][5-i];
for(i = 0; i < 6; i++)
for(j = 0; j < 6; j++)
pattern[i][j] = p[i][j];
/*for(i = 0; i < 6; i++, puts(""))
for(j = 0; j < 6; j++)
putchar(pattern[i][j]);
puts("");*/
}
void decode(char s[]) {
int i, j, k;
char g[6][6];
for(i = 0, k = 0; i < 6; i++)
for(j = 0; j < 6; j++)
g[i][j] = s[k++];
retidx += 36;
for(i = 0; i < 4; i++) {
counterclockwise();
for(j = 5; j >= 0; j--)
for(k = 5; k >= 0; k--)
if(pattern[j][k] == '_')
ret[--retidx] = g[j][k];
}
retidx += 36;
}
int main() {
char s[1005];
while(gets(s)) {
int i, j, len = strlen(s);
retidx = 0;
for(i = 0; i < len; i += 36)
decode(s+i);
i = 0;
while(i < retidx && ret[i] == '#')
i++;
for(j = len-1; j >= i; j--)
putchar(ret[j]);
puts("");
}
return 0;
}