Toll Lanes: Car Arrival Counting

The questions below are due on Sunday July 27, 2025; 10:00:00 PM.
 
You are not logged in.

Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
1

Description

You want to examine the behavior of cars passing through a toll road checkpoint. The toll checkpoint you're examining has n toll booths (one for each of the n lanes), each of which takes exactly 1 minute to toll a car2.

Using a camera mounted at the checkpoint and some image processing, you have compiled historical data about the checkpoint in a Python list lane_lines. Each element of lane_lines is itself a list, containing n nonnegative integers which indicate how many cars are in line for each of the n lane lines. There is one list in lane_lines for every minute of recorded data—the first element in lane_lines describes the length of the lane lines at the beginning of the first minute; the second element describes the length of the lines at the beginning of the second minute; etc.

For example,

lane_lines = [[0, 0, 0],
              [1, 1, 0],
              [0, 0, 2],
              [2, 3, 1]]

contains data on three toll lanes over three minutes. It says:

  • At the beginning of the first minute, there were no cars in any of the toll lanes.
  • At the beginning of the second minute, there was one car in line for the first lane and one in line for the second, and none in line for the third.
  • At the beginning of the third minute, there were no cars in line for the first or second lanes, and two cars in line for the third.
  • At the beginning of the fourth minute (i.e. the end of the third minute), there were two cars in line for the first lane, three cars in line for the second lane, and one car in line for the third.

Importantly, during one minute, the following two things happen in every lane:

  • if any cars are in that lane's line, exactly one of the cars is tolled (and leaves the line).
  • any number of new cars can arrive.

Cars cannot change lanes once they arrive in a particular toll lane.

Therefore, from the lane_lines example above, here's what we can reconstruct happened:

  • during the first minute: one car arrived to each of the first two lanes
  • during the second minute: one car was tolled in each of the first two lanes, and two cars arrived in the third lane
  • during the third minute: two cars arrived in the first lane, three cars arrived in the second lane, and one car was tolled in the third lane

Your Task

Given historical data of this form, you want to know how many distinct cars arrived at the toll checkpoint (in any lane).

Answer the below questions manually, before writing code, to check your understanding.

Try Now:

For the lane_lines example above, how many distinct cars arrived at the toll checkpoint?

9 cars. During the first minute one car arrived in the lane at index 0 and one car arrived in the lane at index 1. During the second minute, the first two lanes tolled a car and two cars arrived in the lane at index 2. During the third minute, two cars arrived in lane 0, three cars arrived in lane 1, and lane 2 tolled one car (but no new cars arrived.) Overall, 2 + 2 + 5 = 9 cars arrived.

lane_lines2 = [[2, 3, 1, 2, 2, 1],
               [2, 3, 1, 2, 2, 1],
               [1, 2, 2, 1, 1, 0],
               [9, 1, 2, 0, 0, 1],
               [8, 0, 1, 0, 0, 0]]
Try Now:

How many lanes are in the toll checkpoint for the lane_lines2 historical data?

There are 6 lanes because each "column" of the data represents a lane. In other words, the length of one inner list is the number of lanes.

Try Now:

How many minutes of data are represented in lane_lines2?

The data represents 4 minutes. There are 5 "rows" in the data. The first stores the status of lines at the beginning of the first minute; the second stores the status at the beginning of the second; ... and the fourth stores the status at the beginning of the fourth minute, which is also the end of the third minute. In this way, a "minute" occurs between two recorded data row entries.

Try Now:

How many distinct cars arrived according to the data in lane_lines2? Note that cars which are present at the beginning of the first minute of data should not be counted as arrivals.

  • At the beginning the number of cars in each toll lane is:

[2, 3, 1, 2, 2, 1]

  • After one minute the number of cars in each toll lane is:

[2, 3, 1, 2, 2, 1]

That means during the first minute, exactly one car was tolled in each lane, but exactly one new car arrived too (so the number of cars in each lane stayed the same).

  • After the second minute the number of cars in each toll lane is:

[1, 2, 2, 1, 1, 0]

So during the second minute, all lanes tolled one car and two cars arrived in the lane at index 2.

  • After the third minute the number of cars in each toll lane is:

[9, 1, 2, 0, 0, 1]

During the third minute, all lanes except the last one tolled a car, 9 cars arrived in the lane at index 0, 1 car arrived in the lane at index 2, and 1 car arrived in the lane at index 5.

  • After four minutes the toll lanes look like:

[8, 0, 1, 0, 0, 0]

So four cars were tolled but no cars arrived during the fourth minute.

The total number of cars that arrived is then 6 + 2 + 11 + 0 = 19.

Now, write a function num_arrivals(lane_lines) which returns the number of distinct cars that arrive according to the data in lane_lines. Note again that cars present in the very first entry of the data are not counted as arrivals.

Code Submission

Once you have confirmed your code works via your own small test cases, upload it below:

  No file selected

Next Exercise: Toll Lanes: Behavior Hypothesis

Back to exercises


 
Footnotes

1Source: [https://www.flickr.com/photos/massdot/4293675322](https://www.flickr.com/photos/massdot/4293675322). Noncommercial reuse allowed. (click to return to text)

2Your toll checkpoint does not have EasyPass or other special toll lanes like that. (click to return to text)