Stretch 1

Parse a receipt

A receipt is one string with one line per item, each line being <item> x <quantity> @ <price>. Write receipt_total(text) that returns the total cost. Lines may have extra spaces at the ends; blank lines are skipped.

receipt_total("bread x 3 @ 25\nmilk x 2 @ 2.5")  ->  80.0
receipt_total("")                                  ->  0

def receipt_total(text):
    ...

Top sellers

sales is a list of item names, one per sale. Write top_sellers(sales, k) that returns the k most sold items as (item, count) tuples, most sold first. Items with the same count are ordered alphabetically. k may exceed the number of distinct items.

top_sellers(["milk", "bread", "milk", "apple", "bread", "milk"], 2)  ->  [("milk", 3), ("bread", 2)]

def top_sellers(sales, k):
    ...

A day at the bakery

All of the day's orders are waiting when the bakery opens, as (priority, name) tuples with distinct priorities, where a smaller number means more urgent. The bakery makes one order per hour, always the most urgent one still waiting. Write schedule(orders, hours) that returns the names made in the first hours hours, in order. If the bakery runs out of orders early, the list is shorter.

schedule([(3, "bread"), (1, "cake"), (2, "rolls")], 2)  ->  ["cake", "rolls"]
schedule([(1, "cake")], 5)                              ->  ["cake"]

import heapq

def schedule(orders, hours):
    ...

Anagram groups

Two words are anagrams if they use exactly the same letters. Write anagram_groups(words) that groups the words into lists of anagrams, with each group in original order, and the groups sorted by their first word.

anagram_groups(["tea", "eat", "tan", "ate", "nat", "bat"])  ->  [["bat"], ["tan", "nat"], ["tea", "eat", "ate"]]

def anagram_groups(words):
    ...

Longest streak

daily is a list of how many loaves were sold each day. Write longest_streak(daily, target) that returns the length of the longest run of consecutive days with sales of at least target.

longest_streak([5, 12, 14, 3, 10, 11, 15], 10)  ->  3
longest_streak([1, 2], 10)                      ->  0

def longest_streak(daily, target):
    ...

Expand shelf ranges

Shelf labels are given as a string like "3-5, 8, 10-11": comma-separated, each part either a single number or a range a-b inclusive. Write expand(text) that returns the full list of numbers in order.

expand("3-5, 8, 10-11")  ->  [3, 4, 5, 8, 10, 11]
expand("7")              ->  [7]

def expand(text):
    ...

Pairs that make a price

Write pairs_summing(prices, target) that returns how many pairs of positions (i, j) with i < j have prices[i] + prices[j] == target.

pairs_summing([10, 30, 20, 30], 40)  ->  2     (10+30 at positions 0,1 and 0,3)
pairs_summing([5], 10)               ->  0

def pairs_summing(prices, target):
    ...

A queue with VIPs

Customers arrive as (name, is_vip) tuples. VIPs go to the front of the line, behind any VIPs already there; everyone else joins the back. Write serving_order(arrivals) that returns the order in which everyone is served.

serving_order([("Ada", False), ("Grace", True), ("Linus", False), ("Ken", True)])  ->  ["Grace", "Ken", "Ada", "Linus"]

from collections import deque

def serving_order(arrivals):
    ...

Compress repeated letters

Write compress(text) that replaces each run of the same character with the character followed by the run length, leaving single characters alone.

compress("aaabccdddd")  ->  "a3bc2d4"
compress("abc")         ->  "abc"
compress("")            ->  ""

def compress(text):
    ...

Undo and redo

actions is a list of strings: "undo" cancels the most recent action in effect, "redo" restores the most recently undone action, and anything else is a new action. A new action clears the redo history. Write final(actions) that returns the actions in effect, in order. Undo or redo with nothing to act on is ignored.

final(["a", "b", "undo", "redo"])        ->  ["a", "b"]
final(["a", "b", "undo", "c", "redo"])   ->  ["a", "c"]
final(["undo", "redo", "a"])             ->  ["a"]

def final(actions):
    ...

Next: Stretch 2.