21
\$\begingroup\$

The task:

Given an integer n, find the next number that follows the following requirements

  • The next greater number is a number where each digit, from left to right, is greater than or equal to the previous one.

    Consider \$1455\$, for example:

    \$1 < 4\$

    \$4 < 5\$

    \$5 \leq 5\$

  • The next greater number has to be bigger than n

Test Cases:

  • \$10 \to 11\$
  • \$19 \to 22\$
  • \$99 \to 111\$
  • \$321 \to 333\$
  • \$1455 \to 1456\$
  • \$11123159995399999 \to 11123333333333333\$

This is , so shortest code wins!

\$\endgroup\$
8
  • 8
    \$\begingroup\$ I'd suggest not requiring answers to finish for the last test case. Doing so means that this is essentially a chameleon challenge - the focus is no longer on golfing, but on optimisation, an entirely different goal \$\endgroup\$ Jan 8 at 1:11
  • 1
    \$\begingroup\$ Suggested test case: 1455 -> 1456 \$\endgroup\$ Jan 8 at 1:18
  • 1
    \$\begingroup\$ Ohh Thats a very nice test case! i like how u exploit the number>n \$\endgroup\$
    – DialFrost
    Jan 8 at 1:20
  • 4
    \$\begingroup\$ I'm guessing (and suggest that) you mean either "positive integer" or "non-negative integer", but if not what is the expected output for, say, -113? (Note that, strictly speaking, the digits of -113 are [-1, -1, -3] even though these might not be considered "digits"!), i.e. \$-113=-1*100+-1*10+-1*1\$, and as such the the answer would be -111 but most solutions would probably output -112) hence easiest to limit to at least "non-negative integers" \$\endgroup\$ Jan 8 at 2:41
  • 4
    \$\begingroup\$ These numbers are A009994. \$\endgroup\$
    – pxeger
    Jan 8 at 6:50

24 Answers 24

10
\$\begingroup\$

Brachylog, 3 bytes

<.o

Try it online! or Try more cases

?<.o.   # implicit input (?) and output (.)
?<.     # the input is smaller than the output
  .o.   # the output is itself when ordered
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Reading this challenge I knew immediately Brachylog would be great for it. \$\endgroup\$
    – Fatalize
    Jan 8 at 9:27
7
\$\begingroup\$

Husk, 6 bytes

ḟoΛ≤d→

Try it online!

Explanation

ḟoΛ≤d→
ḟ       find the first integer
     →  starting from input incremented
 o      such that composed function
  Λ d   every digit
   ≤    is less that or equal to the previous
\$\endgroup\$
6
\$\begingroup\$

Jelly, 7 bytes

‘DṢƑ$1#

Try it online!

How it works

‘DṢƑ$1# - Main link. Takes n on the left
‘       - Yield n+1
    $1# - Starting from n+1, find the first integer after such that:
 D      -   The digits are
   Ƒ    -   Invariant under
  Ṣ     -   Sorting
\$\endgroup\$
1
  • 2
    \$\begingroup\$ caird would you mind explaining the code? not meaning to waste your time but it really helps explain how your code actually works \$\endgroup\$
    – DialFrost
    Jan 8 at 1:12
6
\$\begingroup\$

Haskell, 52 41 bytes

9 bytes saved by AZTECCO and 2 bytes saved by xnor

g(a:b)|[a]>b=a<$a:b|1>0=a:g b
g.show.(+1)

Try it online!

Solves all the cases nearly instantly.

Explanation

The first thing to observe is that:

Find the smallest ascending digit number greater than \$n\$.

Is significantly harder than:

Find the smallest ascending digit number greater or equal to than \$n\$.

The former has a lot of edge cases around numbers that are themselves ascending in digits while the latter can be solved fairly easily.

But we can turn the latter to the former by just adding 1 before we run our algorithm. If g is the function that solves it then we just have g.show.(+1) to solve the actual problem.

So I solve the latter first:

g(a:b)|[a]>b=a<$a:b|1>0=a:g b

This goes along the list until either we meet a pair of digits that is descending (e.g. 21) or we reach the end. At that point we replace everything left with the digit we just read and exit.

So for example

122334555612990
         ^^
122334555666666

Here's what the solution looks like without this observation just handling the edge cases naively:

92 bytes

x!q@(a:b:c)|a>b=a<$q|1>0=(x++[a])!(b:c)
x!"9"=""!x++"1"
x!""="1"
x!y=x++show(1+read y)
f=(""!)

Try it online!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ @AZTECCO That's a very nice save. \$\endgroup\$
    – Wheat Wizard
    Jan 8 at 17:42
  • \$\begingroup\$ Doesn't this produce larger numbers than needed sometimes because it targets the leftmost decrease, like for 98142? \$\endgroup\$
    – xnor
    Jan 8 at 18:12
  • \$\begingroup\$ @xnor I don't think so. What should 98142 produce? \$\endgroup\$
    – Wheat Wizard
    Jan 8 at 18:14
  • \$\begingroup\$ Never mind, you're right, 99999 is the smallest \$\endgroup\$
    – xnor
    Jan 8 at 18:16
  • \$\begingroup\$ -2 bytes \$\endgroup\$
    – xnor
    Jan 8 at 18:26
6
\$\begingroup\$

R, 65 58 bytes

Or R>=4.1, 51 bytes by replacing the word function with a \.

Edit: -7 bytes thanks to @Dominic van Essen.

function(n){while(any(diff((n=n+1)%/%10^(n:0)%%10)<0))0
n}

Try it online! Try it on rdrr.io (for larger test-cases)!

Straightforward brute-force:

  1. Increment n.
  2. Split to digits (with leading 0s that don't matter).
  3. Take differences.
  4. If any of the differences is <0, loop back to 1. Otherwise, stop and output n.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 58 bytes but for some reason doesn't work for moderately large test cases on TIO... (works fine on my laptop and at rdrr.io) \$\endgroup\$ Jan 8 at 20:10
  • 3
    \$\begingroup\$ @Dominicvanessen TIO is on 3.5.2; apparently as of 3.6.2, the behavior for %/% changed for infinite values (from NEWS): "x %% L for finite x no longer returns NaN when L is infinite, nor suffers from cancellation for large finite L, thanks to Long Qu's PR#17611. Analogously, x %/% L and L %/% x suffer less from cancellation and return values corresponding to limits for large L." \$\endgroup\$
    – Giuseppe
    Jan 8 at 20:56
5
\$\begingroup\$

Vyxal, 6 bytes

{›Ds≠|

Try it Online!

{      # While...
 ›     # Increment
  D    # Make three copies
   s≠  # Check if sorted
     | # Do nothing
\$\endgroup\$
5
\$\begingroup\$

Perl 5 -p, 26 bytes

1while++$_-join'',sort/./g

Try it online!

The last test case would take about 194 hours (which is 8 days where I live). So I removed the last five digits from the test case to get the result in 7 sec. For "instant" result, also for the last big test case, this is a 78 byte suggestion: $_++;s/(@{[join"|",map$_."[0-".($_-1)."]",1..9]}).*/substr($1,0,1)x length$&/e ...try it online!

\$\endgroup\$
5
\$\begingroup\$

Ruby, 35 bytes

->x{x.next![x.chars.sort*'']||redo}

Try it online!

-8 thanks to Dingus!

\$\endgroup\$
1
  • \$\begingroup\$ @Dingus Very nice, thanks. \$\endgroup\$
    – Jonah
    Jan 8 at 23:21
4
\$\begingroup\$

C (gcc), 48 bytes

i;f(n){for(i=++n;n=n%10<n/10%10?++i:n/10;);i=i;}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 2, 49 bytes

f=lambda n:-~n*(list(`-n`)<sorted(`~n`))or f(-~n)

Attempt This Online!

Brute force: increments the given number until it is great. Unsurprisingly, chokes on the larger test case.

Python, 77 bytes

f=lambda n,t=1:(n:=n+t)*([*str(n)]<=sorted(str(n)))or 10*(g:=f(n//10,0))+g%10

Attempt This Online!

This constructs the result directly. Handles all test cases.

\$\endgroup\$
1
  • \$\begingroup\$ really nice u passed the last test case! \$\endgroup\$
    – DialFrost
    Jan 10 at 9:35
3
\$\begingroup\$

Python 3, 84

f=lambda n:n+1if all(int(i)<=int(j)for i,j in zip(str(n+1),str(n+1)[1:]))else f(n+1)

Fails on the last case due to exceeding the maximum recursion depth.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to the site! The spaces between ) and other tokens like for and else are not needed, you can remove them to save bytes. \$\endgroup\$
    – Wheat Wizard
    Jan 8 at 10:41
  • \$\begingroup\$ @WheatWizard Thanks! If you got any other tips, I'll be glad to utilize them. \$\endgroup\$
    – solid.py
    Jan 8 at 10:47
  • 1
    \$\begingroup\$ Sure we have an entire question to catalog python tips that you can check out. \$\endgroup\$
    – Wheat Wizard
    Jan 8 at 10:54
3
\$\begingroup\$

C (gcc), 59 48 bytes

f(n,t){t=++n?t=f(n/10-1),10*t+t%10:0;n=t>n?t:n;}

Try it online!

f(n,t){
  t=++n             // increment input
    ? t=f(n/10-1),  // recurse on prefix
      10*t+t%10     //   and append its last digit
    : 0;            // (base case =0)
  n=t>n?t:n;        // max of above and input
}
\$\endgroup\$
3
\$\begingroup\$

PowerShell, 48 bytes

Very simply iterates through numbers starting from the input until a number equals the sorted string representation of itself, then returns that number.

param($n)for(;++$n-ne-join("$n"|% T*y|sort)){}$n

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 67 bytes

T`9d`d`.9*$
^0
10
.
$*_¶
+`((_+¶)(?!_*\2)(_*¶)*)_*¶$
$2$1
(_+)¶
$.1

Try it online! Link includes test cases. Explanation:

T`9d`d`.9*$

Increment the input.

^0
10

Deal with any carry.

.
$*_¶

Convert each digit to unary.

+`((_+¶)(?!_*\2)(_*¶)*)_*¶$
$2$1

Propagate the first digit greater than its successor to the end of the number. E.g. 11123159995400000, 11123315999540000, 11123331599954000, ... 1123333333333331, 1123333333333333.

(_+)¶
$.1

Convert the digits back to decimal.

\$\endgroup\$
2
  • \$\begingroup\$ "Increment the input" can be shorter: .+(linefeed)$.(*.. \$\endgroup\$
    – m90
    Jan 9 at 4:46
  • \$\begingroup\$ @m90 Not in Retina 0.8.2 \$\endgroup\$
    – Neil
    Jan 9 at 8:15
2
\$\begingroup\$

Charcoal, 25 bytes

≔I⊕Nθ…θ⌕Eθ›ι§θ⊕κ¹×⁻Lθⅈ§θⅈ

Try it online! Link is to verbose version of code. Explanation:

≔I⊕Nθ

Input n, increment it, and turn it into a string.

…θ⌕Eθ›ι§θ⊕κ¹

Print the prefix up to the first digit that is greater than its subsequent digit. (There is an edge case here when all the digits are equal but the remaining code will just fill with that digit because it has no other choice.)

×⁻Lθⅈ§θⅈ

Fill the rest of the string with that digit.

\$\endgroup\$
2
\$\begingroup\$

Japt, 8 bytes

È-ìn}fUÄ

Try it

\$\endgroup\$
2
\$\begingroup\$

MathGolf, 7 bytes

)∙▒sy=▼

Port of my 05AB1E answer.

Try it online.

Explanation:

      ▼ # Do-while false with pop:
)       #  Increase the current integer by 1
        #  (which will be the implicit input in the first iteration)
 ∙      #  Triplicate it
  ▒     #  Convert the top copy to a list of digits
   s    #  Sort those digits
    y   #  Join it back together to an integer
     =  #  Check if the sorted integer is still the same as the triplicated integer
        # (after the do-while loop, output the entire stack implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Pip, 8 bytes

T$<=Ua_a

Attempt This Online!

Explanation

          ; a is command-line argument
T         ; Loop till
    Ua    ;   Increment a, and
 $        ;   Fold on
  <=      ;   Less-than-or-equal
          ; is true:
      _   ;   No-op
       a  ; After the loop, autoprint the modified value of a

Folding a number such as 1455 on <= is the equivalent of computing 1 <= 4 <= 5 <= 5, which (thanks to Pip's chaining comparison operators) is equivalent to (1 <= 4) & (4 <= 5) & (5 <= 5).


Here's a 19-byte version that can handle the largest test case:

O@Ua{y?ya>b?Yab}MPa

Attempt This Online!

O@Ua{y?ya>b?Yab}MPa
  Ua                 ; Increment a
 @                   ; Get its first digit
O                    ; Output it without a newline
    {          }MPa  ; Map this function to each pair of adjacent digits in a:
     y?              ;   Has y been assigned yet?
       y             ;   If so, use that as the next digit
        a>b?         ;   Otherwise, is the first digit of the pair greater than
                     ;   the second digit of the pair?
            Ya       ;   If so, assign the first digit to y and use that
              b      ;   Otherwise, use the second digit
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 6 bytes

[>Ð{Q#

Try it online or verify almost all test cases (except for the last one, which is shortened a bit).

Explanation:

[       # Loop indefinitely:
 >      #  Increase the current value by 1
        #  (which will be the implicit input in the first iteration)
  Ð     #  Triplicate it
   {    #  Sort the digits in the top copy
    Q   #  Pop it and another copy and check if they're still the same
     #  #  If it is: stop the infinite loop
        # (after which the remaining third value is output implicitly as result)

Here a different approach which also handles the largest test case (14 bytes):

>Dü›Å¡ćJs˜¬s∍«

Try it online or verify all test cases.

Explanation:

               #  E.g. input = 11123159995399999 
>              # Increase the (implicit) input-integer by 1
               #  STACK: 11123159995400000
 D             # Duplicate it
               #  STACK: 11123159995400000,11123159995400000
  ü            # For each overlapping pair of digits:
   ›           #  Check if the first is larger than the second
               #   STACK: 11123159995400000,[0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0]
    Å¡         # Split the (implicit) input-integer at the truthy positions
               #   STACK: [[1,1,1,2],[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]]
      ć        # Extract head; pop and push first list and remainder-lists
               # separated to the stack
               #  STACK: [[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]],[1,1,1,2]
       J       # Join this first list together to a single integer
               #  STACK: [[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]],1112
        s      # Swap to get the remainder-list
               #  STACK: 1112,[[3,1,5,9,9],[9],[5],[4,0,0,0,0,0]]
         ˜     # Flatten it
               #  STACK: 1112,[3,1,5,9,9,9,5,4,0,0,0,0,0]
          ¬    # Push its first digit (without popping the list)
               #  STACK: 1112,[3,1,5,9,9,9,5,4,0,0,0,0,0],3
           s   # Swap so the list is at the top
               #  STACK: 1112,3,[3,1,5,9,9,9,5,4,0,0,0,0,0]
            ∍  # Extend this digit to the length of this list
               #  STACK: 1112,3333333333333
             « # Append the two strings together
               #  STACK: 11123333333333333
               # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

APL 1612 16 bytes

New Approch

10⊥⌈/\⍎¨⍕1∘+

It's just a append scan and then maximum of each cell doesnt work in case idetified by @ova

1∘+⍣{∧/2≤/⍎¨⍕⍺}

Explanation

1∘+ adds 1

{∧/2≤/⍎¨⍕⍺} checks weather each number is bigger than the one preceding it

1∘+⍣{∧/2≤/⍎¨⍕⍺} continously adds 1 untill the previous function returns true i.e. A fixed point function

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This returns 15599 for 15195, where 15555 would be enough. 1∘+⍣{∧/2≤/⍎¨⍕⍺} did handle this correctly \$\endgroup\$
    – ovs
    Jan 10 at 11:29
  • \$\begingroup\$ Thanks for catching it, the second one will works as intended I will be removing the first one @ovs \$\endgroup\$ Jan 10 at 14:17
2
\$\begingroup\$

Desmos, 159 155 149 bytes

The code below supports all integers, with negative integers supported as described in Jonathan Allan's comment.

o->T(o+1-sign(o-c)min(1-sign(L-sort(L))^2)),c->T(c)
i=0
o=0
c=0
s=sign(o)
a=abs(o)
L=smod(floor(a/10^{[floor(log(a+1-ss))...0]}),10)
T(n)=\{i=c:n,i\}

Try It On Desmos!

Try It On Desmos! - Prettified

This uses a variable c to cache the input so that changes in the input can be detected (with the function T(n)), causing the rest of the program to react accordingly (That is why the program won't break if the input is changed while the ticker is still running).

The byte count can actually be lowered significantly if some liberties (A.K.A. removing the caching variable) can be taken with the I/O method:

127 123 117 bytes, with modified I/O method

o->o+1-sign(o-i)min(1-sign(L-sort(L))^2)
i=0
o=0
s=sign(o)
a=abs(o)
L=smod(floor(a/10^{[floor(log(a+1-ss))...0]}),10)

Try It On Desmos!

Try It On Desmos! - Prettified

This version removes the caching variable c and the function T(n) completely, which means that the code cannot detect any changes in the input. This means that extra steps have to be taken in order to enter in or change the input and run the code.

I'm not too sure which I/O method is considered the "accepted" version, so I'm putting both.

Also, it's unclear whether or not we have to support negative integers. If we only have to support non-negative integers or positive integers, the code can be shortened even more (the code below uses the caching variable):

140 134 bytes, supports all non-negative integers

o->T(o+1-sign(o-c)min(1-sign(L-sort(L))^2)),c->T(c)
i=0
o=0
c=0
L=mod(floor(o/10^{[floor(log(a+1-sign(o)))...0]}),10)
T(n)=\{i=c:n,i\}

Try It On Desmos!

Try It On Desmos! - Prettified

128 122 bytes, supports positive integers

o->T(o+1-sign(o-c)min(1-sign(L-sort(L))^2))),c->T(c)
i=1
o=1
c=0
L=mod(floor(o/10^{[floor(logo)...0]}),10)
T(n)=\{i=c:n,i\}

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 48 bytes

Prompts for integer

n←⍴v←⍎¨⍕⎕+1⋄10⊥⌽((n-⍴v)⍴¯1↑v),⌽v←(^\0≤1,-2-/v)/v

Try it online! Thanks to Dyalog Classic

The final example throws an error in the final digit in Dyalog Classic on TIO. Dropping the last digit of that example gives the expected result.

\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 34 bytes

~x=while !issorted("$(x[]+=1)")end

Try it online!

by bruteforcing, input is a singleton and the function mutates it

Julia 1.0, 38 bytes

!a=(m='0';map(i->m=max(i,m),"$(a+1)"))

Try it online!

more efficient approach, allowing to compute the bigger test case. Input is a number and output is a string

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 39 bytes

a->until(vecsort(d=digits(a))==d,a++);a

Try it online!

\$\endgroup\$

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.