Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E3-33'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-33

Question

A Caesar shift (see Section 21.6 (page 697)) is a very simple class of ciphers for secret messages. Unfortunately, they can be broken using statistical properties of English. Develop a program capable of decrypting Caesar shifts of sufficiently long texts.

Solution

Outline

I implemented "Decrypt" program and as a auxiliary tool "Encrypt" program.

"Encrypt" reads from a text file and converts an alphabet into another alphabet and store as another text file. 26 alphabets are converted without any duplication.

"Decrypt" reads from the alphabet-order converted file and analyzes its frequency of occurences of alphabet. Then it compare the result with built-in frequency table, and decrypt the text so that the text recovers its order of alphabet.

Codes

Encrypt
#include <algorithm>
#include <array>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
constexpr std::array<char, 26> lowercase_letters{
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

int main(int argc, char const *argv[]) {
    std::vector<char> cp_low{lowercase_letters.cbegin(),
                             lowercase_letters.cend()};
    std::random_shuffle(cp_low.begin(), cp_low.end());

    std::ifstream inf{"../data/some-text.txt"};
    if (!inf) {
        std::cerr << "cannot open file" << std::endl;
        return 1;
    }
    std::ofstream outf{"../data/char-rotated-text.txt"};
    if (!outf) {
        std::cerr << "cannot operate file" << std::endl;
        return 1;
    }

    std::string strInput{};
    while (std::getline(inf, strInput)) {
        for (auto it{strInput.begin()}; it != strInput.end(); it++) {
            if (std::isalpha(*it)) {
                if (std::islower(*it))
                    *it = cp_low[*it - 'a'];
                else
                    *it = cp_low[*it - 'A'] ^ 32;
            }
        }
        outf << strInput << std::endl;
    }

    return 0;
}
Decrypt
// frequency of letters:
//  http://en.algoritmy.net/article/40379/Letter-frequency-English
#include <algorithm>
#include <array>
#include <cstddef>
#include <fstream>
#include <iostream>
#include <vector>

constexpr std::array<char, 26> freq_order{
    'z', 'q', 'x', 'j', 'k', 'v', 'b', 'p', 'y', 'g', 'f', 'w', 'm',
    'u', 'c', 'l', 'd', 'r', 'h', 's', 'n', 'i', 'o', 'a', 't', 'e',
};

struct Char_counter {
    char counterpart_freq_char;
    size_t orig_pos;
    unsigned long cnt{0};
};

int main(int argc, char const *argv[]) {
    std::vector<Char_counter> v_char(26);
    for (size_t i = 0; i < v_char.size(); i++) {
        v_char[i].orig_pos = i;
    }

    std::ifstream inf{"../data/char-rotated-text.txt"};
    if (!inf) {
        std::cerr << "cannot open file" << std::endl;
        return 1;
    }
    // read frequency information of the input file
    std::string strInput{};
    while (std::getline(inf, strInput)) {
        for (auto it{strInput.cbegin()}; it != strInput.cend(); it++) {
            if (std::isalpha(*it)) {
                auto c{*it};
                if (std::islower(c))
                    v_char[c - 'a'].cnt++;
                else
                    v_char[c - 'A'].cnt++;
            }
        }
    }
    // sort the result and link the letter in frequency table with the result
    std::sort(v_char.begin(), v_char.end(),
              [](auto e1, auto e2) { return e1.cnt < e2.cnt; });
    for (size_t i = 0; i < v_char.size(); i++) {
        v_char[i].counterpart_freq_char = freq_order[i];
    }
    // resort to restore the order
    std::sort(v_char.begin(), v_char.end(),
              [](auto e1, auto e2) { return e1.orig_pos < e2.orig_pos; });
    // read again and convert letters with the appropriate frequency letters
    // save the result to output file
    std::ofstream outf{"../data/char-rerolated-text.txt"};
    if (!outf) {
        std::cerr << "cannot operate file" << std::endl;
        return 1;
    }
    inf.clear();
    inf.seekg(0);
    while (std::getline(inf, strInput)) {
        for (auto it{strInput.begin()}; it != strInput.end(); it++) {
            if (std::isalpha(*it)) {
                if (std::islower(*it))
                    *it = v_char[*it - 'a'].counterpart_freq_char;
                else
                    *it = v_char[*it - 'A'].counterpart_freq_char - 32;
            }
        }
        outf << strInput << std::endl;
    }
    return 0;
}