Need help with project

Pages: 123
markyrocks (346)
Snip. I was wrong my apologies.
Last edited on
lastchance (6980)
I concur with @dutch's count of 60 (but it took me a lot longer than 5 minutes to write the code!)

The calculation here was done by back-tracking, as already mentioned.

However, you could also do it (here) by brute force: it's only (8-1)! = 5040 permutations to check if you want to fix the first knight and then permute all the others. (Remember to check that the last of your 8 would also "loop round" to be a friend of the first.) 5040 sequences to check is easily feasible.

1: Agrawain Galahad Bedivere Mordred Gwain Percival Dinadan Lancelot 
2: Agrawain Galahad Bedivere Mordred Percival Gwain Dinadan Lancelot 
3: Agrawain Galahad Bedivere Lancelot Dinadan Percival Mordred Gwain 
4: Agrawain Galahad Bedivere Lancelot Dinadan Gwain Mordred Percival 
5: Agrawain Galahad Lancelot Dinadan Bedivere Mordred Gwain Percival 
6: Agrawain Galahad Lancelot Dinadan Bedivere Mordred Percival Gwain 
7: Agrawain Galahad Lancelot Bedivere Dinadan Percival Mordred Gwain 
8: Agrawain Galahad Lancelot Bedivere Dinadan Gwain Mordred Percival 
9: Agrawain Galahad Lancelot Bedivere Mordred Gwain Dinadan Percival 
10: Agrawain Galahad Lancelot Bedivere Mordred Percival Dinadan Gwain 
11: Agrawain Galahad Mordred Bedivere Lancelot Dinadan Percival Gwain 
12: Agrawain Galahad Mordred Bedivere Lancelot Dinadan Gwain Percival 
13: Agrawain Galahad Mordred Gwain Percival Dinadan Bedivere Lancelot 
14: Agrawain Galahad Mordred Percival Gwain Dinadan Bedivere Lancelot 
15: Agrawain Percival Dinadan Bedivere Lancelot Galahad Mordred Gwain 
16: Agrawain Percival Dinadan Lancelot Galahad Bedivere Mordred Gwain 
17: Agrawain Percival Dinadan Lancelot Bedivere Galahad Mordred Gwain 
18: Agrawain Percival Dinadan Gwain Mordred Bedivere Galahad Lancelot 
19: Agrawain Percival Dinadan Gwain Mordred Bedivere Lancelot Galahad 
20: Agrawain Percival Dinadan Gwain Mordred Galahad Bedivere Lancelot 
21: Agrawain Percival Gwain Dinadan Bedivere Mordred Galahad Lancelot 
22: Agrawain Percival Gwain Dinadan Lancelot Bedivere Mordred Galahad 
23: Agrawain Percival Gwain Mordred Bedivere Dinadan Lancelot Galahad 
24: Agrawain Percival Gwain Mordred Galahad Bedivere Dinadan Lancelot 
25: Agrawain Percival Mordred Bedivere Galahad Lancelot Dinadan Gwain 
26: Agrawain Percival Mordred Gwain Dinadan Bedivere Galahad Lancelot 
27: Agrawain Percival Mordred Gwain Dinadan Bedivere Lancelot Galahad 
28: Agrawain Percival Mordred Gwain Dinadan Lancelot Bedivere Galahad 
29: Agrawain Percival Mordred Galahad Bedivere Lancelot Dinadan Gwain 
30: Agrawain Percival Mordred Galahad Lancelot Bedivere Dinadan Gwain 
31: Agrawain Lancelot Dinadan Bedivere Galahad Mordred Gwain Percival 
32: Agrawain Lancelot Dinadan Bedivere Galahad Mordred Percival Gwain 
33: Agrawain Lancelot Dinadan Percival Gwain Mordred Bedivere Galahad 
34: Agrawain Lancelot Dinadan Gwain Percival Mordred Bedivere Galahad 
35: Agrawain Lancelot Galahad Bedivere Dinadan Percival Mordred Gwain 
36: Agrawain Lancelot Galahad Bedivere Dinadan Gwain Mordred Percival 
37: Agrawain Lancelot Galahad Bedivere Mordred Gwain Dinadan Percival 
38: Agrawain Lancelot Galahad Bedivere Mordred Percival Dinadan Gwain 
39: Agrawain Lancelot Galahad Mordred Bedivere Dinadan Percival Gwain 
40: Agrawain Lancelot Galahad Mordred Bedivere Dinadan Gwain Percival 
41: Agrawain Lancelot Bedivere Dinadan Percival Gwain Mordred Galahad 
42: Agrawain Lancelot Bedivere Dinadan Gwain Percival Mordred Galahad 
43: Agrawain Lancelot Bedivere Galahad Mordred Gwain Dinadan Percival 
44: Agrawain Lancelot Bedivere Galahad Mordred Percival Dinadan Gwain 
45: Agrawain Gwain Dinadan Bedivere Lancelot Galahad Mordred Percival 
46: Agrawain Gwain Dinadan Lancelot Galahad Bedivere Mordred Percival 
47: Agrawain Gwain Dinadan Lancelot Bedivere Galahad Mordred Percival 
48: Agrawain Gwain Dinadan Percival Mordred Bedivere Galahad Lancelot 
49: Agrawain Gwain Dinadan Percival Mordred Bedivere Lancelot Galahad 
50: Agrawain Gwain Dinadan Percival Mordred Galahad Bedivere Lancelot 
51: Agrawain Gwain Mordred Bedivere Galahad Lancelot Dinadan Percival 
52: Agrawain Gwain Mordred Percival Dinadan Bedivere Galahad Lancelot 
53: Agrawain Gwain Mordred Percival Dinadan Bedivere Lancelot Galahad 
54: Agrawain Gwain Mordred Percival Dinadan Lancelot Bedivere Galahad 
55: Agrawain Gwain Mordred Galahad Bedivere Lancelot Dinadan Percival 
56: Agrawain Gwain Mordred Galahad Lancelot Bedivere Dinadan Percival 
57: Agrawain Gwain Percival Dinadan Bedivere Mordred Galahad Lancelot 
58: Agrawain Gwain Percival Dinadan Lancelot Bedivere Mordred Galahad 
59: Agrawain Gwain Percival Mordred Bedivere Dinadan Lancelot Galahad 
60: Agrawain Gwain Percival Mordred Galahad Bedivere Dinadan Lancelot


Here's my graph-maker:
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
 
void makeGraph( int &N, map<string,vector<string>> &M )
{
   istringstream in( "Agrawain  Galahad  Percival  Lancelot  Gwain  \n"
                     "Bedivere  Dinadan  Galahad  Mordred  Lancelot \n"
                     "Dinadan  Bedivere  Lancelot  Percival  Gwain  \n"
                     "Galahad  Agrawain  Bedivere  Lancelot  Mordred\n"
                     "Gwain  Dinadan  Agrawain  Mordred  Percival   \n"
                     "Lancelot  Agrawain  Dinadan  Galahad  Bedivere\n"
                     "Mordred  Bedivere  Gwain  Percival  Galahad   \n"
                     "Percival  Agrawain  Dinadan  Gwain  Mordred   \n" );

   M.clear();
   set<string> S;

   for ( string line; getline( in, line ); )
   {
      stringstream ss( line );
      string first, pal;
      for ( ss >> first; ss >> pal; ) M[first].push_back( pal );
   }

   for ( const auto &pr : M )
   {
      for ( const auto &e : pr.second ) S.insert( e );
   }
   N = S.size();
}


Last edited on
markyrocks (346)
im having buggy issues now. I went through my code again and found a mistake.... the weird part is that the damn thing works better with the mistake.

in summary if my code doesn't intentionally erroneously exit out of the function im back to my stack overflow situation. I think it has to do with too many threads trying to access a array at one time? or maybe its just too many threads period. The thing is tho as i said b4 my code does verify the results so unless its just reading trash data from somewhere idk how they couldn't be accurate.

now like magic i'm getting 60 results but i still don't know how its possible that i was able to get more previously. I'm going to try using a semaphore and see if that helps.

well i'll be damned i guess the number is 60. I still don't know how my code was able to find more results even tho i was doing an indepth analysis of them b4 they were displayed. it was weird that the mistake produced more results than less bc if anything it should have limited the results and not pushed out more...

but the way i solved my stack overflow problem was i added a halfassed thread counter that made the function return if it got over a certain amount. Just weird that it should be necessary when using a single threaded program. beyond me how this issue arrises. I could understand if i was attempting to suck out the entire result using one recursive call but im using a loop that calls the recursive function. i'd assume that if a particular call was in a scenario where it was hanging forever that the program would just sleep. but i'm glad i finally got it sorted. Very interesting project. Definitely a good learning experience.
Last edited on
dhayden (5799)
I think it has to do with too many threads trying to access a array at one time?
...
i changed it to look randomly in the friend list
...
and i'm working from the outer edges inwards from both sides at the same time.

This sounds way more complicated than it needs to be. Just do a DFS.
dhayden (5799)
For example:
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
 
#include <iostream>
#include <vector>

using std::vector;

enum { Agrawain, Bedivere, Dinadan, Galahad, Gwain, Lancelot, Mordred, Percival, LastKnight };
constexpr unsigned NumKnights = LastKnight;

const char *names[NumKnights] = {
  "Agrawain", "Bedivere", "Dinadan", "Galahad", "Gwain", "Lancelot",
  "Mordred", "Percival"};

// Unique bits for each knight so they can be combined in a bit map
constexpr unsigned AgrawainBit = 1 << Agrawain;
constexpr unsigned BedivereBit = 1 << Bedivere;
constexpr unsigned DinadanBit = 1 << Dinadan;
constexpr unsigned GalahadBit = 1 << Galahad;
constexpr unsigned GwainBit = 1 << Gwain;
constexpr unsigned LancelotBit = 1 << Lancelot;
constexpr unsigned MordredBit = 1 << Mordred;
constexpr unsigned PercivalBit = 1 << Percival;

// Bit maps of the friends of each knight
unsigned friends[NumKnights] = {
    GalahadBit | PercivalBit | LancelotBit | GwainBit, //  Agrawain
    DinadanBit | GalahadBit | MordredBit | LancelotBit, //  Bedivere
    BedivereBit | LancelotBit | PercivalBit | GwainBit, //  Dinadan
    AgrawainBit | BedivereBit | LancelotBit | MordredBit, //  Galahad
    DinadanBit | AgrawainBit | MordredBit | PercivalBit, //  Gwain
    AgrawainBit | DinadanBit | GalahadBit | BedivereBit, //  Lancelot
    BedivereBit | GwainBit | PercivalBit | GalahadBit, //  Mordred
    AgrawainBit | DinadanBit | GwainBit | MordredBit //  Percival
};

// Print the names of an array of knights
void				
printSoFar(const vector<unsigned> &soFar)
{
    for (auto knight : soFar) {
	std::cout << names[knight] << ' ';
    }
    std::cout << '\n';
}

// Recursively check for a seating solution.
// soFar contains the knights who are already seated.
// bits is a bitmap of those same seated knights and exists only for performance.
void
checkSeating(vector<unsigned> &soFar, unsigned bits)
{
    // Uncomment the next 2 lines for debugging.
    // std::cout << "checkSeating(): " ;
    // printSoFar(soFar;
    if (soFar.size() >= NumKnights) {
	// Everyone is seated. Print them out. Note that I'm NOT check
	// whether the first knight is friends with the last one, assuming that
	// Arthur can sit between them.  If would be simple to add code here to
	// check if soFar[0] is friends with soFar[idx-1]
	printSoFar(soFar);
    } else {
	unsigned neighbor = soFar.back(); // last seated knight
	for (unsigned knight=0; knight< NumKnights; ++knight) {
	    unsigned knightBit = 1 << knight;
	    if ((friends[neighbor] & knightBit) && // neighbor and knight are friends
		!(bits & knightBit)) {		// knight hasn't been seated
		soFar.push_back(knight);
		checkSeating(soFar, bits | knightBit);
		soFar.pop_back();
	    }
	}
    }
}

int main()
{
    vector<unsigned> soFar;

    // Start with the first knight (Agrawain) seated
    soFar.push_back(Agrawain);
    checkSeating(soFar, AgrawainBit);
}

markyrocks (346)
1
2
3
 

This sounds way more complicated than it needs to be. Just do a DFS


I got it sorted. I'm not the op just an enthusiast. My solution ended up being way more complicated than necessary bc the thing kept overflowing bc of a recursive function. So it caused me to have to keep changing it even though the solution seemed obvious enough. My solution is single threaded but I'm assuming that the stack memory wasn't being cleared fast enough. Its literally a problem I've been battling the whole time. Previous attempts may have been correct but I couldn't wrap my mind around the exemptions that I was experiencing. I wanted to use the recursive function bc its not something that I had played with b4. The thread counter is just a global variable that increments everytime a call to the recursive function is made and just decrements every time it returns. If it goes over a certain number it just returns. Just kept it from going too deep into the hole. But it works good now, finds all the results in like 2 seconds.

your code looks very sophisticated. i understand the very basics of messing with bits but its also way beyond me. My only question is does the above figure out all the possible combinations? Just for my own curiosity.
Last edited on
dutch (2548)
I was dreading checking this thread this morning, just in case. But happily lastchance concurs, which is good news for me! As for the five minutes ... maybe it took a little longer. :-) But it is pretty simple.

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
 
#include <iostream>
#include <string>
#include <map>

const bool CheckEnds = true;

using Map = std::map<char, const std::string>;

bool place(Map& friends, char knight, std::string& seats, int& count) {
    if (seats.size() == friends.size()) {
        if (!CheckEnds || friends[seats.front()].find(seats.back()) != seats.npos) {
            for (char ch: seats) std::cout << ch << ' ';
            std::cout << '\n';
            ++count;
            return true;
        }
    }
    else
        for (char f: friends[knight])
            if (seats.find(f) == seats.npos) {
                seats.push_back(f);
                place(friends, f, seats, count);
                seats.pop_back();
            }
    return false;
}

int main() {
    Map friends {
        { 'A', "GHLP" },
        { 'B', "DGLM" },
        { 'D', "BHLP" },
        { 'G', "ABLM" },
        { 'H', "ADMP" },
        { 'L', "ABDG" },
        { 'M', "BGHP" },
        { 'P', "ADHM" }
    };
    std::string seats {'A'};
    int count = 0;
    place(friends, 'A', seats, count);
    std::cout << "Number of solutions: " << count << '\n';
}

markyrocks (346)
damn. pure genius. (and i dont' say that sarcastically).
dutch (2548)
damn. pure genius

No, just experience.
I've seen similar things a hundred times before. :-)
And it's not the most efficient implementation if it were to be scaled up.
I was just trying to get the answer.
jonnin (11495)
well it would run a ton faster if you quit once you found an answer instead of looking for more :)
dutch (2548)
True. I became interested in the total number of answers after solving the original problem. My original ("five minute") version stopped when it found an answer. It's a little shorter.

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
 
#include <iostream>
#include <string>
#include <map>

using Map = std::map<char, const std::string>;

bool place(Map& friends, char knight, std::string& seats) {
    if (seats.size() == friends.size())
        return friends[seats.front()].find(seats.back()) != seats.npos;
    for (char f: friends[knight])
        if (seats.find(f) == seats.npos) {
            seats.push_back(f);
            if (place(friends, f, seats))
                return true;
            seats.pop_back();
        }
    return false;
}

int main() {
    Map friends {
        { 'A', "GHLP" },
        { 'B', "DGLM" },
        { 'D', "BHLP" },
        { 'G', "ABLM" },
        { 'H', "ADMP" },
        { 'L', "ABDG" },
        { 'M', "BGHP" },
        { 'P', "ADHM" }
    };
    std::string seats {'A'};
    if (place(friends, 'A', seats))
        for (char ch: seats) std::cout << ch << ' ';
    else
        std::cout << "No solution.";
    std::cout << '\n';
}

dhayden (5799)
your code looks very sophisticated.
Nah. It's actually the same algorithm as Dutch's, only using different data to represent things.
i understand the very basics of messing with bits but its also way beyond me.
I'm a crusty old bit twiddler so this stuff is completely natural to me. I'll try doing it with bitset<> to make it clearer.
My only question is does the above figure out all the possible combinations? Just for my own curiosity.
Yes. It finds the 100 possibilities when Arthur sits between the first and last knights.
Agrawain Galahad Bedivere Lancelot Dinadan Gwain Mordred Percival 
Agrawain Galahad Bedivere Lancelot Dinadan Gwain Percival Mordred 
Agrawain Galahad Bedivere Lancelot Dinadan Percival Gwain Mordred 
Agrawain Galahad Bedivere Lancelot Dinadan Percival Mordred Gwain 
Agrawain Galahad Bedivere Mordred Gwain Percival Dinadan Lancelot 
Agrawain Galahad Bedivere Mordred Percival Gwain Dinadan Lancelot 
Agrawain Galahad Lancelot Bedivere Dinadan Gwain Mordred Percival 
Agrawain Galahad Lancelot Bedivere Dinadan Gwain Percival Mordred 
Agrawain Galahad Lancelot Bedivere Dinadan Percival Gwain Mordred 
Agrawain Galahad Lancelot Bedivere Dinadan Percival Mordred Gwain 
Agrawain Galahad Lancelot Bedivere Mordred Gwain Dinadan Percival 
Agrawain Galahad Lancelot Bedivere Mordred Gwain Percival Dinadan 
Agrawain Galahad Lancelot Bedivere Mordred Percival Dinadan Gwain 
Agrawain Galahad Lancelot Bedivere Mordred Percival Gwain Dinadan 
Agrawain Galahad Lancelot Dinadan Bedivere Mordred Gwain Percival 
Agrawain Galahad Lancelot Dinadan Bedivere Mordred Percival Gwain 
Agrawain Galahad Lancelot Dinadan Gwain Percival Mordred Bedivere 
Agrawain Galahad Lancelot Dinadan Percival Gwain Mordred Bedivere 
Agrawain Galahad Mordred Bedivere Lancelot Dinadan Gwain Percival 
Agrawain Galahad Mordred Bedivere Lancelot Dinadan Percival Gwain 
Agrawain Galahad Mordred Gwain Percival Dinadan Bedivere Lancelot 
Agrawain Galahad Mordred Gwain Percival Dinadan Lancelot Bedivere 
Agrawain Galahad Mordred Percival Gwain Dinadan Bedivere Lancelot 
Agrawain Galahad Mordred Percival Gwain Dinadan Lancelot Bedivere 
Agrawain Gwain Dinadan Bedivere Lancelot Galahad Mordred Percival 
Agrawain Gwain Dinadan Lancelot Bedivere Galahad Mordred Percival 
Agrawain Gwain Dinadan Lancelot Galahad Bedivere Mordred Percival 
Agrawain Gwain Dinadan Percival Mordred Bedivere Galahad Lancelot 
Agrawain Gwain Dinadan Percival Mordred Bedivere Lancelot Galahad 
Agrawain Gwain Dinadan Percival Mordred Galahad Bedivere Lancelot 
Agrawain Gwain Dinadan Percival Mordred Galahad Lancelot Bedivere 
Agrawain Gwain Mordred Bedivere Galahad Lancelot Dinadan Percival 
Agrawain Gwain Mordred Galahad Bedivere Lancelot Dinadan Percival 
Agrawain Gwain Mordred Galahad Lancelot Bedivere Dinadan Percival 
Agrawain Gwain Mordred Percival Dinadan Bedivere Galahad Lancelot 
Agrawain Gwain Mordred Percival Dinadan Bedivere Lancelot Galahad 
Agrawain Gwain Mordred Percival Dinadan Lancelot Bedivere Galahad 
Agrawain Gwain Mordred Percival Dinadan Lancelot Galahad Bedivere 
Agrawain Gwain Percival Dinadan Bedivere Lancelot Galahad Mordred 
Agrawain Gwain Percival Dinadan Bedivere Mordred Galahad Lancelot 
Agrawain Gwain Percival Dinadan Lancelot Bedivere Galahad Mordred 
Agrawain Gwain Percival Dinadan Lancelot Bedivere Mordred Galahad 
Agrawain Gwain Percival Dinadan Lancelot Galahad Bedivere Mordred 
Agrawain Gwain Percival Dinadan Lancelot Galahad Mordred Bedivere 
Agrawain Gwain Percival Mordred Bedivere Dinadan Lancelot Galahad 
Agrawain Gwain Percival Mordred Bedivere Galahad Lancelot Dinadan 
Agrawain Gwain Percival Mordred Galahad Bedivere Dinadan Lancelot 
Agrawain Gwain Percival Mordred Galahad Bedivere Lancelot Dinadan 
Agrawain Gwain Percival Mordred Galahad Lancelot Bedivere Dinadan 
Agrawain Gwain Percival Mordred Galahad Lancelot Dinadan Bedivere 
Agrawain Lancelot Bedivere Dinadan Gwain Percival Mordred Galahad 
Agrawain Lancelot Bedivere Dinadan Percival Gwain Mordred Galahad 
Agrawain Lancelot Bedivere Galahad Mordred Gwain Dinadan Percival 
Agrawain Lancelot Bedivere Galahad Mordred Gwain Percival Dinadan 
Agrawain Lancelot Bedivere Galahad Mordred Percival Dinadan Gwain 
Agrawain Lancelot Bedivere Galahad Mordred Percival Gwain Dinadan 
Agrawain Lancelot Dinadan Bedivere Galahad Mordred Gwain Percival 
Agrawain Lancelot Dinadan Bedivere Galahad Mordred Percival Gwain 
Agrawain Lancelot Dinadan Gwain Percival Mordred Bedivere Galahad 
Agrawain Lancelot Dinadan Gwain Percival Mordred Galahad Bedivere 
Agrawain Lancelot Dinadan Percival Gwain Mordred Bedivere Galahad 
Agrawain Lancelot Dinadan Percival Gwain Mordred Galahad Bedivere 
Agrawain Lancelot Galahad Bedivere Dinadan Gwain Mordred Percival 
Agrawain Lancelot Galahad Bedivere Dinadan Gwain Percival Mordred 
Agrawain Lancelot Galahad Bedivere Dinadan Percival Gwain Mordred 
Agrawain Lancelot Galahad Bedivere Dinadan Percival Mordred Gwain 
Agrawain Lancelot Galahad Bedivere Mordred Gwain Dinadan Percival 
Agrawain Lancelot Galahad Bedivere Mordred Gwain Percival Dinadan 
Agrawain Lancelot Galahad Bedivere Mordred Percival Dinadan Gwain 
Agrawain Lancelot Galahad Bedivere Mordred Percival Gwain Dinadan 
Agrawain Lancelot Galahad Mordred Bedivere Dinadan Gwain Percival 
Agrawain Lancelot Galahad Mordred Bedivere Dinadan Percival Gwain 
Agrawain Lancelot Galahad Mordred Gwain Percival Dinadan Bedivere 
Agrawain Lancelot Galahad Mordred Percival Gwain Dinadan Bedivere 
Agrawain Percival Dinadan Bedivere Lancelot Galahad Mordred Gwain 
Agrawain Percival Dinadan Gwain Mordred Bedivere Galahad Lancelot 
Agrawain Percival Dinadan Gwain Mordred Bedivere Lancelot Galahad 
Agrawain Percival Dinadan Gwain Mordred Galahad Bedivere Lancelot 
Agrawain Percival Dinadan Gwain Mordred Galahad Lancelot Bedivere 
Agrawain Percival Dinadan Lancelot Bedivere Galahad Mordred Gwain 
Agrawain Percival Dinadan Lancelot Galahad Bedivere Mordred Gwain 
Agrawain Percival Gwain Dinadan Bedivere Lancelot Galahad Mordred 
Agrawain Percival Gwain Dinadan Bedivere Mordred Galahad Lancelot 
Agrawain Percival Gwain Dinadan Lancelot Bedivere Galahad Mordred 
Agrawain Percival Gwain Dinadan Lancelot Bedivere Mordred Galahad 
Agrawain Percival Gwain Dinadan Lancelot Galahad Bedivere Mordred 
Agrawain Percival Gwain Dinadan Lancelot Galahad Mordred Bedivere 
Agrawain Percival Gwain Mordred Bedivere Dinadan Lancelot Galahad 
Agrawain Percival Gwain Mordred Bedivere Galahad Lancelot Dinadan 
Agrawain Percival Gwain Mordred Galahad Bedivere Dinadan Lancelot 
Agrawain Percival Gwain Mordred Galahad Bedivere Lancelot Dinadan 
Agrawain Percival Gwain Mordred Galahad Lancelot Bedivere Dinadan 
Agrawain Percival Gwain Mordred Galahad Lancelot Dinadan Bedivere 
Agrawain Percival Mordred Bedivere Galahad Lancelot Dinadan Gwain 
Agrawain Percival Mordred Galahad Bedivere Lancelot Dinadan Gwain 
Agrawain Percival Mordred Galahad Lancelot Bedivere Dinadan Gwain 
Agrawain Percival Mordred Gwain Dinadan Bedivere Galahad Lancelot 
Agrawain Percival Mordred Gwain Dinadan Bedivere Lancelot Galahad 
Agrawain Percival Mordred Gwain Dinadan Lancelot Bedivere Galahad 
Agrawain Percival Mordred Gwain Dinadan Lancelot Galahad Bedivere

dhayden (5799)
Here it is with bitset<>. This runs in about 90ms on my laptop.
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
 
#include <iostream>
#include <vector>
#include <bitset>

using std::vector;

enum { Agrawain, Bedivere, Dinadan, Galahad, Gwain, Lancelot, Mordred, Percival, LastKnight };
constexpr unsigned NumKnights = LastKnight;
const char *names[NumKnights] = {
  "Agrawain", "Bedivere", "Dinadan", "Galahad", "Gwain", "Lancelot",
  "Mordred", "Percival"};

using Bits = std::bitset<NumKnights>;

// Unique bits for each knight so they can be combined in a bit map
constexpr unsigned AgrawainBit = 1 << Agrawain;
constexpr unsigned BedivereBit = 1 << Bedivere;
constexpr unsigned DinadanBit = 1 << Dinadan;
constexpr unsigned GalahadBit = 1 << Galahad;
constexpr unsigned GwainBit = 1 << Gwain;
constexpr unsigned LancelotBit = 1 << Lancelot;
constexpr unsigned MordredBit = 1 << Mordred;
constexpr unsigned PercivalBit = 1 << Percival;

// Bit maps of the friends of each knight
Bits friends[NumKnights] = {
    GalahadBit | PercivalBit | LancelotBit | GwainBit, //  Agrawain
    DinadanBit | GalahadBit | MordredBit | LancelotBit, //  Bedivere
    BedivereBit | LancelotBit | PercivalBit | GwainBit, //  Dinadan
    AgrawainBit | BedivereBit | LancelotBit | MordredBit, //  Galahad
    DinadanBit | AgrawainBit | MordredBit | PercivalBit, //  Gwain
    AgrawainBit | DinadanBit | GalahadBit | BedivereBit, //  Lancelot
    BedivereBit | GwainBit | PercivalBit | GalahadBit, //  Mordred
    AgrawainBit | DinadanBit | GwainBit | MordredBit //  Percival
};

// Print the names of an array of knights
void				
printSoFar(const vector<unsigned> &soFar)
{
    for (auto knight : soFar) {
	std::cout << names[knight] << ' ';
    }
    std::cout << '\n';
}

// Recursively check for a seating solution.
// soFar contains the knights who are already seated.
// bits is a bitmap of those same seated knights and exists only for performance.
void
checkSeating(vector<unsigned> &soFar, Bits seated)
{
    // Uncomment the next 2 lines for debugging.
    // std::cout << "checkSeating(): " ;
    // printSoFar(soFar;
    if (soFar.size() >= NumKnights) {
	// Everyone is seated. Print them out. Note that I'm NOT check
	// whether the first knight is friends with the last one, assuming that
	// Arthur can sit between them.  If would be simple to add code here to
	// check if soFar[0] is friends with soFar[idx-1]
	printSoFar(soFar);
    } else {
	unsigned neighbor = soFar.back(); // last seated knight
	for (unsigned knight=0; knight< NumKnights; ++knight) {
	    if ((friends[neighbor].test(knight)) && // neighbor and knight are friends
		!(seated.test(knight))) {		// knight hasn't been seated
		soFar.push_back(knight);
		seated.set(knight);
		checkSeating(soFar, seated);
		soFar.pop_back();
		seated.reset(knight);
	    }
	}
    }
}

int main()
{
    vector<unsigned> soFar;

    // Start with the first knight (Agrawain) seated
    soFar.push_back(Agrawain);
    checkSeating(soFar, AgrawainBit);
}

markyrocks (346)
im definetly seeing the pattern of the algorithm and i'm understanding how it like rolls itself up and then unrolls once a good or bad result is found. Im actually reworking mine to simulate what you guys have posted.

I only have one last question and this is killing me. Is there some kinda undefined behavior that takes place when passing arrays around in a recursive function?

like literally ive initialized a 2d int array (tried both in main and globally no difference).

i've printed out the array to verify that the damn thing is structured correctly. but i swear

that if i do the following;


it doesn't crash it just returns zero every time. when i know that the element isn't zero.
Last edited on
dhayden (5799)
That should be okay. Maybe you're stomping on the array somewhere else. Can you post your full code?
markyrocks (346)
That should be okay. Maybe you're stomping on the array somewhere else. Can you post your full code?


i figured it out. i just had been staring at the screen for too long and was delirious. The number being returned was actually zero.... lol im retarded. Or i was returning zero as a false result from somewhere else i can't remember. But lesson learned on returning 0 as an error result from a function that returns an int.
lastchance (6980)
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
 
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
using namespace std;

using Sequence = vector<string>;
using Graph = map<string,Sequence>;

//======================================================================

bool isValid( const Sequence &seq, int last )
{
   if ( last == seq.size() - 1 ) return ( seq[0] == seq[last] );
   for ( int i = 0; i < last; i++ ) if ( seq[last] == seq[i] ) return false;
   return true;
}

//======================================================================

Graph makeGraph( istream &in )
{
   Graph G;
   for ( string line; getline( in, line ); )
   {
      stringstream ss( line );
      string first, pal;
      for ( ss >> first; ss >> pal; ) G[first].push_back( pal );
   }
   return G;
}

//======================================================================

void print( const Sequence &seq )
{
   for ( int e = 0; e < seq.size() - 1; e++ ) cout << seq[e] << ' ';
   cout << '\n';
}

//======================================================================

bool update( int i, Graph &G, Sequence &seq, int &counter, bool showAll )
{
   if ( i == seq.size() )
   {
      counter++;
      print( seq );
      return !showAll;
   }

   for ( auto e : G[seq[i-1]] )
   {
      seq[i] = e;
      if ( isValid( seq, i ) && update( i + 1, G, seq, counter, showAll ) ) return true;
   }
   return false;
}

//======================================================================

int solve( Graph &G, Sequence &seq, bool showAll = false )
{
   int counter = 0;
   seq[0] = (*G.begin()).first;
   update( 1, G, seq, counter, showAll );
   return counter;
}

//======================================================================

int main()
{
   istringstream in( "Agrawain  Galahad  Percival  Lancelot  Gwain  \n"
                     "Bedivere  Dinadan  Galahad  Mordred  Lancelot \n"
                     "Dinadan  Bedivere  Lancelot  Percival  Gwain  \n"
                     "Galahad  Agrawain  Bedivere  Lancelot  Mordred\n"
                     "Gwain  Dinadan  Agrawain  Mordred  Percival   \n"
                     "Lancelot  Agrawain  Dinadan  Galahad  Bedivere\n"
                     "Mordred  Bedivere  Gwain  Percival  Galahad   \n"
                     "Percival  Agrawain  Dinadan  Gwain  Mordred   \n" );
   Graph G = makeGraph( in );
   Sequence seq( G.size() + 1 );

// solve( G, seq );                        // Find ANY solution
   int counter = solve( G, seq, true );    // Find ALL solutions
   cout << "Number of solutions = " << counter << '\n';
}

Last edited on
markyrocks (346)
THANK GOD. this was driving me crazy!!!!!!!

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
 

#include<Windows.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
struct l {

	const int agr, bed, din, gal, gwa, lan, mor, per; int resultcount, start, pos;
	const int list[8][4]; int seated[8];
	l()
		: agr(0), bed(1), din(2), gal(3), gwa(4), lan(5), mor(6), per(7), list{ {gal,per,lan,gwa},{din,gal,mor,lan},{bed,lan,per,gwa},{agr,bed,lan,mor},{din,agr,mor,per},
{agr,din,gal,bed},{bed,gwa,per,gal},{agr,din,gwa,mor} }, seated{}, resultcount{ 0 }, start(1) {}

	bool areFriends(int p1, int p2) {
		for (int i = 0; i < 4; i++) {
			if (this->list[p1][i] == p2) {
				return true;
			}
		}
		return false;
	}
	bool verifyResult() {
		int count = 0;
		int* seated = this->seated;
		if (!areFriends(seated[0], seated[7])) {  return false; }
		return true;
	}
	bool notSeated(int p1) {
		for (int i = 0; i < 8; i++) {
			if (p1 == this->seated[i]) { return false; }
		}
		return true;
	}
	void printResultAlt() {
		for (int i = 0; i < 8; i++) {
			cout << this->seated[i] << "  ";
		}
		cout << "\n";
		this->resultcount++;
	}
	void recursive() {
		int* start = &this->start;
		int* seated = this->seated;

		for (int i = 0; i < 4; i++) {
			if (*start == 8) {
				if (this->verifyResult()) { this->printResultAlt(); return; }
				else { return; }
			}
			if (*start < 8) {
				if (notSeated(this->list[seated[*start - 1]][i])) {
					seated[*start] = this->list[seated[*start - 1]][i];
				}
				else { seated[*start] = -1; }
			}                                                           
			if (seated[*start] > 0) {
				*start += 1;
				this->recursive();
				seated[*start] = 0;
				*start -= 1;
			}
		}
	}
};

int main() {

	l l_list;
	l_list.seated[0] = 0;
	l_list.recursive();
	cout << "result count  =  " << l_list.resultcount<< "\n";
}
Last edited on
dutch (2548)
I had a free five minutes :), so here's a random input generator. It may end up in an infinite loop in some cases, so be ready to kill it if it takes more than a few seconds. It might be better to add backtracking, but I didn't bother. Some inputs always create an infinite loop. (Something to do with prime or relatively-prime numbers?). And when it creates a graph, its not guaranteed (checked) to be solvable.

Usage: gen_graph -s SIZE -e EDGES -n NAMELEN -x SEED -p -j
         Generate random input for King Arthur problem.
         Values must have a space before them.
         -s size of graph (number of nodes)
         -e number of edges (defaults to size / 2)
         -n length of names (defaults to 5)
         -x seed to use (defaults to random_device)
         -p write seed to std::cerr
         -j just spaces (no punctuation)

$ ./gen_graph     # defaults
Gedop: Kemih, Xudax, Yafet, Zinax
Kemih: Gedop, Sekeh, Xuguy, Zinax
Sekeh: Kemih, Xuguy, Yafet, Zinax
Texat: Xudax, Xuguy, Yafet, Zinax
Xudax: Gedop, Texat, Xuguy, Yafet
Xuguy: Kemih, Sekeh, Texat, Xudax
Yafet: Gedop, Sekeh, Texat, Xudax
Zinax: Gedop, Kemih, Sekeh, Texat

$ ./gen_graph -s 12 -n 1   # edges defaults to half size
B: C, D, G, M, N, V
C: B, P, W, X, Y, Z
D: B, G, P, V, X, Y
G: B, D, M, N, W, Z
M: B, G, N, W, Y, Z
N: B, G, M, P, X, Y
P: C, D, N, V, X, Z
V: B, D, P, X, Y, Z
W: C, G, M, X, Y, Z
X: C, D, N, P, V, W
Y: C, D, M, N, V, W
Z: C, G, M, P, V, W

$ ./gen_graph -s 10 -e 6 -n 4 -j     # -j removes punctuation
Gode Naqa Qige Teki Xeba Yoha Yumo
Move Naqa Qige Teki Vere Xeba Yoha
Naqa Gode Move Qaya Teki Xeba Yumo
Qaya Naqa Teki Vere Xeba Yoha Yumo
Qige Gode Move Teki Vere Yoha Yumo
Teki Gode Move Naqa Qaya Qige Yoha
Vere Move Qaya Qige Xeba Yoha Yumo
Xeba Gode Move Naqa Qaya Vere Yumo
Yoha Gode Move Qaya Qige Teki Vere
Yumo Gode Naqa Qaya Qige Vere Xeba


You can pipe the output to your program, and maybe just time the actual processing, not reading the input:
$ ./gen_graph -s 30 -j -y | ./arthur
1
2
3
4
5
 
    // input ...
    time_t t_start = clock(); // clock() measures processor usage
    // process ...
    time_t t_end = clock();
    cout << (t_end - t_start) / (CLOCKS_PER_SEC / 1e6) << " us\n";


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
 
// Generate Friend Graph (C++14)
#include <iostream>
#include <algorithm>
#include <random>

using std::cout;
using std::string;
using std::vector;

using IntDist = std::uniform_int_distribution<int>;

const int MaxTries = 1000; // to detect "unsolvable" state

// global
std::default_random_engine RndEngine;

struct Node {
    std::string name;
    int num_edges;
    vector<bool> bits;

    Node(int size, string n, int ne)
        : name(n), num_edges(ne), bits(size) {}
};

string rnd_name(int len) {
    // Create strings out of alternating vowel/non-vowel letters
    string non_vowels{"bcdfghjklmnpqrstvwxyz"};
    IntDist dist_nonvowel(0, non_vowels.size() - 1);
    string vowels{"aeiou"};
    IntDist dist_vowel(0, vowels.size() - 1);

    string s;
    for (int i = 0; i < len; ++i)
        s.push_back(i % 2 ? vowels    [dist_vowel   (RndEngine)]
                          : non_vowels[dist_nonvowel(RndEngine)]);
    s.front() = std::toupper(s.front());

    return s;
}

auto make_graph(int size, int edges, int namelen) {

    IntDist dist_edge(0, size - 1);
    vector<Node> g; // graph to return

    for (int i = 0; i < size; ) {
        string name = rnd_name(namelen);
        if (find_if(g.begin(), g.end(),
                [&name](auto& a){ return a.name == name; }) == g.end()) {
            g.emplace_back(size, name, edges);
            ++i;
        }
    }

    sort(g.begin(), g.end(), [](auto& a, auto& b){ return a.name < b.name; });

    for (int i = 0; i < size; ++i) {
        int cnt = 0;
        while (g[i].num_edges > 0) {
            int r = dist_edge(RndEngine);
            if (r == i || g[r].num_edges < 1 || g[r].bits[i]) {
                // Give up after MaxTries tries.
                if (++cnt > MaxTries) { g.clear(); return g; }
                continue;
            }
            g[i].bits[r] = g[r].bits[i] = true; // unordered graph
            --g[i].num_edges;
            --g[r].num_edges;
        }
    }

    return g;
}

void print_graph(std::ostream& out, const vector<Node>& nodes, bool just_spaces) {
    for (const Node& nd: nodes) {
        out << nd.name << (just_spaces ? " " : ": ");
        bool comma = false;
        for (int i = 0; i < int(nodes.size()); ++i)
            if (nd.bits[i]) {
                cout << (comma ? (just_spaces ? " " : ", ") : "")
                     << nodes[i].name;
                comma = true;
            }
        out << '\n';
    }
}

int main(int, char **argv) {

    int size = 8;
    int edges = -1; // defaults to half size below
    int namelen = 5;
    unsigned seed = std::random_device{}();
    bool print_seed = false;
    bool just_spaces = false;

    for (++argv; *argv; ++argv) {
        using std::stoi;
        string s{*argv};
        if      (s == "-s") size = stoi(*++argv);
        else if (s == "-e") edges = stoi(*++argv);
        else if (s == "-n") namelen = stoi(*++argv);
        else if (s == "-x") seed = std::stoul(*++argv);
        else if (s == "-p") print_seed = true;
        else if (s == "-j") just_spaces = true;
        else {
            std::cerr <<
                "Usage: gen_graph -s SIZE -e EDGES -n NAMELEN -x SEED -p -j\n"
                "         Generate random input for King Arthur problem.\n"
                "         Values must have a space before them.\n"
                "         -s size of graph (number of nodes)\n"
                "         -e number of edges (defaults to size / 2)\n"
                "         -n length of names (defaults to 5)\n"
                "         -x seed to use (defaults to random_device)\n"
                "         -p write seed to std::cerr\n"
                "         -j just spaces (no punctuation)\n";
            return 1;
        }
    }

    RndEngine.seed(seed);

    if (edges < 0) edges = size / 2;

    if (size < 2 || edges >= size || namelen < 1) {
        std::cerr << "error: size < 2 or edges >= size or namelen < 1\n";
        return 1;
    }

    // Output seed on std::cerr so it doesn't go through the pipe
    if (print_seed) std::cerr << seed << '\n';

    vector<Node> g;
    do // try over and over again until we get a graph
        g = make_graph(size, edges, namelen);
    while (g.empty());

    print_graph(cout, g, just_spaces);
}

Last edited on
TheToaster (628)
@dhayden
You could also use an enum here right?

1
2
3
4
5
6
7
8
9
10
11
 
enum
{
    AgrawainBit = 1 << Agrawain,
    BedivereBit = 1 << Bedivere,
    DinadanBit = 1 << Dinadan,
    GalahadBit = 1 << Galahad,
    GwainBit = 1 << Gwain,
    LancelotBit = 1 << Lancelot,
    MordredBit = 1 << Mordred,
    PercivalBit = 1 << Percival
};


That would make these true compile-time constants.
Pages: 123