Znajdź lata do sortowania


26

Rok 2013 miał ciekawą właściwość: cyfry są sortowane po kolei (0123). Nazwijmy ten typ liczbą liczbą możliwą do sortowania: nieujemną liczbą całkowitą, której 10-cyfrowe cyfry są następujące po sortowaniu. Niestety, powtórzy się to dopiero w 2031 r., A potem dopiero w 2103. Wyzwanie polega na napisaniu programu lub funkcji, która, gdy otrzyma nieujemną liczbę całkowitą za pomocą dowolnej standardowej metody, wyświetli lub zwróci następną możliwą do sortowania liczbę.

Zasady

  • Wejście i wyjście musi być w bazie 10.
  • Dane wyjściowe mogą być w dowolnym rozsądnym formacie (literał liczbowy, literał łańcuchowy, tablica jednopunktowa, ...).
  • Twój kod musi wygenerować poprawny wynik w ciągu 1 minuty dla wszystkich danych wejściowych do 98764.

Przypadki testowe

    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

Numery sortowalne tworzą A215014 . Lista wszystkich wpisów do 98765 znajduje się tutaj .

Punktacja

To jest , więc wygrywa najkrótszy kod w bajtach.


Co masz na myśli przez pracę ? Czy to w porządku, jeśli zajmuje to naprawdę dużo czasu?
Dennis

@Dennis Musi zakończyć się 1 minutę dla wszystkich danych wejściowych do 98764. Zostało to wyjaśnione w poście.
ETHproductions

@ETHproductions Czy w ogóle musi obsługiwać większe nakłady?
Martin Ender

@MartinEnder Nie, chociaż spodziewam się większości (jeśli nie wszystkich) rozwiązań. Czy wymóg powinien być wyższy?
ETHproductions

@ETHproductions Nie sądzę, chciałem się tylko upewnić.
Martin Ender

Odpowiedzi:


9

Python 2 , 61 bajtów

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

Wypróbuj online!


1
Chcę '0123456789'być czymś takim 1./81, ale to nie do końca działa.
xnor

Najlepsze, co dostajesz, to to, 1./81.0000001co nadal nie działa poprawnie i jest dłuższe
Alfie Goodacre,

@AlfieGoodacre Mógłbyś zrobić to lepiej, 1./81-1e-10ale nadal ma 10 bajtów i nadal będziesz musiał go obciąć.
Martin Ender

7

Galaretka , 11 10 9 bajtów

⁵ḶwṢ
‘Ç1#

Zwraca tablicę singletonów. Wypróbuj online!

Jak to działa

‘Ç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.

6

MATL , 8 bajtów

`QtVSdqa

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

`     % 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)

5

JavaScript (ES6), 64 54 bajtów

Oszczędność ogromnych 10 bajtów dzięki Neilowi

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

Przypadki testowe


2
Możesz zapisać 2 bajty z oryginalnej odpowiedzi, zauważając, że trzecim parametrem mapwywołania zwrotnego jest sama tablica, ale możesz dalej robić znacznie lepiej:f=n=>[...++n+''].sort().some((v,i,a)=>v-i-a[0])?f(n):n
Neil,


4

PowerShell v2 +, 71 68 67 bajtów

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

Wypróbuj online!

Iteracyjne rozwiązanie, które działa niemal natychmiast na moim komputerze.

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

TotalSeconds : 0.0487127

Tak, to jest pętla do/ untilw golfie kodowym. Przepraszam, nie przepraszam. Zasadniczo zapętlamy w górę od naszego wejścia, $n$n|sorted regex -matchprzeciw 0123456789. Następnie umieszczamy $nw potoku, a wynik jest niejawny.

Zapisano bajt, zdając sobie sprawę, że -join(0..9)jest on o jeden bajt krótszy niż ciąg literalny 0123456789.


3

Mathematica, 63 bajty

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

Zastępuje #+1następną wartością, o ile Differences@Sort@IntegerDigits@x~MatchQ~{1...}ma wartość false, co jest warunkiem sortowania bieżącej wartości.

Oto kolejny zabawny pomysł, który niestety okazał się zbyt długi:

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

W tym pierwszym generuję wszystkie sortowalne lata, a następnie wybieram pierwszy, który jest większy niż nakład.

Kilka innych pomysłów, które nie okazały się krótsze niż pierwsza próba:

#+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&

3

PHP, 105 103 89 bajtów

Nowa wersja 89 bajtów dzięki Titusowi:

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

Stosowanie:

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

Poprzednia wersja 103 bajtów dzięki Xanderhall:

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

Poprzednia 105 bajtów wersja:

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

Zastosowanie: sortable-years.php?n=9000wyjścia 9678.

Wersja bez golfa z przypadkami testowymi:

$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

Przetestuj online! (Nowa wersja 89 bajtów)

Przetestuj online! (Poprzednia wersja 103 bajtów)

Przetestuj online! (Poprzednia wersja 105 bajtów)

Czas wykonania może wynosić <= 1 sekundę dla wszystkich przypadków testowych.



@Xanderhall dzięki za ulepszenia. Właściwie to próbowałem znaleźć sposób, aby zabrać to break( exitw wersji golfowej), znalazłeś to! Świetny.
Mario,

Link, który zamieściłem, był tylko kodem, aby dać ci wyobrażenie, jak to poprawić, nie jest w pełni
golfowy

$i=0jest niepotrzebne (-4). joinjest aliasem dla implode(-3). echo$njest wystarczająca moc wyjściowa (-5). $argv[1]zamiast $_GET[n]pozwala, -rco pozwala pominąć <?znacznik (-2).
Tytus

@Titus bardzo dziękuję za wasze świetne wskazówki golfowe, wciąż mam wiele do nauczenia się na ten temat, a także muszę zwracać większą uwagę na niektóre szczegóły, za którymi tęsknię ... Nie znałem jeszcze joinjako aliasu implode! O tym php -rparametrze użyłem w przeszłości, ale ostatnio go nie używam, ponieważ (nie wiem dlaczego) czasami nie mogę sprawić, aby działał poprawnie w niektórych przypadkach.
Mario,

2

Perl 6 , 49 bajtów

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

Wyjaśnienie

{

  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

2

C #, 153 130 101 bajtów ( 122 99 83 z wyłączeniem deklaracji przestrzeni nazw)

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

-23 bajty dzięki pinkfloydx33

kolejne -29 dzięki Link Ng (naprawdę powinienem wiedzieć, że nie muszę konwertować go na tablicę)

Cholerne konwersje.

(Dodano bonus, który jest zaskakująco szybki)


Nie musisz ciągnąć, używać $"{n}".ToCharArray()lub (""+n).ToCharArray()i nie potrzebujesz po tym czasie nawiasów: while(!s.Contains...)n++;lub lepiej jeszcze połącz je i pozostaw pustą while(!s.Contains(.....$"{n++}".ToCharArray()....);return n;var s="... "while(!"0123456789".Contains(...
treść

Myślę, że możesz także usunąć pierwszy n++i zamiast tego połączyć go z powyższym i zrobić$"{++n}".ToCharArray()
pinkfloydx33

@ pinkfloydx33 Dodałem większość zmian, które zasugerowałeś, jeśli nie wszystkie!
Alfie Goodacre,

1
Usuń use System;i użyj stringzamiast String11 bajtów. Użyj string.Concatzamiast string.Joini zachowaj tylko drugi parametr dla 1 bajtu. Zmień ""+ ++nna ++n+""na 1 bajt. Pozostawiony tobie jako ćwiczenie: można usunąć jeszcze 14 bajtów.
Link z

@LinkNg zmiany zostały wprowadzone - Czuję się jak głupiec dla tablicy xD
Alfie Goodacre

1

Befunge , 117 bajtów

&>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@._<$<>

Wypróbuj online!

Sposób, w jaki sprawdzamy, czy rok jest sortowany, polega na utworzeniu „tablicy” (zapisanej w literale ciągu w linii piątej) i dla każdej cyfry w roku ustawiamy ten indeks na tablicę na 1. Po tym, jak wszystkie cyfry zostaną przetworzone, zliczamy, ile jeden z nich jest po kolei, a jeśli liczba ta jest równa długości roku, możemy założyć, że rok jest posortowany.

Szczegółowe wyjaśnienie

&>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.

1

Rubinowy, 51 bajtów

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

1

Python 2, 68 bajtów

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

Dobrze pobity przez @Dennis, ale i tak opublikowany jako alternatywna metoda.


1

C #, 127 bajtów

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;};

Pokonaj bieżące przesłanie C # o 3 bajty: p Pobity już
wiem Wiem, że odpowiedź zostanie łatwo pobrana ...
repl.it demo

Nie golfił

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;
};


1

Python 2, 118 117 114 108 bajtów

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

EDYTOWAĆ:

-1 bajtów dzięki @ Gábor Fekete

-6 Bajtów dzięki @Zachary T.


Możesz zapisać 1 bajt poprzez aliasing sortedfunkcji.
Gábor Fekete

Nie możesz zapisać niektórych bajtów, konwertując na Python 2?
Zacharý

Tak, mogłem, dzięki, nie myślałem o tym.
sonrad10,

1

PHP, 90 89 88 bajtów

zupełnie inne podejście:

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

Uruchom z -r.

awaria

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

0

Clojure, 104 96 91 bajtów

Długie nazwy metod nie są takie krótkie ... Przynajmniej map-indexedi -wykonuj główne obliczenia w zgrabny sposób.

Edycja 1 : Zgrabne, zapomniałem też o =wielu argumentach, więc nie muszę sprawdzać, czy liczba różnych wartości wynosi 1.

Edycja 2 : Nie musisz biegać (sort(seq(str %))), (sort(str %))działa równie dobrze.

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

Nie golfowany:

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

0

R, 87 bajtów

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

Jak zwykle, jeśli chodzi o dzielenie liczb na cyfry, R nie ma natywnego sposobu na zrobienie tego. W związku z tym musimy zmusić dane wejściowe do postaci, podzielić na wektor znaków, a następnie przekonwertować z powrotem na dowolny typ liczbowy.

Wypróbuj online

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.