Cele: Wyprowadź ciąg znaków, który zawiera każdą dodatnią liczbę całkowitą ściśle poniżej 1000.

Oczywistą odpowiedzią byłoby połączenie każdego z nich, a to stworzyłoby Łańcuch 2890 znaków (dzięki manatwork), aby uniknąć tego rodzaju łatwej odpowiedzi, długość łańcucha musi być mniejsza niż 1500 znaków. Oto prosty kod Java, który generuje łańcuch znaków o długości 1200 znaków.

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

import static org.junit.Assert.assertTrue;

/**
 * Created with IntelliJ IDEA.
 * User: fab
 * Date: 05/11/13
 * Time: 09:53
 * To change this template use File | Settings | File Templates.
 */
public class AStringToContainThemAll {

    @Test
    public void testsubStrings() throws Exception {
        String a = generateNewString();
        boolean cool = true;
        for (int i = 0; i < 1000; i++) {
            assertTrue(a.contains(Integer.toString(i)));
        }
    }

    private String generateNewString() {
        List<Integer> myTree = new ArrayList<Integer>();
        String finalString = new String("100");
        for (int i = 10; i < 1000; i++) {
            myTree.add(i);
        }
        while (myTree.size() > 0) {
            if (finalString.contains(Integer.toString(myTree.get(0)))) {
                myTree.remove(0);
            } else {
                String substringLong = finalString.substring(finalString.length() - 2, finalString.length());
                boolean found = false;
                loop:
                for (Integer integer : myTree) {
                    if (integer.toString().startsWith(substringLong) && !finalString.contains(integer.toString())) {
                        finalString = finalString.concat(integer.toString().substring(2, 3));
                        myTree.remove(integer);
                        found = true;
                        break loop;
                    }
                }
                if(! found){
                    finalString = finalString.concat(myTree.get(0).toString());
                    myTree.remove(0);
                }
            }


        }
        return finalString;
    }
}

Zwycięstwo najkrótszego kodu, punkt bonusowy za najkrótszy ciąg!

Golfscript - 13 bajtów, 1315 danych wyjściowych

991,{`.$2>>},

Powyższe wybiera liczby od 0-990, których pierwsza cyfra jest największą cyfrą liczby, tj. Ostatnia cyfra reprezentacji posortowanego łańcucha jest leksykograficznie mniejsza niż sam ciąg. Logika jest następująca:

W przypadku trzycyfrowej liczby abc , jeśli a nie jest największą cyfrą liczby, liczbę można pominąć, ponieważ zostanie ona później uwzględniona w jednym z dwóch przypadków:

1. b <c (np. 123 )
   Ponieważ c jest największą cyfrą, numer kabiny nie zostanie pominięty. W tym przykładzie 312 nie zostanie pominięte, podobnie jak kolejna wartość 313 , która po konkatenacji ( 312 313 ) zawiera 123 .

2. b ≥ c (np. 132 )
   Ponieważ b jest największą cyfrą, liczba bca nie zostanie pominięta. W tym przykładzie 321 nie zostanie pominięte, podobnie jak kolejna wartość 322 , która po konkatenacji ( 321 322 ) zawiera 132 . Jeśli b = c (np. 122 ), ten przypadek ma również zastosowanie. Wartość bca nie zostanie pominięta, jak poprzednio, a ponieważ a jest koniecznie mniejsza niż b , bc <a + 1> również nie zostanie pominięte. W tym przykładzie 221 222 zawiera 122 .

Ponieważ powyższy kod testuje trzecią cyfrę, a nie ostatnią, wszystkie wartości od 0 do 99 są uwzględnione w wyniku. Wartości od 1 do 99 można jednak pominąć, ponieważ jeśli występuje każda 3-cyfrowa sekwencja, wówczas każda 1-cyfrowa i 2-cyfrowa sekwencja musi być również obecna.

Wartości z 991-999 mogą być również pomijane, ponieważ są generowane przez ( 909 910 , 919 920 , ... 989 990 ).

Przy 1315 bajtach mocy wyjściowej jest to wygodnie poniżej specyfikacji problemu mniejszej niż 1500.

Wynik:

0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Wariant nr 1

14 bajtów, wyjście 1233

991,{`.$-1>>},

Wybierając ściśle ostatnią cyfrę do porównania, a nie trzecią, eliminuje się wiele niepotrzebnych wartości mniejszych niż 100 , co skraca otrzymany ciąg.

101120212230313233404142434450515253545560616263646566707172737475767780818283848586878890919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Wariant nr 2

16 bajtów, wyjście 1127

991,99>{`.$2>>},

Odrzucając wszystkie wartości mniejsze niż 99 , powstały ciąg można jeszcze bardziej skrócić.

99100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Golfscript - 19 bajtów, wyjście 1016

910,99>{`.2$\?)>+}/

Powyższe liczy od 99 do 909 , dodając dowolną wartość, która jeszcze się nie pojawiła ( 909 normalnie byłaby ostatnią wartością dodaną w ten sposób). Przesunięcie 99 do przodu jest optymalizacją, aby uniknąć konieczności używania 910 z tyłu.

Wynik:

99100101102103104105106107108109111112113114115116117118119120122123124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190192193194195196197198199200202203204205206207208209222223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333334335336337338339340344345346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444445446447448449450455456457458459460465466467468469470475476477478479480485486487488489490495496497498499500505506507508509555556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666667668669670677678679680687688689690697698699700707708709777778779780788789790798799800808809888889890899900909

Golfscript 26 bajtów, wyjście 999

909.,99>{`..$.2><3$@?+>+}/

Zauważ, że ciąg znaków 1016 wytworzony przez poprzednie rozwiązanie jest prawie optymalny, z wyjątkiem dwóch dodatkowych cyfr dla każdej wielokrotności 111 (tj. 11111Zamiast 111, 22222zamiast 222, itp.). Rozwiązanie można zoptymalizować, usuwając te dodatkowe cyfry (wstawiając tylko jedną cyfrę dla każdej z tych wartości zamiast trzech) i obracając 909do przodu, eliminując a 9(różni się to od poprzednich wersji, które 9100zamiast tego przesunęły się do tyłu ).

Rozwinął i skomentował:

909.,99>  # add 909 to the stack, and duplicate
          # create an array from 0..908, and 
          # remove the first 99 elements (99..908)
{
  `..     # stringify, duplicate twice

  $.2><   # non-divisibility by 111 check
          # true if the last char of the sorted
          # string is greater than the first char

  3$@?    # first position of this number in
          # the total string so far (-1 if not found)

  +>      # add the two previous results,
          # and slice from that point
          # (see explanation below)

  +       # concat what remains to the total string

}/        # loop over the set

Logika wyboru, które znaki mają być dołączane, przebiega w trzech przypadkach:

1. 111 ∤ n , n ⊄ s
   Wartość z pierwszego sprawdzenia to 1 , a od drugiego -1 .
   Wycinek rozpocznie się od indeksu 0 ; zwróci cały ciąg.
2. 111 ∤ n , n ⊂ s
   Wartość z pierwszego sprawdzenia wynosi 1 , a od drugiego coś ≥ 2 .
   Plasterek zacznie się zaczynać od indeksu ≥ 3 ; zwróci pusty ciąg.
3. 111 ∣ n , n ⊄ s
   Wartość z pierwszego sprawdzenia to 0 , a od drugiego -1 .
   Wycinek rozpocznie się od indeksu -1 ; zwróci tylko ostatnią postać.

Suma logiki jest taka, że ​​każda wartość, która jeszcze się nie pojawiła, zostanie dodana w całości - chyba że jest wielokrotnością 111 , w którym to przypadku zostanie dodany tylko jeden znak. Wszystkie pozostałe wartości zostaną zignorowane.

Zauważ, że wyprodukowany ciąg znaków różni się od optymalnego wytworzonego przez odpowiedź Petera Taylora .

Historia:

899,{101+.111%{`.2$\?0<*}{3/9%}if+}/

899,{101+`.2$\?0<\.~111%2*)<*+}/0

899,{101+`.2$\?0<\..2>-!2*>*+}/0

899,{101+`...2>|,1|<2$@?0<*+}/0

999,{`..$.2>>2*>2$@?0<*+}/3>0

899,{101+`..$.2><3$@?+>+}/0

Wynik:

909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900

GolfScript ( 35 31 26 znaków)

10,{:x),{:&x=x+,{x&@}/}/}/

Dane wyjściowe to

000100110111200201210211220221222300301302310311312320321322330331332333400401402403410411412413420421422423430431432433440441442443444500501502503504510511512513514520521522523524530531532533534540541542543544550551552553554555600601602603604605610611612613614615620621622623624625630631632633634635640641642643644645650651652653654655660661662663664665666700701702703704705706710711712713714715716720721722723724725726730731732733734735736740741742743744745746750751752753754755756760761762763764765766770771772773774775776777800801802803804805806807810811812813814815816817820821822823824825826827830831832833834835836837840841842843844845846847850851852853854855856857860861862863864865866867870871872873874875876877880881882883884885886887888900901902903904905906907908910911912913914915916917918920921922923924925926927928930931932933934935936937938940941942943944945946947948950951952953954955956957958960961962963964965966967968970971972973974975976977978980981982983984985986987988990991992993994995996997998999

(1020 znaków) Jest to wariant podejścia Lyndona do konkatenacji słów: zamiast prymitywnych słów 1-znakowych używa wielokrotności 111 dla krótszego kodu, ale powtarzające się wystąpienia tych liczb; i zamiast używać minimalnych elementów grup koniugacji, używa maksymalnych elementów, ponieważ skraca to pętle.

10,:^{:x^>{x.@:&<+^>{.x>{x&@}*}/}/}%3>0.

przy 40 znakach (prawdopodobnie nadal można je poprawić) generuje optymalny ciąg, który ma długość 999 znaków:

100200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908108208308408508608708808909109209309409509609709809911121131141151161171181191221231241251261271281291321331341351361371381391421431441451461471481491521531541551561571581591621631641651661671681691721731741751761771781791821831841851861871881891921931941951961971981992223224225226227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274275276277278279283284285286287288289293294295296297298299333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944454464474484494554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569576577578579586587588589596597598599666766866967767867968768868969769869977787797887897987998889899900

Próba zrobienia tego w odwrotnych ciągach powoduje problemy z pominięciem wielokrotności 111.

Aby zobaczyć, że 999 jest optymalną długością (ponieważ moje krótkie komentarze powyżej nie przekonują wszystkich), zacznij od pełnej sekwencji de Bruijna, która (traktowana jako ciąg cykliczny) zawiera każdą 3-cyfrową sekwencję znaków od 0 do 9. Ponieważ jest ich 1000, musi mieć co najmniej 1000 znaków; że może być dokładnie 1000 znaków zwykle sprawdzone przez Eulera spacer na wykresie, którego węzły są sekwencje dwucyfrowe xyz 10 krawędziami, każdy oznaczony z jednej cyfry z, które odbywają xysię yz.

Nie potrzebujemy początku sekwencji 0, więc biorąc pod uwagę sekwencję de Bruijna, możemy obrócić, aby umieścić 000na końcu. Wtedy nie potrzebujemy żadnej z sekwencji, które zawijają się do początku, ale potrzebujemy dwóch z 0s, aby zakończyć sekwencję zaczynając od cyfry wcześniej 000, więc możemy usunąć jedną z nich, aby uzyskać ciąg 999 znaków. Wszystkie pozostałe 0są używane w liczbie, która nie zaczyna się od 0.

GolfScript, 17 znaków

999,{`1$1$?0<*+}/

Proste podejście do dodawania każdej liczby, jeśli nie jest jeszcze obecna w ciągu (uwaga: 999 nie jest zaznaczone ani dodane, ale jest już zawarte w danych wyjściowych).

Dane wyjściowe to 1133 znaków:

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Nie mam żadnego kodu, ale pomyślałem, że ktoś może docenić ten intuicyjny dowód, że 999 znaków jest dolną granicą długości danych wyjściowych:

Po pierwsze, każda 1- i 2-cyfrowa liczba jest częścią 3-cyfrowej liczby, więc zignoruj ​​wszystko mniej niż 100. 100-999 włącznie to 900 3-cyfrowych liczb.

Najbardziej optymalnym sposobem rozwiązania problemu jest użycie każdej postaci w jak największym stopniu. Oznacza to, że liczby nakładają się na siebie tak bardzo, jak to możliwe:

123
 234
  345

Pierwszy numer doda zatem 3 znaki, a każdy kolejny numer doda 1 znak. To daje 3 + 899 = 902 znaków jako dolną granicę.

Jednak gdy jest zero, nie możemy go użyć do rozpoczęcia nowej 3-cyfrowej liczby. Możemy jednak użyć go ponownie w środku innej 3-cyfrowej liczby, o ile nie następuje po nim kolejne zero:

120
 203  <- Ok.
  034 <- not a number 100-999.

Ale:

100
 002  <- not a number 100-999.
  023 <- not a number 100-999.

Dlatego każde zero, które pojawia się na wyjściu, rozszerza wynik o 1 znak - z wyjątkiem dwóch ostatnich znaków, które mogą być zerowe, ponieważ nie nakładają się na żadne dalsze liczby:

???
 ??0
  ?00

Istnieje 81 liczb ze ściśle jednym zerem na środku (? 0?), 81 ze ściśle jednym zerem na końcu (? 0) i 9 z dwoma zerami (? 00).

Każda liczba 0 może dzielić zero z liczbą 0 numer lub liczba 00, ale nie oba. 0? i? 00 nigdy nie może dzielić zer, więc na wyjściu musi być co najmniej 81 + 9 * 2 zer.

Daje to dolną granicę 3 + 899 + 81 + 9 * 2 - 2 = 999 znaków.

Przepraszam, jeśli jest to uważane za nie na temat, ale było zbyt długo, aby zmieścić się w komentarzu.

Perl, 37 34 33 32 (1136 1132 znaków)

for$@(1..999){$_.=$@x!/$@/}print

za $ @ (1..999) {$ _. = $ @ if! / $ @ /} print

dla $ i (1..999) {$ _. = $ i jeśli! / $ i /} drukuj

for (1..1e3) {$ s. = $ _ if $ s! ~ / $ _ /} print $ s

Wyjścia:

12345678910111314151617181920212224252627282930323335363738394043444647484950545557585960656668697076777980878890991001021031041051061071081091101121141151161171181191201241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901931941951961971981992002032042052062072082092192202212232252262272282292302312352362372382392402432442452462472482492502532542552562572582592602632642652662672682692702732742752762772782792802832842852862872882892902942952962972982993003043053063073083093113293303323343363373383393403423463473483493503543553563573583593603643653663673683693703743753763773783793803843853863873883893903953963973983994004054064074084094224394404434454474484494504534574584594604654664674684694704754764774784794804854864874884894904964974984995005065075085095335495505545565585595605645685695705765775785795805865875885895905975985996006076086096446596606656676696706756796806876886896906986997007087097557697707767787807867907977998008098668778798808878888978988999009089329439549659769799879891000

Krótszy ciąg: 38 37 34 (1020 znaków):

$_.=$@x!/$@/while$@=--$@%1e3;print

for ($ @ = 1e3; $ @ -;) {$ _. = $ @ if! / $ @ /} print

for ($ i = 1e3; $ i -;) {$ _. = $ i jeśli! / $ i /} drukuj

Wyjścia:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Wciąż niezadowolony z powielania, zwłaszcza 99999 na początku! Myślę jednak, że o wiele więcej kontroli stworzyłoby o wiele więcej kodu ...

Edycja: Dodano sugestię @Peter Taylor

Edycja 2: Kilka świetnych sugestii od @primo! Dziękuję Ci

APL (20, wyjście: 1020)

{∨/⍺⍷⍵:⍵⋄⍵,⍺}/⍕¨⍳999

Wyjaśnienie:

• {∨/⍺⍷⍵:⍵⋄⍵,⍺}: if ⍺jest podciągiem ⍵, return ⍵, else return⍵,⍺
• /: zmniejszyć ponad
• ⍕¨: reprezentacja ciągu każdego z nich
• ⍳999: liczby całkowite od 1do 999.

Wynik:

9999989979969959949939929919909889879869859849839829819809789779769759749739729719709689679669659649639629619609589579569
      55954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913
      91291191090890790690590490390290190088888788688588488388288188087787687587487387287187086786686586486386286186085785
      68558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108
      07806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735
      73473373273173072672572472372272172071671571471371271171070670570470370270170066666566466366266166065565465365265165
      06456446436426416406356346336326316306256246236226216206156146136126116106056046036026016005555545535525515505445435
      42541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411
      410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

APL (41, wyjście: 999)

'0',⍨⊃{⍵,⍺⍴⍨(1=⍴∪⍺)∨3×~∨/⍺⍷⍵}/⌽⍕¨100+⍳898

Wyjaśnienie:

• ⌽⍕¨100+⍳898: ('999' '998' ... '101')(w odwrotnej kolejności, ponieważ redukcja idzie w prawo do lewej w APL, tj. F/a b c ≡ a F (b F c))
• /: zmniejszyć
• ⍵,⍺⍴⍨: prawy argument, po którym następują pierwsze Nznaki lewego argumentu, gdzie Njest:
• 3×~∨/⍺⍷⍵: 3jeśli ⍺nie jest podciągiem ⍵, w przeciwnym razie0
• (1=⍴∪⍺): 1jeśli ⍺ma tylko jeden unikalny charakter, w przeciwnym razie0
• ∨: największy wspólny dzielnik dwóch poprzednich wartości, więc: 1jeśli ⍺nie jest już w nim ⍵i ma tylko jeden unikalny znak, 3jeśli ⍺nie jest już w nim, ⍵ale ma więcej niż jeden niepowtarzalny znak, w 0przeciwnym razie.
• '0',⍨: dodaj zero na końcu wyniku

Wynik:

10110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451
      46147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188
      18919019219319419519619719819920020220320420520620720820922232242252262272282292302332342352362372382392402432442452
      46247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294
      29529629729829930030330430530630730830933343353363373383393403443453463473483493503543553563573583593603643653663673
      68369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444544644744844945045545645
      74584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566
      56756856957057657757857958058658758858959059659759859960060660760860966676686696706776786796806876886896906976986997
      00707708709777877978078878979079879980080880988898908999009099100

Rubinowy: 50 46 znaków (1020 znaków wyjściowych)

s=""
999.downto(0){|i|s[n=i.to_s]||s+=n}
$><<s

Przykładowy przebieg:

bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||s+=n};$><<s'
999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Testowe uruchomienie:

bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||s+=n};$><<s' | ruby -ne 'p (0..999).reject{|i|$_[i.to_s]}'
[]

Rubinowy: 102 97 znaków (999 znaków wyjściowych)

s=""
999.downto(0){|i|s[n=i.to_s]||[2,1].map{|j|n[0,j]==s[-j,j]&&s+=n[j,9]and break}&&s+=n}
$><<s

Przykładowy przebieg:

bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||[2,1].map{|j|n[0,j]==s[-j,j]&&s+=n[j,9]and break}&&s+=n};$><<s'
999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110100

Testowe uruchomienie:

bash-4.1$ ruby -e 's="";999.downto(0){|i|s[n=i.to_s]||[2,1].map{|j|n[0,j]==s[-j,j]&&s+=n[j,9]and break}&&s+=n};$><<s' | ruby -ne 'p (0..999).reject{|i|$_[i.to_s]}'
[]

JavaScript, 39

for(k=i="999";~k.indexOf(--i)?i:k+=i;);

Wynik 1020 znaków:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Weryfikacja: for(i=0;i<1000;i++)console.assert(k.indexOf(i)>=0)

Mathematica ( 62 64 znaki, wyjście 1002)

Ponieważ wykorzystuje to natywną funkcję, tym bardziej doceniam piękno krótszych rozwiązań od zera. Dane wyjściowe mają długość 1002 znaków.

<< Combinatorica`
"79" <> DeBruijnSequence["0"~CharacterRange~"9", 3]

"799798787770760750740730720710980970960950940930920910108908708608508408308208889998988081009909008007006005004003002000190180170160150140130120119118117116115114113112912812712612512412312213913813713613513413313214914814714614514414314215915815715615515415315216916816716616516416316217917817717617517417317218918818718618518418318219919819719619519419319212111029028027026025024023022922822722622522422392382372362352342332492482472462452442432592582572562552542532692682672662652642632792782772762752742732892882872862852842832992982972962952942932322202103903803703603503403393383373363353349348347346345344359358357356355354369368367366365364379378377376375374389388387386385384399398397396395394343330320310490480470460450449448447446445945845745645546946846746646547947847747647548948848748648549949849749649545444043042041059058057056055955855755695685675665795785775765895885875865995985975965655505405305205106906806706696686679678677689688687699698697676660650640630620610790780779778978879"

Mathematica, 51 znaków

""<>Table[ToString/@({i,j,k}-1),{i,10},{j,i},{k,i}]

Wyjście (1155 znaków):

000100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999

Python - 53 63, 1134 wyjście

Jest to dość brutalna siła, ale jest ważna. Tak, ma wiodące zero, ale zapisuje dwa znaki, nie mając range(1,1000).

s=''
for i in range(1e3):s+=`i`*(not`i`in s)
print s

Powyższe rzuca DeprecationWarningponad użycie 1e3 w range()wywołaniu, ale ratuje postać przed użyciem 1000.

Istnieje również nieco bardziej optymalna wersja wyjściowa długości, poprzez odwrócenie łańcucha kosztem 65 znaków (dzięki res i filmor za wskazówki) :

Python - 58, 1021 danych wyjściowych

s=''
for i in range(999,9,-1):s+=`i`*(not`i`in s)
print s

K, 33

{$[#ss[x]@y;x;,/x,y]}/["";$!1000]

Zasadniczo to samo co rozwiązanie Howardsa - 1133 znaków.

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Java - 126 98 znaków (Java 6)

class b{static{String s="";for(int a=999;a>0;a--)s=s.contains(""+a)?s:s+a;System.out.println(s);}}

Wyjście (1020 znaków):

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Może osiągnąć dobry (według Petera Taylora , ale później powiedział, że 999 jest optymalny) Długość łańcucha, dodając kilka znaków (+20 znaków dla 147 118):

class b{static{String s="";for(int a=999;a>0;a--)s=s.contains(""+a)?s:(a+1)%111==0?s+a%10:s+a;System.out.println(s);}}

Wyjście (1002 znaków):

999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110101100

Edycja : Podziękowania dla Fabinout za wskazanie, że Java 6 może zapisać 28 znaków.

Windows PowerShell - wyjście 40, 1020

999..0|%{$s+=if(!($s-match$_)){"$_"}};$s

Wynik:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Haskell, 75 bajtów - wyjście 1002

Podejście sitowe, które zwraca minimalne rozwiązanie.

(\n->head.filter(\s->and[show k`isInfixOf`s|k<-[1..n]]).map show$[1..])1000

Pamiętaj, że to rozwiązanie jest niepraktycznie wolne.

PowerShell, 36 bajtów, 1020 danych wyjściowych

999..9|%{$s+=(,"$_")[$s-match$_]};$s

Wynik:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Alternatywnie, 69 bajtów, 1000 wyjść

999..9|%{$s+=("$_",($x="$_"[-1]))[2*($s-match$_)+($s+$x-match$_)]};$s

Wynik:

9998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101100

Alternatywnie, 82 73 bajty, wyjście 999 (minimum)

for(;$z=9..0|?{"000$x"-notmatch-join"$x$_"[-3..-1]}|%{"$_"}){$x+=$z[0]}$x

Jest to uproszczony algorytm z Generuj najkrótszy De Bruijn dostosowany do stałych: alfabet = 9876543210i długość =3

Wynik:

999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110100

Skrypt testowy:

$f= {

#999..0|%{$s+=if(!($s-match$_)){"$_"}};$s

#999..9|%{$s+=("$_",($x="$_"[-1]))[2*($s-match$_)+($s+$x-match$_)]};$s-replace'1100','100'
#999..9|%{$s+=("$_",($x="$_"[-1]))[2*($s-match$_)+($s+$x-match$_)]};$s
#999..9|%{$s+=(,"$_")[$s-match$_]};$s-replace'(.)\1{3,}','$1$1$1'
#999..9|%{$s+=(,"$_")[$s-match$_]};$s-replace'(.)\1{3,}','$1$1$1'-replace'1100','0'
 for(;$z=9..0|?{"000$x"-notmatch-join"$x$_"[-3..-1]}|%{"$_"}){$x+=$z[0]}$x
#999..9|%{$s+=(,"$_")[$s-match$_]};$s

}

$s=&$f

$s
"Length:"
$s.Length
"count(###)!=1:"
$x=@{}
0..($s.Length-3)|%{$s.Substring($_,3)}|Group|%{
    $x[+$_.Name]=$_.Count
}
100..999|?{$x.$_-ne1}|%{,($_,+$x.$_)}|%{"$_"}
"count(##)!=10:"
$x=@{}
0..($s.Length-2)|%{$s.Substring($_,2)}|Group|%{
    $x[+$_.Name]=$_.Count
}
10..99|?{$x.$_-ne10}|%{,($_,+$x.$_)}|%{"$_"}
"count(#)!=100:"
$x=@{}
0..($s.Length-1)|%{$s.Substring($_,1)}|Group|%{
    $x[+$_.Name]=$_.Count
}
0..9|?{$x.$_-ne100}|%{,($_,+$x.$_)}|%{"$_"}
"All numbers:"
999-eq(1..999|?{$s-match$_}).Count

05AB1E , 9 bajtów i 1109 znaków

₄FDNå_iNì

Wyjścia:

90990190089989088981980980880079979879078978878077977870970870770069969869769068968868768067967867767066966866760960860760660059959859759659058958858758658057957857757657056956856756656055955855755650950850750650550049949849749649549048948848748648548047947847747647547046946846746646546045945845745645545044944844744644540940840740640540440039939839739639539439038938838738638538438037937837737637537437036936836736636536436035935835735635535435034934834734634534434033933833733633533430930830730630530430330029929829729629529429329028928828728628528428328027927827727627527427327026926826726626526426326025925825725625525425325024924824724624524424324023923823723623523423323022922822722622522422320920820720620520420320220019919719619519419319219118918818718618518418318218017917817717617517417317217016916816716616516416316216015915815715615515415315215014914814714614514414314214013913813713613513413313213012912812712612512412312212011811711611511411311211110910810710610510410310210110099919089888079787770696867666059585756555049484746454440393837363534333029282726252423222018171615141312119876543210

Wypróbuj online lub sprawdź, czy zawiera wszystkie liczby poniżej 1000 .

Wyjaśnienie:

₄            # Push 1000
 F           # Loop N in the range [0,1000):
  D          #  Duplicate the top value on the stack
   Nå_i      #  If it does not contain N as substring yet:
       Nì    #   Prepend N to it
             # (Output implicitly after the loop)

Pyke, 13 bajtów (niekonkurujących), długość łańcucha 1133

Pyke jest nowszy niż wyzwanie i dlatego jest niekonkurencyjny.

k~mV~oi{!o`*+

Wypróbuj tutaj!

              - o = 0
k~mV          - repeat 1000 times, i = ""
    ~oi{      -     str(o) in i
        !     -    not ^
         o`*  -   str(o++) * ^
            + -  i += ^

PHP, 48 44 bajtów

Dzięki @primo za przypomnienie mi ereg.

for($i=1e3;--$i;ereg($i,$s)?:$s.=$i);echo$s;

lub

for($i=1e3;ereg(--$i,$s)?$i:$s.=$i;);echo$s;

wyjście: 1020 znaków. wymaga PHP <7

PHP 7, 48 bajtów:

ereg został usunięty w PHP 7

for($i=1e3;--$i;strstr($s,"$i")?:$s.=$i);echo$s;

Jeśli drugi argument funkcji strstr(lub strposinnych funkcji wyszukiwania ciągów) nie jest ciągiem, zostanie użyty jako kod ascii, więc $iwymaga rzutowania na ciąg.

Groovy, 49 znaków / bajtów

Nie byłem pewien, czy zrobić to jako funkcję zwracającą zmienną łańcuchową, czy wydrukować wynik, więc to po prostu wypisuje ją na standardowe wyjście. Za pomocą wyrażenia regularnego zapisano 2 bajty, używając operatora trójskładnikowego zamiast „if” zapisano kolejny bajt. Łańcuch wyjściowy ma 1133 znaków.

a='';1000.times{a+=(a==~/.*$it.*/)?'':it};print a

Wynik:

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Game Maker Language, 1014 - String 1000

show_message(909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900)

Również:

Ruby, 1003 - Ciąg 1000

p'909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900'