Erdos Numbers/임인택

# -*- coding: UTF-8 -*-
import unittest

def readFile(fileName):
        f = file(fileName, "r")
        lines = []
        line = f.readline()
        while line!='' :
                lines.append(line)
                line = f.readline()

        f.close()
        return lines

def extractInfo(lines):
        idx = 0
        sNum = int(lines[idx])
        idx += 1

        sInfo = lines[idx].split()
        nPaper = int(sInfo[0])
        nPerson = int(sInfo[1])

        return sNum, nPaper, nPerson

def stripWhiteSpaces(str):
        return str.lstrip().rstrip()

def extractNames(str):
        parts = str.split(':')
        names = parts[0].split('.,')

        for i in range(0, len(names)):
                dot = ''
                if i < len(names)-1 :
                        dot = '.'
                names[i] = stripWhiteSpaces(names[i]+dot)

        return names

def erdosNumber(fileName):
        erdosName = 'Erdos, P.'

        lines = readFile(fileName)
        sNum, nPaper, nPerson = extractInfo(lines)

        allNames = {}
        allNames[erdosName] = 0

        for i in range(2, 2+nPaper):
                names = extractNames(lines[i])

                erdosFriend = None
                minErdosNum = -1

                for name in names:
                        if allNames.has_key(name) and (minErdosNum == -1 or minErdosNum>allNames[name]) :
                                minErdosNum = allNames[name]
                                erdosFriend = name

                        if name == erdosName: # �~Y�~]� �~S� �~B��~^~L�~S�
                                erdosFriend = erdosName
                                break

                if erdosFriend == erdosName:
                        erdosCoAuthor(allNames, names, erdosName)
                elif erdosFriend == None:
                        erdosNotRelated(allNames, names)
                else :
                        erdosCoAuthorCoAuthor(allNames, names, erdosFriend)

        printResults(lines[2+nPaper:], allNames)
        return allNames

def printResults(names, allNames):
        for name in names:
                name = stripWhiteSpaces(name)
                print name,
                if allNames[name] == -1 :
                        print 'infinite'
                else:
                        print allNames[name]

def erdosCoAuthor(allNames, names, erdosName):
        for name in names :
                if name != erdosName:
                        allNames[name] = 1

def erdosNotRelated(allNames, names):
        for name in names:
                allNames[name] = -1

def erdosCoAuthorCoAuthor(allNames, names, erdosFriend):
        for name in names:
                if name != erdosFriend :
                        allNames[name] = allNames[erdosFriend] + 1


class TestErdos(unittest.TestCase):
        def setUp(self):
                self.lines = readFile("sample.txt")
        def testStripstring(self):
                self.assertEqual('aaa', stripWhiteSpaces(' aaa  '))
                self.assertEqual('bbb', stripWhiteSpaces('  bbb'))
                self.assertEqual('ccc', stripWhiteSpaces('ccc   '))

        def testInputInfo(self):
                sNum, nPaper, nPerson = extractInfo(self.lines)
                self.assertEqual(1, sNum)
                self.assertEqual(4, nPaper)
                self.assertEqual(3, nPerson)

        def testAllNames(self):
                sNum, nPaper, nPerson = extractInfo(self.lines)

                allNames = {}

                for i in range(2, 2+nPaper):
                        names = extractNames(self.lines[i])
                        for name in names:
                                allNames[name] = 0

                self.assertEqual(True, allNames.has_key('Smith, M.N.'))
                self.assertEqual(True, allNames.has_key('Martin, G.'))
                self.assertEqual(True, allNames.has_key('Erdos, P.'))
                self.assertEqual(True, allNames.has_key('Reisig, W.'))
                self.assertEqual(True, allNames.has_key('Chen, X.'))
                self.assertEqual(True, allNames.has_key('Jablonski, T.'))
                self.assertEqual(True, allNames.has_key('Hsueh, Z.'))

        def testErdosNum(self):
                sNum, nPaper, nPerson = extractInfo(self.lines)
                erdosNum = erdosNumber("sample.txt")

                self.assertEqual(1, erdosNum[stripWhiteSpaces(self.lines[6])])
                self.assertEqual(-1, erdosNum[stripWhiteSpaces(self.lines[7])])
                self.assertEqual(2, erdosNum[stripWhiteSpaces(self.lines[8])])



if __name__=='__main__':
        #unittest.main(argv=('','-v'))
        erdosNumber("sample.txt")


----
ErdosNumbers