AIO programming challenge - Friendlist - Who has the most friends?

Question

I attempted this sample question from the Australia Infomatics Competition. TL;DR - Each line of input contains two numbers, representing a mutual friendship relationship. The output needs to be the number representing the person who has the most friends (and if there is a tie, list them in numerical order).

Exact Words:

Input

The first line of input will contain the integer f, 1 <= f <= 1,000,000.

Each of the following f lines will be of the form a b, where a and b are different player IDs. This indicates that player #a is friends with player #b, and vice versa. All player IDs are integers between 0 and 1000 inclusive.

(Note that no friendship will ever be listed twice: for example, if "2 5" is one of the lines in the input, then neither "2 5" nor "5 2" will appear anywhere else in the input)

Output

Output should consist of all the player IDs that are tied for biggest friendlist. These IDs should be given in ascending order.

Sample Input:

6

5 6

0 1

1 4

5 4

1 2

4 0

Sample Output:

1

4

Here is my current code (in Python 2.6.6 as per the comp's requirements):

fileInput = open("listin.txt", "r")
InputList = map(int, fileInput.read().split())
fileInput.close()

input1 = InputList[1:]
friends_dict = {}

for each in xrange(int(InputList[0])+1):
    friends_dict[each] = input1.count(each)        

highest = max(friends_dict.values())

biggest_nums = sorted([k for k, v in friends_dict.items() if v == highest])

Output = "\n".join([str(e) for e in biggest_nums])

fileOutput = open("listout.txt", "w")
fileOutput.write(str(Output))
fileOutput.close()

My Approach

1. First read in the whole file at once (is this a good idea? would it be better to do line by line?)

2. Count all occurrences of a friend ID and then assign it to a spot in the dictionary (thus works in theory as if A is friends with B and A is friends with C, if we were to count them, A appears 2x and that is how many friends A has, likewise with B = 1 and C = 1)

3. Find the maximum score(s)

The code seems to work alright (although the test machine did say one case failed - it works for the smaple input and some cases I made up, but I think that there are still flaws in the method) but the main issue seems to be that it is too slow. Over half the trial cases failed due to going over the 1 sec limit. I am open to any suggestions or even a new algorithm is general and suggestions to my coding in general.

I have been at this for a while now and I can't think of anything else to shave off. I suspect the bottleneck may be at the end which is simply finding the largest friend counts and ordering them.

I would appreciate any feedback whatsoever, be it from my coding practices to the implementation of or the actual algorithm. I would really like to be able to produce a faster and more efficient version of this code.

Answer 1

Take a look at my snippet which passes all the test cases. First thing you can improve is both reading and incrementing (in the same loop) number of friendships for each id. Try to not use also count method of the list, it also searches through the whole list every time.

#!/usr/bin/python
friendlist = [0] * 1001

with open("listin.txt", "r") as listin:
    for i, line in enumerate(listin):
        if i > 0:
            a,b = line.split()
            friendlist[int(a)] += 1
            friendlist[int(b)] += 1

max_friends_num = max(friendlist)
listout = open("listout.txt", "w")
for id,val in enumerate(friendlist):
    if val == max_friends_num:
        listout.write(str(id)+'\n')
listout.close()

Best regards!