9
\$\begingroup\$

I've written a Vigenere decypher and I would like to have some opinions before I try to refactor it into more OOP style with classes and such.

#include <bits/stdc++.h>
#define Rep(i,a,n) for(int i = a; i < n; i++)
#define rep(i,n) Rep(i,0,n)
using namespace std;
int main(){
    string key, line, code = "", dict = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", decoded = "";
    cin >> key;
    int n = dict.length();
    char** key_matrix = new char*[n];
    rep(i,n) 
        key_matrix[i] = new char[n];
    rep(i,n)
        rep(j,n)
            key_matrix[i][j] = dict[(i+j)%n];
    fstream file;
    file.open("text.txt");
    while(getline(file, line))
        code += line;
    file.close();
    rep(i,code.length()){
        if(!iswspace(code[i])){
            rep(j,n)
                if(key_matrix[j][0] == key[i%key.length()]){
                    rep(k,n)
                        if(key_matrix[j][k] == code[i]){
                            decoded += key_matrix[0][k];
                            break;
                        }
                }
        }else{
            decoded += " ";
        }
    }
    cout << decoded;
}
\$\endgroup\$
  • \$\begingroup\$ Is your odd indentation a direct result of your defines? Have you checked whether the inner loops work as intended? \$\endgroup\$ – Mast Jul 18 '18 at 7:44
  • \$\begingroup\$ @Mast Everything works just fine. I just want to know what can be improved or maybe golfed of some sort. All opinions are welcome. \$\endgroup\$ – Never Lucky Jul 18 '18 at 7:45
  • \$\begingroup\$ Are you looking for readability, performance, memory or code-length improvements? And yes, picking all 4 won't work. \$\endgroup\$ – Mast Jul 18 '18 at 7:46
  • \$\begingroup\$ Performance and memory mostly, perhaps there is a way to drop a loop here and there? Maybe use different data structures? \$\endgroup\$ – Never Lucky Jul 18 '18 at 7:49
15
\$\begingroup\$
#include <bits/stdc++.h>

This is distinctly non-portable. The files in bits/ are internal to GCC, may change without warning, and and are probably inefficient. Use the correct Standard C++ headers instead:

#include <cctype>
#include <fstream>
#include <iostream>
#include <string>

#define Rep(i,a,n) for(int i = a; i < n; i++)
#define rep(i,n) Rep(i,0,n)

Macros are dangerous - that's why we minimise their use, and use uppercase names for them. In this case, they serve mainly to obfuscate the code (in particular, they tend to hide mismatches between int and the type of n; they also introduce risk of repeating operations within n).


using namespace std;

This namespace is not one of the few intended to be imported wholesale. Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.


string key, line, code = "", dict = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", decoded = "";

Prefer one declaration per line, and declare as close to first use as possible. dict doesn't need to be mutable:

static const std::string dict = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
static const std::size_t n = dict.length();

std::string key;
std::cin >> key;

std::cin >> key;

This won't read beyond the first whitespace. Is that made obvious to users somehow?


char** key_matrix = new char*[n];
rep(i,n) 
    key_matrix[i] = new char[n];
rep(i,n)
    rep(j,n)
        key_matrix[i][j] = dict[(i+j)%n];

You'll find it easier to use a vector rather than an array of arrays here. That will automatically fix the memory leak you have. However, do you really need to allocate this storage? There's a simple arithmetical relationship between each member, and I don't see that you get any benefit from storing each table, compared to processing on the fly.


std::fstream file;
file.open("text.txt");

Instead of hard-coding the file name, why not pass it as an argument? That would make the program much more flexible. Even better, just read from standard input, and accept the key as argument - that's much more consistent with user expectations.


std::string code = "";
std::string line;
while(getline(file, line))
    code += line;
file.close();

There's no need to read the whole of the input before starting to write any output. The code will scale much better if you operate on reasonable-sized chunks (even a character at a time - that's why standard I/O is buffered), and write the output as it's produced.


std::string decoded = "";
for (std::size_t i = 0;  i < code.length(); ++i) {
    if (!iswspace(code[i])) {
        rep(j,n)
            if(key_matrix[j][0] == key[i%key.length()]){
                rep(k,n)
                    if(key_matrix[j][k] == code[i]){
                        decoded += key_matrix[0][k];
                        break;
                    }
            }
    } else {
        decoded += " ";
    }
}

This whole nested loops of linear search appears very inefficient. It also drops all characters that are not spaces and not in dict - i.e. all punctuation and lower-case letters.

(It's not clear why you're using std::iswspace() instead of std::isspace() - we deal with plain char everywhere else, so why use the wide-char function here? In any case, we need a cast to unsigned type, as char may be signed.)

I suggest a re-think of the algorithm here. We need to be able to convert input characters to their indices in dict - I suggest a lookup table for that (with a sentinel value to indicate "not present"). We can pre-process the key by converting each character to the corresponding index before we start. Then just iterate over input adding the current character's index to the corresponding key value, and indexing back into dict to give the output value.

We can avoid using % when indexing into dict by populating it with two copies of the alphabet.


Improved version

#include <cctype>
#include <climits>
#include <iostream>
#include <string>
#include <vector>

static const std::string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

static const std::vector<int> index = []{
    std::vector<int> v(UCHAR_MAX+1, -1);
    for (auto i = 0u;  i < alphabet.length();  ++i) {
        unsigned char c = alphabet[i];
        v[c] = i;
    }
    return v;
}();


int main(int argc, char **argv)
{
    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " KEY" << std::endl;
        return 1;
    }

    std::vector<int> key;
    for (char *p = argv[1];  *p;  ++p) {
        int i = index[*p];
        if (i >= 0)
            key.push_back(i);
    }

    if (key.empty()) {
        std::cerr << "Invalid key" << std::endl;
        return 1;
    }

    std::size_t keypos = 0;

    char c;
    while (std::cin >> c) {
        auto i = index[c];
        if (i < 0) {
            std::cout << c;
        } else {
            static const std::string alphabet2 = alphabet + alphabet;
            std::cout << alphabet2[i+key[keypos++]];
            if (keypos >= key.size())
                keypos = 0;
        }
    }
}

You might want instead to process chunks (perhaps lines), in which case a function like this would be more appropriate:

// decrypt using key beginning at keypos; update keypos with new position
static std::string decrypt(const std::vector<int>& key, std::size_t& keypos, std::string s)
{
    static const std::string alphabet2 = alphabet + alphabet;

    for (auto& c: s) {
        auto i = index[c];
        if (i >= 0) {
            c = alphabet2[i+key[keypos++]];
            if (keypos >= key.size())
                keypos = 0;
        }
    }

    return s;
}

This separated function also makes it easier to test functionality (I did that myself whilst writing the monolithic main() above), and it may well be a stepping-stone to creating an object-oriented version (where key and keypos would be members of the decryption object).

\$\endgroup\$
  • \$\begingroup\$ Thank you for your in-depth review. There are some things I do not understand, but it is really nice to learn in such way. Also, ideally, the key and the dictionary variables should be passed somehow to this whole program. I hardcoded dict so i wouldn't have to type it or paste it everytime im testing the code. Anyway, thank you! \$\endgroup\$ – Never Lucky Jul 18 '18 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.