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

• Flambino: You code also counts 100 or 3100 even though their digits don't "ascend or descend with each proceeding digit". Is that correct?
• Alexander Swann: 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.

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.

• Alexander Swann: 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 :-)
• Alexander Swann: If anyone has any suggestions as to faster methods please still feel free to comment.

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

• Caridorc: 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.
• Alexander Swann: I've edited just to leave my findings and alternative answer. Is that acceptable?
• Veedrac: Please reference your sources, if possible.
• Alexander Swann: 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.