One Ring to rule them all. One String to contain them all

Question

Objectives: Output a String which contains every positive integer strictly below 1000.

The obvious answer would be to concatenate every one of them, and that would create a String of 2890 characters (thanks manatwork), to avoid this kind of easy answer, the length of the string must be under 1500 characters. Here is a straightforward Java code which outputs a 1200 chars String.

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

Shortest code win, bonus point for the shortest String!

Answer 1

GolfScript (35 31 26 chars)

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

Output is

000100110111200201210211220221222300301302310311312320321322330331332333400401402403410411412413420421422423430431432433440441442443444500501502503504510511512513514520521522523524530531532533534540541542543544550551552553554555600601602603604605610611612613614615620621622623624625630631632633634635640641642643644645650651652653654655660661662663664665666700701702703704705706710711712713714715716720721722723724725726730731732733734735736740741742743744745746750751752753754755756760761762763764765766770771772773774775776777800801802803804805806807810811812813814815816817820821822823824825826827830831832833834835836837840841842843844845846847850851852853854855856857860861862863864865866867870871872873874875876877880881882883884885886887888900901902903904905906907908910911912913914915916917918920921922923924925926927928930931932933934935936937938940941942943944945946947948950951952953954955956957958960961962963964965966967968970971972973974975976977978980981982983984985986987988990991992993994995996997998999

(1020 chars) This is a variant on the Lyndon word concatenation approach: rather than use the primitive 1-char words it uses multiples of 111 for shorter code but repeated occurrences of those numbers; and rather than use minimal elements of the conjugacy groups it uses maximal elements, because that shortens the loops.

---

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

at 40 chars (can probably still be improved) generates an optimal string, which is of length 999 chars:

100200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908108208308408508608708808909109209309409509609709809911121131141151161171181191221231241251261271281291321331341351361371381391421431441451461471481491521531541551561571581591621631641651661671681691721731741751761771781791821831841851861871881891921931941951961971981992223224225226227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274275276277278279283284285286287288289293294295296297298299333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944454464474484494554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569576577578579586587588589596597598599666766866967767867968768868969769869977787797887897987998889899900

Trying to make this do reverse strings runs into problems with omitting the multiples of 111.

To see that 999 is the optimal length (since my brief comments above don't convince everyone), start from the full de Bruijn sequence which (taken as a cyclic string) contains every 3-digit sequence of characters from 0 to 9. Since there are 1000 of them, it must be at least 1000 characters long; that it can be precisely 1000 characters long is usually proven by an Eulerian walk on a graph whose nodes are two-digit sequences xy with 10 edges, each labelled with one digit z, which take xy to yz.

We don't need sequences beginning 0, so given a de Bruijn sequence we can rotate to put 000 at the end. Then we don't need either of the sequences which wrap round to the beginning, but we do need two of the 0s to finish the sequence starting with the digit before 000, so we can delete one of them to get a 999-character string. Every remaining 0 is used in a number which doesn't begin with 0.

Answer 2

GolfScript, 17 characters

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

Plain approach to add each number if not already present in the string (note: 999 is not checked or added, but contained already in the output).

Output is 1133 characters:

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Answer 3

I don't have any code, but I thought someone might appreciate this intuitive proof that 999 characters is the lower bound to the length of the output:

First, every 1- and 2-digit number is part of a 3-digit number, so ignore everything less than 100. 100-999 inclusive is 900 3-digit numbers.

The most optimal way to solve the problem is if every character is used as much as possible. That means the numbers overlap as much as possible, like this:

123
 234
  345

The first number will therefore add 3 characters, and each subsequent number will add 1 character. That gives 3 + 899 = 902 characters as a lower bound.

However, when there is a zero, we can't use it to start a new 3-digit number. We can reuse it in the middle of another 3-digit number though, as long as it is not followed by another zero:

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

But:

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

Therefore, each zero which appears in the output extends the output by 1 character - except for the last two characters which may be zero as they do not overlap any further numbers:

???
 ??0
  ?00

There are 81 numbers with strictly one zero in the middle (?0?), 81 with strictly one zero at the end (??0), and 9 with two zeros (?00).

Every ??0 number can share a zero with either a ?0? number or a ?00 number, but not both. ?0? and ?00 can never share zeros, so there must be at least 81 + 9*2 zeros in the output.

This gives a lower bound of 3 + 899 + 81 + 9*2 - 2 = 999 characters.

Apologies if this is considered off-topic, but it was too long to fit in a comment.

Answer 4

Golfscript - 13 bytes, 1315 output

991,{`.$2>>},

The above selects those numbers from 0-990 whose first digit is the largest digit of the number, i.e. the last digit of the sorted string representation is lexicographically less than the string itself. The logic is the following:

For a 3 digit number abc, if a is not the largest digit of the number, the number my be skipped, because it will be covered by one of two cases later on:

1. b < c (e.g. 123)
   Because c is the largest digit, the number cab will not be skipped. In this example 312 will not be skipped, nor will the next value 313, which when concatenated (312 313) contains 123.

2. b ≥ c (e.g. 132)
   Because b is the largest digit, the number bca will not be skipped. In this example 321 will not be skipped, nor will the next value 322, which when concatenated (321 322) contains 132. If b = c (e.g. 122), this case also applies. The value bca will not be skipped, as before, and because a is necessarily less than b, bc<a+1> will not be skipped either. In this example, 221 222 contains 122.

Because the above code tests the third digit, rather than strictly the last, all values from 0-99 are included in the result. The values from 1-99 may be skipped, however, because if every 3-digit sequence is present, then every 1-digit and 2-digit sequence must also be present.

The values from 991-999 may also be skipped, as the are generated by (909 910, 919 920, ... 989 990).

At 1315 bytes of output, this is comfortably under the problem's specification of less than 1500.

Output:

0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Variation #1

14 bytes, 1233 output

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

By selecting strictly the last digit for comparison, rather than the third, many of the unnecessary values less than 100 are eliminated, shortening the resulting string.

101120212230313233404142434450515253545560616263646566707172737475767780818283848586878890919293949596979899100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

Variation #2

16 bytes, 1127 output

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

By prying off all values less than 99 beforehand, the resulting string can be shortened even more.

99100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990

---

Golfscript - 19 bytes, 1016 output

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

The above counts from 99 to 909, adding any value that hasn't already appeared (909 would normally be the last value added in this way). Moving 99 to the front is an optimization to avoid needing 910 at the back.

Output:

99100101102103104105106107108109111112113114115116117118119120122123124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190192193194195196197198199200202203204205206207208209222223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333334335336337338339340344345346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444445446447448449450455456457458459460465466467468469470475476477478479480485486487488489490495496497498499500505506507508509555556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666667668669670677678679680687688689690697698699700707708709777778779780788789790798799800808809888889890899900909

---

Golfscript 26 bytes, 999 output

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

Note that the 1016 character string produced by the previous solution is nearly optimal, except for having two extra digits for each multiple of 111 (i.e. 11111 instead of 111, 22222 instead of 222, etc.). The solution can be made optimal by removing these extra digits (only inserting one digit at each of these values, instead of three), and by rotating 909 to the front, eliminating a 9 (this differs from the previous versions, which moved 9100 to the back instead).

Unrolled and commented:

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

The logic to choose which characters are appended follows three cases:

1. 111 ∤ n, n ⊄ s
   The value from the first check is 1, and from the second -1.
   The slice will begin starting from index 0; it will return the whole string.
2. 111 ∤ n, n ⊂ s
   The value from the first check is 1, and from the second something ≥ 2.
   The slice will begin staring from index ≥ 3; it will return an empty string.
3. 111 ∣ n, n ⊄ s
   The value from the first check is 0, and from the second -1.
   The slice will begin starting from index -1; it will return the last character only.

The sum of the logic is that any value which hasn't yet appeared will be appended in whole - unless it is a multiple of 111, in which case only one character will be appended. All other values will be ignored.

Note that the string produced is different than the optimal one produced by Peter Taylor's answer.

History:

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

Output:

909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900

Answer 5

Perl, 37 34 33 32 (1136 1132 characters)

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

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

for$i(1..999){$_.=$i if!/$i/}print

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

Outputs:

12345678910111314151617181920212224252627282930323335363738394043444647484950545557585960656668697076777980878890991001021031041051061071081091101121141151161171181191201241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901931941951961971981992002032042052062072082092192202212232252262272282292302312352362372382392402432442452462472482492502532542552562572582592602632642652662672682692702732742752762772782792802832842852862872882892902942952962972982993003043053063073083093113293303323343363373383393403423463473483493503543553563573583593603643653663673683693703743753763773783793803843853863873883893903953963973983994004054064074084094224394404434454474484494504534574584594604654664674684694704754764774784794804854864874884894904964974984995005065075085095335495505545565585595605645685695705765775785795805865875885895905975985996006076086096446596606656676696706756796806876886896906986997007087097557697707767787807867907977998008098668778798808878888978988999009089329439549659769799879891000

Shorter string: 38 37 34 (1020 characters):

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

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

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

Outputs:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Still not happy with the duplication especially the 99999 at the beginning! I think many more checks would create a lot more code though...

Edit: Added suggestion from @Peter Taylor

Edit 2: Some great suggestions from @primo! Thank you

Answer 6

APL (20, output: 1020)

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

Explanation:

• {∨/⍺⍷⍵:⍵⋄⍵,⍺}: if ⍺ is a substring of ⍵, return ⍵, else return ⍵,⍺
• /: reduce over
• ⍕¨: the string representation of each of
• ⍳999: the integers from 1 to 999.

Output:

9999989979969959949939929919909889879869859849839829819809789779769759749739729719709689679669659649639629619609589579569
      55954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913
      91291191090890790690590490390290190088888788688588488388288188087787687587487387287187086786686586486386286186085785
      68558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108
      07806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735
      73473373273173072672572472372272172071671571471371271171070670570470370270170066666566466366266166065565465365265165
      06456446436426416406356346336326316306256246236226216206156146136126116106056046036026016005555545535525515505445435
      42541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411
      410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

APL (41, output: 999)

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

Explanation:

• ⌽⍕¨100+⍳898: ('999' '998' ... '101') (in reverse order, because reduction goes right to left in APL, i.e. F/a b c ≡ a F (b F c))
• /: reduce
• ⍵,⍺⍴⍨: right argument, followed by the first N characters of the left argument, where N is:
• 3×~∨/⍺⍷⍵: 3 if ⍺ is not a substring of ⍵, otherwise 0
• (1=⍴∪⍺): 1 if ⍺ only has one unique characcter, otherwise 0
• ∨: greatest common divisor of the previous two values, so: 1 if ⍺ is not already in ⍵ and only has one unique character, 3 if ⍺ is not already in ⍵ but has more than one unique character, 0 otherwise.
• '0',⍨: add a zero to the end of the result

Output:

10110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451
      46147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188
      18919019219319419519619719819920020220320420520620720820922232242252262272282292302332342352362372382392402432442452
      46247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294
      29529629729829930030330430530630730830933343353363373383393403443453463473483493503543553563573583593603643653663673
      68369370374375376377378379380384385386387388389390394395396397398399400404405406407408409444544644744844945045545645
      74584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566
      56756856957057657757857958058658758858959059659759859960060660760860966676686696706776786796806876886896906976986997
      00707708709777877978078878979079879980080880988898908999009099100

Answer 7

Ruby: 50 46 characters (1020 characters output)

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

Sample run:

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

Test run:

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 characters (999 characters output)

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

Sample run:

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

Test run:

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

Answer 8

JavaScript, 39

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

1020 character output:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

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

Answer 9

Mathematica (62 64 chars, 1002 output)

Because this makes use of a native function, I appreciate all the more the beauty of shorter solutions from scratch. Output is 1002 chars long.

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

"799798787770760750740730720710980970960950940930920910108908708608508408308208889998988081009909008007006005004003002000190180170160150140130120119118117116115114113112912812712612512412312213913813713613513413313214914814714614514414314215915815715615515415315216916816716616516416316217917817717617517417317218918818718618518418318219919819719619519419319212111029028027026025024023022922822722622522422392382372362352342332492482472462452442432592582572562552542532692682672662652642632792782772762752742732892882872862852842832992982972962952942932322202103903803703603503403393383373363353349348347346345344359358357356355354369368367366365364379378377376375374389388387386385384399398397396395394343330320310490480470460450449448447446445945845745645546946846746646547947847747647548948848748648549949849749649545444043042041059058057056055955855755695685675665795785775765895885875865995985975965655505405305205106906806706696686679678677689688687699698697676660650640630620610790780779778978879"

Answer 10

Mathematica, 51 chars

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

Output(1155 chars):

000100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999

Answer 11

Python - 53 63, 1134 output

This is pretty brute forcish, but it is valid. Yes it has a leading zero, but it saves two characters by not having range(1,1000).

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

The above throws a DeprecationWarning over the use of 1e3 in the range() call, but it saves a character over using 1000.

There is a slightly more optimal length output version as well, by reversing the string at the cost of 6 5 characters (thanks to r.e.s and filmor for the tips):

Python - 58, 1021 output

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

Answer 12

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

Output (1020 chars):

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Can reach a good (according to Peter Taylor, but later he said 999 was optimal) String length by adding a few chars (+20 chars for 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);}}

Output (1002 chars):

999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110101100

Edit: Thanks to Fabinout for pointing out that Java 6 can save 28 chars.

Answer 13

K, 33

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

Basically the same as Howards solution - 1133 characters.

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Answer 14

Windows PowerShell - 40, 1020 Output

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

Output:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Answer 15

Pyke, 13 bytes (noncompeting), string length 1133

Pyke is newer than the challenge and thus is noncompetitive .

k~mV~oi{!o`*+

Try it here!

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

Answer 16

Haskell, 75 bytes - 1002 output

A sieve approach that returns a minimal solution.

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

Note that this solution is impractically slow.

Answer 17

Powershell, 36 bytes, 1020 output

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

Output:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100

Alternative, 69 bytes, 1000 output

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

Output:

9998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101100

Alternative, 82 73 bytes, 999 output (minimum)

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

This is simplified algorithm from Generate the shortest De Bruijn adapted for constants: alphabet=9876543210 and length=3

Output:

999899799699599499399299199098898798698598498398298198097897797697597497397297197096896796696596496396296196095895795695595495395295195094894794694594494394294194093893793693593493393293193092892792692592492392292192091891791691591491391291191090890790690590490390290190088878868858848838828818808778768758748738728718708678668658648638628618608578568558548538528518508478468458448438428418408378368358348338328318308278268258248238228218208178168158148138128118108078068058048038028018007776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666566466366266166065565465365265165064564464364264164063563463363263163062562462362262162061561461361261161060560460360260160055545535525515505445435425415405345335325315305245235225215205145135125115105045035025015004443442441440433432431430423422421420413412411410403402401400333233133032232132031231131030230130022212202112102012001110100

---

Test script:

$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

Answer 18

05AB1E, 9 bytes and 1109 characters

₄FDNå_iNì

Outputs:

90990190089989088981980980880079979879078978878077977870970870770069969869769068968868768067967867767066966866760960860760660059959859759659058958858758658057957857757657056956856756656055955855755650950850750650550049949849749649549048948848748648548047947847747647547046946846746646546045945845745645545044944844744644540940840740640540440039939839739639539439038938838738638538438037937837737637537437036936836736636536436035935835735635535435034934834734634534434033933833733633533430930830730630530430330029929829729629529429329028928828728628528428328027927827727627527427327026926826726626526426326025925825725625525425325024924824724624524424324023923823723623523423323022922822722622522422320920820720620520420320220019919719619519419319219118918818718618518418318218017917817717617517417317217016916816716616516416316216015915815715615515415315215014914814714614514414314214013913813713613513413313213012912812712612512412312212011811711611511411311211110910810710610510410310210110099919089888079787770696867666059585756555049484746454440393837363534333029282726252423222018171615141312119876543210

Try it online or verify it contains all numbers below 1000.

Explanation:

₄            # 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)

Answer 19

PHP, 48 44 bytes

Thanks to @primo for reminding me of ereg.

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

or

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

output: 1020 chars. requires PHP<7

PHP 7, 48 bytes:

ereg has been removed in PHP 7

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

If the second argument to strstr (or strpos and other string searching functions) is not a string, it will be used as an ascii code, so $i needs a cast to string.

Answer 20

Groovy, 49 chars/bytes

I wasn't sure whether to do this as a function returning a string variable, or print out the result, so this just prints it to stdout. Using the regex matcher saved 2 bytes, using ternary operator instead of "if" saved another byte. The output string is 1133 characters.

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

Output:

01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989

Answer 21

Game Maker Language, 1014 - String 1000

show_message(909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900)

Also:

Ruby, 1003 - String 1000

p'909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900'