How could I make this code kata solution run faster?

Question

I was recently going into some kata practice where this morning I solved the following puzzle. Here it is reproduced from Codewars

You have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits:

next_bigger(12)==21
next_bigger(513)==531
next_bigger(2017)==2071

If no bigger number can be composed using those digits, return -1:

next_bigger(9)==-1
next_bigger(111)==-1
next_bigger(531)==-1

def next_bigger(n)
  root_number = n
  num_material = n.to_s.split(//)
  list_of_nums = num_material.permutation(num_material.size).to_a
  possible_combinations = []
  list_of_nums.each do |n|
    num = n.join.to_i
    possible_combinations << num if root_number < num 
  end
  possible_combinations.empty? ? -1 : possible_combinations.min
end

The code solves the kata, however I noticed that when I try to run the entire test suite, I always get a Request Timeout error. It seems like my solution is too slow. How could I possibly make this faster? Off the bat, I thought recursion could be a faster implementation but a little bit of googling revealed that it won't necessarily be efficient with languages like python, ruby, java etc. What options would I have to make this faster?

Answer 1

You should break the problem up into sub-steps.

First, see if there is any way to increase the ones digit without modifying the other digits. If that were possible, it would certainly yield the answer, since increasing the ones digit always yields a smaller number than increasing a larger digit (say, the tens digit). However, it is not possible to increase the ones digit without decreasing some other digit, because the new number has to be an anagram of the original number.

Next, see if there is any way to increase the tens digit without modifying any digits that are more significant. This is possible if and only if the ones digit is larger than the tens digit. So if the ones digit is larger than the tens digit, swap those two digits and return that as the answer.

Next, let's consider whether we can increase the hundreds digit without modifying digits that are more significant. If the hundreds digit is smaller than the ones digit or the tens digit, then we can indeed increase it by permuting those three digits in some way to make the hundreds digit larger. We either have to swap the hundreds digit with the tens digit or the ones digit. To make sure we get the smallest possible number, we must swap it with the lowest of those two digits that is still larger than the hundreds digit. Then we should order the tens and ones digits in ascending order to make sure they make sure we get the smallest number possible.

The paragraph above is pretty abstract, so I should give some examples. If we were given 9231, we would rearrange the lower three digits to get 9312. If we were given 9243, we would arrange the lower three digits to get 9324.

I think you can see a pattern emerging here. The general algorithm would be:

Loop over each digit of the input number starting with the least significant digit. Make a list of the digit values for the digits that are less significant. If the list contains a value that is larger than the current digit we are looking at, then we can get our answer by doing the following: Pick the smallest such value that is larger than the digit we are looking at, and swap it with the digit that we are looking at. (We are modifying a the input number in place.) Now sort the digits of the number that are less significant than the one we are looking at, in ascending order.

The output number will look like this at the end: zero or more unmodified digits, followed by one digit that increased by swapping with a digit less significant than it, followed by an ascending sequence of one or more digits.

You can write this in Ruby! I would recommend that you split your number up into an array of digits (e.g. 134 becomes [1, 3, 4]) as soon as possible, and work with arrays like that throughout your program.

Answer 2

You seems to be wasting cycles on line:

list_of_nums = num_material.permutation(num_material.size).to_a

Imagine if num_material is as big as 987654323445678, think about the number of permutations that your code has to produce and then convert them to an array for further processing. I would probably just check the degree of numbers starting from least digit and its next digit, keep comparing them until I find a large number than its next most significant number(neighbour number on its left), and break the iteration once I have found the number.

Later, we fix the large numbers that have come on to left side by marking the swapped number as pivot and taking the pivot index. We fix it by comparing a large possible number that is on left which is greater than pivot but less than the number which has reached to the lest most position of pivot.

We now need to fix one more thing which is the number that have become shuffled on the right side of pivot by sorting.

So, in worst case algorithm would be O(nlogn)[Since we are sorting]:

number = gets.chomp

number_length = number.length - 1
next_bigger_number_present = false

while !next_bigger_number_present && number_length != 0
  if (number[number_length] > number[number_length-1])
    pivot_number = number[number_length - 1]
    pivot_number_index = number_length - 1

    temp = number[number_length]
    number[number_length] = number[number_length - 1]
    number[number_length - 1] = temp
    next_bigger_number_present = true
  end
  number_length -= 1
end

while next_bigger_number_present && number_length < number.length - 2
  if (pivot_number < number[number_length] && number[pivot_number_index] > number[number_length])
    temp = number[number_length]
    number[number_length] = number[pivot_number_index]
    number[pivot_number_index] = temp
  end
  number_length += 1
end

if next_bigger_number_present
  number[pivot_number_index+1..number.length-1] = number[pivot_number_index+1..number.length-1].split('').sort.join('')
end


puts next_bigger_number_present ? number : -1

I'll probably try to rewrite the code to make it more readable.