I am solving the stock picking problem, where I try and find the optimal buy and sell dates given an array of stock prices. I solved the problem with the following code, which works.

def stock_picker(price_list)
  """Returns the largest profit possible given the array of prices""" 
  #should not be able to purchase on the last date
  avalable_purchase_dates = price_list[0..-2]
  maximized_profit = avalable_purchase_dates.reduce(-(Float::INFINITY)) do |profit, buy_price|
    available_sell_prices = price_list[price_list.index(buy_price) 1, price_list.length] 
    max_profit = (available_sell_prices.map {|sell_price| sell_price-buy_price}).max
    profit = [profit, max_profit].max 
  end
  return maximized_profit #, buy ,sell
end

b = stock_picker([137,3,6,9,15,8,6,1,10,19,-4]) #returns 18
print (b)

The logic of the code is that it looks at the prices on each date and calculates the maximum profit possible if purchased at this price, and if the potential profit is larger than the aggregator, it sets the aggregator equal to the potential profit.

I was wondering if there was a way to avoid having to set the default value of my reduce method aggregator to negative infinity. I set the default to negative infinity so that the first potential profit will be greater and thus the aggregator will be set to that value. I want to be able to just avoid that altogether and have ruby perform the callback for each array value and set the default to the first calculation and not a specific value. My current solution is easy to get confused and write the logic incorrectly, for example if I had set the default to zero, my solution would not work for a decreasing series of prices.

Thanks!

CodePudding user response：

Does this work for you? It bypasses all intricacies of inject.

def stock_picker(price_list)
  price_list.combination(2).max_by{|buy_price, sell_price| sell_price - buy_price}
end

p stock_picker( [137,3,6,9,15,8,6,1,10,19,-4]) # =>[1, 19]

CodePudding user response：

You will want to make a single pass through the array. I assume that before calling the method you have checked that the array of prices contains at least two elements.

def stock_picker(prices)
  best_buy_period = prices[1] < prices[0] ? 1 : 0
  (2..prices.size-1).reduce(buy:0, sell: 1, profit:prices[1]-prices[0]) do |best,i|
    candidate = prices[i]-prices[best_buy_period]
    best = { buy:best_buy_period, sell:i, profit:candidate } if
      candidate > best[:profit]
    best_buy_period = i if prices[i] < prices[best_buy_period]
    best
  end
end

price_list = [137,3,6,9,15,8,6,1,10,19,-4]
  #=>{:buy=>7, :sell=>9, :profit=>18}

We can follow what's happening by adding some puts statements.

def stock_picker(prices)
  best_buy_period = prices[1] < prices[0] ? 1 : 0
  (2..prices.size-1).reduce(buy:0, sell:1, profit:prices[1]-prices[0]) do |best,i|
    puts "i = #{i}, best_buy_period = #{best_buy_period}, best = #{best}"
    candidate = prices[i]-prices[best_buy_period]
    puts "best = #{best}, candidate = #{candidate}"        
    best = { buy:best_buy_period, sell:i, profit:candidate } if
      candidate > best[:profit]
    best_buy_period = i if prices[i] < prices[best_buy_period]
    best
  end
end

stock_picker(prices)
  #=>{:buy=>7, :sell=>9, :profit=>18}
i = 2, best_buy_period = 1, best = {:buy=>0, :sell=>1, :profit=>-134}
best = {:buy=>0, :sell=>1, :profit=>-134}, candidate = -1
i = 3, best_buy_period = 2, best = {:buy=>1, :sell=>2, :profit=>-1}
best = {:buy=>1, :sell=>2, :profit=>-1}, candidate = 7
i = 4, best_buy_period = 2, best = {:buy=>2, :sell=>3, :profit=>7}
best = {:buy=>2, :sell=>3, :profit=>7}, candidate = 13
i = 5, best_buy_period = 2, best = {:buy=>2, :sell=>4, :profit=>13}
best = {:buy=>2, :sell=>4, :profit=>13}, candidate = 6
i = 6, best_buy_period = 2, best = {:buy=>2, :sell=>4, :profit=>13}
best = {:buy=>2, :sell=>4, :profit=>13}, candidate = 4
i = 7, best_buy_period = 2, best = {:buy=>2, :sell=>4, :profit=>13}
best = {:buy=>2, :sell=>4, :profit=>13}, candidate = -1
i = 8, best_buy_period = 7, best = {:buy=>2, :sell=>4, :profit=>13}
best = {:buy=>2, :sell=>4, :profit=>13}, candidate = 9
i = 9, best_buy_period = 7, best = {:buy=>2, :sell=>4, :profit=>13}
best = {:buy=>2, :sell=>4, :profit=>13}, candidate = 18
i = 10, best_buy_period = 7, best = {:buy=>7, :sell=>9, :profit=>18}
best = {:buy=>7, :sell=>9, :profit=>18}, candidate = -5

Note that ...reduce(buy: 0, sell: 1, profit: prices[1]-prices[0]) do... is shorthand for ...reduce({ buy: 0, sell: 1, profit: prices[1]-prices[0] }) do....

The method can alternatively be written as follows.

def stock_picker(prices)
  best_buy_period = prices[1] < prices[0] ? 1 : 0
  (2..prices.size-1).each_with_object(buy:0, sell:1, profit:prices[1]-prices[0]) do |i,best|
    candidate = prices[i]-prices[best_buy_period]
    best.replace(buy:best_buy_period, sell:i, profit:candidate) if
      candidate > best[:profit]
    best_buy_period = i if prices[i] < prices[best_buy_period]
  end
end

CodePudding user response：

As a middle ground, you can iterate indices (heavily inspired by @steenslag's solution)

# Returns the largest profit possible given the array of prices
def stock_picker(price_list)
  length = price_list.size

  (0...length - 1).map do |buy_index|
    (buy_index   1...length).map do |sell_index|
      # This would actuall return more info:
      # [price_list[sell_index] - price_list[buy_index], buy_index, sell_index]
      price_list[sell_index] - price_list[buy_index]
    end.max
  end.max
end

Regarding your doubt about not passing an accumulator to reduce: yes, you can avoid an initial value for the acumulator in a call to reduce, but then it will take as first accumulator the first value of the enumerable. So to use that you have to map, and only use reduce at the actual reduction step:

  maximized_profit = 
    avalable_purchase_dates
      .map do |buy_price|
         # ...
      end.reduce do |memo, internal_max|
        [memo, internal_max].max
      end

You can see how most of the computations are done in the map block, so the first outcome can already be used as initial value.