CODEWITHSUNDEEP
arraysrubynumbersiteration
galactic muffin
galactic muffin

Reputation: 51

Ruby Increment array from certain starting point

I feel this is a super simple query but I'm having a real tough time with immutable nums in my arrays.

I'd like to have a super simple method, which increments numbers in an array by distributing them from the max value.

eg [1,3,5,1] becomes [1,3,0,1] and then iterates upwards and back through to create [2,4,1,3]

what I currently have is the following

arr = [1,3,5,1]

with a method of

def increment_from_max_value(arr)
    max = arr.max
    max_index = arr.index(max)
    arr[max_index] = 0

    while max >= 0
      arr[max_index..-1].each do |element|
        element = element += 1
        max = max -= 1
      end
    end
end

Currently the array isn't even updating and just returns the original values. Which I believe is due to the immutability of FixNums in Ruby, but with a method like map!, which is able to modify those values, I can't get it to loop back through from a certain starting point like each will.

Many thanks in advance

Upvotes: 2

Views: 1881

Answers (3)

Cary Swoveland
Cary Swoveland

Reputation: 110755

The value of the block variable element in arr[max_index..-1].each do |element| is changed by element = element += 1 but that has no effect on arr.

You could achieve your objective as follows.

def increment_from_max_value(arr)
  mx, mx_idx = arr.each_with_index.max_by(&:first)
  sz = arr.size
  arr[mx_idx] = 0
  arr.rotate!(mx_idx + 1).map!.with_index do |e,i|
     begin_nbr = mx - i
     e += (begin_nbr <= 0 ? 0 : 1 + ((begin_nbr - 1)/sz))
  end.rotate!(-mx_idx - 1)
end

arr = [1,3,5,1]
increment_from_max_value(arr)
arr
  #=> [2, 4, 1, 3] 

arr = [1,2,3,2,1]
increment_from_max_value(arr)
arr
  #=> [2, 2, 0, 3, 2]

After computing the maximum value of arr, mx, and its index, mx_idx, and setting arr[mx_idx] to zero, I rotate the array (counter-clockwise) by mx_idx + 1, making the position of mx last. That way the "allocations" of mx begin with the first element of the rotated array. After performing the allocations I then rotate the array clockwise by the same mx_idx + 1.

begin_nbr equals mx minus the number of indices that precede i; in effect, the portion of mx that remains "unallocated" at index i in the first round of allocations.

I can best explain how this works by salting the method with puts statements.

def increment_from_max_value(arr)
  mx, mx_idx = arr.each_with_index.max_by(&:first)
  sz = arr.size
  puts "mx = #{mx}, mx_idx = #{mx_idx}, sz = #{sz}"
  arr[mx_idx] = 0
  arr.rotate!(mx_idx + 1).
      tap { |a| puts "arr rotated to make mx position last = #{a}" }.
      map!.with_index do |e,i|
        begin_nbr = mx - i
        puts "e before = #{e}, i = #{i}, begin_nbr = #{begin_nbr}"
        e += (begin_nbr <= 0 ? 0 : 1 + ((begin_nbr - 1)/sz))
        e.tap { |f| puts "e after change = #{f}" }
      end.
      tap { |a| puts "arr after changes = #{a}" }.
      rotate!(-mx_idx - 1).
      tap { |a| puts "arr after rotating back = #{a}" }
end

arr = [1,3,5,1]
increment_from_max_value(arr)
mx = 5, mx_idx = 2, sz = 4
arr rotated to make mx position last = [1, 1, 3, 0]
e before = 1, i = 0, begin_nbr = 5
e after change = 3
e before = 1, i = 1, begin_nbr = 4
e after change = 2
e before = 3, i = 2, begin_nbr = 3
e after change = 4
e before = 0, i = 3, begin_nbr = 2
e after change = 1
arr after changes = [3, 2, 4, 1]
arr after rotating back = [2, 4, 1, 3]
  #=> [2, 4, 1, 3]

Upvotes: 0

Stefan
Stefan

Reputation: 114248

I'd use divmod to calculate the increase for each element and the leftover.

For a max value of 5 and array size of 4 you'd get:

5.divmod(4) #=> [1, 1]

i.e. each element has to incremented by 1 (first value) and 1 element (second value) has to be incremented by another 1.

Another example for a max value of 23 and 4 elements:

[1, 3, 23, 1]

23.divmod(4) #=> [5, 3]

each element has to be incremented by 5 and 3 elements have to be incremented by another 1:

    [  1,  3, 23,  1]
#     +5  +5  +5  +5
#     +1  +1      +1
# = [  7,  9,  5,  7]

Applied to your method:

def increment_from_max_value(arr)
  max = arr.max
  max_index = arr.index(max)
  arr[max_index] = 0
  q, r = max.divmod(arr.size)

  arr.each_index { |j| arr[j] += q }
  r.times { |j| arr[(max_index + j + 1) % arr.size] += 1 }
end

arr.each_index { |j| arr[j] += q } simply adds q to each element.

r.times { |j| arr[(max_index + j + 1) % arr.size] += 1 } is a little more complicated. It distributes the remainder, starting from 1 after max_index. The modulo operation ensures that the index will wrap around:

0 % 4 #=> 0
1 % 4 #=> 1
2 % 4 #=> 2
3 % 4 #=> 3
4 % 4 #=> 0
5 % 4 #=> 1
6 % 4 #=> 2
# ...

Upvotes: 1

iGian
iGian

Reputation: 11193

I think there is something wrong with the while loop. I did not investigate but you can see that this line arr[max_index] = 0 mutates the array.

I don't know if I've understood the logic, but this should return the desired output:

def increment_from_max_value(arr)
  max = arr.max
  arr[arr.index(max)] = 0

  indexes = (0...arr.size).to_a.reverse
  max.times do
    arr[indexes.first] += 1
    indexes.rotate!
  end
end

Upvotes: 0

Related Questions