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