Reduce method in the stock picker exercise?-CodePudding

The problem gives an array where each index is the price of a stock in each day:

array = [17,3,6,9,15,8,6,1,10]

For example, 1st of November the price is $17, 2nd of November the price is $3, 3rd of November the price is $6, etc.

I have to find the best days to buy and sell, so it should return [#{buy_day}, #{sell_day}]

The correct answer in this case is [1, 4] for a profit of $12 (buy at $3 and sell at $15). To do this, I used the reduce method and it works fine, but I was told I am not using the reduce method correctly.

stock = [17,3,6,9,15,8,6,1,10]
stocks_new = [17,3,6,9,15,8,6,1,10]
best_profit = 0
days = []

stock.length.times do |day|
  stocks_new.reduce do |acc, val|
    acc = stocks_new[0]
    profit = val - acc
    if profit > best_profit
      best_profit = profit
      days = [stock.index(acc), stock.index(val)]
    end
  end
  stocks_new.shift
end

I first copied the array onto another variable (stocks_new), and I shift at the end of every loop. I do this to avoid the val in |acc, val| from starting behind the accumulator in the iteration.

Is there a way to set the val in reduce method to start from the acc 1 index on each iteration so i don't have to create this stocks_new array and shift each time?

CodePudding user response：

Not sure about reduce method issue, but maybe you could consider a one-pass solution, that does not need any copying:

def max_profit(stock)
    min_price = (1 << 31) - 1  # stock.max
    max_profit = 0
    min_day_index = 0
    sell_day = 0
    buy_day = 0
    stock.each_with_index do |price, day_index|
        if price < min_price
            min_price = price
            min_day_index = day_index
        end
        profit = price - min_price
        if profit > max_profit
            max_profit = profit
            sell_day = day_index
            buy_day = min_day_index
        end
    end
    max_profit > 0 ? [buy_day, sell_day] : "Cannot make profit"
end

CodePudding user response：

The straightforward way to solve this problem, as suggested by @steenslag in a comment, is

(0..arr.size-1).to_a.combination(2).max_by { |i,j| arr[i]-arr[j] }

This requires (n^2)/2 calculations, where n is the size of the array.

Code

I am going to focus on a more complex solution that I believe greatly reduces solution times for larger arrays.

def best_sell_buy(arr)
  last_idx = arr.size-1
  start_buy_idx = 1
  sell_idx = 0
  best = -Float::INFINITY
  best_sell_buy = []
  loop do
    buy_idx = (start_buy_idx..last_idx).min_by { |i| arr[i] }
    sell_idx = 
    if buy_idx == 1
      0
    else
      [sell_idx, *start_buy_idx-1..buy_idx-1].max_by { |i| arr[i] }
    end
    cand = arr[sell_idx] - arr[buy_idx]
    if cand > best
      best = cand
      best_sell_buy = [sell_idx, buy_idx]
    end
    break if buy_idx == last_idx
    start_buy_idx =  buy_idx   1
  end
  best_sell_buy
end

Examples

arr = [17, 3, 6, 9, 15, 8, 6, 1, 10]
best_sell_buy(arr) # 2 iterations
  #=> [0, 7]
arr[0]
  #=> 17 (sell in period 0)
arr[7]
  #=> 1 (buy in period 7)

prices = (100..300).to_a
  #=> [100, 101, 102,..., 299, 300]

arr = 100.times.map { prices.sample }
  #=> [254, 167, 182, 282, 119, 242, 181, 218, 269, 275,
  #    ... (80 elements)
  #    255, 187, 205, 145, 189, 290, 254, 299, 224, 218]   b 
best_sell_buy(arr) # 4 iterations
  #=> [31, 88]
arr[31]
  #=> 299 (sell in period 31)
arr[88]
  #=> 104 (buy in period 88)

arr = 100_000.times.map { prices.sample }
best_sell_buy(arr) # 468 iterations
  #=> [110, 427]
arr[110]
  #=> 300 (sell in period 110)
arr[427]
  #=> 100 (buy in period 427)

I will explain what I mean by "iterations" in the next section.

The last example is not surprising, as 100,000 samples are drawn from a population of size 201, so there are many duplicates. In fact, a solution which sells at the maximum value (300) and buys at the minimum value (100) is found within the first 428 elements, so no improvement is possible after that.

Explanation

I will explain what's happening in terms of an example:

arr = [5, 13, 6, 9, 1, 4, 17, 2, 10]

The first step is to obtain the index of the smallest value (buy):

i = arr.size.times.min_by { |i| arr[i] }
  #=> 4 (arr[4] => 1)

Next we obtain the largest value (sell) that precedes this minimum value (i.e., in arr[0..i-1] #=> arr[0..3]):

j = arr[0..3].max_by { |j| arr[j] }
  #=> 1 (arr[1] => 13)

We have now found the optimal solution for the array arr[0..4], which we save:

best_sell_buy = [1, 4]
best = arr[1] - arr[4] #=> 12

Next, we find the minimum value in the remainder of the array that follows the index of the smallest value just found (arr[i 1..-1]):

i = arr[5..-1].min_by { |i| arr[i] }
  #=> 7 (arr[7] => 2)

We now determine the best sell period for this buy period. Previously we have considered periods 0..3, of which 1 was best. We therefore must consider the periods 4..6, as well as our previously-found maximum in period 1:

j = [1, *4..6].max_by { |i| arr[i] }
  #=> 6 (arr[6] #=> 17)

Selling in period 6 for 17 and buying in period 7 for 2 nets 15. As this is greater than

best #=> 12

we set

best_sell_buy = [6, 7]
best = 15

We now have an optimal solution for the array arr[0..7].

Lastly, we compute

i = arr[8..-1].min_by { |i| arr[i] }
  #=> 8 (arr[8..-1] => [10])

and

j = [6, 7].max_by { |j| arr[j] }
  #=> 6

arr[6] - arr[8] = 17 - 10 = 7 < 15 (= best)

and i indexes the last element of arr, we conclude the optimal solution (for arr) is [6, 7].

This example required three "iterations" if I regard the calculation of each i, j pair as being one iteration. I've shown the numbers of iterations required to solve each of the earlier examples.