【算法】用c#实现自定义字符串编码及围栏解码方法

  • 【算法】用c#实现自定义字符串编码及围栏解码方法已关闭评论
  • 98 次浏览
  • A+
所属分类:.NET技术
摘要

编写一个函数/方法,它接受2个参数、一个字符串和轨道数,并返回ENCODED字符串。

编写一个函数/方法,它接受2个参数、一个字符串和轨道数,并返回ENCODED字符串。

编写第二个函数/方法,它接受2个参数、一个编码字符串和轨道数,并返回DECODED字符串。

然后使用围栏密码对其进行解码。

这种密码用于通过将每个字符沿着一组“竖状轨道”依次放在对角线上来对字符串进行编码。首先开始对角向下移动。当你到达底部时,反转方向,对角向上移动,直到你到达顶部轨道。继续,直到到达字符串的末尾。然后从左到右读取每个“尾号”以导出编码字符串。

例如,字符串“WEAREDISCOVEREDFLEATONCE”可以在三轨系统中表示如下:
W E C R L T E

E R D S O E E F E A O C

A I V D E N

编码的字符串将是:
WECRLTEERDSOEEFEAOCAIVDEN

对于编码和解码,假设尾号的数量>=2,并且传递空字符串将返回空字符串。

请注意,为了简单起见,上面的示例排除了标点符号和空格。然而,也有一些测试包括标点符号。不要过滤掉标点符号,因为它们是字符串的一部分。


算法实现:

 1 using System;  2 using System.Linq;  3   4 public class RailFenceCipher  5 {  6    public static string Encode(string s, int n)  7    {  8        var mod = (n - 1) * 2;  9        return string.Concat(s.Select((c, i) => new { c, i }) 10           .OrderBy(a => Math.Min(a.i % mod, mod - a.i % mod)) 11           .Select(a => a.c)); 12    } 13  14    public static string Decode(string s, int n) 15    { 16        var mod = (n - 1) * 2; 17        var pattern = Enumerable.Range(0, s.Length) 18           .OrderBy(i => Math.Min(i % mod, mod - i % mod)); 19        return string.Concat(s.Zip(pattern, (c, i) => new { c, i }) 20           .OrderBy(a => a.i).Select(a => a.c)); 21    } 22 }

测试用例:

  1 using NUnit.Framework;   2 using System;   3 using System.Collections.Generic;   4 using System.Linq;   5 public class SolutionTest   6 {   7     [Test]   8     public void BasicTests()   9     {  10         string[][] config =  11         {  12             new[] { "Hello, World!", "Hoo!el,Wrdl l" },               // encode  13             new[] { "Hello, World!", "Hlo ol!el,Wrd" },               // encode  14             new[] { "Hello, World!", "H !e,Wdloollr" },               // encode  15             new[] { "H !e,Wdloollr", "Hello, World!" },               //  decode  16             new[] { "", "" },                            // encode  17             new[] { "", "" },                            //  decode  18             new[] { "WEAREDISCOVEREDFLEEATONCE", "WECRLTEERDSOEEFEAOCAIVDEN" },   // encode  19             new[] { "WECRLTEERDSOEEFEAOCAIVDEN", "WEAREDISCOVEREDFLEEATONCE" },   //  decode  20             new[] { "WEAREDISCOVEREDFLEEATONCE", "WIREEEDSEEEACAECVDLTNROFO" },   // encode  21             new[] { "WIREEEDSEEEACAECVDLTNROFO", "WEAREDISCOVEREDFLEEATONCE" },   //  decode  22             new[] { "WEAREDISCOVEREDFLEEATONCE", "WCLEESOFECAIVDENRDEEAOERT" },   // encode  23             new[] { "WECRLTEERDSOEEFEAOCAIVDEN", "WLSADOOTEEECEAEECRFINVEDR" }    //  decode  24         };  25         int[] rails = { 3, 2, 4, 4, 3, 3, 3, 3, 4, 4, 5, 5 };  26         for (int i = 0; i < config.Length; i++)  27         {  28             var actual = i % 2 == 0 || i == 1  29                 ? RailFenceCipher.Encode(config[i][0], rails[i])  30                 : RailFenceCipher.Decode(config[i][0], rails[i]);  31   32             Assert.AreEqual(config[i][1], actual);  33         }  34     }  35   36     /* *****************  37      *   RANDOM TESTS  38      * *****************/  39   40     private class Sol  41     {  42         private static IEnumerable<T> Fencer<T>(int n, IEnumerable<T> str)  43         {  44             var rails = Enumerable.Range(0, n).Select(r => new List<T>()).ToList();  45             int[] data = { 0, 1 };  46             int x = 0, dx = 1;  47             foreach (var t in str)  48             {  49                 rails[data[x]].Add(t);  50                 if (data[x] == n - 1 && data[dx] > 0 || data[x] == 0 && data[dx] < 0)  51                     data[dx] *= -1;  52                 data[x] += data[dx];  53             }  54             return rails.SelectMany(lst => lst);  55         }  56   57         public static string Encode(string s, int n) => new string(Fencer(n, s).ToArray());  58   59         public static string Decode(string s, int n)  60         {  61             char[] arr = new char[s.Length];  62             int[] j = { 0 };  63             Fencer(n, Enumerable.Range(0, s.Length)).ToList().ForEach(i => arr[i] = s[j[0]++]);  64             return new string(arr);  65         }  66     }  67   68     private Random rnd = new Random();  69   70     private int Rand(int start, int end) { return start + rnd.Next(end - start); }  71   72     [Test]  73     public void FixedStringVariousRails()  74     {  75         var msg = "WEAREDISCOVEREDFLEEATONCE";  76         Console.WriteLine($"Input for these tests:n{msg}");  77   78         for (int r = 0; r < 10; r++)  79         {  80             var rails = Rand(2, 11);  81             var exp = Sol.Encode(msg, rails);  82             Assert.AreEqual(exp, RailFenceCipher.Encode(msg, rails));  83   84             rails = Rand(2, 11);  85             exp = Sol.Decode(msg, rails);  86             Assert.AreEqual(exp, RailFenceCipher.Decode(msg, rails));  87         }  88     }  89   90     private static string lorem = "Amet non facere minima iure unde, provident, "  91                                   + "veritatis officiis asperiores ipsa eveniet sit! Deserunt "  92                                   + "autem excepturi quibusdam iure unde! Porro alias distinctio "  93                                   + "ipsam iure exercitationem molestiae. Voluptate fugiat quasi maiores!jk";  94     private static List<string> lorarr = lorem.Split(' ').ToList();  95   96     [Test]  97     public void RandomTests()  98     {  99         Console.WriteLine($"Base string for these tests (or a shuffled version):n{lorem}"); 100  101         for (int r = 0; r < 50; r++) 102         { 103             var msg = Shuffle(); 104             int rails = Rand(2, 51); 105             var exp = Sol.Encode(msg, rails); 106             Assert.AreEqual(exp, RailFenceCipher.Encode(msg, rails)); 107  108             msg = Shuffle(); 109             rails = Rand(2, 51); 110             exp = Sol.Decode(msg, rails); 111             Assert.AreEqual(exp, RailFenceCipher.Decode(msg, rails)); 112         } 113     } 114  115     private string Shuffle() 116     { 117         Shuffle(lorarr); 118         return string.Join(" ", lorarr); 119     } 120  121     public static void Shuffle<T>(List<T> deck) 122     { 123         var rnd = new Random(); 124         for (int n = deck.Count - 1; n > 0; --n) 125         { 126             int k = rnd.Next(n + 1); 127             T temp = deck[n]; 128             deck[n] = deck[k]; 129             deck[k] = temp; 130         } 131     } 132 }