Problem 137150 · hard · Level 01 Prerequisites & Setup

Oldest Shares Sell First

dictionaries · lists as queues · tuples · state · py-dicts · py-lists · py-tuples · py-functions

You are writing the bookkeeping for a small share-trading app. transactions is a list of tuples, processed in order:

  • ("buy", ticker, qty, price): buy qty shares of ticker at price each. They form a new lot (qty, price), placed after that ticker's older lots.
  • ("sell", ticker, qty, price): sell qty shares at price each. Shares are always taken from the oldest lot first; if that lot runs out, the rest comes from the next oldest, and so on. Each share sold earns price minus the price of the lot it came from (a loss is a negative profit). If the account holds fewer than qty shares of that ticker in total, the whole sell is rejected and nothing changes.
  • ("split", ticker, factor): every lot (q, p) of that ticker becomes (q * factor, p / factor). A split of a ticker with no lots does nothing.

Write ledger(transactions) that returns a tuple (profits, holdings, rejected):

  • profits: a dictionary from every ticker that was ever bought to its total realised profit so far (0.0 if nothing was sold);
  • holdings: a dictionary from every ticker that still has shares to its list of lots (qty, price), oldest first;
  • rejected: the positions (0-based) of the rejected sells, in order.

Money values are compared with a small tolerance. The helper trade_log(n, seed) returns n random transactions.

Examples

Input:  transactions = [("buy", "ACME", 10, 5.0), ("buy", "ACME", 5, 8.0),
                        ("sell", "ACME", 12, 9.0), ("sell", "ACME", 4, 9.0),
                        ("split", "ACME", 2), ("sell", "ACME", 2, 5.0)]
Output: ({"ACME": 44.0}, {"ACME": [(4, 4.0)]}, [3])
Explanation: the first sell takes all 10 shares of the 5.0 lot (profit 40) and 2 of
the 8.0 lot (profit 2), leaving (3, 8.0). Selling 4 is rejected: only 3 are held.
The split turns (3, 8.0) into (6, 4.0); selling 2 at 5.0 earns 2 more.

Input:  transactions = [("buy", "BOLT", 3, 2.5), ("buy", "CRUX", 1, 100.0),
                        ("sell", "BOLT", 3, 2.0), ("sell", "DUSK", 1, 1.0)]
Output: ({"BOLT": -1.5, "CRUX": 0.0}, {"CRUX": [(1, 100.0)]}, [3])

Constraints

  • 0 <= len(transactions) <= 20000
  • 1 <= qty <= 1000, 0 < price <= 10**4, factor is 2 or 3
  • the result does not depend on randomness or the clock

Goals

  • Keep per-key state in a dictionary of lists of tuples and update it transaction by transaction
  • Make an all-or-nothing change: check first, then modify
  • Rebuild tuples instead of trying to change them in place
Starting Python…