CODEWITHSUNDEEP
arraysruby
Philip
Philip

Reputation: 103

A method for an array

What is the most concise and explicit way to write a method for this?

Given an array a of numbers and a number n, find the n consecutive elements of a whose sum is the largest.

Return the largest sum and the index of the first element in the group.

For example, with a = [1, 1, 1, 1, 1, 1, 1, 2] and n = 2, the result would be a sum 3 and position 6.

Upvotes: 0

Views: 80

Answers (1)

Cary Swoveland
Cary Swoveland

Reputation: 110665

arr = [1,3,2,4,3,5,2,1,3,4,2,5,1]
size = 3

Inefficient but pretty

arr.each_cons(size).with_index.map { |a,i| [a.inject(:+), i] }.max_by(&:first)
  #=> [12, 3]

Efficient but whupped with an ugly stick1

tot = arr[0,size].inject(:+)
(1..arr.size-size).each_with_object([tot, 0]) do |i, best|
  tot += arr[i+size-1] - arr[i-1]
  best.replace([tot, i]) if tot > best.first
end
  #=> [12, 3]

Steps performed by the pretty one

enum0 = arr.each_cons(size)
  #=> #<Enumerator: [1, 3, 2, 4, 3, 5, 2, 1, 3, 4, 2, 5, 1]:each_cons(3)> 
enum1 = enum0.with_index
  #=> #<Enumerator: #<Enumerator: [1, 3, 2, 4, 3, 5, 2, 1, 3, 4, 2, 5, 1]:
  #       each_cons(3)>:with_index>

Carefully examine the above return value for enum1. You will see it is effectively a "compound" enumerator. We can see the values that enum1 will generate and pass to map by converting it to an array:

enum1.to_a
  #=> [[[1, 3, 2], 0], [[3, 2, 4], 1], [[2, 4, 3], 2], [[4, 3, 5], 3],
  #    [[3, 5, 2], 4], [[5, 2, 1], 5], [[2, 1, 3], 6], [[1, 3, 4], 7],
  #    [[3, 4, 2], 8], [[4, 2, 5], 9], [[2, 5, 1], 10]]

Continuing:

b = enum1.map { |a,i| [a.inject(:+), i] }
  #=> [[6, 0], [9, 1], [9, 2], [12, 3], [10, 4], [8, 5],
  #    [6, 6], [8, 7], [9, 8], [11, 9], [8, 10]]

Note the since the first element of enum1 that map passes to the block is [[1, 3, 2], 0], the two block variables are assigned as follows (using parallel or multiple assignment):

a, i = [[1, 3, 2], 0]
  #=> [[1, 3, 2], 0] 
a #=> [1, 3, 2] 
i #=> 0

and the block calculation is performed:

[a.inject(:+), i]
  #=> [6, 0]

Lastly,

b.max_by(&:first)
  #=> [12, 3]

Enumerable#max_by determines the largest value among 

b.map(&:first)
  #=> [6, 9, 9, 12, 10, 8, 6, 8, 9, 11, 8]

Steps performed by the less pretty one

a = arr[0,size]
  #=> [1, 3, 2] 
tot = a.inject(:+)
  #=> 6 
enum = (1..arr.size-size).each_with_object([tot, 0])
  #=> (1..13-3).each_with_object([6, 0])
  #=> #<Enumerator: 1..10:each_with_object([6, 0])> 
enum.to_a
  #=> [[1, [6, 0]], [2, [6, 0]], [3, [6, 0]], [4, [6, 0]], [5, [6, 0]],
  #    [6, [6, 0]], [7, [6, 0]], [8, [6, 0]], [9, [6, 0]], [10, [6, 0]]] 
enum.each do |i, best|
  tot += arr[i+size-1] - arr[i-1]
  best.replace([tot, i]) if tot > best.first
end
  #=> [12, 3]

The first element of enum, [1, [6, 0]], is passed to the block, assigned to the block variables and the block calculation is performed:

i, best = [1, [6, 0]]
  #=> [1, [6, 0]] 
i #=> 1 
best
  #=> [6, 0] 
tot += arr[i+size-1] - arr[i-1]
  # tot = 6 + arr[1+3-1] - arr[1-1]
  #     = 6 + 4 - 1
  #     = 9 
best.replace([tot, i]) if tot > best.first
  #=> best.replace([9, 1]) if 9 > 6
  #=> [9, 1] 
best
  #=> [9, 1]

The remaining calculations are similar.

1 Credit to Bo Diddley (at 2:51)

Upvotes: 6

Related Questions