# Sorting a list of numbers, each with a character label

I am working on a project that requires me to modify an input list as follows:

INPUT: List of numbers, each tagged with a label i.e. [[2, 'a'], [3, 'b'], [1, 'c'], ...]

DESIRED OUTPUT: Sort the list and grab the elements with the highest numerical component, store them in another list, and maybe rerun the function on the new list. This is an order determination scheme based on players rolling dice.

I have created the following code in Python 3.7 and it works just fine for me. I am curious to see if there are more clever ways to arrive at the same output. For some reason this took me about two hours to come up with (I am learning from scratch).

list = [[1,'a'],[3,'b'],[7,'c'],[6,'d'],[4,'e'],[1,'f'],[7,'g'],[4,'h'],[6,'i']]

def comp(list):

new_list = []
list.sort(reverse = True)
for y in range(1, len(list)):
if list[0][0] > list[y][0]:
new_list.append(list[y])
top_rolls = [x for x in list if x not in new_list]
return(top_rolls)

• I'd like to point out that "maybe" has no place in a proper requirements statement. – Reinderien Dec 21 '18 at 15:50
• Thanks Reinderien, I was simply writing shorthand instead of saying that I would like to rerun the function if the new list contains more than one element. I understand the logic behind your statement. – JacobCheverie Dec 21 '18 at 16:53

## 3 Answers

Names

Using the name list for a variable is legal but usually avoided because it hides the list builtin. The name lst would be a better candidate.

The function name comp could be improved as well. Maybe get_best_elements (even though I am not fully convinced).

Tests

Before going further, it may be wise to add tests so that you can easily be sure that we do not break anything.

A proper solution would involve a unit-test framework but for the time being, we can go for the simple:

TESTS = (
([], []),
([[1,'a']], [[1, 'a']]),
([[1,'a'], [1,'a'], [1,'a'], [1,'a']], [[1,'a'], [1,'a'], [1,'a'], [1,'a']]),
([[1,'a'], [1,'b'], [1,'c'], [1,'d']], [[1,'d'], [1,'c'], [1,'b'], [1,'a']]),
([[1,'a'],[3,'b'],[7,'c'],[6,'d'],[4,'e'],[1,'f'],[7,'g'],[4,'h'],[6,'i']], [[7, 'g'], [7, 'c']]),
([[1,'a'],[3,'b'],[7,'c'],[6,'d'],[4,'e'],[1,'f'],[4,'h'],[6,'i']], [[7, 'c']]),
)

for test_input, expected_output in TESTS:
output = get_best_elements(test_input)
assert output == expected_output
print("OK")


Style

Parenthesis are not required in the return statements. Also, the temporary variable is not really required.

List comprehension

The new_list could be defined with a list comprehension.

def get_best_elements(lst):
lst.sort(reverse = True)
new_lst = [lst[y] for y in range(1, len(lst)) if lst[0][0] > lst[y][0]]
return [x for x in lst if x not in new_lst]


Loop like a native

I highly recommend Ned Batchelder's talk "Loop like a native" about iterators. One of the most simple take away is that whenever you're doing range(len(lst)), you can probably do things in a better way: more concise, clearer and more efficient.

In our case, we'd have something like:

def get_best_elements(lst):
lst.sort(reverse = True)
new_lst = [e for e in lst if e[0] < lst[0][0]]
return [x for x in lst if x not in new_lst]


Another approach

The last list comprehension can be quite expensive because for each element x, you may perform a look-up in the list. This can lead to a O(n²) behavior.

Instead of filtering out elements that do not correspond to the biggest number, we could just keep the one that do correspond to the biggest number.

def get_best_elements(lst):
if not lst:
return []
lst.sort(reverse = True)
big_n = lst[0][0]
return [x for x in lst if x[0] == big_n]


Sort a smaller numbers of elements

You could use max to get big_n.

Also, we could perform the sorting on the filtered list so that we have fewer elements to sort:

def get_best_elements(lst):
if not lst:
return []
big_n = max(lst)[0]
return list(sorted((x for x in lst if x[0] == big_n), reverse=True))


You could simplify by directly making a list with the highest scores instead of creating and subtracting another list containing what you don't want :

def comp(rolls):
top_rolls = []
rolls.sort(reverse=True)
for y in range(len(rolls)):
if rolls[0][0] == rolls[y][0]:
top_rolls.append(rolls[y])
return top_rolls


Once you've done that it becomes easy to fit it in a list comprehension:

def comp(list):
rolls.sort(reverse=True)
top_rolls = [rolls[y] for y in range(len(rolls)) if rolls[0][0] == rolls[y][0]]
return top_rolls


Or even shorter:

def comp(list):
list.sort(reverse=True)
return [rolls[y] for y in range(len(rolls)) if rolls[0][0] == rolls[y][0]]

• That's great, thank you. I don't know why I created a list of things that I don't want just to subtract it from the overall list. Your method is much more concise. – JacobCheverie Dec 21 '18 at 16:55
• Don't name an argument list. That will shadow the built-in type also called list. – Reinderien Dec 21 '18 at 18:00
• I am renaming everything after I am finished, I am more concerned about the appropriate syntax for now. – JacobCheverie Dec 21 '18 at 18:45

Based on your stated use case:

I would like to rerun the function if the new list contains more than one element.

you don't even need to return a list; just return the highest element's roll and name, which can be unpacked by the caller as a 2-tuple:

def comp(rolls):
return max(rolls)


That said, you haven't explicitly stated how to resolve ties with rolls of the same value. That will affect this solution.

• The max function on it's own will only return one players roll, so if there is a tie it will not be handled. Working with a simplification similar to one that @Comte_Zero provided, I am handling the case of a tie separately. I am sure that code could use some enhancing as well, I am just trying to get the basic form nailed down and make edits later. – JacobCheverie Dec 21 '18 at 18:47
• I'd propose that tie resolution should be built into this function. – Reinderien Dec 21 '18 at 19:12