5
ORGANIZING VALUES USING LISTS

We’ve seen that we can use strings to work with a sequence of characters. In this chapter, we’ll learn about lists, which help us work with sequences of other types of values, such as integers and floats. We’ll also learn that we can nest lists inside of lists, which lets us work with grids of data.

We’ll solve three problems using lists: finding the smallest neighborhood of a collection of villages, determining whether sufficient money has been raised for a school trip, and calculating the number of bonuses offered by a bakery.

Problem #11: Village Neighborhood

In this problem, we’re going to find the size of the smallest neighborhood of a collection of villages. We’ll find it helpful to store all of the neighborhood sizes. We might have as many as 100 villages, though, and using a separate variable for each village would be a nightmare. We’ll see that lists allow us to aggregate what would otherwise be separate variables into one collection. We’ll also learn about Python’s powerful list operations for modifying, searching, and sorting a list.

This is DMOJ problem ccc18s1.

The Challenge

There are n villages located at distinct points on a straight road. Each village is represented by an integer that indicates its position on the road.

A village’s left neighbor is the village with the next smallest position; a village’s right neighbor is the village with the next biggest position. The neighborhood of a village consists of half the space between that village and its left neighbor, plus half the space between that village and its right neighbor. For example, if there’s a village at position 10, with its left neighbor at position 6 and its right neighbor at position 15, then this village’s neighborhood starts from position 8 (halfway between 6 and 10) and ends at position 12.5 (halfway between 10 and 15).

The leftmost and rightmost villages have only one neighbor, so the definition of a neighborhood doesn’t make sense for them. We’ll ignore the neighborhoods of those two villages in this problem.

The size of a neighborhood is calculated as the neighborhood’s rightmost position minus the neighborhood’s leftmost position. For example, the neighborhood that goes from 8 to 12.5 has size 12.5 – 8 = 4.5.

Determine the size of the smallest neighborhood.

Input

The input consists of the following lines:

• A line containing integer n, the number of villages. n is between 3 and 100.
• n lines, each of which gives the position of a village. Each position is an integer between –1,000,000,000 and 1,000,000,000. The positions need not come in order from left to right; the neighbor of a village could be anywhere in these lines.

Output

Output the size of the smallest neighborhood. Include exactly one digit after the decimal point.

Why Lists?

As part of reading the input, we’ll need to read n integers (the integers that represent the positions of the villages). We dealt with this once already when solving Data Plan in Chapter 3. There, we used a range for loop to loop exactly n times. We’ll do that here, too.

There’s one crucial difference between Data Plan and Village Neighborhood. In Data Plan, we read an integer, used it, and never referred to it again. We didn’t need to keep it around. But in Village Neighborhood, it’s not enough to see each integer just once. A village’s neighborhood depends on its left and right neighbors. Without access to those neighbors, we can’t calculate the size of the village’s neighborhood. We need to store all of the village positions for later use.

For an example of why we need to store all of the village positions, consider this test case:

6
20
50
4
19
15
1

There are six villages here. To find the size of a village’s neighborhood, we need that village’s left and right neighbors.

The first village in the input is at position 20. What’s the size of that village’s neighborhood? To answer that, we need access to all of the village positions so that we can find its left and right neighbors. Scanning through the positions, you can identify that the left neighbor is at position 19 and the right neighbor is at position 50. The size of this village’s neighborhood is therefore (20 – 19)/2 + (50 – 20)/2 = 15.5.

The second village in the input is at position 50. What’s the size of that village’s neighborhood? Again, we need to look through the positions to figure it out. This village happens to be the rightmost one, so we ignore this village’s neighborhood.

The third village in the input is at position 4. The left neighbor is at position 1, and the right neighbor is at position 15, so the size of this village’s neighborhood is (4 – 1)/2 + (15 – 4)/2 = 7.

The fourth village in the input is at position 19. The left neighbor is at position 15, and the right neighbor is at position 20, so the size of this village’s neighborhood is (19 – 15)/2 + (20 – 19)/2 = 2.5.

The only remaining village that we need to consider is at position 15. If you calculate its neighborhood size, you should get an answer of 7.5.

Comparing all of the neighborhood sizes that we calculated, we see that the minimum—and the correct answer for this test case—is 2.5.

We need a way to store all of the village positions so that we can find the neighbors of each village. A string won’t help, because strings store characters, not integers. Python lists to the rescue!

Lists

A list is a Python type that stores a sequence of values. (You’ll sometimes see list values referred to as elements.) We use opening and closing square brackets to delimit the list.

We can store only characters in strings, but we can store any type of value in lists. This list of integers holds the village positions from the prior section.

>>> [20, 50, 4, 19, 15, 1]
[20, 50, 4, 19, 15, 1]

Here’s a list of strings:

>>> ['one', 'two', 'hello']
['one', 'two', 'hello']

We can even create a list whose values are of different types:

>>> ['hello', 50, 365.25]
['hello', 50, 365.25]

Much of what you learned about strings applies to lists as well. For example, lists support the + operator for concatenation and the * operator for replication:

>>> [1, 2, 3] + [4, 5, 6]
[1, 2, 3, 4, 5, 6]
>>> [1, 2, 3] * 4
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]

We even have the in operator, which tells us whether a value is in a list or not:

>>> 'one' in ['one', 'two', 'hello']
True
>>> 'n' in ['one', 'two', 'three']
False

And we have the len function to give us the length of a list:

>>> len(['one', 'two', 'hello'])
3

A list is a sequence, and we can use a for loop to loop through its values:

>>> for value in [20, 50, 4, 19, 15, 1]:
...     print(value)
...
20
50
4
19
15
1

We can make variables refer to lists, just as we make them refer to strings, integers, and floats. Let’s make two variables refer to lists and then concatenate them to produce a new list.

>>> lst1 = [1, 2, 3]
>>> lst2 = [4, 5, 6]
>>> lst1 + lst2
[1, 2, 3, 4, 5, 6]

While we displayed the concatenated list, we did not store it, as we can see by looking at the lists again:

>>> lst1
[1, 2, 3]
>>> lst2
[4, 5, 6]

To make a variable refer to the concatenated list, we use assignment:

>>> lst3 = lst1 + lst2
>>> lst3
[1, 2, 3, 4, 5, 6]

Names like lst, lst1, and lst2 can be used when there’s no need to be more specific about what a list contains.

But don’t use list itself as a variable name. It’s already a name that we can use to convert a sequence to a list:

>>> list('abcde')
['a', 'b', 'c', 'd', 'e']

If you make a variable named list, you’ll lose this valuable behavior, and you’ll confuse readers who will expect list not to be tampered with.

Finally, lists support indexing and slicing. Indexing returns a single value, and slicing returns a list of values:

>>> lst = [50, 30, 81, 40]
>>> lst[1]
30
>>> lst[-2]
81
>>> lst[1:3]
[30, 81]

If we have a list of strings, we can access one of its string’s characters by indexing twice, first to select a string and then to select a character:

>>> lst = ['one', 'two', 'hello']
>>> lst[2]
'hello'
>>> lst[2][1]
'e'

List Mutability

Strings are immutable, which means they cannot be modified. When it looks like we’re changing a string (for example, using string concatenation), we’re really creating a new string, not modifying one that already exists.

Lists, on the other hand, are mutable, which means they can be modified.

We can observe this difference by using indexing. If we try to change a character of a string, we get an error:

>>> s = 'hello'
>>> s[0] = 'j'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

The error message says that strings don’t support item assignment, which just means that we can’t change their characters.

But because lists are mutable, we can change their values:

>>> lst = ['h', 'e', 'l', 'l', 'o']
>>> lst
['h', 'e', 'l', 'l', 'o']
>>> lst[0] = 'j'
>>> lst
['j', 'e', 'l', 'l', 'o']
>>> lst[2] = 'x'
>>> lst
['j', 'e', 'x', 'l', 'o']

Without a precise understanding of the assignment statement, mutability can lead to seemingly bewildering behavior. Here’s an example:

   >>> x = [1, 2, 3, 4, 5]
❶ >>> y = x
   >>> x[0] = 99
   >>> x
   [99, 2, 3, 4, 5]

No surprises yet. But you might be surprised by this:

>>> y
[99, 2, 3, 4, 5]

How did the 99 get into y like that?

When we assign x to y ❶, y is set to refer to the same list as x. The assignment statement doesn’t copy the list. There’s only one list, and it happens to have two names (or aliases) that refer to it. So if we make a change to that list, we see that change whether we refer to the list by x or y.

Mutability is useful because it directly models what we might want to do with the values in a list. If we want to change a value, we just change it. Without mutability, changing one value isn’t possible. We’d have to create a new list that was the same as the old list except for the value that we wanted to change. That would work, but it is a roundabout and less transparent way of changing a value.

If you really do want a copy of a list, not just another name for it, you can use slicing. Leave out both the start and end indices, which results in a copy of the entire list:

>>> x = [1, 2, 3, 4, 5]
>>> y = x[:]
>>> x[0] = 99
>>> x
[99, 2, 3, 4, 5]
>>> y
[1, 2, 3, 4, 5]

Observe this time that the y list didn’t change when the x list changed. They’re separate lists.

Learning About Methods

Like strings, lists have many useful methods. I’ll show you some of them in the next section, but first I’d like to show you how you can learn about methods on your own.

You can use Python’s dir function to get a list of methods for a particular type. Just call dir with a value as the argument, and you’ll get the methods for the type of that value.

Here’s what we get when we call dir using a string value as the argument:

>>> dir('')
['__add__', '__class__', '__contains__', '__delattr__',
<more stuff with underscores>
'capitalize', 'casefold', 'center', 'count', 'encode',
'endswith', 'expandtabs', 'find', 'format',
'format_map', 'index', 'isalnum', 'isalpha', 'isascii',
'isdecimal', 'isdigit', 'isidentifier', 'islower',
'isnumeric', 'isprintable', 'isspace', 'istitle',
'isupper', 'join', 'ljust', 'lower', 'lstrip',
'maketrans', 'partition', 'replace', 'rfind', 'rindex',
'rjust', 'rpartition', 'rsplit', 'rstrip', 'split',
'splitlines', 'startswith', 'strip', 'swapcase', 'title',
'translate', 'upper', 'zfill']

Notice that we called dir with an empty string. We could have called dir with any string value; the empty string is just fastest to type.

Ignore the names at the top with underscores; those names are for Python’s internal use and not generally of interest to programmers. The rest of the names are string methods that you can call. In that list, you’ll find string methods that you already know, such as isupper and count, and many others that we haven’t come across yet.

To learn how to use a method, you can use the name of that method in a call to help. Here’s the help we get on the string count method:

>>> help(''.count)
Help on built-in function count:

count(...) method of builtins.str instance
  ❶ S.count(sub[, start[, end]]) -> int

     Return the number of non-overlapping occurrences of
     substring sub in string S[start:end].  Optional
     arguments start and end are interpreted as in
     slice notation.

The help tells us how to call the method ❶.

Square brackets identify optional arguments. You would use start and end if you wanted to count the occurrences of sub within only a slice of the string.

It’s worth browsing the list of methods to check whether one is available to help with your current programming task. Even if you’ve used a method before, looking at the help can show you features that you didn’t know existed!

To see which list methods are available, call dir([]). To learn about them, call help([].xxx), where xxx is the name of a list method.

List Methods

Time to make progress on Village Neighborhood. I can think of two operations on a list that would help us solve it.

First, adding to a list. We’ll start off with no village positions and read them one at a time from the input. We therefore need a way to add each of these positions to a growing list: first the list will have nothing, and then it will have one village position in it, then two, and so on.

Second, sorting a list. Once we’ve read in the village positions, we need to find the smallest neighborhood. This involves looking at each village position and the distance to its left and right neighbors. The village positions could come in any order, so in general it’s not easy to find the neighbors of a given village. Think back to the work we did in “Why Lists?” in this chapter. For each village, we had to scan the entire list to find its neighbors. It’d be so much easier if we had the villages ordered by position. Then we’d know exactly where the neighbors were: they’d be just to the left and just to the right of a village.

For example, here are our sample villages in the order that we read them:

20 50 4 19 15 1

That’s a mess! On a real street, they’d come in order of position, like this:

1 4 15 19 20 50

Want the neighbors of the village at position 4? Just look immediately to the left and immediately to the right: 1 and 15. The neighbors of the village at 15? Boom, they’re right there—4 and 19. No more searching all over the place. We’ll sort the list of village positions to simplify our code.

We can add to a list using the append method and sort a list using the sort method. We’ll learn these two methods, and a few others that you’ll likely find useful as you continue working with lists, and then we’ll come back to solve Village Neighborhood.

Adding to a List

The append method appends to a list, which means that it adds a value to the end of the values already there. Here’s append adding three village positions to an initially empty list:

>>> positions = []
>>> positions.append(20)
>>> positions
[20]
>>> positions.append(50)
>>> positions
[20, 50]
>>> positions.append(4)
>>> positions
[20, 50, 4]

Notice that we’re using append without using an assignment statement. The append method doesn’t return a list; it modifies an existing list.

It’s a common error to use an assignment statement with a method that changes a list. Making this error results in the list being lost, like this:

>>> positions
[20, 50, 4]
>>> positions = positions.append(19)
>>> positions

Nothing is there! Technically, positions now refers to a None value; you can see that using print:

>>> print(positions)
None

The None value is used to convey that no information is available. That’s absolutely not expected here—we wanted our four village positions!—but we’ve lost the list through an errant assignment statement.

If your list is disappearing or you’re getting error messages related to the None value, make sure you’re not using an assignment statement with a method that simply modifies a list.

The extend method is related to append. You use extend whenever you’d like to concatenate a list (not a single value) to the end of an existing list. Here’s an example:

>>> lst1 = [1, 2, 3]
>>> lst2 = [4, 5, 6]
>>> lst1.extend(lst2)
>>> lst1
[1, 2, 3, 4, 5, 6]
>>> lst2
[4, 5, 6]

If you want to insert into a list at a position other than its end, you can use the insert method. It takes an index and a value and inserts the value at the index:

>>> lst = [10, 20, 30, 40]
>>> lst.insert(1, 99)
>>> lst
[10, 99, 20, 30, 40]

Sorting a List

The sort method sorts a list, putting its values in order. If we call it with no arguments, it sorts from smallest to largest:

>>> positions = [20, 50, 4, 19, 15, 1]
>>> positions.sort()
>>> positions
[1, 4, 15, 19, 20, 50]

If we call it with a reverse argument of value True, it sorts from largest to smallest:

>>> positions.sort(reverse=True)
>>> positions
[50, 20, 19, 15, 4, 1]

The syntax that I’ve used, reverse=True, is new. Based on how we’ve called methods and functions to this point in the book, you might expect that True by itself would work. But no: sort requires the whole reverse=True to be there, for reasons I’ll explain in Chapter 6.

Removing Values from a List

The pop method removes a value by index. If no argument is provided, pop both removes and returns the rightmost value.

>>> lst = [50, 30, 81, 40]
>>> lst.pop()
40

We can pass the index of the value to remove as an argument to pop. Here, we remove and return the value at index 0:

>>> lst.pop(0)
50

Since pop returns something—unlike methods like append and sort—it makes sense to assign its return value to a variable:

>>> lst
[30, 81]
>>> value = lst.pop()
>>> value
81
>>> lst
[30]

The remove method removes by value, not index. Pass it the value to remove, and it removes the leftmost occurrence of that value from the list. If the value is not present, remove produces an error. In the following, there are two occurrences of 50 in the list, so remove(50) works twice before producing an error:

>>> lst = [50, 30, 81, 40, 50]
>>> lst.remove(50)
>>> lst
[30, 81, 40, 50]
>>> lst.remove(50)
>>> lst
[30, 81, 40]
>>> lst.remove(50)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: list.remove(x): x not in list

Solving the Problem

Suppose that we’ve successfully read and sorted the village positions. Here’s what our list would look like at that point:

>>> positions = [1, 4, 15, 19, 20, 50]
>>> positions
[1, 4, 15, 19, 20, 50]

To find the size of the smallest neighborhood, we start by finding the size of the neighborhood for the village at index 1. (Notice that we don’t start at index 0: the village at index 0 is the leftmost one, and per the problem description, we can ignore it.) We can find that neighborhood size like this:

>>> left = (positions[1] - positions[0]) / 2
>>> right = (positions[2] - positions[1]) / 2
>>> min_size = left + right
>>> min_size
7.0

The left variable stores the size of the left part of the neighborhood, and right stores the size of the right part. We then add them up to obtain the total size of the neighborhood. We get a value of 7.0.

That’s the value to beat. How do we know whether any other village has a smaller neighborhood? We can use a loop to process those other villages. If we find a neighborhood that’s smaller than our current smallest, we update our current smallest to that smaller size.

The code for our solution is in Listing 5-1.

   n = int(input())

❶ positions = []

❷ for i in range(n):
    ❸ positions.append(int(input()))

❹ positions.sort()

❺ left = (positions[1] - positions[0]) / 2
   right = (positions[2] - positions[1]) / 2
   min_size = left + right

❻ for i in range(2, n - 1):
       left = (positions[i] - positions[i - 1]) / 2
       right = (positions[i + 1] - positions[i]) / 2
       size = left + right
    ❼ if size < min_size:
           min_size = size

   print(min_size)

Listing 5-1: Solving Village Neighborhood

We begin by reading n, the number of villages, from the input. We also set positions to refer to an empty list ❶.

Each iteration of the first range for loop ❷ is responsible for reading one village position and appending it to the positions list. It does that by using input to read the next village position, int to convert it to an integer, and the list method append to append that integer to the list ❸. That one line ❸ is equivalent to these three separate lines:

    position = input()
    position = int(position)
    positions.append(position)

Having read the village positions, we next sort them in increasing order ❹. We then find the size of the neighborhood of the village at index 1, storing it using min_size ❺.

Next, in a second loop, we loop through each of the other villages whose neighborhood sizes we need to compute ❻. Those villages start at index 2 and end at index n - 2. (We don’t want to consider the village at index n - 1, because that’s the rightmost village.) We therefore use range with a first argument of 2 (thus starting at 2) and a second argument of n - 1 (thus ending at n - 2).

Inside the loop, we calculate the size of the current village’s neighborhood, exactly as we did for the first village. The size of the smallest neighborhood that we’ve found so far is referred to by min_size. Is the current village’s neighborhood smaller than our smallest so far? To answer that, we use an if statement ❼. If this village’s neighborhood is smaller than min_size, we update min_size to the size of this neighborhood. If this village’s neighborhood isn’t smaller than min_size, then we do nothing, because this village doesn’t change the size of the smallest neighborhood.

Having gone through all of the villages, min_size must be the size of the smallest neighborhood. We therefore output the value of min_size.

The “Output” section of this problem description specified “Include exactly one digit after the decimal point.” What if the smallest size was something like 6.25 or 8.33333? Shouldn’t we do something about that?

No. We’re safe with what we’ve done. The only neighborhood sizes we can get are numbers like 3.0 (with a 0 after the decimal point) and 3.5 (with a .5 after the decimal point). Here’s why. When we calculate the left part of a neighborhood, we subtract two integers and divide that resulting integer by 2. If we have an even integer before dividing by 2, then dividing gives us a .0 number (no remainder). And if we have an odd integer before dividing by 2, then dividing gives us a .5 number. The same goes for the right part of the neighborhood: the size will be a .0 number or a .5 number. Adding the left and right parts to get the total size is therefore guaranteed to give us another .0 or .5 number.

Avoiding Code Duplication: Two More Solutions

It’s a little disappointing that we’re including the “compute neighborhood size” code both prior to and in the second range for loop. In general, repeated code is a sign that we might be able to improve the code’s design. We’d like to avoid repeated code because it adds to the amount of code that we must maintain, and it makes it harder to fix problems in the code if it turns out that the repeated code is flawed. Here, the repeated code seems acceptable to me (it’s only three lines), but let’s talk about two ways to avoid it. These are general approaches that you’ll be able to apply to other similar problems.

Using a Huge Size

The only reason we’re calculating the size of a village’s neighborhood before the loop is so that the loop has something to compare the other neighborhood sizes against. If we entered the loop without a value for min_size, we’d get an error when the code tries to compare it to the size of the current village.

If we set min_size to 0.0 before the loop, then the loop will never find a smaller size, and we’ll incorrectly output 0.0 no matter the test case. Using 0.0 would be a bug!

But a huge value, one at least as big as every possible neighborhood size, will work. We just need to make it so huge that the first iteration of the loop is guaranteed to find a size that’s no bigger, ensuring that our fake huge size never gets output.

From the “Input” section of this problem description, we know that each position is between –1,000,000,000 and 1,000,000,000. The biggest neighborhood we could ever have, then, occurs when we have a village at position –1,000,000,000, another at position 1,000,000,000, and a village somewhere in between. That in-between village will have a neighborhood size of 1,000,000,000. We can therefore start min_size with a size of 1000000000.0 or greater. This alternate approach is in Listing 5-2.

   n = int(input())

   positions = []

   for i in range(n):
       positions.append(int(input()))

   positions.sort()

   min_size = 1000000000.0

❶ for i in range(1, n - 1):
       left = (positions[i] - positions[i - 1]) / 2
       right = (positions[i + 1] - positions[i]) / 2
       size = left + right
       if size < min_size:
           min_size = size

   print(min_size)

Listing 5-2: Solving Village Neighborhood with a huge value

Careful! We need to start computing sizes at index 1 now ❶ (not 2); otherwise, we’d forget to include the neighborhood of the village at index 1.

Building a List of Sizes

Another way to avoid the code duplication is to store each neighborhood size in a list of sizes. Python has a built-in min function that takes a sequence and returns its minimum:

>>> min('qwerty')
'e'
>>> min([15.5, 7.0, 2.5, 7.5])
2.5

(Python also has a max function that returns the maximum of a sequence.)

See Listing 5-3 for a solution that uses min on a list of neighborhood sizes.

n = int(input())

positions = []

for i in range(n):
    positions.append(int(input()))

positions.sort()

sizes = []

for i in range(1, n - 1):
    left = (positions[i] - positions[i - 1]) / 2
    right = (positions[i + 1] - positions[i]) / 2
    size = left + right
    sizes.append(size)

min_size = min(sizes)
print(min_size)

Listing 5-3: Solving Village Neighborhood using min

Feel free to submit any of these solutions to the judge, whichever you like best!

Before continuing, you might like to try solving exercise 1 from “Chapter Exercises” on page 134.

Problem #12: School Trip

Many problems you’ll encounter have input with multiple integers or floats per line. We’ve avoided these problems until now, but they are everywhere! We’ll now learn how we can use lists to process the input for these kinds of problems.

This is DMOJ problem ecoo17r1p1.

The Challenge

Students would like to go on a school trip at the end of the year, but they need money to pay for it. To raise money, they have organized a brunch. To attend the brunch, a student in their first year pays $12, a student in their second year pays $10, a student in their third year pays $7, and a student in their fourth year pays $5.

Of all of the money raised at the brunch, 50 percent of it can be used to pay for the school trip (the other 50 percent is used to pay for the brunch itself).

We are told the cost of the school trip, the proportion of students in each year, and the total number of students. Determine whether the students need to raise more money for the school trip.

Input

The input consists of 10 test cases, with three lines per test case (30 lines in all). Here are the three lines for each test case:

• The first line contains the cost in dollars of the school trip; it’s an integer between 50 and 50,000.
• The second line contains four numbers indicating the proportion of brunching students who are in first, second, third, and fourth year, respectively. There is a space between each pair of numbers. Each number is between 0 and 1, and their sum is 1 (for 100 percent).
• The third line contains integer n, the number of students attending the brunch. n is between 4 and 2,000.

Output

For each test case: if the students need to raise more money for the school trip, output YES; otherwise, output NO.

A Catch

Suppose that there are 50 students and that 10 percent of them (a proportion of 0.1) are in their fourth year. Then we can calculate that 50 * 0.1 = 5 students are in their fourth year.

Now suppose that there are 50 students, but that 15 percent of them (a proportion of 0.15) are in their fourth year. If we multiply, we get 50 * 0.15 = 7.5 students in their fourth year.

Having 7.5 students doesn’t make any sense, and I haven’t told you what we should do in such a case. The full problem description specifies that we are to round down—so we’d round down to 7 here. This could result in the sum of the students in first year, second year, third year, and fourth year not equaling the total number of students. For the students who are not accounted for, we are to add them to the year with the most students. It’s guaranteed that exactly one year will have the most students (there won’t be a tie between multiple years).

We’ll first solve the problem ignoring this catch. Then we’ll incorporate the catch to give us a full solution.

Splitting Strings and Joining Lists

The second line of each test case consists of four proportions, like this:

0.2 0.08 0.4 0.32

We need a way to extract those four numbers from a string for further processing. We’ll learn about the string split method for splitting a string into a list of its pieces. While we’re at it, we’ll also learn about the string join method, which lets us go the other way and collapse a list into a single string.

Splitting a String into a List

Remember that the input function returns a string, no matter what the input looks like. If the input should be interpreted as an integer, we need to convert the string to an integer. If the input should be interpreted as a float, we need to convert the string to a float. And if the input should be interpreted as four floats? Well, then we had better split it up into individual floats before converting anything!

The string split method splits a string into a list of its pieces. By default, split splits around spaces, which is exactly what we need for our four floats:

>>> s = '0.2 0.08 0.4 0.32'
>>> s.split()
['0.2', '0.08', '0.4', '0.32']

The split method returns a list of strings, at which point we can access each one independently. Here, I save the list that split returns and then access two of its values:

>>> proportions = s.split()
>>> proportions
['0.2', '0.08', '0.4', '0.32']
>>> proportions[1]
'0.08'
>>> proportions[2]
'0.4'

Data in the wild is often comma-separated rather than space-separated. Piece of cake: we can call split with an argument that tells it what to use as a separator:

>>> info = 'Toronto,Ontario,Canada'
>>> info.split(',')
['Toronto', 'Ontario', 'Canada']

Joining a List into a String

To go the other way, from a list to a string rather than a string to a list, we can use the string join method. The string on which join is called is used as the separator between list values. Here are two examples:

>>> lst = ['Toronto', 'Ontario', 'Canada']
>>> ','.join(lst)
'Toronto,Ontario,Canada'
>>> '**'.join(lst)
'Toronto**Ontario**Canada'

Technically, join can join the values in any sequence, not just in a list. Here’s an example of joining the characters from a string:

>>> '*'.join('abcd')
'a*b*c*d'

Changing List Values

When we use split on a string of four pieces, we get a list of strings:

>>> s = '0.2 0.08 0.4 0.32'
>>> proportions = s.split()
>>> proportions
['0.2', '0.08', '0.4', '0.32']

In “Converting Between Strings and Integers” in Chapter 1, we learned that strings that look like numbers can’t be used in numerical calculations. So, we need to convert this list of strings to a list of floats.

We can convert a string to a float using float, like this:

>>> float('45.6')
45.6

That’s just one float. How can we convert a whole list of strings to a list of floats? It’s awfully tempting to try to make that happen using the following loop:

>>> for value in proportions:
...     value = float(value)

The logic is that this should go through each value in the list and convert it to a float.

Sadly, it doesn’t work. The list still refers to strings:

>>> proportions
['0.2', '0.08', '0.4', '0.32']

What could be wrong? Is float not working? We can see that float is doing just fine by looking at the type of value after conversion:

>>> for value in proportions:
...     value = float(value)
...     type(value)
...
<class 'float'>
<class 'float'>
<class 'float'>
<class 'float'>

Four floats! But the list obdurately remains one of strings.

What’s happening here is that we’re not changing the values referred to in the list. We’re changing what the variable value refers to, but that doesn’t change the fact that the list refers to the old string values. To actually change the values that the list references, we need to assign new values at the list’s indices. Here’s how to do it:

>>> proportions
['0.2', '0.08', '0.4', '0.32']
>>> for i in range(len(proportions)):
...     proportions[i] = float(proportions[i])
...
>>> proportions
[0.2, 0.08, 0.4, 0.32]

The range for loop loops through each index, and an assignment statement changes what’s referred to by that index.

Solving Most of the Problem

We’re now in good shape to solve the problem minus the catch.

We’ll start with an example to highlight what our code will have to do. Then we’ll move onto the code itself.

Exploring a Test Case

The input for this problem consists of 10 test cases, but I’ll present only one here. If you type this test case from the keyboard, you’ll see the answer. But the program won’t terminate there, because it’s waiting for the next test case. If you use input redirection with this test case, you’ll again see the answer. But then you’ll get an EOFError. EOF stands for “end of file”; the error is caused by the program trying to read more input than is available. Once your code is working for one test case, you can try adding a few more to your input to make sure that those work, too. Once you have 10, your program should run to completion.

Here’s the test case I’d like to trace with you:

504
0.2 0.08 0.4 0.32
125

The school trip costs $504, and there are 125 students who attend the brunch.

To determine how much money is raised at the brunch, we calculate the money raised from each year of students. There are 125 * 0.2 = 25 students in their first year, and each of them pays $12 for the brunch. So, the first-year students raise 25 * 12 = 300 dollars. We can similarly calculate the money raised by the students in second, third, and fourth years. See Table 5-1 for this work.

Table 5-1: School Trip Example

Year	Students in year	Cost per student	Money raised
First year	25	12	300
Second year	10	10	100
Third year	50	7	350
Fourth year	40	5	200

The money raised by each year of students is calculated by multiplying the number of students in that year by the cost per student in that year; see the rightmost column of the table. For the total money raised by all students, we can add the four numbers in this rightmost column. That gives us 300 + 100 + 350 + 200 = 950 dollars. Only 50 percent of that can be used for the school trip. So we’re left with 950 / 2 = 475 dollars, not sufficient to pay for the $504 trip. The correct output is therefore YES, because more money must be raised.

The Code

This partial solution will correctly handle any input where multiplying a proportion by the number of students gives a whole number of students (such as the test case that we just did). See Listing 5-4 for the code.

❶ YEAR_COSTS = [12, 10, 7, 5]


❷ for dataset in range(10):
       trip_cost = int(input())
    ❸ proportions = input().split()
       num_students = int(input())

    ❹ for i in range(len(proportions)):
           proportions[i] = float(proportions[i])

    ❺ students_per_year = []

       for proportion in proportions:
        ❻ students = int(num_students * proportion)
           students_per_year.append(students)

       total_raised = 0
    ❼ for i in range(len(students_per_year)):
           total_raised = total_raised + students_per_year[i] * YEAR_COSTS[i]

    ❽ if total_raised / 2 < trip_cost:
           print('YES')
       else:
           print('NO')

Listing 5-4: Solving most of School Trip

To begin, we use variable YEAR_COSTS to refer to a list of costs for attending the brunch: the cost for students in their first, second, third, and fourth year ❶. Once we’ve determined the number of students in each year, we’ll multiply by these values to determine the money raised. The costs never change, so we’ll never change what this variable refers to. For such “constant” variables, Python convention is to write their names in capital letters, as I’ve done here.

The input contains 10 test cases, so we loop 10 times ❷, once for each test case. The rest of the program is inside this loop, because we want to repeat everything 10 times.

For each test case, we read the three lines of input. The second line is the one that has the four proportions, so we use split to split it into a list of four strings ❸. We use a range for loop to convert each of those strings to a float ❹.

Using those proportions, our next task is to determine the number of students in each year. We begin with an empty list ❺. Then, for each proportion, we multiply the total number of students by that proportion ❻ and append it to the list. Notice at ❻ that I’m using int to guarantee that we’re appending only integers. When used on a float, int drops the fractional part by rounding toward 0.

Now we have the two lists that we need to calculate how much money has been raised. In students_per_year, we have a list of the number of students in each year, which looks something like this:

[25, 10, 50, 40]

And in YEAR_COSTS, we have the cost of brunch for students in each year:

[12, 10, 7, 5]

Each value at index 0 in these lists tells us something about students in their first year, each value at index 1 tells us something about students in their second year, and so on. Such lists are called parallel lists, because they work in parallel to tell us more than each does alone.

We use these two lists to calculate the total money raised, by multiplying each number of students by the corresponding cost per student and adding up all of these results ❼.

Has enough money been raised for the school trip? To find out, we use an if statement ❽. Half of the money raised by the brunch can be used for the school trip. If that amount is less than the cost of the school trip, then we need to raise more money (YES); otherwise, we don’t (NO).

The code we’ve written is very general. The only clue that there are four years of students is at ❶. If we wanted to solve a similar problem for a different number of years, all we’d have to do is change that line (and provide input with the expected number of proportions). This is the power of lists: they help us write flexible code that can accommodate changes to problems we are solving.

How to Handle the Catch

Now let’s see why our current program does the wrong thing for some test cases, and the Python features we’ll use to fix it.

Exploring a Test Case

Here’s a test case that our current code gets wrong:

50
0.7 0.1 0.1 0.1
9

This time, the school trip costs $50, and there are nine students that attend the brunch. For the number of students in their first year, our current program would calculate 9 * 0.7 = 6.3 and then round down to 6. The fact that we have to round down is why we have to be careful with this test case. To see what our current program would do for all four years, see Table 5-2.

Table 5-2: An Example Case from School Trip That Our Current Program Gets Wrong

Year	Students in year	Cost per student	Money raised
First year	6	12	72
Second year	0	10	0
Third year	0	7	0
Fourth year	0	5	0

In each year besides the first year, there are 0 students because 9 * 0.1 = 0.9 rounds down to 0. So it looks like all we raise is $72. Half of $72 is $36, not sufficient to pay for the $50 school trip. Our current program outputs YES. We need to raise more money.

. . . Or not. We’re supposed to have nine students here, not six! We’ve lost three students to rounding. The problem description specifies that we should add those students to the year with the most students, which in this case is the first year. If we do that, we see that we actually raise 9 * 12 = 108 dollars. Half of $108 is $54, so in fact we do not need to raise any more money for the $50 school trip! The correct output is NO.

More List Operations

To fix our program, we need to do two things: figure out how many students were lost to rounding, and add those students to the year with the most students.

Summing a List

To determine the number of students lost to rounding, we can add up the students in our students_per_year list and then subtract that from the total number of students. Python’s sum function takes a list and returns the sum of its values:

>>> students_per_year = [6, 0, 0, 0]
>>> sum(students_per_year)
6
>>> students_per_year = [25, 10, 50, 40]
>>> sum(students_per_year)
125

Finding the Index of the Maximum

Python’s max function takes a sequence and returns its maximum value:

>>> students_per_year = [6, 0, 0, 0]
>>> max(students_per_year)
6
>>> students_per_year = [25, 10, 50, 40]
>>> max(students_per_year)
50

We want the index of the maximum, not the maximum itself, so that we can increase the number of students at that index. Given the maximum value, we can find its index using the index method. It returns the leftmost index where the provided value is found or generates an error if the value is not in the list at all:

>>> students_per_year = [6, 0, 0, 0]
>>> students_per_year.index(6)
0
>>> students_per_year.index(0)
1
>>> students_per_year.index(50)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 50 is not in list

We’ll be searching for a value that we know is in the list, so we won’t have to worry about getting an error.

Solving the Problem

We’re there! We can now update our partial solution to handle any valid test case. The new program is in Listing 5-5.

YEAR_COSTS = [12, 10, 7, 5]


for dataset in range(10):
    trip_cost = int(input())
    proportions = input().split()
    num_students = int(input())

    for i in range(len(proportions)):
        proportions[i] = float(proportions[i])

    students_per_year = []

    for proportion in proportions:
        students = int(num_students * proportion)
        students_per_year.append(students)

 ❶ counted = sum(students_per_year)
    uncounted = num_students - counted
    most = max(students_per_year)
    where = students_per_year.index(most)
 ❷ students_per_year[where] = students_per_year[where] + uncounted

    total_raised = 0

    for i in range(len(students_per_year)):
        total_raised = total_raised + students_per_year[i] * YEAR_COSTS[i]

    if total_raised / 2 < trip_cost:
        print('YES')
    else:
        print('NO')

Listing 5-5: Solving School Trip

The only new code is the five lines starting at ❶. We use sum to calculate how many students we’ve counted so far and then subtract this from the total number of students to arrive at the number of uncounted students. We then use max and index to identify the index of the year to which we should add the uncounted students. Finally, we add the uncounted students to this index ❷. (Adding 0 to a number doesn’t change that number, so don’t worry about coding special behavior for when uncounted is 0. This code is safe in that case.)

That’s all for this problem. Go ahead and submit to the judge! And then come back—we’re about to explore even more general list structures.

Before continuing, you might like to try solving exercise 5 from “Chapter Exercises” on page 134.

Problem #13: Baker Bonus

In this problem, we’ll see how lists help us work with two-dimensional data. This kind of data arises often in real-world programs. For example, data in the form of a spreadsheet consists of rows and columns; processing such data requires techniques like those we’re about to learn.

This is DMOJ problem ecoo17r3p1.

The Challenge

Baker Brie has a number of franchisees, each of which sells baked goods to consumers. Having reached the milestone of being in business for 13 years, Baker Brie will celebrate by awarding bonuses based on sales. The bonuses depend on sales per day and sales per franchisee. Here’s how the bonuses work:

• For every day on which the total sales across all franchisees is a multiple of 13, that multiple will be given as bonuses. For example, a day where the franchisees sold a combined 26 baked goods will add 26 / 13 = 2 bonuses to the total.
• For every franchisee whose total sales across all days is a multiple of 13, that multiple will be given as bonuses. For example, a franchisee that sold a total of 39 baked goods will add 39 / 13 = 3 bonuses to the total.

Determine the total number of bonuses awarded.

Input

The input consists of 10 test cases. Each test case contains the following lines:

• A line containing the integer number of franchisees f and integer number of days d, separated by a space. f is between 4 and 130, and d is between 2 and 4,745.
• d lines, one per day, containing f integers separated by spaces. Each integer specifies a number of sales. The first of these lines gives the sales for each franchise on the first day, the second gives the sales for each franchise on the second day, and so on. Each integer is between 1 and 13,000.

Output

For each test case, output the total number of bonuses awarded.

Representing a Table

The data for this problem can be visualized as a table. We’ll start with an example and then look at how to represent a table as a list.

Exploring a Test Case

If we have d days and f franchisees, we can lay out the data as a table with d rows and f columns.

Here’s a sample test case:

6 4
1 13 2 1 1 8
2 12 10 5 11 4
39 6 13 52 3 3
15 8 6 2 7 14

The table corresponding to this test case is in Table 5-3.

Table 5-3: Baker Bonus Table

	0	1	2	3	4	5
0	1	13	2	1	1	8
1	2	12	10	5	11	4
2	39	6	13	52	3	3
3	15	8	6	2	7	14

I’ve numbered the rows and columns starting at 0 to coincide with how we’ll shortly store this data in a list.

How many bonuses are awarded in this test case? Let’s first look at the rows of the table, which correspond to days. The sum of the sales for row 0 is 1 + 13 + 2 + 1 + 1 + 8 = 26. As 26 is a multiple of 13, this row gives us 26 / 13 = 2 bonuses. The sum of row 1 is 44. That’s not a multiple of 13, so no bonuses there. The sum of row 2 is 116—again, no bonuses. The sum of row 3 is 52, which gives us 52 / 13 = 4 bonuses.

Now let’s look at the columns, which correspond to franchisees. The sum of column 0 is 1 + 2 + 39 + 15 = 57. That’s not a multiple of 13, so no bonuses. In fact, the only column that gives us any bonuses is column 1. Its sum is 39, giving us 39 / 13 = 3 bonuses.

The total number of bonuses awarded is 2 + 4 + 3 = 9. So, 9 is the correct output for this test case.

Nested Lists

To this point, we’ve seen lists of integers, floats, and strings. We can also create lists of lists, called nested lists. Each value of such a list is itself a list. It’s common to use a variable name like grid or table to refer to a nested list. Here’s a Python list corresponding to Table 5-3:

>>> grid = [[ 1, 13,  2,  1,  1,  8],
...         [ 2, 12, 10,  5, 11,  4],
...         [39,  6, 13, 52,  3,  3],
...         [15,  8,  6,  2,  7, 14]]

Each list value corresponds to one row. If we index once, we get a row, which is itself a list:

>>> grid[0]
[1, 13, 2, 1, 1, 8]
>>> grid[2]
[39, 6, 13, 52, 3, 3]

If we index twice, we get a single value. Here’s the value in row 1, column 2:

>>> grid[1][2]
10

Working with columns is a little trickier than working with rows, because each column is spread over multiple lists. To access a column, we need to aggregate one value from each row. We can do that with a loop, which incrementally builds a new list representing a column. Here, I obtain column 1:

   >>> column = []
   >>> for i in range(len(grid)):
❶ ...     column.append(grid[i][1])
   ...
   >>> column
   [13, 12, 6, 8]

Notice how the first index (the row) varies, but the second (the column) does not ❶. This picks out each value with the same column index.

What about summing rows and columns? To sum a row, we can use the sum function. Here’s the sum of row 0:

>>> sum(grid[0])
26

We can also use a loop, like this:

>>> total = 0
>>> for value in grid[0]:
...     total = total + value
...
>>> total
26

Using sum is the easier option, so we’ll use that.

To sum a column, we can build a column list and use sum on that, or we can calculate it directly without making a new list. Here’s the latter approach for column 1:

>>> total = 0
>>> for i in range(len(grid)):
...     total = total + grid[i][1]
...
>>> total
39

Solving the Problem

Our code to solve this problem is in Listing 5-6.

for dataset in range(10):
 ❶ lst = input().split()
    franchisees = int(lst[0])
    days = int(lst[1])
    grid = []

 ❷ for i in range(days):
        row = input().split()
     ❸ for j in range(franchisees):
            row[j] = int(row[j])
     ❹ grid.append(row)

    bonuses = 0

 ❺ for row in grid:
     ❻ total = sum(row)
        if total % 13 == 0:
            bonuses = bonuses + total // 13

 ❼ for col_index in range(franchisees):
        total = 0
     ❽ for row_index in range(days):
            total = total + grid[row_index][col_index]
        if total % 13 == 0:
            bonuses = bonuses + total // 13

    print(bonuses)

Listing 5-6: Solving Baker Bonus

As with School Trip, the input contains 10 test cases, so we place all of our code inside a loop that iterates 10 times.

For each test case, we read the first line of input and call split to break it into a list ❶. That list will contain two values—the number of franchisees and the number of days—and we convert them to integers and assign them to appropriately named variables.

The grid variable begins as an empty list. It will ultimately refer to a list of rows, where each row is a list of sales for a given day.

We use a range for loop to loop once for each day ❷. We then read a row from the input and call split to split it into a list of individual sales values. These values are strings right now, so we use a nested loop to convert them all to integers ❸. Then, we add the row to our grid ❹.

We’ve now read the input and stored the grid. It’s time to add up the number of bonuses. We take that in two steps: first for the bonuses from the rows and second for the bonuses from the columns.

To find the bonuses from the rows, we use a for loop on grid ❺. As with any for loop on a list, it gives us its values one at a time. Here, each value is a list, so row refers to a different list on each iteration. The sum function works on any list of numbers, so we use it here to add up the values in the current row ❻. If the sum is divisible by 13, then we add the number of bonuses.

We can’t loop through columns of the list like we did rows, so we have to resort to looping through indices. We accomplish that by using a range for loop through the indices of the columns ❼. Using sum is not an option for summing the current column, so we’ll need a nested loop. That nested loop goes through the rows ❽, adding up each value in the desired column. We then check whether that total is divisible by 13 and add any bonuses if it is.

We finish by printing the total number of bonuses.

Judge time! If you submit our code, you should see that all test cases pass.

Summary

In this chapter, we learned about lists, which help us work with collections of whatever type we choose. Lists of numbers, lists of strings, lists of lists: Python supports whatever we need. We also learned about list methods and why sorting a list can make it easier to process the values in a list.

In contrast to strings, lists are mutable, which means that we can change their contents. This helps us more easily manipulate lists, but we must be careful to modify the list that we think we’re modifying.

We’re at the point in our learning where we can write programs with many lines of code. We can direct what our programs do using if statements and loops. We can store and manipulate information using strings and lists. We can write programs to solve challenging problems. Such programs can become difficult to design and read. Fortunately, there’s a tool we can use to help us organize our programs to keep their complexity under control, and we’ll learn that tool in the next chapter. Working through some of the following exercises may deepen your appreciation of the difficulty in writing larger amounts of code. Then you’ll be ready to continue!

Chapter Exercises

Here are some exercises for you to try.

1. DMOJ problem ccc07j3, Deal or No Deal Calculator
2. DMOJ problem coci17c1p1, Cezar
3. DMOJ problem coci18c2p1, Preokret
4. DMOJ problem ccc00s2, Babbling Brooks (Check out Python’s round function.)
5. DMOJ problem ecoo18r1p1, Willow’s Wild Ride
6. DMOJ problem ecoo19r1p1, Free Shirts
7. DMOJ problem dmopc14c7p2, Tides
8. DMOJ problem wac3p3, Wesley Plays DDR
9. DMOJ problem ecoo18r1p2, Rue’s Rings (If you use f-strings here, you’ll need a way to include the { and } symbols themselves. You can include a { in the f-string by using {{ and a } by using }}.)
10. DMOJ problem coci19c5p1, Emacs
11. DMOJ problem coci20c2p1, Crtanje (You’ll need to support rows from –100 to 100. But how do we support negative-indexed rows when Python lists start at index 0? Here’s a trick: use index x + 100 any time you need access to row x. That shifts the row numbers to be between 0 and 200 rather than between –100 and 100. Also, one small annoyance here with strings: is a special character, so you’ll have to use '' rather than '' if you want a character.)
12. DMOJ problem dmopc19c5p2, Charlie’s Crazy Conquest (You’ll have to be careful with indices and the game rules for this one!)

Notes

Village Neighborhood is originally from the 2018 Canadian Computing Competition, Senior Level. School Trip is originally from the 2017 Educational Computing Organization of Ontario Programming Contest, Round 1. Baker Bonus is originally from the 2017 Educational Computing Organization of Ontario Programming Contest, Round 3.