Algorithm for a problem

[zoran404]

Script Coder; I didn't even sow your code till now, but I don't think it works.

[zoran404]

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.

[zoran404]

My code:

#include <iostream>
#include <cmath>

#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<<x))!=0);
    } cout<<'\n';
    
    for(ep=pp; ep; ep=ep->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<<x))!=0);
    }
    
    delete pp; //Delite the list
    
    cin.get();cin.get();
    
    return 0;
}

void putanja(short x)
{
    put *p = ep; //Remember which path this is
    unsigned long long j; //Counter var
    short y, s; //More counters
    
    for(y=o[x].kon(&j, &s); y!=-1; y=o[x].kon(&j, &s)) //Get a flag (it's details)
    {
        if(!(p->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;
}

[Script Coder]

define "path" because according to my definition there is only one possible path that connects all pieces.

[zoran404]

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.

[zoran404]

Why no repy?