CodeEval Find the highest score

Given the representation of a flattened table of scores where the rows represents artists and columns painting styles, give back a string containing the highest score for each style. This is a minimal description of the CodeEval problem #208, and here I am showing my Python 3 solution.

I converted the provides samples in test cases:
def test_provided_1(self):
    self.assertEqual('100 250 150', solution('72 64 150 | 100 18 33 | 13 250 -6'))

def test_provided_2(self):
    self.assertEqual('13 25 70 44', solution('10 25 -30 44 | 5 16 70 8 | 13 1 31 12'))

def test_provided_3(self):
    self.assertEqual('100 200 300 400 500', solution('100 6 300 20 10 | 5 200 6 9 500 | 1 10 3 400 143'))
Then I divided the problem in for steps.

1) Convert the input line in an integer table of scores, where each row represents an artist and each column a style.
2) Rearrange the table so that it can easily be scanned by style.
3) For each style, get its maximum value.
4) Convert the maximum collection in a string and return it.

Authors table

Let's use a list comprehension:
authors = [[int(score) for score in author.split()] for author in line.split('|')]
If your reaction is "what?!", here is the same thing unwinded:
authors = [] # 1
for author in line.split('|'): # 2
    row = [] # 3
    for score in author.split(): # 4
        row.append(int(score)) # 5
    authors.append(row) # 6
1) Create an empty list. This will be our resulting table.
2) Split the input line, using the pipe as separator, and loop on each resulting element.
3) Create an empty list, the current raw we'll fill with scores and push to the table.
4) Split the current section of the input line using the default blank character as separator, and loop on each element, a string that represents the current score.
5) Convert the current score to an integer and push it in the row.
6) Push the row in the authors table.

In a way or the other now we have our table of scores. Given the first test case, author is this list of lists:
[[72, 64, 150], [100, 18, 33], [13, 250, -6]]

Style table

The point of this step is simplify the next one. We could happly skip it, but it improves so much the resulting code readability that we don't really want to miss it.
Besides, here we have a way to put the handy * (star, asterisk, unpack) list operator and the zip built-in function at work.

We want to traspose our table, so that we have styles in the rows. Done in a jiffy
styles = zip(*authors)
The star operator unpacks the authors list, passing its rows, each of them by requirement is an equally sized list, to the zip function.
Zip packs back (for a formal description of its job, see the online Python documentation) the lists, putting in its first element all the first elements of the input lists, down to the last elements.

The result is that in styles we have something that could be seen in this way
[(72, 100, 13), (64, 18, 250), (150, 33, -6)]
(I avoid the details because here I just want to get the problem solved. Please, check about Python iterators and iterables to have more information on what is really going on here.)
Notice that rows are now represented by tuples and not as lists as in the original table. Not a problem, since we don't want to change them in any way.

Max for style

To perform this step I am going to use the built-in functions max(), that returns the largest value among the passed ones, and map(), works like zip, but applying a function to the input data. Putting them together I get:
result = map(max, styles)
If I print result for the first test case, I should get something like
[100, 250, 150]
That is almost the expected output, I only have to format it in the right way.

Let's say we don't want to transpose the table, as done in the previous step. Maybe we want to solve a more complex problem, where tables could be huge, and we don't want to pay the cost of that job. In that case we can fall back to less readable but more efficient code like this:
size = len(table[0]) # 1
result = [-1000 for score in range(size)] # 2
for row in table: # 3
    for i in range(size): # 4
        if row[i] > result[i]:
            result[i] = row[i]
1. By requirement, all rows have the same size.
2. Another requirement is that the lowest score is -1000, I shouldn't use it as a magic number, I know. However, I initialize result to have each element set to the lowest possible value.
3. Scan all the rows.
4. For each element in the row, compare it against the current result for that style, if bigger store it as candidate result.

It should be clear why we prefer the write the map-max version instead of this one, if we don't really have to.

Formatting the result

Usual stuff, convert the solution to a string of blank separated values. Here there is just a minor tweak:
return ' '.join(map(str, result))
I can't join directly on result, because it contains integers, not strings! So, I map result using the str() function that converts its input to string. Done.

Being CodeEval happy with my solution, I pushed test cases and python function source code to GitHub.

No comments:

Post a Comment