Module assignment: Shop visit analyzer in Python

What you will build

A small shop writes one line to a log every time a customer buys an item. Each line holds a customer name and an item name, separated by a space. At the end of the day the manager wants a short report: how many different customers came in, which item sold most, which customers bought the most, and which customers bought the same item more than once.

Your task is to write a Python program that reads the log and prints that report. The program uses everything from this module. You will count with a dict, check for repeats with a set, and sort the output with sorted(). You will also choose each structure on purpose and be able to explain why. The work is not large, but it has enough small rules that a careless solution will fail some of them.

This assignment is the last lesson of the module, so it is a test of the whole module. Work through it in order. Read the specification, write the checklist, try the first version on the examples, and only then open the hints. The reference solution is at the end, but try the problem yourself first. The solution is far more useful after you have struggled with a version of your own.

The input

The first line holds one whole number n, the number of purchase lines. Each of the next n lines holds one purchase: a customer name, one space, and an item name. Names are lowercase letters only, with no spaces inside a name.

The limits are generous, so your program must be efficient. The number n is between 1 and 100000. Each name is between 1 and 20 letters long.

Read all of the input at once with sys.stdin.read(), then split it into tokens with split(). A token is a run of characters with no spaces, so the first token is n, and the names follow in pairs: the customer, then the item, for each purchase. Splitting on any whitespace also handles the line breaks for you. Lesson 2 showed input() for reading one line at a time. For this job, reading everything at once is simpler and fast enough for 100000 lines.

The output

Your program prints exactly four lines, in this order. The wording and the spacing must match, because the checker compares the text.

1. distinct users: X, where X is the number of different customers.
2. top item: NAME, where NAME is the item bought the most times. Count each purchase line as one sale. If two items tie, print the one that comes first in alphabetical order.
3. top buyers: a 3, b 2, c 2, which lists up to three customers, the most active first. Each entry is the customer name, one space, and the number of purchases. Customers with the same count appear in alphabetical order. If there are fewer than three customers, list them all. Separate the entries with a comma and a space.
4. repeat buyers: a, b, which lists the customers who bought the same item at least twice. The list is in alphabetical order and separated by a comma and a space. A customer appears once even if they repeated more than one item. If nobody repeated, print repeat buyers: none.

Every line ends with a newline character, which print adds for you.

Worked example 1

Here is the sample input. Type 7 on the first line of the input, and the seven purchase lines on the lines after it.

7
asha book
ravi pen
asha book
meera book
ravi book
asha pen
ravi pen

Work the answer out by hand before you look at the output. Count the purchases per customer first. asha made three purchases: book, book and pen. ravi also made three: pen, book and pen. meera made one: book. So there are three distinct customers.

Count the purchases per item next. book was bought four times: twice by asha, once by meera, and once by ravi. pen was bought three times. The top item is book.

The top buyers are asha and ravi, each with three purchases. They tie, so alphabetical order puts asha first. Then meera with one purchase. The repeat buyers are asha, who bought book twice, and ravi, who bought pen twice. meera bought book only once, so she is not in the list.

The correct output is:

distinct users: 3
top item: book
top buyers: asha 3, ravi 3, meera 1
repeat buyers: asha, ravi

Check your hand count against this output. If they differ, find out which line is different before you change your code. Usually the difference is in the tie rule or in the repeat rule, and those are the two places where beginners make the most mistakes.

Worked example 2

The second example checks the edge cases. Two purchases, two different customers, and no repeat.

2
asha book
ravi pen

Here the expected output is:

distinct users: 2
top item: book
top buyers: asha 1, ravi 1
repeat buyers: none

Notice the top item. Both items were bought once, so they tie, and book comes before pen alphabetically. Notice also that the top buyers list has two entries, not three, because there are only two customers. And the repeat line says none, because no customer bought the same item twice.

Your program should handle both examples. Test a third case of your own, such as one customer who buys one item a hundred times, to see whether your counting is right.

Requirements checklist

Copy this list into a file and tick each box as you finish the step. A solution that ticks every box and passes both examples is a complete solution. The rubric below describes what each level of quality looks like.

• The program reads n and then exactly 2 * n names.
• The first line of output is distinct users: X with the correct count.
• The item count uses a dict from item name to number of purchases.
• The top item uses the smallest alphabetical name when two items tie.
• The top buyers list is sorted by count, highest first, then by name.
• The top buyers list has at most three entries and separates them with , .
• A customer who bought the same item at least twice appears in the repeat list.
• The repeat list is sorted alphabetically and has no duplicates.
• The line repeat buyers: none appears when nobody repeated.
• Both worked examples produce the exact output shown.
• The program runs in time for n = 100000 with long names and many repeats.

Grading rubric

A 60 percent solution reads the input and prints the right distinct count and top item, using a dict. It may get the tie rule wrong, print the buyers unsorted, or miss the repeat line. It runs correctly on the first example but may fail on ties or on the second example.

An 80 percent solution prints all four lines correctly on both worked examples. It handles ties in the top item and in the buyers list, and it uses a set and sorted() for the repeat buyers. Its counts are right, but it may build strings in a clumsy way or use a slow pass over the data, such as a nested loop over the purchase lines.

A 100 percent solution does all of the above, and it is clean. It uses one pass over the input to build the dicts, a sorted() call with a key function for the ordering rules, and ", ".join(...) for the output. Each variable has a clear name. The program handles the case with fewer than three customers and the case with no repeat, and it runs in about linear time. Its code would survive a review by a colleague: no magic numbers without a comment, no unused variables, and no repeated code where a helper would do.

Your mark also depends on your explanation. If you can explain why a dict is right for counting, why the buyers list needs a sort, and why the repeat check uses a tuple of the customer and the item as its key, you have shown that you understand the module, not just the program.

Plan before you code

A good plan has four steps. Write them down before you type code.

1. Decide the data. You need three counts: purchases per customer, purchases per item, and purchases per (customer, item) pair. Choose a container for each. A dict works for all three, because you do not need an order while you count.
2. Read and count. Read all the tokens, take n, and loop n times. Read the customer and the item. Update the three dicts. Do not print anything inside this loop.
3. Answer each question. For the distinct count, use the length of the customer dict. For the top item, use min with a key function that sorts by highest count and then by name, so the tie rule comes out right. For the top buyers, sort the customer entries with a key of the negative count and then the name, and take the first three. For the repeat buyers, loop over the pair dict, and collect the customer names where the count is at least 2 into a set.
4. Print in the right format. Print the four lines in order. For the buyers list, build the string with ", ".join, and print none when the repeat set is empty.

Write the code in that order, and test after each step. A common mistake is to write everything at once and then find that one line is wrong in a way that is hard to see. Testing after each step makes the bug easy to find.

Hints

Try the plan first. If you are stuck, open one hint at a time. Each hint is a complete program that answers one part of the report. The sample input is written into the program as a string, so each one runs as it is, and you can check your understanding by changing the sample.

Reference solution

Try the assignment before you read this. The solution below uses the same ideas as the hints, combined into one program that prints all four lines. It makes one pass over the input, and it uses three dicts and two sorted results. Read it, and then close it and write your own version from memory. The second version is the one that teaches you the module.

import sys
 
data = sys.stdin.read().split()
n = int(data[0])
 
buys_by_user = {}
buys_by_item = {}
buys_of_pair = {}
for i in range(n):
    user = data[1 + 2 * i]
    item = data[2 + 2 * i]
    buys_by_user[user] = buys_by_user.get(user, 0) + 1
    buys_by_item[item] = buys_by_item.get(item, 0) + 1
    pair = (user, item)
    buys_of_pair[pair] = buys_of_pair.get(pair, 0) + 1
 
print("distinct users:", len(buys_by_user))
 
top_item, _ = min(buys_by_item.items(), key=lambda kv: (-kv[1], kv[0]))
print("top item:", top_item)
 
ranked = sorted(buys_by_user.items(), key=lambda kv: (-kv[1], kv[0]))[:3]
print("top buyers: " + ", ".join(f"{name} {count}" for name, count in ranked))
 
repeat = sorted({user for (user, _), count in buys_of_pair.items() if count >= 2})
print("repeat buyers: " + (", ".join(repeat) if repeat else "none"))

Read the code in the order the report is built. The first loop reads all the purchases and fills three dicts. The distinct count is just the length of the customer dict. The top item comes from min with a key that sorts by the negative count and then the name, so the highest count wins and the alphabetically first name wins a tie. The buyers list is a sorted call with the same kind of key, and the first three entries are joined with ", ". The repeat set collects the customers from the pair dict, and sorted puts them in order. The none text covers the empty case.

The code makes a few passes over dicts and lists, and each pass is linear, or n log n for a sort. The dicts take O(n) space in total, because each purchase adds at most one entry to each dict. A test with 100000 purchase lines, 5000 different names and long names ran in about 0.2 seconds on the machine used for this lesson, and the time will differ on other machines.

Stretch extension

When you have a correct solution, extend it. Add a line most bought by top buyer: ITEM that names the item the first-listed top buyer bought most often. Use the pair dict to find the count for each item that customer bought, and break ties alphabetically. Test it with the sample input, where asha bought book twice and pen once, so the answer is book.

A harder extension uses the cache from lesson 4. After the report, the program reads a list of customer names from the input and prints the last purchase count for each name. Keep only the two most recently asked names in an LRU cache, so repeated questions for the same name are answered from the cache. Print HIT or MISS for each question, as lesson 4 names each call a hit or a miss. This ties together the dict, the set, the sorted results and the cache from the whole module.

What this module covered

• A hash table turns a key into a bucket with a hash function, and collisions are handled by probing or chaining.
• A Python dict needs keys that are hashable, with == and hash that agree.
• A set answers "have I seen this?", and a sorted list with bisect answers nearest-key questions.
• get with a default, defaultdict and Counter replace most manual checks in counting and grouping code.
• Two-sum, frequency counting, anagram groups, duplicates, longest runs and prefix-sum subarray counts all follow the pattern of remembering what you have seen.
• An LRU cache combines a dict with a doubly linked list, and OrderedDict with move_to_end is the shortcut.