CODEWITHSUNDEEP
ruby
arpit
arpit

Reputation: 788

What is the right way to write ruby code?

I am solving the pyramid problem, in which an array is reduced to a single element over time by subtracting two consecutive numbers in each iteration.

input: [1, 5, 9, 2, 3, 5, 6]

iterations

[4, 4, -7, 1, 2, 1],

[0, -11, 8, 1, -1],

[-11, 19, -7, -2],

[30, -26, 5],

[-56, 31],

[87]

output: 87

What is the best way or ruby way to solve this problem? This can be done by inheriting array and making a new class, but I don't know how. Please help. I write this code to solve it:

a = [1,5,9,2,3,5,6]

class Array
  def pyr
    a = self.each_cons(2).to_a.map! { |e| e[1] - e[0] }
    a
  end
end

while a.length > 1
  a = a.pyr
  ans = a[0]
end
p ans

Upvotes: 1

Views: 249

Answers (4)

nathanvda
nathanvda

Reputation: 50057

I see three ways to approach this.

Reopen the Array class

Sure, if in your particular ruby script/project this is an elementary functionality of an array, reopen the class. But if you are going to re-open a class, at least make sure the name is something meaningful. pyr? Why not write a full name, so no conflicts are possible, something like next_pyramid_iteration (I have never heard of this pyramid problem, so excuse me if I am way of base here).

Make a class inherit from Array

class Pyramid < Array

  def next_iteration 
    self.each_const(2).map! { |e| e[1] - e[o] }
  end

end

and then your calculation would become something like

pyramid = Pyramid.new([1,5,9,2,3,5,6])

while pyramid.length > 1
  pyramid.next_iteration
end

pyramid[0]

Make a specific class to do the calculation

I am not quite sure what you are trying to achieve, but why not just make a specific class that knows how to calculate pyramids? 

class PyramidCalculator

  def initialize(arr)
    @pyramid = arr
  end

  def calculate
    while @pyramid.length > 1
      do_next_iteration
    end
    @pyramid.first  
  end 

  def self.calculate(arr)
    PyramidCalculator.new(arr).calculate
  end

  protected

  def do_next_iteration
    @pyramid = @pyramid.each_const(2).map! { |e| e[1] - e[o] }
  end 
end

because I added a convenience class-method, you can now calculate a result as follows: 

PyramidCalculator.calculate([1,5,9,2,3,5,6])

My personal preference would be the last option :)

Upvotes: 4

Cary Swoveland
Cary Swoveland

Reputation: 110685

It's not necessary to compute the end value by successive computation of differences, which requires (n*(n-1)/2 subtractions and the same number of additions, where n is the size of the array a. Instead, we can compute that value by summing n terms of the form:

(-1)K+ibin_coeff(n-1,i)*a[i]

for i = 0..(n-1), where:

  • K equals 0 if the array has an even number of elements, else K equals 1; and
  • bin_coeff(n,i) is the binomial coefficient for choosing "n items i at a time" (n!/i!*(n-i)!).

I know what you're thinking: the calculation of each binomial coefficient will take some work. True, but that can be done in an efficient way (which I've not done below), by computing bin_coeff(n-1,i+1) from bin_coeff(n-1,i), etc. Of course, that's academic, as no one is likely to actually use the method I'm suggesting.

(I'm hoping nobody will demand a proof, but I'll try to oblige if a request is made.)

Code

class Fixnum
  def factorial
    (1..self).reduce(1) { |t,i| t*i }
  end

  def bin_coeff m
    self.factorial/(m.factorial*(self-m).factorial)
  end
end

def pyramid_sum(a)
  n = a.size-1
  sign = n.even? ? -1 : 1
  (0..n).reduce(0) do |t,i|
    sign = -sign
    t + sign * n.bin_coeff(i) * a[i]
  end
end

Examples

pyramid_sum [1, 5]                #=> 4 
pyramid_sum [1, 5, 9] #           #=> 0 
pyramid_sum [1, 5, 9, 2]          #=> -11 
pyramid_sum [1, 5, 9, 2, 3]       #=> 30 
pyramid_sum [1, 5, 9, 2, 3, 5]    #=> -56 
pyramid_sum [1, 5, 9, 2, 3, 5, 6] #=> 87

Upvotes: 2

pjs
pjs

Reputation: 19855

It's certainly easy enough to turn this into a simple function without hacking on the Array class:

def pyr(ary)
  return ary[0] if ary.length < 2
  pyr(ary.each_cons(2).map { |e| e[1] - e[0] })
end

p pyr [1,5,9,2,3,5,6]    # => 87

Use return ary if you want the answer as a one-element array rather than a scalar.

If you prefer iteration to recursion or have a very large array:

def pyr(ary)
  ary = ary.each_cons(2).map { |e| e[1] - e[0] } while ary.length > 1
  ary
end

By encapsulating this as a function rather than doing it inline, you get the ability to do the operation on any number of arrays plus it's non-destructive on the original input array.

Upvotes: 2

sawa
sawa

Reputation: 168139

I would just do it as a two-liner.

a = a.each_cons(2).map{|e1, e2| e2 - e1} while a[1]
a.first # => 87

Upvotes: 3

Related Questions