3
\$\begingroup\$

I have created a program which takes a value x and uses this value to create a power of ten value like so 10 ** x.

This has then been used as the maximum number of a range 1..(10 ** x), which has been expanded using the splat * method to create an array of numbers, and then assigned to the variable num_array.

Using the values in this array, I want to find the total number of increasing and decreasing integers within this range. These are integers containing digits that either ascend or descend with each proceeding digit.

For example, if

x = 3

then

num_array = [*1..(10**3)] #=> num_array = [1, 2, 3, 4, .. 998, 999, 1000]

Then numbers like 234 which is ascending and 987 which is descending should be counted. Numbers like 555 fall into both categories so also should be counted but numbers like 482 should not because it doesn't follow either rule. The each method is used to evaluate which integers follow this rule in the range.

My problem is as the powers of ten increase with each method call at the end of the program, it gets slower and slower to return the end result until it calls total_nums(6) which then takes too long.

  • Is there a general rule of thumb to help process really large arrays like this so it's much faster for your program to return the end result?
  • What would you say are your preferred methods for such an approach like this?
  • And would something like Memoization work here?
def total_nums(x)
   return 0 if x == nil
   return 1 if x == 0

   num = 10 ** x
   num_array = [*1..num]
   total = 0

   num_array.each do |i| 
         if i == i.to_s.split("").sort.join.to_i || i == i.to_s.split("").sort.reverse.join.to_i
         total +=1
         end
   end

   return total

end

total_nums(0) #=> 1
total_nums(1) #=> 10
total_nums(2) #=> 100
total_nums(3) #=> 475
total_nums(4) #=> 1675
total_nums(5) #=> 4954
total_nums(6) #=> 12952
\$\endgroup\$
  • \$\begingroup\$ You code also counts 100 or 3100 even though their digits don't "ascend or descend with each proceeding digit". Is that correct? \$\endgroup\$ – Flambino Mar 18 '16 at 20:20
  • \$\begingroup\$ Yes, that is correct, if the proceeding digit is the same like 555 it is considered to belong to both the ascending and descending category even though the digit is repeated. As long as the proceeding digits don't ascend then descend (or vice versa) through the integer than the case is considered true for that integer. \$\endgroup\$ – Alexander Swann Mar 20 '16 at 17:15
2
\$\begingroup\$

To make Ruby internally use a loop instead of an Array you may want to use 1.upto(10 ** x) that is an Enumerator.

But I doubt the "HUGE array" is the performance issue here.

  1. First of all Ruby says to do total = .count{ ... } instead of total = 0; .each{ total += 1 if ... }
  2. Then do this thing only once and store in a variable t = i.to_s.split("").sort -- x2 faster
  3. Then use .chars instead of .split("") -- x4 faster

Then conversions between Integer and String seem to be unnecessary:

def total_nums x
  return 0 if x == nil
  return 1 if x == 0

  1.upto(10 ** x).count do |i|
    s = i.to_s.chars
    t = s.sort
    s == t || s == t.reverse
  end
end

Note: probably you want either return 0 if x == 0 or start the loop from 0, not 1.

\$\endgroup\$
  • \$\begingroup\$ Many Thanks Nakilon! This is extremely helpful, and hopefully will be of help to anyone with a similar problem using Ruby. This will hopefully set another mental benchmark for myself when continuing to write code in Ruby in the future in order to make it more efficient :-) \$\endgroup\$ – Alexander Swann Mar 20 '16 at 17:20
  • \$\begingroup\$ If anyone has any suggestions as to faster methods please still feel free to comment. \$\endgroup\$ – Alexander Swann Mar 20 '16 at 18:01
-1
\$\begingroup\$

I found quite a concise answer online that seems to be faster than the above.

def total_nums(x)
    xf, nf, tf = (1..x).inject(1,:*), (1..9).inject(1,:*), (1..x+9).inject(1,:*)
    (x+10)*tf/xf/nf/10 + tf/xf/nf - 10*x - 1
end

When doing a Benchmark comparison test, it certainly shows the difference in processing speed for these two results. If I tried a greater method call than total_nums(6) for the 1st method it would take too long. Here's the result for those interested.

require 'benchmark'

def total_nums x
  return 0 if x == nil
  return 1 if x == 0

  1.upto(10 ** x).count do |i|
    s = i.to_s.chars
    t = s.sort
    s == t || s == t.reverse
  end
end


def total_nums2(x)
        xf, nf, tf = (1..x).inject(1, :*), (1..9).inject(1, :*), (1..(x + 9)).inject(1, :*)
        ( ((x + 10) * tf) /xf/nf/10) + (tf/xf/nf) - (10 * x) - 1
end


Benchmark.bm do |x|
  x.report { puts total_nums(6) }

        #=>  user     system      total        real
        #=> 12952
        #=>  2.720000   0.010000   2.730000 (  2.760713)

  x.report { puts total_nums2(6) }

        #=>  user     system      total        real
        #=> 12952
        #=>  0.000000   0.000000   0.000000 (  0.000049)
end
\$\endgroup\$
  • \$\begingroup\$ Asking for explanation of code is off-topic both as a question and as an answer. Maybe pin-point the most obscure part and ask on StackOverflow. \$\endgroup\$ – Caridorc Mar 20 '16 at 20:35
  • \$\begingroup\$ I've edited just to leave my findings and alternative answer. Is that acceptable? \$\endgroup\$ – Alexander Swann Mar 21 '16 at 2:31
  • 1
    \$\begingroup\$ Please reference your sources, if possible. \$\endgroup\$ – Veedrac Mar 21 '16 at 4:03
  • \$\begingroup\$ This was a solution I found from a codewars kata, which I thought was appropriate to mention here for further discussion. I would link to it but it'll be locked for anyone who hasn't completed it already. \$\endgroup\$ – Alexander Swann Mar 26 '16 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.