Counting numbers whose digits all go up or down

Question

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

Answer 1

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.

Answer 2

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