google code jam exercise——File Fix It

前几天一直卡在Making Chess Board那道题上，目前还没有完全解决，打算先跳过。这次是Round 1B 2010的第一道题，还算比较简单，具体如下。

在Linux系统中，创建文件夹需要使用mkdir，如果父文件夹不存在则需要先创建父文件夹，题目先给出一组已经创建的文件路径，然后给出一组需要创建的文件路径，计算最少的mkdir的次数。当然，没有使用mkdir -p。

直接的想法就是，对已经创建的路径进行hash，放入dict，所以读取一个已经创建的路径的时候，先查看整个路径是否已经在dict中，如果不在，将其添加到dict中，剥掉最后一层，继续检查路径是否在dict中，如果在，则结束。

同样地，创建给出的文件路径时，先检查整个路径，然后一层一层的剥掉。如果不存在，则mkdir加1.

用什么做dict的key呢？如何剥掉最后一层呢？

这里使用os.path.girname(path)，返回path去掉最后一层的值，跟/有关，总是去掉最后一个/及其后面的字符串，到最后留下根目录/。所以一开始需要将/加入dict中。path始终是字符串，可以做dict的key。

代码如下：

#!/usr/bin/python
#encoding:UTF-8
#Filename:FileFixIt.py

import sys
import os

inname = "input.txt"
outname = "output.txt"
if len(sys.argv)>1:
    inname = sys.argv[1]
    outname = inname.rstrip(".in")
    outname = outname + ".out"
fin = open(inname,"r")
fout = open(outname,"w")

testCaseNum = int(fin.readline().rstrip("\n"))
caseNum = 0

for caseNum in xrange(1,testCaseNum+1):
    (createdNum,toCreateNum)=[int(val) for val in fin.readline().rstrip("\n").split()]
    createdDict = dict()
    createdDict["/"] = 1
    for i in range(createdNum):
        line = fin.readline().rstrip("\n")
        while(1):
            if line not in createdDict:
            #    print "not in dict",line
                createdDict[line] = 1
                line = os.path.dirname(line)
            else:
                break
    mkdirCnt = 0
    for i in xrange(toCreateNum):
        line = fin.readline().rstrip("\n")
        while(1):
            if line not in createdDict:
            #    print "not in dict",line
                createdDict[line] = 1
                line = os.path.dirname(line)
                mkdirCnt = mkdirCnt + 1
            else:
                break

    answer = "Case #%d: %d\n" %(caseNum,mkdirCnt)
    fout.write(answer)

fin.close()
fout.close()

最后small和large case测试都通过了。