Google CodeJam–Problem A: Fix-it

 

Question

You have a list of Unix file paths present in the system without repetition. Then there is another list of file paths which are required to be created based on the previous list.

The Unix file path is tree based. :) So, it obviously gives as the idea that, we need to do a tree.

The problem statement is here: http://code.google.com/codejam/contest/dashboard?c=635101#

You will be given a list of directory already present in the system like this,

/chicken
/chicken/egg

and you will be asked to create the following new directories
/chicken

/chicken/tom

/chicken/tom/jerry

We should basically check whether directory is already present in the system and also check how many new directories are required.

The output of the above code will be: 2

Since only tom & jerry directories need to be created newly.

 

Answer

class Tree

{

public:

    string name;

    vector<Tree*> list;

    Tree() {}

    Tree(string name)

    {

        this->name = name;

    }

};

Tree* getMatch(vector<Tree*> list, string name)

{

    if(list.empty()) return NULL;

    for(vector<Tree*>::iterator it = list.begin(); it != list.end(); ++it)

    {    

        if((*it)->name == name) {

            return *it;

        }

    }

    return NULL;

}

void addDir(Tree* t, char* dirname)

{

    char* back = strdup(dirname);

    char* next = strtok(back , "/");

    Tree* current = t;

    while(next != NULL)

    {

        Tree* chk = getMatch(current->list, next);

        if(chk == NULL) {

            Tree *newNode = new Tree(next);

            current->list.push_back(newNode);

            current = newNode;

        } else {

            current = chk;

        }

        next = strtok(NULL, "/");

    }

}

void main()

{

    int N;

    ofstream outfile("result.txt");

    scanf("%d",&N);

    for(int Ti=1; Ti<=N; Ti++)

    {

        int c1,c2;

        int count = 0;

        char dirname[105];

        Tree *fs = new Tree();

        fs->name = "/";

        scanf("%d %d",&c1,&c2);

        for(int i=0; i<c1; i++) {

            scanf("%s", dirname);

            addDir(fs, dirname);

        }

        for(int i=0; i<c2; i++) {

            scanf("%s", dirname);

            char* back = strdup(dirname);

            char* next = strtok(back , "/");

            Tree* current = fs;

            while(next != NULL)

            {

                Tree* chk = getMatch(current->list, next);

                if(chk == NULL) {

                    Tree *newNode = new Tree(next);

                    current->list.push_back(newNode);

                    current = newNode;

                    ++count;

                } else {

                    current = chk;

                }

                next = strtok(NULL, "/");

            }

        }

        outfile<<"Case #"<<Ti<<": "<<count<<endl;

    }

}

• When reading the first input of currently present directories, just create a tree (with multiple children). Make sure that you make the next child dir in the path as a children to the previous parent dir path
• After you read path given as present in the system into a tree, next is to read the list of paths for which presence need to verified + new directory need to be created.
• Even in this case do the same first step.  Just start creating the tree and ignore if directory already present. If not present, Just get the count of it which is not already present in the tree.
• Also after taking the count, again add the new dir to the actual tree.
• You are done with the solution!! :)