مساله:
دو تابع برای رمزگذاری و سپس رمزگشایی یک رشته با استفاده از Rail Fence Cipher ایجاد کنید. این رمز برای کدگذاری یک رشته با قرار دادن هر یک از کاراکترها به صورت مورب در امتداد مجموعه ای از “ریل” استفاده می شود. ابتدا حرکت مورب و پایین را شروع کنید. هنگامی که به قسمت پایینی می رسید ، جهت معکوس کرده و مورب و به سمت بالا حرکت کنید تا به ریل بالایی برسید. ادامه دهید تا به انتهای رشته برسید. سپس هر “ریل” از چپ به راست خوانده می شود تا رشته کد شده را بدست آورید.
به عنوان مثال ، رشته “WEAREDISCOVEREDFLEEATONCE” می تواند در یک سیستم سه ریلی به شرح زیر نشان داده شود:
رشته رمزگذاری شده عبارت است از:
WECRLTEERDSOEEFEAOCAIVDEN
یک تابع/متدی بنویسید که 2 آرگومان ورودی، یک رشته و تعداد ریل ها را بگیرد و رشته رمز شده را برگرداند.
یک تابع/روش دوم بنویسید که 2 آرگومان، یک رشته رمزگذاری شده و تعداد ریل ها را گرفته و رشته رمزگشایی را برگرداند.
برای رمزگذاری و رمزگشایی ، تعداد ریلها >= 2 را فرض کنید و پاس دادن یک رشته خالی یک رشته خالی را برمی گرداند.
توجه داشته باشید که در مثال بالا صرفا برای سادگی ، علائم نگارشی و فاصله ها آورده نشده است. با این حال، آزمایشاتی وجود دارد که شامل علائم نگارشی است. علائم نگارشی را فیلتر نکنید زیرا آنها بخشی از رشته هستند.
Description:
Create two functions to encode and then decode a string using the Rail Fence Cipher. This cipher is used to encode a string by placing each character successively in a diagonal along a set of “rails”. First start off moving diagonally and down. When you reach the bottom, reverse direction and move diagonally and up until you reach the top rail. Continue until you reach the end of the string. Each “rail” is then read left to right to derive the encoded string.
For example, the string "WEAREDISCOVEREDFLEEATONCE" could be represented in a three rail system as follows:
The encoded string would be:
WECRLTEERDSOEEFEAOCAIVDEN
Write a function/method that takes 2 arguments, a string and the number of rails, and returns the ENCODED string.
Write a second function/method that takes 2 arguments, an encoded string and the number of rails, and returns the DECODED string.
For both encoding and decoding, assume number of rails >= 2 and that passing an empty string will return an empty string.
Note that the example above excludes the punctuation and spaces just for simplicity. There are, however, tests that include punctuation. Don’t filter out punctuation as they are a part of the string.
راه حل ها:
public class RailFenceCipher {
public static String encode(String s, int n) {
return process(s, n, true);
}
public static String decode(String s, int n) {
return process(s, n, false);
}
private static String process(String s, int n, boolean enc) {
int len = s.length();
int d = n * 2 - 2;
StringBuilder sb = new StringBuilder(s);
int counter = 0;
for (int i = 0; i < n; i++) {
int next = i == n - 1 ? d : d - i * 2;
int index = i;
while (index < len) {
sb.setCharAt((enc ? counter++ : index), s.charAt(enc ? index : counter++));
index += next;
next = (next == d ? d : d - next);
}
}
return sb.toString();
}
}import java.util.stream.*;
import java.util.*;
public class RailFenceCipher {
private static <T> Stream<T> fencer(int n, Stream<T> str) {
List<List<T>> rails = IntStream.range(0,n)
.mapToObj( r -> new ArrayList<T>() )
.collect(Collectors.toList());
int[] data = {0,1};
int x=0, dx=1;
str.forEachOrdered( t -> {
rails.get(data[x]).add(t);
if (data[x]==n-1 && data[dx]>0 || data[x]==0 && data[dx]<0)
data[dx] *= -1;
data[x] += data[dx];
});
return rails.stream().flatMap( lst -> lst.stream() );
}
static String encode(String s, int n) {
return fencer(n, s.chars().mapToObj( c -> ""+(char) c))
.collect(Collectors.joining());
}
static String decode(String s, int n) {
char[] arr = new char[s.length()];
int[] j = {0};
fencer(n, IntStream.range(0,s.length()).boxed())
.forEachOrdered( i -> arr[i] = s.charAt(j[0]++) );
return new String(arr);
}
}import java.util.Arrays;
public class RailFenceCipher {
static String encode(String s, int n) {
String a[]=new String[n], t="";Arrays.fill(a,"");
for(int i=0, r=0, j=-1; i<s.length(); j=i%(n-1)>0?j:-j, r+=j, i++) a[r]+=s.charAt(i);
return String.join("", a);
}
static String decode(String s, int n) {
String t="", a[]=new String[n];
int i,r,j,l[]= new int[n];
for(i=0, r=0, j=-1; i<s.length(); j=i%(n-1)>0?j:-j, r+=j, i++) l[r]++;
for(i=0, r=0; r<n; a[r]=s.substring(i,i+l[r]), i+=l[r], l[r]=0, r++);
for(i=0, r=0, j=-1; i<s.length(); j=i%(n-1)>0?j:-j, r+=j, i++) t+=a[r].charAt(l[r]++);
return t;
}
}import java.util.Arrays;
public class RailFenceCipher {
static String encode(String s, int n) {
String res = "";
String[] divided = divideWord(s, n);
for (int i = 0; i < divided.length; i++) {
res += divided[i];
}
return res;
}
static String decode(String s, int n) {
String[] divided = divideWord(s, n);
int start = 0, end = 0;
for (int i = 0; i < divided.length; i++) {
start = end;
end += divided[i].length();
divided[i] = s.substring(start, end);
}
StringBuilder word = new StringBuilder("");
int counter = 0;
while (counter < s.length()) {
for (int i = 0; i < divided.length; i++) {
String ch = divided[i].charAt(0) + "";
word.append(ch);
divided[i] = divided[i].replaceFirst(ch, "");
counter++;
if (counter==s.length())break;
}
if (counter < s.length()) {
for (int i = divided.length - 2; i > 0; i--) {
String ch = divided[i].charAt(0) + "";
word.append(ch);
divided[i] = divided[i].replaceFirst(ch, "");
counter++;
if (counter==s.length())break;
}
}
}
return word.toString();
}
private static String[] divideWord(String s, int n) {
String[] divided = new String[n];
Arrays.fill(divided, "");
int count = 0;
while (count < s.length()) {
for (int i = 0; i < n; i++) {
divided[i] += s.charAt(count);
count++;
if (count==s.length())break;
}
if (count < s.length()) {
for (int i = n - 2; i > 0; i--) {
divided[i] += s.charAt(count);
count++;
if (count==s.length())break;
}
}
}
return divided;
}
}import java.util.*;
import java.util.stream.*;
public class RailFenceCipher {
static String encode(String s, int n) {
return Arrays.stream(getMatrixFilledWithCharsFromString(n, s, false)).map(array -> Arrays.stream(array).filter(Objects::nonNull).collect(Collectors.joining())).collect(Collectors.joining());
}
static String decode(String s, int n) {
String[][] matrix = getMatrixFilledWithCharsFromString(n, s, true);
String res = "";
for(int i = 0, j = 0, step = -1; i < s.length(); i++, j += step) {
step = (j == n - 1 || j == 0) ? -1 * step : step;
res += matrix[j][i];
}
return res;
}
private static String[][] getMatrixFilledWithCharsFromString(int n, String s, boolean isDecoding) {
String[][] matrix = new String[n][s.length()];
for (int i = 0, j = 0, step = -1; i < s.length(); i++, j += step) {
step = (j == n - 1 || j == 0) ? -1 * step : step;
matrix[j][i] = isDecoding ? "" : "" + s.charAt(i);
}
return isDecoding ? getMatrixWithValuesForDecoding(matrix, s, n) : matrix;
}
private static String[][] getMatrixWithValuesForDecoding(String[][] matrix, String s, int n) {
for (int i = 0, counter = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[i][j] = matrix[i][j] != null ? "" + s.charAt(counter++) : null;
}
}
return matrix;
}
}import java.util.ArrayList;
public class RailFenceCipher {
static String encode(String s, int n) {
String[] rails = new String[n];
for(int i = 0 ; i < n ; i++){
rails[i] = "";
}
int i = 0;
while(i < s.length()){
for(int j = 0; j < n; j++){
if ( i >= s.length()) break;
rails[j] += s.charAt(i++);
}
for(int j = n-2; j > 0; j--){
if ( i >= s.length()) break;
rails[j] += s.charAt(i++);
}
}
return String.join("", rails);
}
static String decode(String s, int n) {
int lowerTail = (n - 1) * 2;
int upperTail = 0;
int textLength = s.length();
ArrayList<String> decoded = new ArrayList<>();
for (int i = 0; i < textLength; i++) {
decoded.add("");
}
for (int i = 0; i < textLength; ) {
boolean downDirection = lowerTail > 0;
for (int j = decoded.indexOf(""); j < textLength; ) {
decoded.set(j, s.charAt(i++) + "");
if (downDirection) {
j += lowerTail;
if (upperTail > 0) {
downDirection = false;
}
} else {
j += upperTail;
if (lowerTail > 0) {
downDirection = true;
}
}
}
lowerTail -= 2;
upperTail += 2;
}
return String.join("", decoded);
}
}class RailFenceCipher {
static String encode(String s, int n) {
if (s.length() < n || n <= 1)
return s;
int rail = n-1, step = n*2-2;
String res = "";
String[] strs = new String[n];
for (int i = 0; i < strs.length; i++)
strs[i] = "";
for (int i = 0; i < s.length(); i++)
strs[rail - Math.abs(i - i / step * step - rail)] += s.charAt(i);
for (String i : strs)
res += i;
return res;
}
static String decode(String s, int n) {
if (s.length() < n || n <= 1)
return s;
String res = "";
char[] chars = new char[s.length()];
int len = s.length(), lines = 1 + (len - n) / (n - 1), tail = lines % 2 == 0 ? (len - n) % (n - 1) : (n - 2) - (len - n) % (n - 1), steps, step1, step2, pos = 0, index, beg = 0;
for (int i = 0; i < n; i++) {
index = beg;
if (i == 0) {
steps = lines - (lines - 1) / 2;
step1 = step2 = n * 2 - 2;
} else if (i == n - 1) {
steps = lines - lines / 2;
step1 = step2 = n * 2 - 2;
} else {
steps = lines%2==0?tail>0?lines+1:lines:tail>0?lines:lines+1;
tail--;
step1 = (n * 2 - 2) - 2 * i;
step2 = 2 * i;
}
for (int j = 0; j < steps; j++) {
chars[index] = s.charAt(pos++);
index += j % 2 == 0 ? step1 : step2;
}
beg += 1;
}
for (char i : chars)
res += i;
return res;
}
}
import java.util.ArrayList;
public class RailFenceCipher {
static String encode(String s, int n) {
if (s.length() <= n) return s;
ArrayList<StringBuilder> rails = new ArrayList<StringBuilder>(n);
for (int i = 0; i < n; i++) {
rails.add(i, new StringBuilder());
}
int len = s.length();
int railNumber = 0;
int next_index = -1;
for (int i = 0; i < len; i++){
rails.get(railNumber).append(s.charAt(i));
if(railNumber >= n-1 || railNumber <= 0) next_index *= -1;
railNumber += next_index;
}
StringBuilder encoded = new StringBuilder();
for (int i = 0; i < n; i++) {
encoded.append(rails.get(i).toString());
}
return encoded.toString();
}
static String decode(String s, int n) {
int len = s.length();
if (len < n) return s;
int modN = len % n;
char[][] railMatrix = new char[len][n];
for (int x = 0; x < len; x++) {
for (int y = 0; y < n; y++) {
railMatrix[x][y] = '\u0000';
}
}
int y = 0;
int next_index = -1;
for (int x = 0; x < len; x++) {
railMatrix[x][y] = '*';
if (y == 0 || y == n-1) next_index *= -1;
y += next_index;
}
int index = 0;
for (y = 0; y < n; y++) {
for (int x = 0; x < len; x++){
if(railMatrix[x][y] == '*') {
railMatrix[x][y] = s.charAt(index);
index++;
}
}
}
StringBuilder sb = new StringBuilder();
y = 0;
next_index = -1;
for (int x = 0; x < len; x++) {
sb.append(railMatrix[x][y]);
if (y == 0 || y == n-1) next_index *= -1;
y += next_index;
}
return sb.toString();
}
}public class RailFenceCipher {
static String encode(String s, int n) {
boolean increasing = true;
String[][] encoding = new String[n][s.length()];
int level = 0;
for(int i = 0; i < s.length(); i++) {
encoding[level][i] = s.substring(i, i + 1);
if(increasing) level++;
if(!increasing) level--;
if(level == 0) increasing = true;
if(level == n - 1) increasing = false;
}
String encoded = "";
for(int rail = 0; rail < n; rail++) {
for(int col = 0; col < s.length(); col++) {
if(encoding[rail][col] != null) encoded += encoding[rail][col];
}
}
System.out.println(encoded);
return encoded;
}
static String decode(String s, int n) {
boolean increasing = true;
String[][] decoding = new String[n][s.length()];
int level = 0;
for(int i = 0; i < s.length(); i++) {
decoding[level][i] = s.substring(i, i + 1);
if(increasing) level++;
if(!increasing) level--;
if(level == 0) increasing = true;
if(level == n - 1) increasing = false;
}
int stringIndex = 0;
for(int rail = 0; rail < n; rail++) {
for(int col = 0; col < s.length(); col++) {
if(decoding[rail][col] != null) { decoding[rail][col] = s.substring(stringIndex, stringIndex + 1); stringIndex++; }
}
}
level = 0;
increasing = true;
String decoded = "";
for(int i = 0; i < s.length(); i++) {
decoded += decoding[level][i];
if(increasing) level++;
if(!increasing) level--;
if(level == 0) increasing = true;
if(level == n - 1) increasing = false;
}
return decoded;
}
}
