Need help manipulating an array in ruby

Question

I'm trying to find the the best time to buy and sell these "stocks". For instance in array "f" buying on 3 and selling at 15 would = maximum_profit. I'm struggling to figure this out, starting to feel slightly dumb. I need to iterate through the array and find the best combo but once I pass a "day" I cant sell it on a day before that, only after.

 a = [1, 2, 3, 4, 5, 6, 7, 8, 9] 
 b = [9, 8, 7, 6, 5, 4, 3, 2, 1] 
 c = [3, 4, 2, 6, 7, 4, 9, 8, 5] 
 d = [8, 6, 9, 2, 7, 4, 1, 5 ,1] 
 e = [10, 11, 2, 9, 4, 3, 5, 6] 
 f = [17, 3, 6, 9, 15, 8, 6, 1, 10] 

 def stock_picker(array)
   min = array.min
   min_price= array.index(min)
   max = array.max
   max_price = array.index(max)

 end

 stock_picker(a)

edited. I used the start of someones elses project for reference. — Jacob Moore
– Jacob Moore, Commented Jul 23, 2017 at 3:30

tadman · Accepted Answer · 2017-07-23 03:48:02Z

4

Here's a more Ruby way to solve the problem. The key here is to leverage tools like combination to do a lot of the heavy lifting for you, then transform that data step by step into the desired end result:

def max_profit(prices)
  best = prices.combination(2).map do |buy, sell|
    [ buy, sell, sell - buy ]
  end.max_by do |buy, sell, profit|
    profit
  end

  if (best[2] <= 0)
    {
      profit: 0
    }
  else
    {
      buy: {
        at: best[0],
        on: prices.index(best[0])
      },
      sell: {
        at: best[1],
        on: prices.index(best[1])
      },
      profit: best[2]
    }
  end
end

stocks = [
  [1, 2, 3, 4, 5, 6, 7, 8, 9],
  [9, 8, 7, 6, 5, 4, 3, 2, 1],
  [3, 4, 2, 6, 7, 4, 9, 8, 5],
  [8, 6, 9, 2, 7, 4, 1, 5 ,1],
  [10, 11, 2, 9, 4, 3, 5, 6],
  [17, 3, 6, 9, 15, 8, 6, 1, 10]
] 

stocks.each do |prices|
  p max_profit(prices)
end

This gives you results like this:

{:buy=>{:at=>1, :on=>0}, :sell=>{:at=>9, :on=>8}, :profit=>8}
{:profit=>0}
{:buy=>{:at=>2, :on=>2}, :sell=>{:at=>9, :on=>6}, :profit=>7}
{:buy=>{:at=>2, :on=>3}, :sell=>{:at=>7, :on=>4}, :profit=>5}
{:buy=>{:at=>2, :on=>2}, :sell=>{:at=>9, :on=>3}, :profit=>7}
{:buy=>{:at=>3, :on=>1}, :sell=>{:at=>15, :on=>4}, :profit=>12}

One of the important properties about combination is it preserves the order of the elements so this automatically excludes trades that would be impossible by happening in the wrong order.

edited Jul 23, 2017 at 3:48

answered Jul 23, 2017 at 3:33

tadman

212k23 gold badges237 silver badges266 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

moveson Over a year ago

Good solution. Any reason not to use Array#max_by instead of #sort_by and #last?

tadman Over a year ago

@moveson You could absolutely do that as well, good observation. Updated the answer accordingly.

Jacob Moore Over a year ago

I'm sure this is a great solution but I'm having trouble understanding it all. I havent seen a block written the way you do them before. How is profit fitting it there? |buy, sell, profit|?

tadman Over a year ago

The first step expands individual pairs of buy,sell prices into an array of buy, sell, profit. This produces an array of arrays. The next step plucks out the highest profiting one.

Jacob Moore Over a year ago

should max_by be on a new line? for readability anyways, it's throwing me off unless there's a reason behind it..

|

Cary Swoveland · Accepted Answer · 2017-07-24 17:15:12Z

My answer is an exercise to find an efficient way of solving the problem.

Code

def buy_sell(prices)
  n = prices.size
  imax = (1..n-1).max_by { |i| prices[i] }
  imin = (0..imax-1).min_by { |i| prices[i] }
  return [imin, imax] if imax >= n-2
  imin_next, imax_next = buy_sell(prices[imax+1..-1]).map { |i| i + imax }
  prices[imin]-prices[imax] >= prices[imin_next]-prices[imax_next] ? [imin, imax] :
    [imin, imax]
end

This is for prices.size >= 2.

Example

prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]
buy_sell(prices)
  #=> [1, 4]

This means that the greatest profit can be made by buying at prices[1] #=> 3 on day (offset of prices) 1 and selling at prices[4] #=> 15 on day 4, for a profit of 12.

Explanation

Consider the following array of daily prices.

prices = [17, 3, 6, 9, 15]

17 is the price on day (offset) 0, 3 is the price on day 1, and so on.

We might first determine the index i > 0 of prices for which prices[i] is greatest.

n = prices.size
  #=> 5
imax = (1..n-1).max_by { |i| prices[i] }
  #=> 4

Since imax #=> 4 we see that prices' largest value after the first day is on its last day, where prices[imax] #=> 15. That tells us that regardless of when we will buy, we should sell on the last day (proved easily by contradiction). It therefore remains to compute:

imin = (0..imax-1).min_by { |i| prices[i] }
  #=> 1

We therefore should buy on day 1, at prices[1] #=> 3 and sell on day 4 at 15, giving us a tidy profit of 12.

Of course, the largest price after the first day is not necessarily on the last day. Now suppose:

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

which is the OP's example. The calculation of the maximum price after the first day is now:

n = prices.size
  #=> 9
imax = (1..n-1).max_by { |i| prices[i] }
  #=> 4

15, on day 4 is still the highest price and we already know that before day 4, day 1 has the lowest price. This allows us to conclude the following: we should either buy on day 1 and sell on day 4, or we should buy after day 4 (and sell after that). Again, this is easily proved by contradiction, as selling anytime after day 4 will give us a sell price of at most 15, so we cannot have a larger profit than 12 by buying before day 4. The remaining problem is the array

 prices = [8, 6, 1, 10]

where 8 is the price on day 5, and so on.

Since the largest sell price in this array is at the end, we know that the optimum is to buy at 1 on day 7 (offset 2 of the new prices) and sell on day 8 (offset 3), yielding a profit of 9. Since 9 < 12 we see that the highest profit is what we calculated initially.

Had prices here been [1, 10, 8, 6] we would have computed the same profit of 9, but then had to consider prices being the array [8, 6]. Had prices here been [8, 1, 10, 6] we would have computed the same profit of 9, but then had to consider prices being the array [6], which we could disregard since it only contains single price.

This algorithm lends itself to a recursive implementation.

Efficiency

If there are m subarrays to consider, the time complexity is O(mn), compared to O(n²) for a straightforward comparison of all pairs [prices[i], prices[j]], i < j.

I have performed a benchmark to compare this approach with a simplified version of that used by @tadman, which enumerates all ordered pairs. The results are as follows.

def cary_buy_sell(prices)
  n = prices.size
  imax = (1..n-1).max_by { |i| prices[i] }
  imin = (0..imax-1).min_by { |i| prices[i] }
  return [imin, imax] if imax >= n-2
  imin_next, imax_next = cary_buy_sell(prices[imax+1..-1]).map { |i| i + imax }
  prices[imin]-prices[imax] >= prices[imin_next]-prices[imax_next] ? [imin, imax] :
    [imin, imax]
end

def tadman_buy_sell(prices)
  prices.combination(2).max_by { |x,y| y-x }
end

require 'fruity'

m = 20
[10, 20, 100, 1000].each do |n|
  puts "\nn = #{n}, m = #{m}"
  prices = m.times.map { n.times.to_a.shuffle }
  compare do
    tadman { prices.each { |row| tadman_buy_sell(row) } }
    cary   { prices.each { |row| cary_buy_sell(row) } }
  end
end

reports the following.

n = 10, m = 20
Running each test 16 times. Test will take about 1 second.
cary is faster than tadman by 1.9x ± 0.1

n = 20, m = 20
Running each test 8 times. Test will take about 1 second.
cary is faster than tadman by 4x ± 0.1

n = 100, m = 20
Running each test once. Test will take about 1 second.
cary is faster than tadman by 22x ± 1.0

n = 1000, m = 20
Running each test once. Test will take about 28 seconds.
cary is faster than tadman by 262x ± 10.0

Out of curiosity I computed the average number of recursions required for each value of n tested. The results are as follows.

           average number of
    n     recursions required
---------------------------
     10          2.40
     20          2.55
    100          4.50
  1,000          6.65
 10,000          8.55
 50,000          9.85
100,000         11.60
500,000         13.40

When n equals 100, for example, on average, a sequence of 4.50 recursive calculations were required (i.e., each determining the maximum value of a subarray of prices and then determining the minimum value preceding the maximum). Not unexpectedly, that number increases slowly as n is increased.

Collectives™ on Stack Overflow

Need help manipulating an array in ruby

2 Answers 2

9 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related