"File Fix-it" challenge

Question

I'm learning Python and have found this problem from Google Code Jam:

How many mkdir commands does it take to construct a given directory tree:

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.

The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)

The next M lines each give the path of one directory that you want to create.

Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of mkdir you need.

I've solved it by writing code shown below, and it works correctly, but how can I make it faster?

import sys

def split_path(path_file,line_count_to_be_read):
    for i in range(line_count_to_be_read):
        # Get the Path line
        line = path_file.readline()
        # Skip the first slash
        line = line[1:]
        line = line.strip()
        splited = line.split('/')
        # make each subpaths from the source path
        for j in range(1,len(splited)+1):
            joined = "/".join(splited[:j])
            yield joined

def main():

    file_name = ""

    try:
        file_name = sys.argv[1]
    except IndexError:
        file_name = "A-small-practice.in"
        
    with open(file_name) as path_file:

        # skip the first line
        line = path_file.readline()
        total_testcases = int(line) # Number of Test Cases - Unused

        case_no = 0

        while True:
            line = path_file.readline()

            if not line:
                break

            # Get Existing path and New path count
            existing_count,new_count = line.split()
            existing_count = int(existing_count)
            new_count = int(new_count)        
            
            # Split Every Path and Make all Subpaths
            existing_paths = list(split_path(path_file,existing_count)) # Existing Subpaths                
            new_paths = list(split_path(path_file,new_count)) # New Subpaths

            # Remove all paths that is in Existing list from the New list
            new_mkdir_set = set(new_paths) - set(existing_paths)        

            case_no += 1
            
            # length of new_set contains number of needed mkdir(s)
            print "Case #{0}: {1}".format(case_no,len(new_mkdir_set))

if __name__ == '__main__':
    main()

Answer 1

Rather than using a list, consider approaching the problem from a graph perspective. Build a tree from the root directory using the existing directories, then traverse it with the new directories, and output a result line each time you have to add a leaf to the graph. This should be a little faster than comparing your two sets.

Answer 2

You can create a tree that you'd update on each iteration (while you calculate also the creation cost). You can do that with a simple nested dictionary. For example:

start with empty filesystem -> fs = {}, cost 0
"/1/2/3" -> fs = {1: {2: 3: {}}}, cost 3
"/1/2/4" -> fs = {1: {2: 3: {}, 4: {}}}, cost 1
"/5" -> fs = {1: {2: 3: {}, 4: {}}, 5: {}}, cost 1

= cost 5

You can use an algorithm with recursion (functional) or loops with inplace modifications (imperative). If you are learning I'd go for the first so you can apply some functional programming concepts (basically, one rule: don't update variables!).