CodeEval Football

We have in input a string that represents a map between countries and the most liked football team in there. Both countries and teams are represented by numbers, the first ones implicitly, by their position, that we should assume 1-based. Our job is to reverse the presentation, giving in output a string in which teams are the keys and countries the values. Both should be sorted in natural order (as numbers, not strings).
Having chosen to use Python 3 as implementation language, this CodeEval problem #230 asks for working with a dictionary.

Let's have a look at the test cases. I found that the ordering requirement was not clarified enough in the provided samples, so I added one test case more:
def test_provided_1(self):
    self.assertEqual('1:1,2,3; 2:1; 3:1,2; 4:1,3;', solution('1 2 3 4 | 3 1 | 4 1'))

def test_provided_2(self):
    self.assertEqual('11:1; 19:1,2; 21:2; 23:2; 29:3; 31:3; 39:3;', solution('19 11 | 19 21 23 | 31 39 29'))

def test_key_numbers(self):
    self.assertEqual('1:1,2,3; 2:2; 4:3; 10:1;', solution('1 10 | 2 1 | 4 1'))
We see how the input line is formatted, and how we have to format the output. The third test case shows that the team "10" has to be placed in the output after the team "4", being number 4 less than 10, and not between "1" and "2" as the sorting in lexicographical order would do.

I divided my solution in two steps.

Dictionary transposition

I have in input a dictionary that maps each country in a list of team, I want to get a dictionary team to countries. Let's build it:
def solution(line):
    teams = {}
    for country, clubs in enumerate(line.split(' | '), start=1): # 1
        for team in map(int, clubs.split()): # 2
            teams.setdefault(team, []).append(str(country)) # 3

# ...
1) The input gives me the country number only implicitly, I make it explicit by using the built-in python function enumerate() that returns a tuple containing a count (that I force to be 1-based by the parameter start) and a value from the passed iterable. As iterable I have passed to enumerate() the input string, as resulting from splitting it on ' | ', that's it, a list of strings containing a space separated string representing the most cheered teams (I called them "clubs" to avoid name clashes) in that country.
2) I split the clubs string, I convert on the fly, by map(), each resulting value to an integer, and I loop on them.
3) Finally, push a value, stored in country, to the teams dictionary for the key stored in club. However, I should be careful not to append the value on nothing. Meaning I need to explicitly consider the case the current team is not already in the dictionary. This is done by a call to setdefault(), that returns the value associated to the passed key if it exists, otherwise create a new entry for it, with the other parameter as its value (by default None, I have astutely passed an empty list instead).

Formatting the dictionary

I have the data in the teams dictionary, I just need to create a string out of it, respecting the required format. I did it in this way:
result = ["{}:{};".format(key, ",".join(teams[key])) for key in sorted(teams.keys())]
return ' '.join(result)
To keep the code compact, I did large part of the job in a list comprehension, and then I simply joined each element on a blank string. But let's how I built up the list.

Firstly, look to the right. I have got the keys() from the teams dict, I sorted them, as required - notice that in (2) above I converted them to integers, so the order is the expected one - and I loop on them.
Now on the left. Each element in the list is a string in the format "{}:{};" where the curly brackets are parameters received from the for loop on the right. The first parameter is easy, just the key as retrieved from the dictionary, namely a team number. The second one in a string generated by joining on a comma the value associated to the key on the dictionary. That is the list of countries for the given team.

As a minor point, there is no need to sort the countries, since we have pushed them in the map respecting the order given implicitly in input.

Solution accepted by CodeEval, code pushed to GitHub, both test cases and python script.

No comments:

Post a Comment