# "File Fix-it" challenge

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

for i in range(line_count_to_be_read):
# Get the Path line
# 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
total_testcases = int(line) # Number of Test Cases - Unused

case_no = 0

while True:

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()

• You should really comment your code. Now we will have to basically solve the problem for you before we even understand what your code does. That is a lot of work... Mar 14, 2011 at 10:46
• @Lennart Sorry, I should done it first. I hope these comments will help more.
– gkr
Mar 15, 2011 at 2:53

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.

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!).

• Thanks. Is doing functional way increase speed ?
– gkr
Mar 16, 2011 at 3:43
• @gkr: probably not, but it will increase your programming skills :-p Seriously, functional programming is a whole new world (and you don't need to use Haskell to apply its principles), it's not about speed (or not only) but about writing clear, modular code. Mar 16, 2011 at 9:38