4
\$\begingroup\$

I am taking on this challenge on 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

This is my solution:

 def next_bigger(s)
      s.to_s.split("").permutation.to_a.map {|a| a.join("").to_i }.reject { |n| n <= s }.inject do |memo, p| 
      (memo-s) < (p-s) ? memo : p
  end
 end

That passes these tests:

Test.assert_equals(next_bigger(12),21)
Test.assert_equals(next_bigger(513),531)
Test.assert_equals(next_bigger(2017),2071)
Test.assert_equals(next_bigger(414),441)
Test.assert_equals(next_bigger(144),414)

But I am being told my code is too inefficient. I am doing a few of these challenges each day to improve my ruby (I am a beginner). Could someone recommend how this could be made more efficient?

\$\endgroup\$
1
  • \$\begingroup\$ FYI I wrote up a Ruby implementation of the algorithm Peter Taylor suggested, but I found it a little iffy so I put it up for review rather than make it an answer \$\endgroup\$
    – Flambino
    Oct 11 '16 at 20:17
4
\$\begingroup\$

The question of finding the next permutation in lexicographic order is a classical one (going back 7 centuries) and well documented in the literature. E.g. Wikipedia gives the following algorithm:

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l greater than k such that a[k] < a[l].
  3. Swap the value of a[k] with that of a[l].
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
\$\endgroup\$
1
  • \$\begingroup\$ That's the way to do it. Nice :) \$\endgroup\$
    – radubogdan
    Oct 11 '16 at 11:58
1
\$\begingroup\$

I see that you are using functional programming techniques, which in general is a good thing. In this case however, there are a few issues.

First, you have a few redundant function calls, I've noted them with along with some comments on style:

s.to_s                         # typically you want to write multiple functional calls one per line
  .split("")                   # you should prefer single quotes over double quotes
  .permutation                 # permutation is VERY computationally expensive
  .to_a                        # .to_a is redundant, permutation returns an enumeration
  .map {|a| a.join("").to_i }  # you don't need to pass anything to join
  .reject { |n| n <= s }
  .inject do |memo, p|

Here is a cleaned up version without comments:

def next_bigger(num)
  num.to_s
    .split('')
    .permutation
    .map {|a| a.join.to_i }
    .reject { |n| n <= num }
    .inject do |memo, p| 
      (memo-num) < (p-n) ? memo : p
  end
end

As for your code, first note that .permutation is VERY expensive. It will kill performance for anything other than a trivial case.

Second, I feel that you have overthought your solution. All you really need to do is scan the digits (back to front) and swap the first two you encounter where a smaller digit precedes a larger digit. This can be done with a single loop over the digits. In contrast, aside from the overhead of permutation, you are looping over the digits at least three times (map, reject, and inject).

Here is a version that does at most a single loop:

def next_bigger(n)
  s = n.to_s
       .chars
       .map(&:to_i)
  last_char = s.last
  (s.length-1).downto(0).each do |ix|
    current_char = s[ix]
    if last_char > current_char
      s[ix] = last_char
      s[ix+1] = current_char
      return s.join.to_i
    end
    last_char = current_char
  end
  return n  # return original number as a failsafe
end

Consider a 1000 digit number, 999 '1's followed by a '2': 1111...11112 The single loop would look at the last two digits, swap them and immediately return. Your code would do 1000!(permutations) * 1000(map) * 1000(reject) * 1000(inject) operations.

Consider '12' followed by 998 '1's: 12111...11111. The single look would do 999 comparisons, swap them, and return. Your code would still do 1000!*1000^3 operations.

Profiling Code: See my answer here on profiling code. Profiling code in this manner is a good way to see what is taking the most time in a function. If you didn't know that permutation has very high overhead, profiling would have revealed it.

\$\endgroup\$
4
  • \$\begingroup\$ "swap the first two you encounter where a smaller digit precedes a larger digit" is not a correct algorithm. Consider the two test cases 132 -> 213 and 231 -> 312. \$\endgroup\$ Oct 11 '16 at 10:08
  • \$\begingroup\$ Well, it passes all of your original cases, but I see your point on the two new ones. It might be helpful next time to include a non-trivial test case; I wasn't entirely sure what was being asked for so mostly relied on the test cases you provided. The comment about permutation being very expensive and the link about profiling your code are still accurate \$\endgroup\$
    – Zack
    Oct 11 '16 at 13:06
  • \$\begingroup\$ I think you're confusing me with OP. \$\endgroup\$ Oct 11 '16 at 13:36
  • \$\begingroup\$ Sorry, I had 30 seconds to look at this this morning, and didn't do a very good job of checking names \$\endgroup\$
    – Zack
    Oct 11 '16 at 14:23

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.