Brute-Force algorithm in C++

Question

I wrote a brute-force algorithm which shall find all possible combinations of ASCII-values that can sum up to a specific value (int hashval).

The algorithm is derived from a recursive algorithm that could print all binary numbers that are possible within a specific length characters. I modified it, so it now iterates over all ints between first and last, thus building all combinations there are. If the sum of the combination is equal to hashval, then the combination is saved in vector<vector<int[]>> combinations. When all possible combinations are found the content of combinations is printed into a file.

I already use some little tricks I learned for competitive programming, but the algorithm is still too slow. At the moment it is running for approximately 3 hours for no more than 13 characters, with no end in sight, file I/O hasn't even started yet. I know that its Big-O for runtime is horrible, no doubt. (if I get it right it is O(m^n) ).

I considered adding a check for n=1 since that would leave only one possibility for the last character, saving some recursive calls, but that would add another if to be called in every function call, either.

What more ways are there to improve the speed? Any improvements are not bound to C++, I will take a look at every programming language which might be more efficient in this case, though I guess there scarcely will be one.

The algorithm:

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <cstdio>

using namespace std;
using namespace std::chrono;

//values in decimal
int first = 32, last = 126, characters = 13, hashval = 1207;

vector<vector<int>> combinations;

void brute(int n, int it, vector<int> values) {
    if (n == 0) {
        int sum = 0;

        //sum up recent values
        for (int j = 0; j < characters; ++j) {
            sum += values[j];
        }
        //save values if matching to hash
        if (sum == hashval) {
            combinations.push_back(values);
        }
    } else {
        for (int i = first; i <= last; ++i) {
            values[it] = i;
            brute(n - 1, it + 1, values);
        }
    }
}

Printing the output to a file:

void printToFile(){
    freopen("fileContent.brute", "w", stdout);
    cout << "\n\nFound " << combinations.size() << " combinations." << endl;
    int counter = 0;
    for (auto combo = combinations.begin(); combo != combinations.end(); ++combo){
        for (int i = 0; i <  characters; ++i) {
            cout << (char) combinations.at(counter).at(i) << " ";
        }
        cout<< "\r\n";
        counter++;
    }
}

The main-method:

int main() {
    auto start = high_resolution_clock::now();
    //characters = 3, first = 0, last = 3, hashval = 6;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> values;

    for (int i = 0; i < characters; ++i) {
        values.push_back(first);
    }

    brute(characters, 0, values);

    printToFile();
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<seconds>(stop - start);
    cout << "Brute-forcing needed " << duration.count() << " seconds.\r\n";

    cout.flush();

    return 0;
}

Answer 1

Here are a number of ideas that may help you improve your program.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers). In this particular case, I happen to think it's perfectly appropriate because it's a single short program that and not a header. Some people seem to think it should never be used under any circumstance, but my view is that it can be used as long as it is done responsibly and with full knowledge of the consequences.

Don't #include <bits/stdc++.h>

This is not a standard header and it is poor practice to include a gcc specific header in your program. See this question for elaboration on why you should not do that.

Avoid the use of global variables

My rewrite of this code uses no global variables, so clearly they are neither faster nor necessary. Eliminating them allows your code to be more readable and maintainable, both of which are important characteristics of well-written code. Global variables introduce messy linkages that are difficult to spot and error prone.

Use iostreams

Using both iostreams and cstdio functions is not really helpful. It's easy enough and usually cleaner to use only iostreams in modern C++ programs.

Use constexpr where appropriate

In this program, the values of first, last, characters and hashval are never altered, so we can easily enable some compiler optimizations by declaring them all constexpr.

Use a class

C++ is an object oriented language, and it seems natural for this problem to use an object to represent an array with the given number of characters. I implemented such a thing and the class header looks like this:

#ifndef REVERSE_HASHER2_H
#define REVERSE_HASHER2_H
#include <iostream>
#include <string>

class ReverseHasher {
public:
    explicit ReverseHasher(char first, char last, char len, int hashval); 
    ReverseHasher& operator++();
    bool isMax() const { return !more; }
    friend std::ostream& operator<<(std::ostream& out, const ReverseHasher& fh);
private:
    bool more{true};
    const char first;
    const char last;
    const char characters;
    std::string values;
};

#endif // REVERSE_HASHER2_H

As you can see, the constructor is given all of the relevant numbers and contains a single string of values (as per the original code) which contains the hashed string. I'll show a bit more of how this works a little later.

Use a better algorithm

The algorithm used here is much slower than it needs to be and there are several things we could do to speed things up. First, we can check that the hash is even possible by quickly calculating the minimum and maximum values for the given character range. If the desired hash is not within that range, there are zero combinations and we're done in microseconds. Second, we can easily calculate a value that satisfies the hash value.

For instance, let's say there are \$n = 10\$ characters and the values range from \$a = 0\$ to \$b = 9\$ inclusive. It's easy to understand that the minimum hash value is \$x_{\text{min}} = n * a = 10 * 0 = 0\$ and the maximum value would be \$x_\text{max} = n * b = 10 * 9 = 90\$. For any hash value \$x\$ in that range, we could simply fill \$\lfloor \frac{x}{b-a} \rfloor\$ characters with \$b\$ and fill one character with the remainder of that division (if any) and the rest with the minimum value \$a\$. We can embody all of that in a constructor for the class shown above:

ReverseHasher::ReverseHasher(char first, char last, char len, int hashval) : 
    first{first}, last{last}, characters{len}, values(characters, first) 
{
    const int minval{characters * first};
    const int maxval{characters * last};
    const int range{last - first};
    if (hashval < minval) {
        throw std::domain_error("hashvalue too low; no combinations possible\n");
    }
    if (hashval > maxval) {
        throw std::domain_error("hashvalue too high; no combinations possible\n");
    }
    hashval -= minval;
    std::generate(values.rbegin(), values.rend(), [&hashval,first,range](){
        auto digitval = std::min(hashval, range);
        hashval -= digitval;
        return first + digitval;
    });
}

The effect is that this code either creates a sequence with the given hashval or if that's not possible, it throws an exception to indicate what's wrong.

Increment intelligently

Rather than simply incrementing values and hoping to eventually encounter a string with the same sum, we can be a lot smarter about incrementing so that we only have valid values. Conceptually this is not hard. If we have, for instance a string of three digits, 0-9 that must sum to 11, by the previous point, we can easily come up with a valid value 029 that sums to that value. It would be nice if we increment so that the values are in numeric sequence; that is, if the values come out already sorted. So in this case, the next value would be 038. If you work through this particular example, you'll see that the next values are 047, 056, 065, 074, 083 and 092. The pattern is that we subtract one from the lowest digit and add one to the next digit. If we always subtract and add the same amounts, it's obvious we will always maintain a valid value. The algorithm is a bit tricky, but here's how it can be implemented in C++:

ReverseHasher& ReverseHasher::operator++() {
    // from the right, try +1, -1 until it works
    auto it{values.rbegin()};
    auto end{values.rend()};
    auto movable{0};
    for (auto prev{it++}; it != end; ++it) {
        if (*it != last && *prev != first) {
            ++(*it);
            --(*prev);
            if (movable != 0) { //propagate to the right
                auto debt{movable};
                while (movable && prev != values.rbegin()) {
                    auto delta{std::min(*prev - first, movable)};
                    *prev -= delta;
                    movable -= delta;
                    --prev;
                }
                debt -= movable;
                for (auto ptr{values.rbegin()}; debt; ++ptr) {
                    auto delta{std::min(last - *ptr, debt)};
                    *ptr += delta;
                    debt -= delta;
                }
            }
            return *this;
        }
        movable += last - *prev;
        prev = it;
    }
    more = false;
    return *this;
}

Essentially what this does it to keep trying to do the \$+1, -1\$ on consecutive digits, sliding to the left until it's possible to do that. But there's another step needed to make sure everything comes out in order. If we consider that the next step after 092 in the previous example would be 182 if we just did the increment in that way. That's a valid value, but in fact, the next one in sorted order would instead be 128 so we need to do a little adjustment. Essentially, as we're looking for a value to increment, each value to the right of that which isn't at the maximum value (last in the code) represents a lower value (numerically sorted). The code above keeps track of the sum of those residual values in the variable movable and then essentially redistributes that value over the next digits after the incremented one such that the largest digits are to the right and the lowest numbers are to the left, thus insuring that the terms are created in ascending order.

Putting it all together

Here's a main function that uses this:

main.cpp

#include <iostream>
#include <chrono>
#include "ReverseHasher2.h"

int main() {
    using namespace std;
    using namespace std::chrono;
    auto start = high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cerr.imbue(locale(""));  // get pretty local formatting for numeric values
    int count{0};
    for (ReverseHasher fh(32, 32+5, 13, 450); !fh.isMax(); ++fh) {
        ++count;
        std::cout << fh << '\n';
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start);
    cerr << "Found " << count << " solutions in " << double(duration.count()/1000.0) << " seconds.\r\n";
}

Here's the full header file:

ReverseHasher2.h

#ifndef REVERSE_HASHER2_H
#define REVERSE_HASHER2_H
#include <iostream>
#include <string>

class ReverseHasher {
public:
    explicit ReverseHasher(char first, char last, char len, int hashval); 
    ReverseHasher& operator++();
    bool isMax() const { return !more; }
    friend std::ostream& operator<<(std::ostream& out, const ReverseHasher& fh);
private:
    bool more{true};
    const char first;
    const char last;
    const char characters;
    std::string values;
};

#endif // REVERSE_HASHER2_H

And finally the full implementation of this, as mostly already listed above:

ReverseHasher2.cpp

#include "ReverseHasher2.h"
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

ReverseHasher::ReverseHasher(char first, char last, char len, int hashval) : 
    first{first}, last{last}, characters{len}, values(characters, first) 
{
    const int minval{characters * first};
    const int maxval{characters * last};
    const int range{last - first};
    if (hashval < minval) {
        throw std::domain_error("hashvalue too low; no combinations possible\n");
    }
    if (hashval > maxval) {
        throw std::domain_error("hashvalue too high; no combinations possible\n");
    }
    hashval -= minval;
    std::generate(values.rbegin(), values.rend(), [&hashval,first,range](){
        auto digitval = std::min(hashval, range);
        hashval -= digitval;
        return first + digitval;
    });
}

ReverseHasher& ReverseHasher::operator++() {
    // from the right, try +1, -1 until it works
    auto it{values.rbegin()};
    auto end{values.rend()};
    auto movable{0};
    for (auto prev{it++}; it != end; ++it) {
        if (*it != last && *prev != first) {
            ++(*it);
            --(*prev);
            if (movable != 0) { //propagate to the right
                auto debt{movable};
                while (movable && prev != values.rbegin()) {
                    auto delta{std::min(*prev - first, movable)};
                    *prev -= delta;
                    movable -= delta;
                    --prev;
                }
                debt -= movable;
                for (auto ptr{values.rbegin()}; debt; ++ptr) {
                    auto delta{std::min(last - *ptr, debt)};
                    *ptr += delta;
                    debt -= delta;
                }
            }
            return *this;
        }
        movable += last - *prev;
        prev = it;
    }
    more = false;
    return *this;
}

std::ostream& operator<<(std::ostream& out, const ReverseHasher& fh) {
    return out << fh.values;
}

Results

I noticed this in one of the comments:

the outcome for parameters characters = 13, last = first+5, hashval = 450 was: 9 minutes runtime

I wrote a streamlined and simplified version using the same algorithm as your original and got this result:

Found 812,525,155 solutions in 257.426 seconds.

I piped the result to /dev/null (I'm running this on a 64-bit Linux machine) because I didn't really want to waste drive space on the resulting >10GiB file. That's over 4 minutes.

With the code posted above, I got this result:

Found 812,525,155 solutions in 31.458 seconds.

In other words, it's over eight times faster.

Going further

There are still enhancements that could be done, such as doing parallel processing, but they are not likely to buy much overall performance because the I/O is likely to be the bottleneck at this point. It's an interesting intellectual puzzle, but you probably don't really need a 10GiB file on your computer either, so it may be worth pondering in more detail what you're really trying to do, especially since this represents only a very tiny subset of the range your code was originally using. Some benchmarking and estimation of how many solutions there might be and how much space they'll require is likely to be useful in determining whether or not it's even worthwhile writing a program to do this.

Answer 2

Use a better container

The main issue is that std::vector<int> is a bad container for storing a set of ASCII characters. Every vector allocates on the heap, and an empty vector is likely 24 bytes in size. So this is huge waste. Why not use a container designed to hold a series of ASCII characters, like... std::string!

Do you need to store all possible combinations in memory?

You are first building a vector of all possible combinations with the desired sum. But the only thing you are doing with it afterwards is writing the result to a file. That's a huge waste of memory, and maintaining the vector of vectors in itself costs some CPU time as well. Why not write the results to a file immediately?

Exit early when your combination has already exceeded the desired sum

You always try to fill the vector values with characters elements, and try each possible element at each position. However, in brute(), you should calculate the partial sum of elements 0 up to n, and then just check in the for loop whether adding i to that sum would be equal to or higher than the desired sum. If so, if it's equal output the combination, but in any case return at that point instead of trying other values.

Use \n consistently to end lines

You are mixing \n, \r\n and std::endl in your code. Stick to \n, it is the standard way of ending a line in C and C++. The underlying I/O routines will automatically convert the newlines to \r\n on Windows.

std::endl is equivalent to \n plus a call to flush(). Unless there is a good reason to, you don't want this extra flushing to happen, since it reduces the performance of your program. Normally, std::cout is line-buffered, so if something ends with a \n, it is already flushed automatically. This also means you should remove the explicit call to cout.flush().

Answer 3

This shouldn't be in your program:

#include <bits/stdc++.h>

You should never #include <bits/stdc++.h>. It is not even proper C++. It ruins portability and fosters terrible habits. See Why should I not #include <bits/stdc++.h>.

This is also questionable:

using namespace std;
using namespace std::chrono;

Using using directives globally is considered bad practice because it introduces name clashes and defeats the purpose of namespaces. You will encounter problems when you try to utilize an identifier as innocent as size or count.

Answer 4

put something like this at the beginning of your brute function and you'll see the problem pretty quick. if i had to guess this is going to take a few centuries to complete.

std::printf("brute(%d, %d, %s)\n", n, it, join(values).c_str());

ed: it's actually far worse than i imagined. on my computer it took 37.4 seconds to get one tick in the 9th cell. since you need 94 such ticks to budge the 8th cell, it will be 3520 seconds for that.

eventually you get to the 6th cell, which takes 1 year to tick. you can see now the 5th cell is going to take roughly one century.

689 billion years is a round figure to finish.

Answer 5

Searching that way is futile, the number of candidate solutions grows exponentially with the number of characters, I would ballpark over 10^20 candidate solutions for 13 characters (an average of (95^13 / (95 * 13)) = 4.15x10^22 but it strongly depends on the value of hashval). The solutions of the equation a_1 + a_2 + ... + a_n = x form an hyperplane of dimension n - 1.

If you know that your plaintext contains only english words limit your search to these.