[Challenge] Maximize Stock Trading Profit

My answer using Python3 for basic with some optimisations (hard difficulty).

We first find the lowest and highest prices and if the days are in chronological order then just report the days. If this is not the case, then iterate through each day (if lower than the previous day) and calculate the maximum return.

https://repl.it/I12j/1

Feedback welcome, thanks.

Unfortunately repl.it doesn’t do Bash… This is the basic challenge, which has a higher complexity than the intermediate challenge…! We only trade if we can make a profit, otherwise an empty tuple is returned. So at least 2 day available in arr and a lower-price day has to occur before a higher-price day.

bestDays(){
  (($#<2)) && return 1  # can't trade
  # p(rice), d(ay), b(uy)/s(ell), c(andidate)
  local p d=0 bd=0 bp=0 sd sp=0 cbd cbp=0
  for p in $*
  do
    [[ $p =~ ^[1-9][0-9]*$ ]] || return 2  # only positive integers
    if ((cbp))
    then  # a new candidate for buying has already been found
      # if the price is lower, update the candidate, if not compare profits
      ((p<cbp)) && cbd=$d cbp=$p || {
        ((p-cbp>sp-bp)) && bd=$cbd bp=$cbp sd=$d sp=$p cbp=0
      }
    elif ((p<bp || bp==0))
    then  # lower price found (or the first day): pick it
      # if a selling day has been picked, update the candidate, otherwise the buy day
      ((sp)) && cbd=$d cbp=$p || bd=$d bp=$p
    else  # it's not lower: if it's higher than the current best selling day, pick it
      ((p>sp)) && sd=$d sp=$p
    fi
    ((++d))
  done
  ((bp<sp)) && echo "$bd $sd"  # only return profitable trades
}

Call as: bestDays 17 11 60 25 150 75 31 120

2 Likes

Again, repl.it doesn’t do Bash… This is the intermediate challenge, which was less complex than the basic challenge…! A profitable sequence of buy and sell pairs (no multidimensional arrays in bash…) is returned, empty if no profitable trade exists. So at least 2 day available in arr and a lower-price day has to occur before a higher-price day.

bestDays(){
  (($#<2)) && return 1  # can't trade
  # l(ast), b(uy)/s(ell), d(ay)/p(rice), t(rades)
  local ld lp=0 bd=0 bp=0 sd=0 sp=0 p d=0 t=()
  for p in $*
  do
    [[ $p =~ ^[1-9][0-9]*$ ]] || return 2  # only positive integers
    ((bp==0)) && bd=$d bp=$p lp=$p && ((++d)) && continue  # first day
    ((p>lp)) && sd=$d sp=$p  # a higher price found: potential sell
    if ((sd))
    then  # potential sell already found
      # record the found buy-sell pair if a new good buy is found or we're at the end 
      ((p<lp || $#==d+1)) && t[$bd]=$bp t[$sd]=$sp bd=$d bp=$p sd=0
    else  # no sell found yet, so the price is equal or lower than any before
      bd=$d bp=$p
    fi
    # remember the previous day's price and go to the next day
    lp=$p
    ((++d))
  done
  echo "${!t[@]}"  # the indexes (array with buy-sell day pairs)
}

Call as: bestDays 90 170 250 300 30 525 685 90

2 Likes

Adding my solution to the intermediate problem. For each day we check the next days return and if it’s positive then we buy if we have no open position. If it’s negative then we sell if we have an open position. On the final day, close any open positions.

https://repl.it/I2v8

Basic solution (ish…) I think this is more complicated in a way than the intermediate, where you can just step through the loop once, no need to scan for maximum or minimums. Yes it’s long, but it covers all the exceptional cases I could think of. It sacrifices code conciseness for error prevention and hopefully a little bit of speed. I am assuming that the input will not always be one week, so that requires a bit of tweaking for large and small inputs.

https://repl.it/I2dJ/16

And here is my intermediate. Much shorter! Similar method to others, with a check for short input at the start and ever-decreasing prices at the end (as suggested in the first comment).

https://repl.it/I2d3/14

Here’s my ruby solution to the basic problem.

def bestDays(values)
  possible=Hash.new #Creates an empty hash to store all the possible buy/sell combinations.
  values..select { |x| values.index(x)!=-1 }.each do |value| #Loops through all the values except the final one.
    value_index=values.index(value) #To maximise efficiency, finds the index of value here (therefore only once per value).
    values.select { |x| values.index(x)>value_index }.each do |value1| #Loops through all the values after value.
      possible[-value+value1]={buy: value, sell: value1} #Adds a key/value pair to possible. The key is the profit after buying and selling and the value is another hash with information on when to buy/sell.
    end
  end
  possible[possible.keys.max] #Returns the value (which will be a hash) with the highest key in the hash of buy/sell combinations.
end

My repl script (without the comments)

Basic level:Didnt find a max-function in Python??

https://repl.it/IZKo/9

Just wanted to say, I’m learning some Bash scripting so this is really interesting for me. Thanks for sharing!

This is in Haskell here. I just started learning it so I’m sure it could be done better. This is not the most efficient solution, but it is the shortest and clearest I could write.

import Data.List

bestDays :: [Int] -> (Int, Int)
bestDays = fst . bestPair
    where
    bestPair = maximumBy comp . factorialList
    comp (_, a) (_, b) = compare a b

factorialList :: [Int] -> [((Int, Int), Int)]
factorialList xs = [((fst buy, fst sell), snd sell - snd buy) | buy <- zipxs, sell <- zipxs, fst buy < fst sell]
    where zipxs = zip [0..] xs

Hi there,

Here are my solutions in Python.

Basic problem
Intermediate problem

Adrien

Hi all

Had some fun working on these. Two completely different strategies for the two problems

Basic problem

The idea is to find any pair of buy/ sell days which maximise the profit. I calculated the profit as price(sell) / price(buy) rather than a simple subtraction, although in this case it gives the same result. I created a triangular matrix with every possible buy day, and each possible sell day following on. These entries are the keys for a dictionary, with the values being the profit calculated as above. The trick is using some list comprehension trickery to get Python to do al the work for me! Then I use a max() function with the key argument to find the dictionary entry with the highest profit.

Intermediate problem

In some ways, the strategy for this is easier. I just look for any day immediately followed by a price rise to buy on; and any day just before a fall to sell on. If only we could do that looking forward in time rather than backwards!

Link to working code in repl.it

Not sure if the embed thing is going to work though! Just in case:

import unittest

pricesBasic = ( 17, 11, 60, 25, 150, 75, 31, 120 )
pricesIntermediate = ( 90, 170, 250, 300, 30, 525, 685, 90 )

def bestDaysBasic(prices):
    
    n = len(prices)    # shorthand, used later
    
    # make a dictionary of (buyday, sellday) : profit 
    # based on a nested comprehension of all pairs of days
    # with sellday coming after buyday
    gains = { (b,s) : prices[s] / prices[b] for (b,s) in \
            [(buy, sell) for buy in range(n)  for sell in range(buy+1,n)] \
            }
    # get the (b,s) key from the dictionary by looking up the highest value of profit
    return max(gains.keys(), key=lambda x: gains[x])
  

def bestDaysIntermediate(prices):
    ret = []
    sell = -1   # preseed the value
    
    while True:
        # buy cannot be on the same day as sell
        buy = sell + 1
        # keep looking until the following day doesn't go down
        while buy < len(prices) - 2 and prices[buy] > prices[buy + 1]:
                buy += 1

        # sell cannot be on same as buy
        sell = buy + 1
        # keep looking until the following day doesn't go up
        while sell < len(prices) - 1 and prices[sell] < prices[sell + 1]:
                sell += 1

        # get out if we hit the end of the list
        if sell == len(prices): 
            break

        # as long as we found rise in price, remember it
        if prices[buy] < prices[sell]:
            ret.append((buy, sell))

    return ret


# classic Test Led Design...
# but repl.it won't run it unfortunately
class TestBasic(unittest.TestCase):
    def test_Basic(self):
        self.assertEqual(bestDaysBasic(pricesBasic), (1,4))

    def test_Intermediate(self):
        self.assertEqual(
                bestDaysIntermediate(pricesIntermediate), 
                [(0,3), (4,6)]
        )


# if __name__ == '__main__':
    # unittest.main()
    
print(bestDaysBasic(pricesBasic))
print(bestDaysIntermediate(pricesIntermediate))

Tim F

I spent more time than I initially thought I would, so I thought I’d better share it…!
If you have any questions, don’t hesitate to ask, I have not held back in the usage of language features, and bash can be quite powerful. (But slow… But, very portable and widely installed…!)

1 Like

Hi!
My programming skills are kind of rusty so I thought solving this challenge can get me back on track. Here’s my solution to basic and intermediate assignments. It’s written in Python3.
Basic ( https://repl.it/I5Ne/1 )
Two for-functions that look for the best combination of selling and buying. The diff variable stores the maximum profit that was noticed. At the end program returns the daybuy and daysell corresponding to that maximum profit.

def bestDays(values):
	# buy and sell only once 
	diff=0
	daybuy=0
	daysell=1
	for i in range(0, len(values)-1):
		for j in range(i+1, len(values)):
			if values[j]-values[i] > diff: 
				diff = values[j]-values[i]
				daybuy=i
				daysell=j
	return daybuy, daysell

Intermediate ( https://repl.it/I5Nk/1 )
This one took me longer than expected. So it ended up being lengthy… but it works! :slight_smile:
In first step I am making a table of profits, compared like in the basic level, but I store the profit and the dates in to result table. In the second step I am looking for the all possible combinations of buying and selling so that the new buy dates are after the previous sell date. This is the part with two for functions and a while function… Cause I needed to take into account what if there is a possibility to make more than 2 buys and sells… The third step searches my combinations table for the highest profit and the fourth step prepares the result.

def bestDays(values):
	# buy and sell multiple times
	results = []
	#get an array of positive income
	for i in range(0, len(values)):
		for j in range(i+1, len(values)):
			if values[j]-values[i] > 0:
				results.append([values[j]-values[i], i, j])

	combinations=[]
	# for every element in array of positive income match other elemetns which don't overlap with their buy dates
	for i in range(0,len(results)-1):
		sum_profit=0
		k=i
		combinations.append([])
		combinations[i].append(1)
		combinations[i].append(results[i])
		sum_profit=results[i][0]
		last_sell_date=results[i][2]
		while k<len(results):
			k=k+1
			for j in range(k, len(results)-1):
				if last_sell_date<results[j][1]:
					combinations[i].append(results[j])
					last_sell_date=results[j][2]
					sum_profit=sum_profit+results[j][0]
		combinations[i][0]=sum_profit

	#search the array
	maximum=0
	pattern=[]
	for element in combinations:
		if element[0] > maximum:
			maximum=element[0]
			pattern=element

	#prepare the result
	final_result=[]
	pattern.pop(0)
	for element in pattern:
		final_result.append([element[1], element[2]])
	return final_result

Thanks for the challenge!

Solution to the Intermediate difficulty in Java. Find the explanation in the comments
.
https://repl.it/I4Mt/75

1 Like

Intermediate level (Ruby)

Code is at https://repl.it/I5Lz/1
of course, recursive function is a first thought. Starting as in the Basic level: calcuclate the result of single transaction with specified Buy and Sell Day (say From 3 To 4) - and add the cumulated best result from the next day (recursive call: From 5 To End). But - wait: I’ve to compute that many times - it will be needed also f.e. calculating the result from 2 To 4. OK - lets store the results in a table and compute it only once if it wasn’t calculated already.
Well - if we start to fill that table from the end (last day) to the begining - no recursion will be necessary. Of course, the value at the day 0 in this table is a result we’re looking for. As we’re required to do at least one transaction - it’ll be better not to store only positive results, but also negative ones (moving from the day K to K-1 we can copy the best solution for the day K - we can obtain only better one). So we have still O(n^2) complexity.

def bestDays(a)
  best, days, last = [], [], a.size-1
  best[last-1] = a[last] - a[last-1]; days[last-1] = [last-1, last]
  (last-2).downto(0).each do |from|
    best[from], days[from] = best[from+1], days[from+1]
    (from+1..last).each do |to|
      res = a[to] - a[from]
      best[from], days[from] = res, [from, to] if best[from] < res
      if to+2 < a.size && res + best[to+1] > best[from] # && best[to+1] > 0 
        best[from] = res + best[to+1]; days[from] = [ [from, to], days[to+1] ]
      end
    end
  end
  return days[0][0].class == Array ? days[0] : [days[0]]
end

test =  [90, 170, 250, 300, 30, 525, 685, 90]
result = bestDays test
result.each {|bs| p "Buy at #{bs[0]} - Sell at #{bs[1]};"}
test = [5, 4, 3, 2, 1, 0]
result = bestDays test
result.each {|b| p "Buy at #{b[0]} - Sell at #{b[1]};"}

https://repl.it/I5Lz/1

Basic level (Ruby)

I must traverse the list at least once (trivial remark). The simplest solution is to compare at each step the price difference to all the remaining days - this the complexity of O(n^2). Rest is straightforward:

def bestDays(a)
  best, from, to = nil, nil, nil
  (0...a.size).each do |buy|
    (buy+1...a.size).each do |sell|
      best, from, to = a[sell] - a[buy], buy, sell if !best || best < a[sell] - a[buy]
    end
  end
  return [from, to]
end

test =  [17, 11, 60, 25, 150, 75, 31, 120]
result = bestDays test
p "Buy at #{result[0]} sell at #{result[1]} yielding #{test[result[1]] - test[result[0]]}"
test = [5, 4, 3, 2, 1, 0]
result = bestDays test
p "Buy at #{result[0]} sell at #{result[1]} yielding #{test[result[1]] - test[result[0]]}"

https://repl.it/I5NR/0

Basic level (Ruby) - O(n) solution

Code is at https://repl.it/I5RH/0
It was veeeery unfair from the challenge jury: of course, i’ve started from the basic level, after that I’ve made my intermediate solution, send the second first, then the first - and then: Eureka - maybe it can be done ALSO by single pass. I’ve rad a science-fiction novel once, when the astronauts was given the fuel for only the HALF of the trip. And - of course - they’ve invented brand new engine for ther rocket.
We’ve to start from the very last possible transaction (al least one have to be done) - Buy the day last-1, Sell the last day. It is our best score so far, remember both prices (and their days). Then start our backward time machine: if the price the previous day is lower than the best Buy price so far - its our new Buy price (and the result is better, remeber it). If the price is higher than the best Sell price so far - remember it as a candidate for better bid (the first candidate price is also the rice of the last possible day). And if the price difference between current day (Buy) and candidate (Sell) is greater than the best score so far - bingo, we have next, higher bid.
Single pass, three variables, complexity of O(n). The code:

def bestDays(a)
  return "data too short" if a.size < 2  
  last = a.size - 1
  bestBuy = a[last-1]; dayBuy = last-1 
  canSell = bestSell = a[last]; dayCan = daySell = last; best = bestSell - bestBuy
  (last-2).downto(0) do |day|
    if a[day] > canSell
      canSell = a[day]; dayCan = day
    elsif a[day] < bestBuy
      bestBuy = a[day]; dayBuy = day; daySell = dayCan; bestSell = canSell; best = bestSell - bestBuy
    elsif canSell - a[day] > best
      bestBuy = a[day]; dayBuy = day; daySell = dayCan; bestSell = canSell;  best = bestSell - bestBuy
    end
  end
  return [dayBuy, daySell]
end

test =  [17, 11, 60, 25, 150, 75, 31, 120]
result = bestDays test
p "Buy at #{result[0]} sell at #{result[1]} yielding #{test[result[1]] - test[result[0]]}"
test = [5, 4, 3, 2, 1, 0]
result = bestDays test
p "Buy at #{result[0]} sell at #{result[1]} yielding #{test[result[1]] - test[result[0]]}"

My contribution was nicked then extended, but I had to know what to look for right?? Some credit. Too much duplication etc etc, but I’m just pleased to have something that works!!

Basic as you like: https://repl.it/I7MQ/5


  function bestDays(arr) {
  //simple check of the array
    if (arr.length === 0) {
        return -1;
    }

    var max = arr[0];
    var min = arr[0];
    var maxIndex = 0;
    var minIndex = 0;

    for (var i = 1; i < arr.length; i++) {
      //iterate through and set the values to check against max and set the index of the highest for use later
        if (arr[i] > max) {
            maxIndex = i;
            max = arr[i];
        }
    }
    
    for (var j = 1; j < arr.length; j++) {
      //as above but for min value. Duplicating is bad, right?
        if (arr[j] < min) {
          minIndex = j;
          min = arr[j];
        }
    }

    console.log("buy on day: ", minIndex);
    console.log("sell on day: ", maxIndex);
    return maxIndex;
}

bestDays([90, 170, 250, 300, 30, 525, 685, 90]);

Your code is nice and readable, but there is a problem with it you can look to address: your code allows maxIndex to be lower than minIndex, meaning it will return values that claim you should sell before you bought anything. Try adding some code that prevents the maxIndex to be lower than the minIndex, either by adding explicit code or by changing the flow of the code (i.e. the order in which code is executed) with some minor additional comparators.
Good luck!

2 Likes