Transit Frequencies

A company specialized in managing large shopping malls aims at avoiding crowded areas anywhere in the mall in order to comply with customers security standards. To that aim it is interested on an information system for automatic detection of areas in the mall where the customers transit is high. The system projected is composed of the following subsystems:

  • The Sensors Network: A number of sensors properly distributed throughout the sections in the mall where customers are passing.

  • the Customers App: An app installed in all customers mobile phones that will send a signal to the sensor when the customer enters that section.

  • The Information System: It gets information about the routes taken by each customer that visited the mall. This information is stored in the so-called trajectory dictionary where:

    • The key is the Customer Id (str)

    • The value is a list of the sensor points (each point is represented as an int) for which the customer has passed. Every pair (tuple) of consecutive points determines a Directed Section (for short we shall call it DSect). Notice that (i, j) and (j, i) are considered different DSects.

See the example below. The first entry in the dictionary trajD says that the customer associated with the 'H11' has walked from point 1 to 5, and then from 5 o 7 and from 7 to 9 and so on.


>>> trajD = {
... 'H11':[1, 5, 7, 9, 6, 2, 6, 9],
... 'M22':[3, 1, 5, 7, 9, 6],
... 'H23':[5, 7, 9, 6, 2, 9, 6],
... }

Now, we define a transit dictionary as a dict where:

  • The keys are DSects.

  • The corresponding value is a list of all customers that passed through that DSect such that:

    • The list includes repetitions: if a customer passed through that DSect a n times will appear in this list that n times.

    • The list is alphabetically ordered.

For example:


>>> corrD = {
... (1, 5): ['H11', 'M22'],
... (5, 7): ['H11', 'H23', 'M22'],
... (7, 9): ['H11', 'H23', 'M22'],
... (9, 6): ['H11', 'H23', 'H23', 'M22'],
... (6, 2): ['H11', 'H23'],
... (2, 6): ['H11'],
... (6, 9): ['H11'],
... (3, 1): ['M22'],
... (2, 9): ['H23'],
... }

Given our purpose and this available information, please implement the following Python functions in the transit module (transit.py file) the following functions.

The first function is:

gen_transitD(trajD)

such that

given trajD, dict, a trajectory dictionary as described above.

returns a dict with the transit dictionary corresponding to trajD as defined above.

Doctests are available at the gen_transitD.test file.

The second function is:

sort_transitD(transitD)

such that

given transitD, a transit dictionary as described above.

returns a list of tuple with all DSects in transitD. Each tuple is composed of:

  • the DSect tuple

  • the list of all customers that passed through that DSect alphabetically ordered.

The list is decreasingly ordered by the number of custormers in that DSect. Those DSect with the same number must be lexicographically ordered by the points of the DSect (hence, ordering first by the first point and, when they are the same, by the second point).

For example, given the transit dictionary


>>> transitD = {
... (1, 3): ['H13', 'H13', 'H55'],
... (3, 5): ['H13', 'H55', 'M22'],
... (5, 9): ['H13', 'H55', 'M22', 'M22'],
... (9, 5): ['H13', 'H55', 'M22', 'M22'],
... (5, 1): ['H13', 'H55', 'M22'],
... (3, 1): ['H13'],
... }

the function should return the list


>>> corrL = [
... ((5, 9), ['H13', 'H55', 'M22', 'M22']), 
... ((9, 5), ['H13', 'H55', 'M22', 'M22']), 
... ((1, 3), ['H13', 'H13', 'H55']), 
... ((3, 5), ['H13', 'H55', 'M22']), 
... ((5, 1), ['H13', 'H55', 'M22']), 
... ((3, 1), ['H13'])]

Doctests are available at the sort_transitD.test file.