Speed Coding 2016 – Q3 Solution
27 July 2016, by Chris Arnott
This post explains the solutions to Question 3 of our speed coding 2016 competition. If you haven’t yet read the question, head back and have a go now.
The quickest answer that came through to this question was from Matthew Richards (have you spotted the pattern yet?). He solved the problem in 17:00 and used C#. Here’s his solution:
using System; using System.IO; namespace Challenge3 { class Program { private static void Main(string[] args) { var cipherStream = File.ReadAllText(@"c:\test\cipher-stream.txt").TrimEnd(); var encryptedText = "PAOOXEFCVLDIRAYAUGQTRMAAQTGKUFECQROIJUKCXTPRSOCWDDCVRWIAOPRBHUGBJPPASPGNAO"; var letterFrequences = new[] { 0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074 }; var minEntropy = double.MaxValue; string bestSoFar = ""; for (int i = 0; i < cipherStream.Length - encryptedText.Length; i++) { var candidate = Decipher(encryptedText, cipherStream.Substring(i, encryptedText.Length)); var entropy = GetEntropy(candidate, letterFrequences); if (entropy < minEntropy) { Console.WriteLine(candidate); minEntropy = entropy; bestSoFar = candidate; } if (i%1000 == 0) { Console.WriteLine("Progress: " + i); } } Console.WriteLine("RESULT:"); Console.WriteLine(bestSoFar); Console.ReadKey(); } static double GetEntropy(string input, double[] frequencies) { var totalEntropy = 0.0; foreach (var c in input) { totalEntropy -= Math.Log(frequencies
); } return totalEntropy; } static string Decipher(string encrypted, string cipher) { string result = ""; for(int i=0;i<encrypted.Length;i++) { char working = (char)(encrypted[i] - cipher[i] + 'A'); if (working < 'A') working = (char)(working + 26); result += working; } return result; } } }
Matthew’s solution wasn’t the neatest here, so here’s Rich Bradley’s (who came 3rd in this question) solution in Scala:
package c_caesar import com.google.common.base.Charsets import com.google.common.io.Files import java.io.File import Math._ object Caesar extends App { val cipherStream = Files.toString(new File("src/c_caesar/cipher-stream.txt"), Charsets.UTF_8) .toCharArray val cryptText = "PAOOXEFCVLDIRAYAUGQTRMAAQTGKUFECQROIJUKCXTPRSOCWDDCVRWIAOPRBHUGBJPPASPGNAO".toCharArray val freqs = Array( 0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074) val minusLogFreqs = freqs.map(f => -log(f)) val plainText = new Array[Char](cryptText.length) var minScore = Double.MaxValue for ( offset val plainTextLetter = decryptLetter(cryptText(i), cipherStream(offset + i)) plainText(i) = plainTextLetter acc + minusLogFreqs(plainTextLetter - 'A') } if (score < minScore) { minScore = score println(s"New best at offset $offset, score = $score: " + plainText.mkString("")) } } def decryptLetter(cryptLetter: Char, cipherStreamLetter: Char): Char = { val cryptVal = cryptLetter - 'A' val cipherVal = cipherStreamLetter - 'A' var plainVal = (cryptVal - cipherVal) % 26 if (plainVal < 0) plainVal += 26 (plainVal + 'A').toChar } }
If you managed to complete this problem in under 24:03, then you would have placed in our top 5!
Tags: 2016, solution, speed coding, technical
Categories: Social, Softwire, Technical