26
\$\begingroup\$

The year 2013 had an interesting property: the digits are consecutive when sorted (0123). Let's call this type of number a sortable number: a non-negative integer whose base-10 digits are consecutive after sorting. Unfortunately, this won't happen again until 2031, and after that, not until 2103. Your challenge is to write a program or function that, when given a non-negative integer through any standard method, outputs or returns the next sortable number.

Rules

  • Input and output must be in base 10.
  • Output may be in any reasonable format (number literal, string literal, single-item array, ...).
  • Your code must produce the proper output within 1 minute for all inputs up to 98764.

Test cases

    0 -> 1
    1 -> 2
    9 -> 10
   10 -> 12
   11 -> 12
   99 -> 102
  233 -> 234
  234 -> 243
  243 -> 312
 2016 -> 2031
 2031 -> 2103
 2103 -> 2130
 2130 -> 2134
 2134 -> 2143
 9876 -> 10234
98764 -> 98765

The sortable numbers form A215014. A list of all entries up to 98765 can be found here.

Scoring

This is , so the shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ What do you mean by work? Is it OK if it takes a really long time? \$\endgroup\$ – Dennis Dec 14 '16 at 16:31
  • \$\begingroup\$ @Dennis It must finish with 1 minute for all inputs up to 98764. This has been clarified in the post. \$\endgroup\$ – ETHproductions Dec 14 '16 at 16:32
  • \$\begingroup\$ @ETHproductions Does it have to support larger inputs at all? \$\endgroup\$ – Martin Ender Dec 14 '16 at 16:36
  • \$\begingroup\$ @MartinEnder No, although I expect most (if not all) solutions will. Should the requirement be higher? \$\endgroup\$ – ETHproductions Dec 14 '16 at 16:39
  • \$\begingroup\$ @ETHproductions I don't think so, I just wanted to make sure. \$\endgroup\$ – Martin Ender Dec 14 '16 at 16:39

19 Answers 19

9
\$\begingroup\$

Python 2, 61 bytes

f=lambda n:-~n*(`sorted(`n+1`)`[2::5]in'0123456789')or f(n+1)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I want '0123456789' to be something like 1./81, but it doesn't quite work. \$\endgroup\$ – xnor Dec 15 '16 at 5:51
  • \$\begingroup\$ Best you're getting is 1./81.0000001 which still wouldn't properly work and is longer \$\endgroup\$ – Alfie Goodacre Dec 15 '16 at 9:43
  • \$\begingroup\$ @AlfieGoodacre You could do better with 1./81-1e-10 but it's still 10 bytes and you'd still have to truncate it. \$\endgroup\$ – Martin Ender Dec 15 '16 at 11:12
7
\$\begingroup\$

Jelly, 11 10 9 bytes

⁵ḶwṢ
‘Ç1#

Returns a singleton array. Try it online!

How it works

‘Ç1#  Main link. Argument: n

‘     Increment; yield n+1.
 Ç1#  Apply the helper link to k = n+1, n+2, n+3, ... until one of them maps to a
      truthy value. Yield a singleton array containing that value of k.

⁵ḶwṢ  Helper link. Argument: k

⁵     Set the return value to 10.
 Ḷ    Unlength; yield [0, ..., 9].
   Ṣ  Sort; yield the sorted array of k's decimal digits.
  w   Window-index; yield the 1-based index(truthy) of the digit array in
      [0, ..., 9], 0 (falsy) if not found.
\$\endgroup\$
6
\$\begingroup\$

MATL, 8 bytes

`QtVSdqa

Try it online! Or verify all test cases.

Explanation

`     % Do...while
  Q   %   Add 1. Takes input (implicit) in the first iteration
  t   %   Duplicate
  V   %   Convert to string. This gives an array of chars (same as a string)
      %   representing the digits
  S   %   Sort
  d   %   Consecutive differences between the chars (automatically converted
      %   to ASCII codes)
  q   %   Subtract 1. This gives an array where consecutive differences equal 
      %   to 1 are converted to 0, and the rest give a nonzero result
  a   %   True if any value is nonzero. This is the loop condition: if true
      %   (which means at least one consecutive difference was not 1), go on
      %   with the next iteration. Else exit loop
      % End do...while (implicit)
      % Display (implicit)
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 64 54 bytes

Saved a massive 10 bytes, thanks to Neil

f=n=>[...++n+''].sort().some((v,i,a)=>v-i-a[0])?f(n):n

Test cases

f=n=>[...++n+''].sort().some((v,i,a)=>v-i-a[0])?f(n):n

console.log(f(0));      // -> 1
console.log(f(1));      // -> 2
console.log(f(9));      // -> 10
console.log(f(10));     // -> 12
console.log(f(11));     // -> 12
console.log(f(99));     // -> 102
console.log(f(233));    // -> 234
console.log(f(234));    // -> 243
console.log(f(243));    // -> 312
console.log(f(2016));   // -> 2031
console.log(f(2031));   // -> 2103
console.log(f(2103));   // -> 2130
console.log(f(2130));   // -> 2134
console.log(f(2134));   // -> 2143
console.log(f(9876));   // -> 10234
console.log(f(98764));  // -> 98765

\$\endgroup\$
  • 2
    \$\begingroup\$ You can save 2 bytes from your original answer by noting that the third parameter to the map callback is the array itself, but you can go on to do much better: f=n=>[...++n+''].sort().some((v,i,a)=>v-i-a[0])?f(n):n \$\endgroup\$ – Neil Dec 14 '16 at 20:55
4
\$\begingroup\$

Pyth - 11 10 bytes

f}S`TjkU;h

Test Suite

\$\endgroup\$
4
\$\begingroup\$

PowerShell v2+, 71 68 67 bytes

param($n)do{$n++}until(-join(0..9)-match-join([char[]]"$n"|sort))$n

Try it online!

An iterative solution that runs pretty much instantaneously on my machine.

PS C:\Tools\Scripts\golfing> measure-command {.\find-the-sortable-years.ps1 98764} | fl totalseconds

TotalSeconds : 0.0487127

Yes, that's a do/until loop in a code-golf. Sorry, not sorry. Basically we loop upwards from our input $n until $n|sorted regex -matches against 0123456789. Then we place $n on the pipeline, and output is implicit.

Saved a byte by realizing that -join(0..9) is one byte shorter than the literal string 0123456789.

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

Mathematica, 63 bytes

#+1//.x_/;!Differences@Sort@IntegerDigits@x~MatchQ~{1...}:>x+1&

Replaces #+1 with the next value as long as Differences@Sort@IntegerDigits@x~MatchQ~{1...} is false, which is the condition that the current value is sortable.

Here's another fun idea, that unfortunately ended up being way too long:

FirstCase[FromDigits/@Union@@Permutations/@Join@@Array[Range,{9,10},0],x_/;x>#]&

In this one, I'm generating all the sortable years first and then I select the first one that is greater than the input.

Some more ideas that didn't turn out to be shorter than the first attempt:

#+1//.x_/;Array[Range,{9,10},0]~FreeQ~Sort@IntegerDigits@x:>x+1&
#+1//.x_/;Subsequences@Range[0,9]~FreeQ~Sort@IntegerDigits@x:>x+1&
#+1//.x_/;0~Range~9~FreeQ~{___,##&@@Sort@IntegerDigits@x,___}:>x+1&
\$\endgroup\$
3
\$\begingroup\$

PHP, 105 103 89 bytes

New 89 bytes version thanks to Titus:

for(;!$p;){$t=str_split($n=++$argv[1]);sort($t);$p=strstr('0123456789',join($t));}echo$n;

Usage:

php -r "for(;!$p;){$t=str_split($n=++$argv[1]);sort($t);$p=strstr('0123456789',join($t));}echo$n;" 9000

Previous 103 bytes version thanks to Xanderhall:

<?for($p=0;!$p;){$t=str_split($n=++$_GET[n]);sort($t);$p=strstr('0123456789',implode($t));}echo "$n\n";

Previous 105 bytes version:

<?for($n=$_GET[n]+1;;$n++){$t=str_split($n);sort($t);if(strstr('0123456789',implode($t))){echo$n;exit;}}

Usage: sortable-years.php?n=9000 outputs 9678.

Ungolfed version with test cases:

$test = array(0,1,9,10,11,99,233,234,243,2016,2031,2103,2130,2134,9876,98764);

foreach ($test as $argv[1]) {
    for(;!$p;){
        $t=str_split($n=++$argv[1]);
        sort($t);
        $p=strstr('0123456789',join($t));
    }
    echo "$n\n"; // add newline for testing
    $p=false; // reset $p for testing
}

Output:
1
2
10
12
12
102
234
243
312
2031
2103
2130
2134
2143
10234
98765

Test online! (New 89 bytes version)

Test online! (Previous 103 bytes version)

Test online! (Previous 105 bytes version)

Execution time maybe <= 1 second for all the test cases.

\$\endgroup\$
  • \$\begingroup\$ Made some improvements \$\endgroup\$ – Xanderhall Dec 15 '16 at 14:21
  • \$\begingroup\$ @Xanderhall thanks for your improvements. Actually I was trying to find a way to take that break (exit on the golfed version) away, you found it! Great. \$\endgroup\$ – Mario Dec 15 '16 at 17:33
  • \$\begingroup\$ The link I posted was just code to give you an idea of how to improve it, it's not fully golfed XD \$\endgroup\$ – Xanderhall Dec 15 '16 at 18:12
  • \$\begingroup\$ $i=0 is unnecessary (-4). join is an alias for implode (-3). echo$n is enough output (-5). $argv[1] instead of $_GET[n] allows -r which allows you to omit the <? tag (-2). \$\endgroup\$ – Titus Dec 16 '16 at 12:02
  • \$\begingroup\$ @Titus thanks a lot for your great golfing tips, I still have so much to learn about it, and I also have to pay more attention on some details too that I miss... I didn't know yet about join as alias of implode! About the php -r parameter, I used in the past but lately I'm not using it because (I don't know why) sometimes I can't make it work properly in some cases. \$\endgroup\$ – Mario Dec 16 '16 at 17:06
2
\$\begingroup\$

Perl 6, 49 bytes

{first {$/eqv($/=.comb.sort).minmax.list},$_^..*}

Explanation

{

  first

  {

    $/             # sorted list from later

    eqv            # is it equivalent

    (

      $/           # store in match variable ( doesn't need to be declared )
      =
      .comb.sort   # sorted list of digits from currently tested value

    ).minmax       # the Range of digits
            .list  # flattened to a list
  },

  $_  ^..  *       # Range starting just after input

}

Test:

# give it a lexical name for clarity
my &code = {first {$/eqv($/=.comb.sort).minmax.list},$_^..*}

my @all = +«'sortable.txt'.IO.lines;

my @gen = code(-1), &code ... ( * >= 98765 );

say @all eqv @gen; # True

say now - INIT now; # 16.3602371
\$\endgroup\$
2
\$\begingroup\$

C#, 153 130 101 bytes (122 99 83 excluding namespace declarations)

using System.Linq;n=>{while(!"0123456789".Contains(string.Concat((++n+"").OrderBy(x=>x))));return n;}

-23 bytes thanks to pinkfloydx33

another -29 thanks to Link Ng (I really should have known I don't need to convert it into an array)

Damn conversions.

(Added bonus this is surprisingly fast)

\$\endgroup\$
  • \$\begingroup\$ You don't need to string, use $"{n}".ToCharArray() or (""+n).ToCharArray() and you don't need the brackets after the while: while(!s.Contains...)n++; or better yet combine them and leave an empty loop body: while(!s.Contains(.....$"{n++}".ToCharArray()....);return n; declare s with var s="... " or remove it entirely: while(!"0123456789".Contains(... \$\endgroup\$ – pinkfloydx33 Dec 15 '16 at 1:31
  • \$\begingroup\$ I think you can also remove the first n++ and instead combine it with the above and do $"{++n}".ToCharArray() \$\endgroup\$ – pinkfloydx33 Dec 15 '16 at 1:40
  • \$\begingroup\$ @pinkfloydx33 I added a majority of the changes you suggested, if not all! \$\endgroup\$ – Alfie Goodacre Dec 15 '16 at 9:21
  • 1
    \$\begingroup\$ Remove use System; and use string instead of String for 11 bytes. Use string.Concat instead of string.Join and keep only the 2nd parameter for 1 byte. Change ""+ ++n to ++n+"" for 1 byte. Left to you as exercise: 14 more bytes can be removed. \$\endgroup\$ – Link Ng Dec 15 '16 at 13:47
  • \$\begingroup\$ @LinkNg changes have been made - I feel like a fool for the array xD \$\endgroup\$ – Alfie Goodacre Dec 15 '16 at 14:02
1
\$\begingroup\$

Befunge, 117 bytes

&>1+0v
9`#v_>:9+0\4p1+:
1:$<v
0g1+>00p:55+%9+1\4p55+/:!#v_0
v+*g09:<".........." 9p09 <
>:00g-v^<
-9:p09_v|
$v@._<$<>

Try it online!

The way we test if a year is sorted is by creating an "array" (written into the string literal on line five) and for every digit in the year, we set that index into the array to 1. Once all the digits have been processed, we count how many 1s there are in sequence, and if that count equals the year length we can assume the year is sorted.

Detailed Explanation

&>1+                              Read the year and increment it.

    0v                            The "array" is initialized with zeros prior
9`#v_>:9+0\4p1+:                     to processing each year.

1:$<v                             For every digit, set the corresponding array index
0g1+>00p:55+%9+1\4p55+/:!#v_0       to one, and increment the year length counter.

                      p09 <       Initialise the sequence counter to zero.
                     9            Push a marker onto the stack.
        ".........."              Push the values from the array onto the stack.

v+*g09:<                          Increment the sequence counter for every 1 in the
>:00g-v^<                           array and reset it on every 0. Break if it equals
-9:p09_v|                           the year length or we encounter the end marker.

  @._<$<                          If we have a match, clear the stack and output the year.
$v      >                         If we've reached the marker, drop it try the next year.
\$\endgroup\$
1
\$\begingroup\$

Ruby, 51 bytes

->n{n+=1 until'0123456789'[n.to_s.chars.sort*''];n}
\$\endgroup\$
1
\$\begingroup\$

Python 2, 68 bytes

n=input()+1
while''.join(sorted(`n`))not in'0123456789':n+=1
print n

Well beaten by @Dennis but just posted as an alternative method anyway.

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

C#, 127 bytes

using System.Linq;n=>{char[]s;while((s=(++n+"").OrderBy(x=>x).ToArray()).Select((x,i)=>i>0&&x-s[i-1]!=1).Any(x=>x));return n;};

Beat the current C# submission by 3 bytes :p Beaten back already
I know this answer will be beaten back easily...
repl.it demo

Ungolfed

n=>
{
    char[] s;
    while((
        // Store char array in variable to be referenced in Select()
        // Increment n and cast to string
        s=(++n+"")
            // Sort ascending, to array
            .OrderBy(x=>x)
            .ToArray())
        // Convert char to true if it's not at position 0,
        // and it is not 1 greater than the previous char
        .Select((x,i)=>i>0&&x-s[i-1]!=1)
        // All false: n is sortable
        // Any true: n is not sortable
        .Any(x=>x))
    // while loop body is empty
    ;
    return n;
};
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 10 9 bytes

-1 thanks to Emigna.

[>D{žhså#

Try it online!

New description coming when I have time.

\$\endgroup\$
  • 2
    \$\begingroup\$ [>D{žhså# for 9 bytes. \$\endgroup\$ – Emigna Dec 15 '16 at 8:36
1
\$\begingroup\$

Python 2, 118 117 114 108 Bytes

x,s=input()+1,sorted
while[j for i,j in enumerate(s(str(x))[1:])if int(s(str(x))[i])+1!=int(j)]:x+=1
print x

EDIT:

-1 Byte thanks to @Gábor Fekete

-6 Bytes thanks to @Zachary T

\$\endgroup\$
  • \$\begingroup\$ You can save 1 byte by aliasing the sorted function. \$\endgroup\$ – Gábor Fekete Dec 16 '16 at 14:49
  • \$\begingroup\$ Can't you save some bytes by converting to python 2? \$\endgroup\$ – Zacharý Dec 20 '16 at 0:19
  • \$\begingroup\$ Yes I could, thanks, I hadn't thought of that. \$\endgroup\$ – sonrad10 Dec 20 '16 at 0:20
1
\$\begingroup\$

PHP, 90 89 88 bytes

a completely different approach:

while(array_unique($a=str_split($n=++$argv[1]))!=$a|max($a)-min($a)-count($a)+1);echo$n;

Run with -r.

breakdown

while(
    array_unique(           // 3. unique values
        $a=str_split(       // 2. split to digits
            $n=++$argv[1]   // 1. increase number
        )
    )
    !=$a                    // 4. repeat while unique digits differ from original digits
    |                       // or
        max($a)-min($a)     // digit range
        -count($a)+1        // differs from count-1
    );
echo$n;                 // print result
\$\endgroup\$
0
\$\begingroup\$

Clojure, 104 96 91 bytes

Long method names don't make this that short... At least map-indexed and - get main calculations done in a neat way.

Edit 1: Neat, I forgot also = can take multiple arguments so I don't need to check if count of distinct values is 1.

Edit 2: No need to run (sort(seq(str %))), (sort(str %)) works equally well.

(fn[i](first(filter #(apply =(map-indexed -(map int(sort(str %)))))(rest(iterate inc i)))))

Ungolfed:

(defn f [i]
  (let [is-sorted? #(= 1 (->> % str sort (map int) (map-indexed -) set count))]
    (->> i (iterate inc) rest (filter is-sorted?) first)))
\$\endgroup\$
0
\$\begingroup\$

R, 87 bytes

f=function(x)`if`(all(diff(sort(as.double(el(strsplit(c(x+1,""),"")))))==1),x+1,f(x+1))

As usual when it comes to splitting numbers into digits, R does not have a native way of doing this. Consequently we have to coerce the input into a character, split into a character vector and subsequently convert back to any numeric type.

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.