Objetivos: Saída de uma String que contém todos os números inteiros positivos estritamente abaixo de 1000.

A resposta óbvia seria concatenar cada um deles, e isso criaria uma String de 2890 caracteres (graças ao manatwork). Para evitar esse tipo de resposta fácil, o comprimento da string deve ter menos de 1500 caracteres. Aqui está um código Java simples que gera uma String de 1200 caracteres.

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

Menor ganho de código, ponto de bônus pela menor string!

Golfscript - 13 bytes, saída 1315

991,{`.$2>>},

O item acima seleciona os números de 0 a 990, cujo primeiro dígito é o maior dígito do número, ou seja, o último dígito da representação da sequência classificada é lexicograficamente menor que a própria sequência. A lógica é a seguinte:

Para um número de 3 dígitos abc , se a não for o maior dígito do número, o número poderá ser ignorado, pois será coberto por um dos dois casos mais tarde:

1. b <c (por exemplo, 123 )
   Como c é o dígito maior, o número da cabine não será pulado. Neste exemplo 312 não será ignorado, nem o próximo valor 313 , que quando concatenado ( 312 313 ) contém 123 .

2. b ≥ c (por exemplo, 132 )
   Como b é o dígito maior, o número bca não será pulado. Neste exemplo, 321 não será ignorado, nem o próximo valor 322 , que quando concatenado ( 321 322 ) contém 132 . Se b = c (por exemplo, 122 ), este caso também se aplica. O valor bca não será ignorado, como antes, e como a é necessariamente menor que b , bc <a + 1> também não será ignorado. Neste exemplo, 221 222 contém 122 .

Como o código acima testa o terceiro dígito, e não estritamente o último, todos os valores de 0 a 99 são incluídos no resultado. Os valores de 1 a 99 podem ser ignorados, no entanto, porque se cada sequência de 3 dígitos estiver presente, todas as seqüências de 1 e 2 dígitos também deverão estar presentes.

Os valores de 991-999 também podem ser ignorados, pois são gerados por ( 909 910 , 919 920 , ... 989 990 ).

Em 1315 bytes de saída, isso está confortavelmente sob a especificação do problema de menos de 1500.

Resultado:

0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Variação # 1

14 bytes, saída 1233

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

Ao selecionar estritamente o último dígito para comparação, em vez do terceiro, muitos dos valores desnecessários menores que 100 são eliminados, diminuindo a sequência resultante.

101120212230313233404142434450515253545560616263646566707172737475767780818283848586878890919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Variação # 2

16 bytes, saída 1127

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

Ao extrair todos os valores com menos de 99 de antemão, a sequência resultante pode ser reduzida ainda mais.

99100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Golfscript - 19 bytes, saída 1016

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

O acima conta de 99 a 909 , adicionando qualquer valor que ainda não apareceu ( 909 seria normalmente o último valor adicionado dessa maneira). Moving 99 para a frente é uma otimização para evitar a necessidade de 910 na parte traseira.

Resultado:

99100101102103104105106107108109111112113114115116117118119120122123124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190192193194195196197198199200202203204205206207208209222223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333334335336337338339340344345346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444445446447448449450455456457458459460465466467468469470475476477478479480485486487488489490495496497498499500505506507508509555556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666667668669670677678679680687688689690697698699700707708709777778779780788789790798799800808809888889890899900909

Golfscript 26 bytes, saída 999

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

Observe que a sequência de 1016 caracteres produzida pela solução anterior é quase ideal, exceto por ter dois dígitos extras para cada múltiplo de 111 (ou seja, em 11111vez de 111, em 22222vez de 222etc.). A solução pode ser otimizada removendo esses dígitos extras (inserindo apenas um dígito em cada um desses valores, em vez de três) e girando909 para a frente, eliminando um 9(que difere das versões anteriores, que foram movidas 9100para trás) )

Desenrolou e comentou:

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

A lógica para escolher quais caracteres são acrescentados segue três casos:

1. 111 ∤ n , n ⊄ s
   O valor da primeira verificação é 1 e da segunda -1 .
   A fatia começará a partir do índice 0 ; retornará toda a cadeia.
2. 111 ∤ n , n ⊂ s
   O valor do primeiro cheque é 1 e, do segundo, algo ≥ 2 .
   A fatia começará a olhar a partir do índice ≥ 3 ; retornará uma string vazia.
3. 111 ∣ n , n ⊄ s
   O valor da primeira verificação é 0 e da segunda -1 .
   A fatia começará a partir do índice -1 ; retornará apenas o último caractere.

A soma da lógica é que qualquer valor que ainda não apareceu será anexado por inteiro - a menos que seja um múltiplo de 111 ; nesse caso, apenas um caractere será acrescentado. Todos os outros valores serão ignorados.

Observe que a sequência produzida é diferente da sequência ideal produzida pela resposta de Peter Taylor .

História:

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

Resultado:

909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900

GolfScript ( 35 31 26 caracteres)

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

Saída é

000100110111200201210211220221222300301302310311312320321322330331332333400401402403410411412413420421422423430431432433440441442443444500501502503504510511512513514520521522523524530531532533534540541542543544550551552553554555600601602603604605610611612613614615620621622623624625630631632633634635640641642643644645650651652653654655660661662663664665666700701702703704705706710711712713714715716720721722723724725726730731732733734735736740741742743744745746750751752753754755756760761762763764765766770771772773774775776777800801802803804805806807810811812813814815816817820821822823824825826827830831832833834835836837840841842843844845846847850851852853854855856857860861862863864865866867870871872873874875876877880881882883884885886887888900901902903904905906907908910911912913914915916917918920921922923924925926927928930931932933934935936937938940941942943944945946947948950951952953954955956957958960961962963964965966967968970971972973974975976977978980981982983984985986987988990991992993994995996997998999

(1020 caracteres) Essa é uma variante da abordagem de concatenação de palavras de Lyndon: em vez de usar as palavras primitivas de 1 caractere, ele usa múltiplos de 111 para código mais curto, mas ocorrências repetidas desses números; e, em vez de usar elementos mínimos dos grupos de conjugação, ele usa elementos máximos, porque isso reduz os loops.

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

em 40 caracteres (provavelmente ainda pode ser aprimorado) gera uma string ideal, que tem 999 caracteres:

100200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908108208308408508608708808909109209309409509609709809911121131141151161171181191221231241251261271281291321331341351361371381391421431441451461471481491521531541551561571581591621631641651661671681691721731741751761771781791821831841851861871881891921931941951961971981992223224225226227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274275276277278279283284285286287288289293294295296297298299333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944454464474484494554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569576577578579586587588589596597598599666766866967767867968768868969769869977787797887897987998889899900

Tentar fazer isso reverter seqüências de caracteres tem problemas ao omitir os múltiplos de 111.

Para ver que 999 é o tamanho ideal (já que meus breves comentários acima não convencem todos), comece na sequência completa de De Bruijn que (tomada como uma sequência cíclica) contém todas as seqüências de 3 dígitos de caracteres de 0 a 9. Como existem 1000, deve ter pelo menos 1000 caracteres; que ele pode ter precisamente 1.000 caracteres é geralmente comprovado por uma caminhada euleriana em um gráfico cujos nós são sequências de dois dígitos xycom 10 arestas, cada uma rotulada com um dígito z, que leva xyayz .

Não precisamos de sequências começando 0, portanto, dada uma sequência de Bruijn, podemos rotacionar para colocar 000no final. Então, não precisamos de nenhuma das seqüências que se resumem ao início, mas precisamos de dois 0para terminar a sequência começando com o dígito anterior 000, para que possamos excluir uma delas para obter uma sequência de 999 caracteres. Todo restante 0é usado em um número que não começa 0.

GolfScript, 17 caracteres

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

Abordagem simples para adicionar cada número, se ainda não estiver presente na sequência (nota: 999 não está marcada ou adicionada, mas já está contida na saída).

A saída tem 1133 caracteres:

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Não tenho nenhum código, mas achei que alguém poderia apreciar essa prova intuitiva de que 999 caracteres é o limite inferior ao comprimento da saída:

Primeiro, todos os números de 1 e 2 dígitos fazem parte de um número de 3 dígitos, portanto, ignore tudo menos que 100. 100-999 inclusive são 900 números de 3 dígitos.

A maneira mais ideal de resolver o problema é se cada personagem for usado o máximo possível. Isso significa que os números se sobrepõem o máximo possível, assim:

123
 234
  345

O primeiro número adicionará, portanto, 3 caracteres e cada número subsequente adicionará 1 caractere. Isso fornece 3 + 899 = 902 caracteres como um limite inferior.

No entanto, quando existe um zero, não podemos usá-lo para iniciar um novo número de 3 dígitos. Podemos reutilizá-lo no meio de outro número de 3 dígitos, desde que não seja seguido por outro zero:

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

Mas:

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

Portanto, cada zero que aparece na saída aumenta a saída em 1 caractere - exceto os dois últimos caracteres que podem ser zero, pois não se sobrepõem a nenhum número adicional:

???
 ??0
  ?00

Existem 81 números com estritamente um zero no meio (? 0?), 81 com estritamente um zero no final (?? 0) e 9 com dois zeros (? 00).

Cada número 0 pode compartilhar um zero com um 0? número ou um número? 00, mas não ambos. 0? e 00 nunca pode compartilhar zeros, portanto, deve haver pelo menos 81 + 9 * 2 zeros na saída.

Isso fornece um limite inferior de 3 + 899 + 81 + 9 * 2 - 2 = 999 caracteres.

Desculpas se isso for considerado fora de tópico, mas foi muito longo para caber em um comentário.

Perl, 37 34 33 32 (1136 1132 caracteres)

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

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

por $ i (1..999) {$ _. = $ i se! / $ i /} print

para (1..1e3) {$ s. = $ _ se $ s! ~ / $ _ /} imprima $ s

Saídas:

12345678910111314151617181920212224252627282930323335363738394043444647484950545557585960656668697076777980878890991001021031041051061071081091101121141151161171181191201241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901931941951961971981992002032042052062072082092192202212232252262272282292302312352362372382392402432442452462472482492502532542552562572582592602632642652662672682692702732742752762772782792802832842852862872882892902942952962972982993003043053063073083093113293303323343363373383393403423463473483493503543553563573583593603643653663673683693703743753763773783793803843853863873883893903953963973983994004054064074084094224394404434454474484494504534574584594604654664674684694704754764774784794804854864874884894904964974984995005065075085095335495505545565585595605645685695705765775785795805865875885895905975985996006076086096446596606656676696706756796806876886896906986997007087097557697707767787807867907977998008098668778798808878888978988999009089329439549659769799879891000

Corda mais curta: 38 37 34 (1020 caracteres):

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

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

para ($ i = 1e3; $ i -;) {$ _. = $ i se! / $ i /} print

Saídas:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Ainda não está satisfeito com a duplicação, especialmente a 99999 no começo! Eu acho que muito mais verificações criariam muito mais código ...

Edit: Adicionado sugestão de @Peter Taylor

Editar 2: ótimas sugestões do @primo! Obrigado

APL (20, saída: 1020)

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

Explicação:

• {∨/⍺⍷⍵:⍵⋄⍵,⍺}: if ⍺é uma substring de ⍵, return ⍵, else return⍵,⍺
• /: reduzir ao longo
• ⍕¨: a representação de cadeia de cada um dos
• ⍳999: os números inteiros de 1a 999.

Resultado:

9999989979969959949939929919909889879869859849839829819809789779769759749739729719709689679669659649639629619609589579569
      55954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913
      91291191090890790690590490390290190088888788688588488388288188087787687587487387287187086786686586486386286186085785
      68558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108
      07806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735
      73473373273173072672572472372272172071671571471371271171070670570470370270170066666566466366266166065565465365265165
      06456446436426416406356346336326316306256246236226216206156146136126116106056046036026016005555545535525515505445435
      42541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411
      410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

APL (41, saída: 999)

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

Explicação:

• ⌽⍕¨100+⍳898: ('999' '998' ... '101')(na ordem inversa, porque a redução vai da direita para a esquerda no APL, ou seja F/a b c ≡ a F (b F c))
• /: reduzir
• ⍵,⍺⍴⍨: argumento da direita, seguido pelos primeiros Ncaracteres do argumento da esquerda, onde Né:
• 3×~∨/⍺⍷⍵: 3se ⍺não for uma substring de ⍵, caso contrário0
• (1=⍴∪⍺): 1se ⍺tiver apenas um caractere exclusivo, caso contrário0
• ∨: maior divisor comum dos dois valores anteriores, portanto: 1se ⍺ainda não estiver dentro ⍵e tiver apenas um caractere único, 3se ⍺ainda não estiver dentro, ⍵mas tiver mais de um caractere exclusivo, 0caso contrário.
• '0',⍨: adicione um zero ao final do resultado

Resultado:

10110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451
      46147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188
      18919019219319419519619719819920020220320420520620720820922232242252262272282292302332342352362372382392402432442452
      46247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294
      29529629729829930030330430530630730830933343353363373383393403443453463473483493503543553563573583593603643653663673
      68369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444544644744844945045545645
      74584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566
      56756856957057657757857958058658758858959059659759859960060660760860966676686696706776786796806876886896906976986997
      00707708709777877978078878979079879980080880988898908999009099100

Ruby: 50 46 caracteres (saída de 1020 caracteres)

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

Exemplo de execução:

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

Execução de teste:

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]}'
[]

Ruby: 102 97 caracteres (saída de 999 caracteres)

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

Exemplo de execução:

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

Execução de teste:

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

Saída de 1020 caracteres:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Verificação: for(i=0;i<1000;i++)console.assert(k.indexOf(i)>=0)

Mathematica ( 62 64 caracteres, saída 1002)

Como isso faz uso de uma função nativa, aprecio ainda mais a beleza de soluções mais curtas do zero. A saída tem 1002 caracteres.

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

"799798787770760750740730720710980970960950940930920910108908708608508408308208889998988081009909008007006005004003002000190180170160150140130120119118117116115114113112912812712612512412312213913813713613513413313214914814714614514414314215915815715615515415315216916816716616516416316217917817717617517417317218918818718618518418318219919819719619519419319212111029028027026025024023022922822722622522422392382372362352342332492482472462452442432592582572562552542532692682672662652642632792782772762752742732892882872862852842832992982972962952942932322202103903803703603503403393383373363353349348347346345344359358357356355354369368367366365364379378377376375374389388387386385384399398397396395394343330320310490480470460450449448447446445945845745645546946846746646547947847747647548948848748648549949849749649545444043042041059058057056055955855755695685675665795785775765895885875865995985975965655505405305205106906806706696686679678677689688687699698697676660650640630620610790780779778978879"

Mathematica, 51 caracteres

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

Saída (1155 caracteres):

000100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999

Python - 53 63., Saída 1134

Esta é uma força bruta, mas é válida. Sim, ele tem um zero à esquerda, mas salva dois caracteres por não ter range(1,1000).

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

O exemplo acima gera um DeprecationWarningexcesso de uso de 1e3 na range()chamada, mas salva um caractere acima de 1000.

Também há uma versão de saída de comprimento um pouco mais ideal, revertendo a corda ao custo de 6 5 caracteres (obrigado a res e filmor pelas dicas) :

Python - saída 58, 1021

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]

Basicamente, o mesmo que a solução Howards - 1133 caracteres.

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Java- 126 98 caracteres (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);}}

Saída (1020 caracteres):

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Pode alcançar um bom (de acordo com Peter Taylor , mas mais tarde ele disse que 999 era o ideal). Comprimento da corda adicionando alguns caracteres (+20 caracteres para 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);}}

Saída (1002 caracteres):

999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110101100

Edit : Obrigado ao Fabinout por apontar que o Java 6 pode salvar 28 caracteres.

Windows PowerShell - Saída 40, 1020

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

Resultado:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Haskell, 75 bytes - saída 1002

Uma abordagem de peneira que retorna uma solução mínima.

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

Observe que esta solução é impraticamente lenta.

Powershell, 36 bytes, saída 1020

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

Resultado:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Alternativa, 69 bytes, saída 1000

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

Resultado:

9998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101100

Alternativa, 82 73 bytes, saída 999 (mínimo)

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

Este é um algoritmo simplificado de Gerar o De Bruijn mais curto adaptado para constantes: alphabet = 9876543210and length =3

Resultado:

999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110100

Script de teste:

$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 bytes e 1109 caracteres

₄FDNå_iNì

Saídas:

90990190089989088981980980880079979879078978878077977870970870770069969869769068968868768067967867767066966866760960860760660059959859759659058958858758658057957857757657056956856756656055955855755650950850750650550049949849749649549048948848748648548047947847747647547046946846746646546045945845745645545044944844744644540940840740640540440039939839739639539439038938838738638538438037937837737637537437036936836736636536436035935835735635535435034934834734634534434033933833733633533430930830730630530430330029929829729629529429329028928828728628528428328027927827727627527427327026926826726626526426326025925825725625525425325024924824724624524424324023923823723623523423323022922822722622522422320920820720620520420320220019919719619519419319219118918818718618518418318218017917817717617517417317217016916816716616516416316216015915815715615515415315215014914814714614514414314214013913813713613513413313213012912812712612512412312212011811711611511411311211110910810710610510410310210110099919089888079787770696867666059585756555049484746454440393837363534333029282726252423222018171615141312119876543210

Experimente online ou verifique se contém todos os números abaixo de 1000 .

Explicação:

₄            # 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 bytes (não-concorrente), comprimento da string 1133

Pyke é mais novo que o desafio e, portanto, não é competitivo.

k~mV~oi{!o`*+

Experimente aqui!

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

PHP, 48 44 bytes

Obrigado a @primo por me lembrar ereg.

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

ou

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

saída: 1020 caracteres. requer PHP <7

PHP 7, 48 bytes:

ereg foi removido no PHP 7

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

Se o segundo argumento para strstr(ou strposoutras funções de pesquisa de string) não for uma string, ele será usado como um código ascii, portanto, será $inecessário converter uma string em string.

Groovy, 49 caracteres / bytes

Eu não tinha certeza se deveria fazer isso como uma função retornando uma variável de seqüência de caracteres ou imprimir o resultado, então isso apenas imprime no stdout. O uso do correspondente regex salvou 2 bytes, usando o operador ternário em vez de "se" salvou outro byte. A sequência de saída tem 1133 caracteres.

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

Resultado:

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Linguagem do Game Maker, 1014 - String 1000

show_message(909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900)

Além disso:

Ruby, 1003 - String 1000

p'909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900'