C++

Forum

 
What is the secret to becoming the greatest programmer in the whole wide world?

Pages: 1... 3456
htirwin (1208)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
#include <algorithm>
#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <ostream>
#include <random>
#include <stdexcept>
#include <thread>
#include <utility>
#include <vector>

namespace {

const std::vector<char> availableElements {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '!', '@', '#', '$', '%', '^', '&', '*', '?', '<', '>', '~'
};

const std::vector<char>::size_type defaultCombinationSize = 8;
std::vector<char> elusiveCombination;

} // namespace

namespace src {

std::vector<char> createRandomCombination(std::vector<char>::size_type vcs = ::defaultCombinationSize)
{
    std::default_random_engine dre(std::chrono::system_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<std::vector<char>::size_type> uid(0, ::availableElements.size() - 1);
    auto getRandomIndex = std::bind(uid, dre);
    std::vector<char> vc(vcs);

    std::generate(vc.begin(), vc.end(), [&getRandomIndex]() -> char {
        return ::availableElements.at(getRandomIndex());
    });

    return vc;
}

std::ostream & operator << (std::ostream &os, const std::vector<char> &vc)
{
    for (char c: vc)
        os << c;

    return os;
}

std::pair<std::vector<char>, bool> first(std::vector<char> vc)
{
    if (vc.size() == ::defaultCombinationSize)
        return std::make_pair(std::vector<char>{}, false);

    vc.push_back(::availableElements.front());
    return std::make_pair(vc, true);
}

std::pair<std::vector<char>, bool> next(std::vector<char> vc)
{
    if (vc.back() == ::availableElements.back())
        return std::make_pair(std::vector<char>{}, false);

    vc.back() = *++std::find(::availableElements.begin(), ::availableElements.end(), vc.back());
    return std::make_pair(vc, true);
}

void whinyChecker(const std::vector<char> &candidateCombination, std::ostream &os = std::cout)
{
    if (candidateCombination.size() != ::elusiveCombination.size())
        throw std::length_error("candidateCombination and ::elusiveCombination are not the same size.");
    else
    if (std::equal(candidateCombination.begin(), candidateCombination.end(), ::elusiveCombination.begin()))
    {
        os << ::elusiveCombination << " == " << candidateCombination << std::endl;
        throw std::logic_error("Solution was found, so why go on?");
    }
    else
        os << ::elusiveCombination << " != " << candidateCombination << std::endl;
}

void whinyBacktrack(const std::vector<char> &target, const std::vector<char> &built)
{
    if (target.size() == built.size())
    {
        whinyChecker(built);
        return;
    }

    auto possibleSolution = first(built);

    while (possibleSolution.second)
    {
        whinyBacktrack(target, possibleSolution.first);
        possibleSolution = next(possibleSolution.first);
    }
}

std::list<std::vector<char>> generateLimits()
{
    std::list<std::vector<char>> lvc;

    for (char c: ::availableElements)
    {
        std::vector<char> vc;

        vc.push_back(c);

        while (vc.size() < ::defaultCombinationSize)
            vc.push_back(::availableElements.back());

        lvc.push_back(vc);
    }

    return lvc;
}

} // namespace src

using src::operator<<;

#ifndef GCC_ACTUALLY_IMPLEMENTS_THREADS

int main()
{
    ::elusiveCombination = src::createRandomCombination();
    src::whinyBacktrack(src::generateLimits().back(), {});
}

#else

int main()
{
    ::elusiveCombination = src::createRandomCombination();

    std::list<std::thread> lt;

    for (const std::vector<char> &vc: src::generateLimits())
        lt.push_back(std::thread(src::whinyBacktrack, std::cref(vc), {}));

    for (std::thread &t: lt)
        t.join();
}

#endif


Bravo.

How long does it take on average?
Last edited on
devonrevenge (2435)
that mingw thing i downloaded, so i installed mingw and its sitting there...my codeblocks needed mingw but now theres a mingw ... outside of it? what do i do with it now? if i install it, do i lose all my settings as they are, its got sdl on it, a better one too but does that mean my sdl wont workify? what do i do with it, by the way these codes are impressive...i want to test them, so i need to know what the bloody hell that thing is (mingw)


havnt tested anyones code yet but woooh! c im busy with my thing for now but this got deep a bit quickly,
aint gonna become the worlds best proggrammer by running away from this stuff though.
Last edited on
htirwin (1208)
I had to -lpthread for std::thread to work with g++-4.6 on linux.
Imadatobanisa (647)
Awesome code :0... But, you should clean up your code a bit... :)
Last edited on
Catfish3 (666)
How long does it take on average?

Forever. Hmm, -lpthread? I'll try that.

Edit:
http://stackoverflow.com/questions/3414834/gcc-stdthread-not-found-in-namespace-std
The native Windows builds of gcc do not support the new C++0x/C++11 thread library.


I'll just... yawn... wait until they do.
Last edited on
Imadatobanisa (647)
Forever

What? You haven't tested it yet?
Catfish3 (666)
@ iseeplusplus: does it compile and run with threads for you?
I can imagine the output is all messed up.

Edit: and I just realized it has a major bug. It always starts from the start, and not from where the previous slice ends.
Last edited on
devonrevenge (2435)
so i have downloaded something i cant use?? i cant wait till this RPI comes in im gonna linux myself all the way to a solitary hermit like existence

Imadatobanisa (647)
Why don't you look at my code example (see previous page). It's a nice method and you only have to put your thread code... And, don't print the result immediately after a loop check, that is very slow IMO.
devonrevenge (2435)
thats one funky program jackson marie i like it ^_^
htirwin (1208)
Here's my multithreaded version. It takes a while to crack an 8 digit code. You can modify the number of digits, symbols, and threads, and the set of symbols by changing the constants. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
#include <iostream>
#include <thread>
#include <ctime>
#include <cmath>

using namespace std;

const int numThreads = 16;
const int numDigits  = 8;
const int numDigitsM1 = numDigits - 1;
const int numSymbols = 22;
const unsigned long long numCombos = pow(numSymbols, numDigits);
const unsigned long long numIterations   = numCombos / numThreads;
const char symbols[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!', '@', '#', '$', '%', '^', '&', '*', '?', '<', '>', '~'};

volatile bool done;
int winner_t;

bool testCombination (int sI[numThreads][numDigits], char com[numDigits], int id) {

    for (int i = 0; i < numDigits; ++i) {
        if (com[i] != symbols[sI[id][i]]) 
            return = false;
    }
    return true;
}

void nextCombination(int sI[numThreads][numDigits], char combo[numDigits], int id) {

    for (unsigned long long i = 0; i < numIterations && !done; ++i, ++sI[id][0]) {
        for  (int j = 0; j < numDigitsM1; ++j) {
            if (sI[id][j] == numSymbols) {
                sI[id][j] = 0;
                ++sI[id][j+1];
            }
        }
        if (testCombination (sI, combo, id)) {
            winner_t = id;
            done = true;
            return;
        }
    }
}

int main() {

    srand(time(0));
    done = false;
    char combo[numDigits];

    cout << endl;
    cout << "set: {" << flush;
    for (int i = 0; i < numSymbols-1; ++i)
        cout << symbols[i] << ", " << flush;
    cout << symbols[numSymbols - 1] << "}" << endl;

    cout << "random combination: " << flush;
    for (int i = 0; i < numDigits; ++i) 
        combo[i] = symbols[rand() % numSymbols];
    
    for (int i = numDigitsM1; i >= 0; --i)    
        cout << combo[i] << " " << flush;
    
    cout << endl << endl;

    int symbolIndex[numThreads][numDigits];

    cout << "number of threads: " << numThreads << endl;

    for (int i = 0; i < numThreads; ++i) {
        unsigned long long offSet = i * numIterations;
        for (int j = numDigitsM1; j >= 0; --j) {
            unsigned long long p = (unsigned long long)pow(numSymbols, j);
            symbolIndex[i][j] = offSet / p;
            offSet -= p * (offSet / p);
        }
    }

    for (int i = 0; i < numThreads; ++i) {
        cout << "thread[" << i <<"] offset: " << flush;
        for (int j = numDigits - 1; j >= 0; --j) {
            cout << symbols[symbolIndex[i][j]] << " " << flush;
        }
        cout << endl;
    }

    cout << endl << "working: please wait" << endl;

    std::thread t[numThreads];

    for (int i = 0; i < numThreads; ++i)
        t[i] = std::thread(nextCombination, symbolIndex, combo, i);

    for (int i = 0; i < numThreads; ++i)
        t[i].join();

    cout << endl << "thread " << winner_t << " won" << endl << "combo was: " << flush;

    for (int i = numDigitsM1; i >= 0; --i)
        cout << symbols[symbolIndex[winner_t][i]] << " " << flush;

    cout << endl << endl;
}

Last edited on
htirwin (1208)
Here it is without so much standard output 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include <iostream>
#include <thread>
#include <ctime>
#include <cmath>

const int numThreads = 16, numDigits = 8, numDigitsM1 = numdigits - 1, numSymbols = 22;
const unsigned long long numCombos = pow(numSymbols, numDigits);
const unsigned long long numIterations   = numCombos / numThreads;
const int symbols[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!', '@', '#', '$', '%', '^', '&', '*', '?', '<', '>', '~'};
volatile bool done;
int winner_t;

bool testCombination (int sI[numThreads][numDigits], int com[numDigits], int id) {
    for (int i = 0; i < numDigits; ++i) 
        if (com[i] != symbols[sI[id][i]]) 
            return false;
    return true;
}

void nextCombination(int sI[numThreads][numDigits], int combo[numDigits], int id) {
    for (unsigned long long i = 0; i < numIterations && !done; ++i, ++sI[id][0]) {
        for  (int j = 0; j < numDigitsM1; ++j) 
            if (sI[id][j] == numSymbols) {
                sI[id][j] = 0;
                ++sI[id][j+1];
            }
        else if (testCombination (sI, combo, id)) {
            winner_t = id;
            done = true;
            return;
        }
    }
}

int main() {
    srand(time(0));
    done = false;

    int combo[numDigits];
    for (int i = 0; i < numDigits; ++i) 
        combo[i] = symbols[rand() % numSymbols];

    int symbolIndex[numThreads][numDigits];
    for (int i = 0; i < numThreads; ++i) {
        unsigned long long offSet = i * numIterations;
        for (int j = numDigitsM1; j >= 0; --j) {
            unsigned long long p = (unsigned long long)pow(numSymbols, j);
            symbolIndex[i][j] = offSet / p;
            offSet -= p * (offSet / p);
        }
    }

    std::thread t[numThreads];
    for (int i = 0; i < numThreads; ++i)
        t[i] = std::thread(nextCombination, symbolIndex, combo, i);

    for (int i = 0; i < numThreads; ++i)
        t[i].join();

    for (int i = 0; i < numDigits; ++i)
        std::cout << std::endl << (char)symbols[symbolIndex[winner_t][i]] << " " << std::flush;
    std::cout << std::endl;
}

Last edited on
TheIdeasMan (6817)
@JM

Awesome code :0... But, you should clean up your code a bit... :)


Why don't you look at my code example (see previous page). It's a nice method ....


Not really, Anyone would be a lot better using the code by the more experienced coders posted on this thread. Yours has infinite loops, and goto (neither which are used appropriately IMO), and as per usual with your code - poorly formatted & hard to read, and no clear flow of logic. Other solutions don't have these, and are C++ oriented not C.

Wouldn't you be better to sit back and see what experienced coders offer, and learn from that rather than offering your own inept attempts?

How is your Starship Enterprise project going? I know you wanted to learn from that no matter how far / short it went, hopefully the lessons on Dog Kennel building are sinking in. We haven't seen much code - just a couple of union declarations, however some progress might have been made if you now know what an enum is. You don't seem to have a clear idea of how it will work or go about it, if you have to ask about this, why take on such a large & involved project? Why not do something easier?

I saw your other project with the menu and the 432K executable. What does that do? Possibly just the menu, maybe it runs existing applications. You haven't posted any code for that at all.

Sorry for the harsh criticism, but I am calling it how I see it, and stand by what I am saying. Of course others can choose whether they want to post or not, I am just trying to warn of the very high chance of the fruitlessness of doing this.
Imadatobanisa (647)
Thanks @TheIdeasMan...
My 432kb executable? In short "Debug" mode... :D
My program has many features... But it requires /Zm500... :(
Last edited on
TheIdeasMan (6817)
@JM

We were posting at the same time, the things I said in my last post still apply.
Catfish3 (666)
Can someone please do me a favor and try to compile and run this, then give me the output (or compiler errors)? Thanks.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
#include <algorithm>
#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <ostream>
#include <random>
#include <stdexcept>
#include <thread>
#include <utility>
#include <vector>

namespace {

const std::vector<char> availableElements {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '!', '@', '#', '$', '%', '^', '&', '*', '?', '<', '>', '~'
};

const std::vector<char>::size_type defaultCombinationSize = 8;
std::vector<char> elusiveCombination;

} // namespace

namespace src {

std::vector<char> createRandomCombination(std::vector<char>::size_type vcs = ::defaultCombinationSize)
{
    std::default_random_engine dre(std::chrono::system_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<std::vector<char>::size_type> uid(0, ::availableElements.size() - 1);
    auto getRandomIndex = std::bind(uid, dre);
    std::vector<char> vc(vcs);

    std::generate(vc.begin(), vc.end(), [&getRandomIndex]() -> char {
        return ::availableElements.at(getRandomIndex());
    });

    return vc;
}

std::ostream & operator << (std::ostream &os, const std::vector<char> &vc)
{
    for (char c: vc)
        os << c;

    return os;
}

bool whinyChecker(const std::vector<char> &candidateCombination, std::ostream &os = std::cout)
{
    if (candidateCombination.size() != ::elusiveCombination.size())
        throw std::length_error("candidateCombination and ::elusiveCombination are not the same size.");
    else
    if (std::equal(candidateCombination.begin(), candidateCombination.end(), ::elusiveCombination.begin()))
    {
        os << ::elusiveCombination << " == " << candidateCombination << std::endl;
        return true;
    }

    os << ::elusiveCombination << " != " << candidateCombination << std::endl;
    return false;
}

void nextPermutation(std::vector<char> &vc)
{
    for (char &c: vc)
        if (c == ::availableElements.back())
            c = ::availableElements.front();
        else
        {
            c = *++std::find(::availableElements.begin(), ::availableElements.end(), c);
            break;
        }
}

void whinyTester(std::pair<std::vector<char>, std::vector<char>> pvc)
{
    while (!whinyChecker(pvc.first))
    {
        if (std::equal(pvc.first.begin(), pvc.first.end(), pvc.second.begin()))
            return;

        nextPermutation(pvc.first);
    }
}

std::list<std::pair<std::vector<char>, std::vector<char>>> generateLimits()
{
    std::list<std::pair<std::vector<char>, std::vector<char>>> lpvc;

    for (char c: ::availableElements)
    {
        std::vector<char> sliceBegin, sliceEnd;

        while (sliceBegin.size() < ::defaultCombinationSize - 1)
            sliceBegin.push_back(::availableElements.front());

        while (sliceEnd.size() < ::defaultCombinationSize - 1)
            sliceEnd.push_back(::availableElements.back());

        sliceBegin.push_back(c);
        sliceEnd.push_back(c);
        lpvc.push_back(std::make_pair(sliceBegin, sliceEnd));
    }

    return lpvc;
}

} // namespace src

using src::operator<<;

int main()
{
    ::elusiveCombination = src::createRandomCombination();

    std::list<std::thread> lt;

    for (const std::pair<std::vector<char>, std::vector<char>> &pv: src::generateLimits())
        lt.push_back(std::thread(src::generateAndTestNext, std::cref(pv.first), std::cref(pv.second)));

    for (std::thread &t: lt)
        t.join();
}

rapidcoder (1010)
Oh, looks like another contest who writes the longest and uggliest code for solving a trivial problem that can be coded in a few short lines in some higher-level language ;)
Catfish3 (666)
Go home rapidcoder, before I start throwing bananas at you.
Imadatobanisa (647)
Good, Catfish3 !!!! That's right!!
rapidcoder (1010)
I like bananas. Go on.
Pages: 1... 3456