### Algorithm for a problem

Pages: 12
Script Coder; I didn't even sow your code till now, but I don't think it works.
I think it would be best if I would explain the whold problem and what did i do so far because this is geting kind of confusing for me.

So in the program you first input how many objects there will be.
Then for each object you instert how many strings it has then you instert the strings.
Each object has different set of strings, but some objects contain all the strings that some other object dose (plus some more strings), so since it contains all of it's strings it can go after it.
Now what I have do is in each of the object I made a set of flags that show which elements can go after it.
Then I have made all posible paths of those objects (even paths with 1 element in it, but it would be good if you could figure out an algorithm which would insert the last last needed flag). You will understand it better when you see the output of my code.

Example of input:
 ```4 2 nes tes 1 yes 1 nes 2 yes nes```
The result should be:
 `2 `
Explenation: (I'll call the elements p1, p2..) first goes p2 foloved by p4, the first path, then p3 and p1, the second path. Meaning minimum 2 paths are needed.

I'll add coments in my code and post it.
My code:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210`` ``````#include #include #define b2n63 9223372036854775808 using std::cin; using std::cout; using std::string; short n, c, ptn, bb, tip, size; unsigned long long bbb; /*n - number of objects, c - used as counter variable and insted of a parameter, ptn - current number of paths, tip - number of bytes in a part of flag set (number of bits in unsigned long long) size - number of "tip's" that are in the flag "variable", bb and bbb - counting variables*/ class juice { /*My objects with strings*/ public: short k, kk, kc; //number of strings in it, counter variable, group of bytes used string *s; //The array of strings unsigned long long *p, kn; //pointer to flags and a flag currently used void add(); /*constructor, and inserting strings*/ void compare(string d[], int f); /*Compare this object with another one and set the flag for it*/ short kon(unsigned long long *j, short *s); /*Returns details of the next object that can go after it*/ void clntext() { delete s; } /*Delete strings*/ ~juice() { delete p; } /*Delete the flags*/ }; class put { /*My paths of objects*/ public: short m; //How many flags it has unsigned long long *t; //The flags put *g; //Next element of the list put(); /*constructor - sets things to zero*/ bool ok(unsigned long long tt[]); /*Return true if any of the flags match*/ ~put() { delete t; delete g; } /*Delite the flag set and the next list element*/ }; juice *o; //Global variable put *pp, *ep; //The beggining of the flag list, and the path currently in use void putanja(short x); int main() { short x, k; //counting variables cin >> n; //How many objects tip = 8 * sizeof(unsigned long long); //Set tip size = (n-1)/tip + 1; //Set size juice l[n]; //Make objects o=l; //Make the objects globaly accesable for(x=0; x!=n; x++) { cin >> c; //How many strings l[x].add(); //Inster strings } for(x=0; x!=n; x++) for(c=0; c!=n; c++) { if(x==c) continue; //Dont compare it with itself l[x].compare(l[c].s, l[c].k); //Compare 2 objects and set flags } for(x=0; x!=n; x++) l[x].clntext(); //Delite strings for(k=x=0; x!=n; x++, k += x%tip?0:1) { if(pp) { ep->g = new put; ep=ep->g; } //New path else pp = ep = new put; ptn++; ep->t[k] = 1<<(x-tip*k); //Set first flag of the path ep->m++; //increment the flag lenght putanja(x); //Search for more elements for the path } for(k=0; k!=n; k++) //Displaying objects flags { cout << "\nE: "; for(bb=0; bb!=size; bb++) for(x=0; x!=n && x!=63; x++) cout << ' ' << ((l[k].p[bb] & (1<g) //Displaying path details { cout << "\nP: " << ep->m << " > t: "; for(bb=0; bb!=size; bb++) for(x=0; x!=n && x!=63; x++) cout << ' ' << ((ep->t[bb] & (1<t[s] & j)) //If the element isn't already in ine path (I'm not realy sure do I need this) { ep->g = new put; //Make a new path and put it on the end of the list ep = ep->g; //Switch to it ptn++; ep->m = p->m +1; //Set lenght for(bb=0; bb!=size; bb++) ep->t[bb] = p->t[bb]; //Copy flags from previus path ep->t[s] |= j; //Add new path putanja(y); //Try to increse it's size again } } return; } void juice::add() { k=c; kk=-1; kn=1; kc=0; s = new string[k]; p = new unsigned long long[size]; for(bb=0; bb!=size; bb++) p[bb]=0; for(bb=0; bb!=k; bb++) cin >> s[bb]; } void juice::compare(string d[], int f) { if(f<=k) return; /*Skip if the other element dosen't have more string than this one*/ short u, j, t; t = (c-1)/tip; //Select the flag "variable" part bbb = 1<<(c-tip*t); //Select the flag for(u=0; u!=k; u++) { for(j=bb=0; bb!=f; bb++) if(!s[u].compare(d[bb])) { j++; break; } if(!j) return; //Can't set the flag } p[t] |= bbb; //Tests passed, set the fag return; } short juice::kon(unsigned long long *j, short *s) { bool b=1; while(1) { kk++; if(kn==b2n63) { kc++; kn=1; } if(kk>=n) { kn=1; kc=0; kk=-1; return -1; } if(p[kc] & kn) break; kn <<= 1; b=0; } *j = kn; *s = kc; if(b) kn <<= 1; return kk; } put::put() { t = new unsigned long long[size]; m = 0; g = NULL; for(bb=0; bb!=size; bb++) t[bb]=0; } bool put::ok(unsigned long long tt[]) { for(bb=0; bb!=size; bb++) if(tt[bb] & t[bb]) return 0; return 1; } ``````
define "path" because according to my definition there is only one possible path that connects all pieces.
No, for me path is a groop of elements (flags 1) that go one after the other (like a path of flags that show the way to go).
And there are combinations of paths, they are the ones that contain all pieces (flags 1), but there can be many combinations of paths.
Why no repy?
Topic archived. No new replies allowed.
Pages: 12