Count the number of mkdir commands required

http://code.google.com/codejam/contest/635101/dashboard#s=p0
To create a directory, you can use the mkdir command. You specify a path, and then mkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the “/home/gcj/finals” and “/home/gcj/quals” directories from scratch, you would need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?

Input
======
0 2
/home/gcj/finals
/home/gcj/quals

Output
======
4

Input
=======
2 1
/chicken
/chicken/egg
/chicken

Output
======
0

Input
=======
1 3
/a
/a/b
/a/c
/b/b

Output
======
4

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Text.RegularExpressions;
using System.Collections;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(@"C:\Users\saikatd\input.txt");
            int i = 0;
            int existingPath = 0;
            int newPath = 0;
            ArrayList paths = new ArrayList();
            for (string str = sr.ReadLine(); str != null; str = sr.ReadLine())
            {
                if (i == 0)
                {
                    //Read the first line
                    Regex reg = new Regex(" ");
                    string[] numStr = reg.Split(str);
                    existingPath = int.Parse(numStr[0]);
                    newPath = int.Parse(numStr[1]);
                    i++;
                }
                else
                {
                    //Read other lines
                    paths.Add(str);
                }
            }
            sr.Close();            
            int k = 0, count = 0;
            //Loop for new directory structure
            for (i = existingPath; i < paths.Count; i++, k++)
            {
                Regex reg = new Regex("/");
                string[] newStructure = reg.Split(paths[i].ToString());
                //Compare with existing directory structure
                int maxMatchCount = 0;
                for (int j = 0; j < existingPath + k; j++)
                {
                    string[] existingStructure = reg.Split(paths[j].ToString());
                    //Check for the max length match
                    int tempCount = 0;
                    for (int p = 1; p < Math.Min(newStructure.Length, existingStructure.Length); p++)
                    {
                        if (newStructure[p] == existingStructure[p])
                        {
                            tempCount++;
                        }
                        else
                        {
                            break;
                        }
                    }
                    if(maxMatchCount < tempCount)
                    {
                        maxMatchCount = tempCount;
                    }
                }
                count = count + (newStructure.Length - maxMatchCount - 1);
            }
            Console.WriteLine("Number of mkdir commands required = " + count);
        }
    }
}

Input
======
3 3
/a/b/c
/a/d/e
/a/f/g
/a/b/c/d
/a/f/g/h
/b/c/d

Output
=======
Number of mkdir commands required = 5
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s