A budgeting app wants to show a user the worst stretch of their year: the largest fall of the account balance from an earlier high point to a later low point.
The account starts at opening cents. statements is a list of monthly statements; each statement is a one-pass stream of changes in cents (positive for money in, negative for money out), and the months follow each other in order. Number the balances along the whole year: position 0 is the opening balance and position j is the balance after the j-th change of the year.
Write deepest_dip(opening, statements) that returns (depth, peak, trough): the largest value of balance[a] - balance[b] over positions a < b, with a and b the positions where it happens. When several pairs give the same depth, use the smallest b, and for that b the smallest a whose balance is the highest before b. If the balance never falls below an earlier value, return (0, None, None).
Helpers you can use with Run: stream(items) (a list as a one-pass stream), statement(seed, n) (one generated month of n changes) and year(seed, months=12, days=30) (a list of such months).
Examples
Input: deepest_dip(100, [stream([50, -80]), stream([30, -120, 200]), stream([-10])])
Output: (170, 1, 4)
Explanation: the balances are 100, 150, 70, 100, -20, 180, 170; from 150 at position 1 down to -20 at position 4.
Input: deepest_dip(0, [stream([5, 5]), stream([])])
Output: (0, None, None)
Constraints
- Up to 24 statements of up to 20,000 changes each; amounts are integers.
- Each statement can be read only once.
Goals
- Read several streams as one with `itertools.chain.from_iterable`
- Turn changes into running balances with `itertools.accumulate` and its `initial` argument
- Track a running maximum and the largest fall below it in one pass