# Speed Coding 2016 – Q3 Solution

27 July 2016, by

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 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);
}

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 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!

Categories: Social, Softwire, Technical