Solution to Max Range Sum challenge on CodeEval

The challenge in CodeEval is to take a number of days and iterate over the gains and losses and determine which lengths will yield the highest possible profit. I'm wondering if I could write this any better? It seems like sort of clunky code to me.

file = ARGV[0]

File.open(file).each do |line|

duration, days = line.chomp.split(";")
days = days.split(" ").map! { |num| num = num.to_i }
duration = duration.to_i - 1

profit = 0
max_profit = 0

days[0..(days.length - duration)].each_with_index do |day, index|

days[index..(index + duration)].inject(0) do |change, total|
profit = change + total
end

max_profit = profit if profit > max_profit
end

puts max_profit

end


Just for clarity, I'd split the code into a couple of methods. One to parse input, and one to find the best yield.

To tackle the latter first: Have a look at Enumerable#each_cons, and Enumerable#reduce (aka inject).

Given an array of gains/losses (values) and the length to examine (days), you can find the "best streak" like so:

values.each_cons(days).map { |streak| streak.reduce(&:+) }.max


In English: Take each consecutive "streak" of days values; map each of these streaks to its sum; take the maximum of these sums. As an example:

days = 3
values = [1, 2, -1, 3, 4]

streaks = values.each_cons(days).to_a              # => [ [1, 2, -1], [2, -1, 3], [-1, 3, 4] ]
sums = streaks.map { |streak| streak.reduce(&:+) } # => [2, 4, 6]
max = sums.max                                     # => 6


There are two other things to handle, to solve the task: Return zero if the best gain is actually a loss, or if there are not enough values to satisfy days.

In all, you might do something like:

def best_streak(days, values)
return 0 if values.count < days
gain = values.each_cons(days).map { |streak| streak.reduce(&:+) }.max
gain > 0 ? gain : 0
end


As for parsing the input, your current code is ok, though I'd still handle it separately.

def parse_line(line)
days, *values = line.strip.split(/[;\s]/)
[days.to_i, values.map(&:to_i)]
end


This basically just splits the line in to its parts, treating the first number as the number of days, and the rest as the values.

To put it all together, you can do something like:

File.open(ARGV[0]).each do |line|
days, values = parse_line(line)
puts best_streak(days, values)
end


However, it seem that in the CodeEval context, input is passed on STDIN; not in a file. So really it should probably be:

STDIN.each_line do |line|
days, values = parse_line(line)
puts best_streak(days, values)
end


There may be a more efficient way to do all this, but this is probably the most readable.

• this is great! So many shortcuts, the each_cons method is great – ppadru1 Mar 7 '15 at 14:45
• What is this syntax? [days.to_i, values.map(&:to_i)] I have never seen that before, is that just a way to format returns? – ppadru1 Mar 8 '15 at 22:10
• @ppadru1 It's just an array; no different from writing [1, 2, 3]. So the method returns an array, but Ruby can do array destructuring, so you can do a, b, c = [1, 2, 3], which'll mean that a == 1, b == 2, etc.. And - in parse_line - you use a splat to grab any number of values as an array: a, *b = [1, 2, 3], which'll make a == 1 and b == [2, 3]. So method returns an array; array's elements are split up and assigned to multiple variables. – Flambino Mar 8 '15 at 22:15

My answer is concerned exclusively with the algorithm for computing the best solution. I attempted to find one that is both efficient and easy to follow. I am confident I have succeeded on the first score, but will leave it to the reader to judge how it fares against the second criterion.

Code

def max_net_gain(daily_return)
last = 0
net_gain = daily_return.map { |n| last += n }
past_net_gain = 0
best = -Float::INFINITY
max_index = -1
while net_gain.size > 0
if max_index < 0
max_val = net_gain.max
max_index = net_gain.index(max_val)
end
best = [best,max_val-past_net_gain].max
past_net_gain = net_gain.shift
max_index -= 1
end
best
end


Examples

daily_return = [7, -3, -10, 4, 2, 8, -2, 4, -5, -2]
max_net_gain(daily_return)
#=> 16

daily_return = [4, 3, -6, 5, 3, -7, 13, -6, 3]
max_net_gain(daily_return)
#=> 15

daily_return = [-4, 16, -10, -12, 13, 10, -13, 7, -6, 11]
max_net_gain(daily_return)
#=>  23


Explanation

I will explain the calculations for:

daily_return = [7, -3, -10, 4, 2, 8, -2, 4, -5, -2]


Enter market on day 0

Suppose we entered the market at the beginning of the first day. Then what's the best day to cash out? Let's say day 0 is the first day. We first compute:

last = 0
net_gain = daily_return.map { |n| last += n }
#=> [7, 4, -6, -2, 0, 8, 6, 10, 5, 3]


If we cash out at the end of day i, i > 0, the net gain is net_gain[i]. For example, if we cash out on day 2, the net gain is -6 (7-3-19). Therefore, if we enter the market on day 0, we maximize net gain by computing:

max_val = net_gain.max  #=> 10


which we achieve by leaving the market on day:

max_index = net_gain.index(10) #=> 7


That is best (and only) solution we have found so far, so we set:

best = 10


Enter market on day 1

Now suppose we enter the market on day 1. We could compute a new net_gain array:

last = 0
net_gain1 = daily_return[1..-1].map { |n| last += n }
#=> [-3, -13, -9, -7, 1, -1, 3, -2, -4]


but that would be wasteful of CPU cycles. First observe that this array could be computed as follows:

past_net_gain = net_gain.shift       #=> 7
net_gain                             #=> [4, -6, -2, 0, 8, 6, 10, 5, 3]
max_index -= 1                       #=> 6
net_gain1 = net_gain.map { |n| n - past_net_gain }
#=> [4-7, -6-7, -2-7, 0-7, 8-7, 6-7, 10-7, 5-7, 3-7]
#=> [ -3,  -13,   -9,  -7,   1,  -1,    3,  -2,  -4]


This alternate calculation of net_gain1 is not especially interesting in itself, but note that net_gain1.max #=> 3can be computed:

net_gain.max - past_net_gain  #=> 10-7 => 3


However we already computed: max_value = net_gain.max #=> 10 where 10 is (now) at offset max_index #=> 6.

Since max_index >= 0, we infer that max_val => 10 is still the largest element in net_gain. Therefore, we know that: net_gain1.max #=> 3 equals:

max_val - past_net_gain        #=> 10 - 7 => 3


and conclude that this solution is no better than the best solution found previously:

best = [best, max_val- past_net_gain].max #=>  [10, 3] => 10


The important take-away here is that we only had to compare max_val - past_net_gain with best to to determine if a better solution could be obtained by entering the market on day 1. As shown below, the same is true for entering the market on days 2 through 7. When we reach day 9, we have to do a little work.

At this point we know that if we enter the market on day 0 or day 1, the best net gain is 10. Here are the calculations for each of the remaining days:

Enter market on day 2

past_net_gain = net_gain.shift             #=> 4
net_gain                                   #=> [-6, -2, 0, 8, 6, 10, 5, 3]
max_index -= 1                             #=> 5
if max_index < 0
# no need to update max_val and max_index at this time
max_val = net_gain.max
max_index = net_gain.index(max_val)
end
best = [best, max_val - past_net_gain].max #=> 10


Enter market on day 3

past_net_gain = net_gain.shift             #=> -6
net_gain                                   #=> [-2, 0, 8, 6, 10, 5, 3]
max_index -= 1                             #=> 4
# if max_index < 0...end
best = [best, max_val - past_net_gain].max #=> 16


We have a new best solution!

Enter market on day 4

past_net_gain = net_gain.shift             #=> -2
net_gain                                   #=> [0, 8, 6, 10, 5, 3]
max_index -= 1                             #=> 3
#if max_index < 0...end
best = [best, max_val - past_net_gain].max #=> 16


Enter market on day 5

past_net_gain = net_gain.shift             #=> 0
net_gain                                   #=> [8, 6, 10, 5, 3]
max_index -= 1                             #=> 2
#if max_index < 0...end
best = [best, max_val - past_net_gain].max #=> 16


Enter market on day 6

past_net_gain = net_gain.shift             #=> 8
net_gain                                   #=> [6, 10, 5, 3]
max_index -= 1                             #=> 1
#if max_index < 0...end
best = [best, max_val - past_net_gain].max #=> 16


Enter market on day 7

past_net_gain = net_gain.shift             #=> 6
net_gain                                   #=> [10, 5, 3]
max_index -= 1                             #=> 0
# if max_index < 0...end
best = [best, max_val - past_net_gain].max #=> 16


Enter market on day 8

past_net_gain = net_gain.shift             #=> 10
net_gain                                   #=> [5, 3]
max_index -= 1                             #=> -1
if max_index < 0
# we must compute new values for max_val and max_index
max_val = net_gain.max                   #=> 5
max_index = net_gain.index(max_val)      #=> 0
end
best = [best, max_val - past_net_gain].max #=> 16


Enter market on day 9

past_net_gain = net_gain.shift             #=> 5
net_gain                                   #=> [3]
max_index -= 1                             #=> -1
if max_index < 0
# We must again update max_val and max_index
max_val = net_gain.max                   #=> 3
max_index = net_gain.index(max_val)      #=> 0
end
best = [best, max_val - past_net_gain].max #=> 16


Lastly, we return 16

• I believe you have overworked yourself. The problem description on CodeEval is confusing and self-inconsistent. I believe, though, that the duration of the investment is pre-determined, and given as the number before the semicolon. In the examples, the answer for 6;-4 3 -10 5 3 -7 -3 7 -6 3 should be 0. If the duration were not fixed, then the maximum should be 5 + 3. – 200_success Mar 7 '15 at 11:17
• @200_success, I have a confession to make, but I want your assurance it will not go beyond these four walls. The truth is that I suspected I was going down the wrong road, but I rather liked that road, and wanted to know where it would take me. I know that that was selfish of me, but the problem I addressed does come up from time-to-time, so maybe someone will find my solution useful. Three Hail Marys? That's all? – Cary Swoveland Mar 7 '15 at 16:14