Syllabus Lesson 137 of 141 · Ten doors and the field kit
Ten doors and the field kit

Door 1: stock on any day

Why it matters The capstone doors mix the moves from the whole course. This one needs a reframe and has a budget. Nothing tells you which reframe.

A warehouse records every stock movement: goods in, goods out, each with a day number and a quantity. Auditors send a batch of questions, "how many of item X did we hold at the end of day D?", thousands at a time, for any day of the year.

The data

moves = [(3, "mug", 10), (1, "mug", 5), (3, "mug", -4), (2, "lamp", 7), (9, "mug", -20)]
queries = [("mug", 0), ("mug", 1), ("mug", 3), ("lamp", 300), ("mug", 9), ("fan", 5)]
stock_on(moves, queries)   # -> [0, 5, 11, 7, -9, 0]

Stock can go negative (back orders). Moves arrive in no particular order.

Your turn

Write stock_on(moves, queries). moves is a list of (day, item, qty) in any order (qty is positive for goods in, negative for goods out; several moves can share a day). queries is a list of (item, day). Return a list with, for each question, the item's stock at the end of that day: the sum of its quantities with move day <= day (0 if none, and 0 for an item never seen). Budget: with 8,000 moves, 20 items and 8,000 questions, your code may run at most 320,000 steps (steps(), lines of your own code), and in that test moves arrives as a Tape you may read at most 40,000 times (five passes). Sorting it or copying it reads it once.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus