The bitcoin1 is a digital currency whose rate can strongly fluctuate from day to day. A good friend with predictive gifts has given you a table with the price of the bitcoin (in euros) for the next $$n \in \mathbb{N}_0$$ days. Your challenge is to use this information to maximize the profit you can make by trading bitcoins during that period. The following rules apply:
-
you do not have a bitcoin at the start of the period
-
you cannot have a bitcoin at the end of the period
-
you may never have more than one bitcoin
-
every day you can either buy one bitcoin (if you don't have one yet), sell your bitcoin (if you have one) or do nothing; you can never buy and sell a bitcoin on the same day
Your goal is to maximize your profit throughout the period. For larger values of $$n$$ it soon becomes intractable to evaluate all possibilities for trading bitcoins in order to see which of these options yields the maximum profit. However, there is a fast strategy to determine the maximum profit: only buy a bitcoin when the rate reaches a local minimum (cheap rate) and only sell the bitcoin when the rate reaches a local maximum (expensive rate). Here's a graphical representation of this strategy:
More formally, this greedy strategy prescribes that each day — except the last day — you need to take the following decisions:
-
if you don't have a bitcoin and bitcoins will become more expensive tomorrow, then buy a bitcoin today
-
if you do have a bitcoin and bitcoins will become cheaper tomorrow, then sell your bitcoin today
- in all other cases you don't trade any bitcoins today
The last day you sell your bitcoin if you have one, to make some extra profit.
If we apply this strategy to the example in the figure above, then we spend €5 to buy a bitcoin on the first day because bitcoins will become more expensive on day 2 (€11) and we don't have a bitcoin at the start of the period. The second day we receive €11 in selling our bitcoin because bitcoins become cheaper on day 3 (€4). The third day we do not buy a bitcoin because bitcoins will become even more inexpensive on day 4 (€2). If we continue in this way, we will ultimately make €17 profit in trading bitcoins.
Assignment
The rate of the bitcoin (in euros) throughout a period of $$n \in \mathbb{N}_0$$ consecutive days is represented as a sequence (list or tuple) containing $$n$$ positive integers (int).
The actions we carry out during such a period in which we trade bitcoins is represented as an $$n$$-character string (str). This string may only contain the following characters:
-
an uppercase letter B indicates that we buy one bitcoin that day
-
an uppercase letter S indicates that we sell one bitcoin that day
-
a hyphen (-) indicates that we do not trade bitcoins that day
Of course, these actions must comply with the rules regarding buying and selling bitcoins as stated in the introduction. Your task:
-
Write a function profit that takes two arguments: i) the rate $$r$$ of the bitcoin (in euros) throughout a period of $$n \in \mathbb{N}_0$$ consecutive days and ii) the actions $$a$$ we carry out during this $$n$$-day period. The function must return the profit (int; in euros) we make if we trade bitcoins during the $$n$$-day period according to the given actions, taking into account the given rate of the bitcoin during that period. The function must explicitly check that the following conditions hold for the actions $$a$$ that are passed to the function:
-
$$a$$ is a string (str)
-
$$a$$ contains the same number of characters as there are elements in $$r$$
-
$$a$$ only contains valid characters (B, S or -)
-
$$a$$ carries out no invalid actions: buying a bitcoin if you already have one, selling a bitcoin that you don't have or having a bitcoin after the last day of the period
In case at least one of these conditions does not hold, an AssertionError must be raised with the message invalid actions.
-
-
Write a function maximal_profit that takes the rate of the bitcoin (in euros) throughout a period of $$n \in \mathbb{N}_0$$ consecutive days. The function must return the maximum profit (int; in euros) that can be obtained by trading bitcoins during this $$n$$-day period, taking into account the rules for trading bitcoins and based on the greedy strategy outlined in the introduction. Note that the maximum profit may possibly be €0, since we are not obliged to buy or sell bitcoins during the $$n$$-day period.
-
Write a function optimal_actions that takes the rate of the bitcoin (in euros) throughout a period of $$n \in \mathbb{N}_0$$ consecutive days. The function must return the actions that we have to carry out during this $$n$$-day period to gain maximum profit when trading bitcoins, taking into account the rules for trading bitcoins and based on the greedy strategy outlined in the introduction.
All of these functions may assume that the first argument passed to the function is a valid representation of the rate of the bitcoin (in euros) throughout a period of $$n \in \mathbb{N}_0$$ consecutive days, without having to check this explicitly.
Example
>>> profit([5, 11, 4, 2, 8, 10, 7, 4, 3, 6], 'BS-B-S--BS')
17
>>> profit((4, 2, 5, 11, 10, 4, 11, 7, 4, 11, 3, 11), '-B-S-BS-BSBS')
31
>>> profit([10, 9, 9, 10, 10, 9, 1, 4, 9, 3, 5, 6, 10], '-B-S--B-SB--S')
16
>>> profit((12, 4, 9, 5, 6, 7, 9, 9, 11, 7, 10), '-BSB----SBS')
14
>>> profit([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], '----------')
0
>>> profit((10, 4, 2, 4, 8, 12), 'B---SS')
Traceback (most recent call last):
AssertionError: invalid actions
>>> maximal_profit([5, 11, 4, 2, 8, 10, 7, 4, 3, 6])
17
>>> maximal_profit((4, 2, 5, 11, 10, 4, 11, 7, 4, 11, 3, 11))
31
>>> maximal_profit([10, 9, 9, 10, 10, 9, 1, 4, 9, 3, 5, 6, 10])
16
>>> maximal_profit((12, 4, 9, 5, 6, 7, 9, 9, 11, 7, 10))
14
>>> maximal_profit([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
0
>>> maximal_profit((10, 4, 2, 4, 8, 12))
10
>>> optimal_actions([5, 11, 4, 2, 8, 10, 7, 4, 3, 6])
'BS-B-S--BS'
>>> optimal_actions((4, 2, 5, 11, 10, 4, 11, 7, 4, 11, 3, 11))
'-B-S-BS-BSBS'
>>> optimal_actions([10, 9, 9, 10, 10, 9, 1, 4, 9, 3, 5, 6, 10])
'--B-S-B-SB--S'
>>> optimal_actions((12, 4, 9, 5, 6, 7, 9, 9, 11, 7, 10))
'-BSB----SBS'
>>> optimal_actions([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
'----------'
>>> optimal_actions((10, 4, 2, 4, 8, 12))
'--B--S'