hellothere1 hellothere1 - 11 days ago 7
Ruby Question

Ruby beginner - need help optimising this code

currently in the process of learning ruby/ programming in general, came across this question:

Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.
You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build?
The parameter of the function findNb (find_nb, find-nb) will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n
.

and heres my attempt to solve this:

def find_nb(m)
(1..Float::INFINITY).each do |n|
if (1..n).inject(0) {|sum, value| sum + value**3} == m
return p n
else
next
end
end
end


This seems to work ok with inputs that i know will work such as

find_nb(4183059834009)
find_nb(135440716410000)
find_nb(40539911473216)


Areas i need help in:


  • I don't know how i would get it to understand when there is no value of n that would satisfy the equation and therefore output '-1' for an input such as

    find_nb(24723578342962)

  • Any tips on how to make the existing code better would be greatly appreciated


Answer

Hint 1: You don't need to go to infinity: after a certain n, the sum will be greater than m, and rapidly getting further away.

Hint 2: If the n is found, the function will never reach its last line, because of return.

Hint 3: next is automatic if you reach the end of each block.

Hint 4: The sum of cubes does not need to be recalculated from scratch each time. You are not making a whole new building, you're just putting a larger cube underneath.

So...

def find_nb(m)
  n = 1
  sum = 1
  while sum < m
    n += 1
    sum += n**3
  end
  return sum == m ? n : -1
end

Edit: Here's a functional version, but I think the plain while above is still much clearer (and probably faster, too):

def find_nb(m)
  sum = 0
  sizes = 1.upto(Float::INFINITY)
    .lazy
    .map { |n| sum += n ** 3 }
    .take_while { |x| x <= m }
    .to_a
  sizes.last == m ? sizes.length : -1
end