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

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++) {
}
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!

• The optimal string is 1002 characters long. Nov 5, 2013 at 10:43
• @PeterTaylor I'm interested, how did you figure that out? Nov 5, 2013 at 10:45
• Basically you're asking for a de Bruijn sequence B(10, 3), but because you don't allow cyclic wrapping it's necessary to repeat the first two characters. Nov 5, 2013 at 10:52
• But I want the string to contain 1, 2 or 56, not necessarily 001 002 and 056. Nov 5, 2013 at 11:09
• This contest would be cooler if it asked for the shortest [size of code] + [size of output]. Oct 26, 2017 at 11:25

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

• That's truly impressive!! Nov 5, 2013 at 11:48
• I'd prefer to use a filtering or generative approach. For the pseudo-Lyndon approach I've got the generative approach down to 32 chars: 10,:^{:x^>{x.@:&<+^>{x&@}/}/}/0. Varying that for true Lyndon words gives 10,:^{:x^>{x.@:&<+^>{.x>{x&@}*}/}/}%3>0. (40 chars) for the optimal string. Nov 5, 2013 at 17:23
• Can you get the optimal string shorter by not using leading zeros for numbers below 100? Nov 5, 2013 at 18:50
• @Random832 I'm pretty sure you can't. You have to include the numbers 100, 200, ... 900, so the minimal string is certainly going to have eight occurances of 00X (one can be at the far right, as above). Note that the optimal string given doesn't contain "001". Nov 5, 2013 at 20:25
• Normally I don't upvote code I don't understand, but in this case I'm upvoting it because I don't understand. Bravo. Nov 6, 2013 at 1:53

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


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.

• It's kinda funny to notice that storing every number up to 999 in a string makes it 999 characters long. Correct me if I'm wrong but I believe that storing every number up to 99 makes it a 100 characters long. Nov 7, 2013 at 9:50
• By the same argument the lower bound is 2 + 89 + 9 - 1 = 99 but this does not prove 99 is possible, only that 98 isn't. Nov 7, 2013 at 12:07

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

+>      # 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. 111n, ns
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. 111n, ns
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. 111n, ns
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


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

• Nice trick to write 1000 as 1e3, but I think it's pointless. The question says “strictly below 1000”, that would mean up to and including 999. (The sample code also processes 0..999.) Nov 5, 2013 at 10:39
• An excellent point! I had a different loop to begin with, I've amended this accordingly! Thanks! Nov 5, 2013 at 11:25
• If you use a non-alphabetic character for your variable can you remove the space? Nov 5, 2013 at 13:00
• A few more minor improvements: instead of $_.=$@if!/$@/, you can use string repetition $_.=$@x!/$@/. The for can be replaced by a while as a statement modifier, using a modulo: ...while$@=--$@%1e3 Nov 5, 2013 at 18:08
• String repetition is an amazing trick, making sure to remember that one, the while+modulo took me a bit to get, but is a nice way to save two more, thank you! Nov 6, 2013 at 8:29

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


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

• Nice idea to go from 999 to 0 and not the opposite way. With this, my Java method outputs a 1048 characters string (instead of 1200). Nov 5, 2013 at 10:54
• If you're just worried about code length and not output length, you could improve the first one using a string range. Something like (?0..?9*3).map{|i|$/[i]||($><<i;$/+=i)} maybe? Nov 6, 2013 at 4:08 # 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) # 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"  • you appear to be missing 799 and 997. see ideone.com/d07bG2 (or write your own check) Nov 5, 2013 at 20:04 • Good catch. By default, DeBruijnSequence assumes cyclic wrapping. Prepending "79", the final two digits, solves the problem. Nov 5, 2013 at 22:21 # Mathematica, 51 chars ""<>Table[ToString/@({i,j,k}-1),{i,10},{j,i},{k,i}]  Output(1155 chars): 000100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999  • What does it do? Nov 5, 2013 at 13:57 • It constructs a list of lists of the form {i, j, k} where i is from 0 to 9 and j, k are smaller than i. Then it converts the list into a string. Nov 5, 2013 at 14:05 # 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*(notiin 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*(notiin s) print s  • I find that your first program has output length 1133, not 1132. In Python 2 (but not Python 3), you can shorten the code to 54 characters by using backticks: for i in range(999):s+=i*(notiin s) Nov 6, 2013 at 2:58 • Wot? They took out backticks? Guido must have been having an I Hate Perl and Everything that Looks like It day when deciding what to keep. Nov 6, 2013 at 11:25 • You can shorten that by one character by using range(999,99,-1) instead of range(1000)[::-1]. Nov 6, 2013 at 17:46 • And the tip by r.e.s. still help, str(i)*(str(i)not in s) is a bit shorter than i=str(i);s+=[i,''][i in s] ;) Nov 6, 2013 at 17:53 • @filmor Made smaller, and smaller again by using 1e3 instead of 1000 – user8777 Nov 6, 2013 at 22:29 # 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. • If you want, you can compile with java 6 and use a static block instead of a System.out.println()!! Nov 8, 2013 at 11:16 • @Fabinout Do you mean instead of a public static void main(String[]a)? (that would change my code from ...public static void main(String[]c){... to ...static{...) Nov 8, 2013 at 17:23 • Yes I do. you can try with Java 6. Nov 8, 2013 at 18:58 • Btw, you should use exit() at the end of your static block if you don't want your program to crash. Even though it's not required in golfing to not crash. Nov 27, 2013 at 8:31 # K, 33 {$[#ss[x]@y;x;,/x,y]}/["";$!1000]  Basically the same as Howards solution - 1133 characters. 01234567891011131415161718192021222425262728293032333536373839404344464748495054555758596065666869707677798087889099100102103104105106107108109110112114115116117118119120124125126127128129130132133134135136137138139140142143144145146147148149150152153154155156157158159160162163164165166167168169170172173174175176177178179180182183184185186187188189190193194195196197198199200203204205206207208209219220221223225226227228229230231235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290294295296297298299300304305306307308309311329330332334336337338339340342346347348349350354355356357358359360364365366367368369370374375376377378379380384385386387388389390395396397398399400405406407408409422439440443445447448449450453457458459460465466467468469470475476477478479480485486487488489490496497498499500506507508509533549550554556558559560564568569570576577578579580586587588589590597598599600607608609644659660665667669670675679680687688689690698699700708709755769770776778780786790797799800809866877879880887888897898899900908932943954965976979987989  ## Windows PowerShell - 40, 1020 Output 999..0|%{$s+=if(!($s-match$_)){"$_"}};$s


Output:

999998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888887886885884883882881880877876875874873872871870867866865864863862861860857856855854853852851850847846845844843842841840837836835834833832831830827826825824823822821820817816815814813812811810807806805804803802801800777776775774773772771770766765764763762761760756755754753752751750746745744743742741740736735734733732731730726725724723722721720716715714713712711710706705704703702701700666665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555554553552551550544543542541540534533532531530524523522521520514513512511510504503502501500444443442441440433432431430423422421420413412411410403402401400333332331330322321320312311310302301300222221220211210201200111110101100


## 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 += ^

• How long is the output? Nov 19, 2016 at 11:20

# Haskell, 75 bytes - 1002 output

A sieve approach that returns a minimal solution.

(\n->head.filter(\s->and[show kisInfixOfs|k<-[1..n]]).map show$[1..])1000  Note that this solution is impractically slow. • You need to include the import of Data.List for isInfixOf, however you can still save 2 bytes by golfing it some more: 1) Hardcode n = 1000 2) Use all over and and a pointfree version of the predicate 3) use (!!0) over head 4) Use list-comprehension over combination of map & filter 5) use (<$>) over map: [s|s<-show<$>[1..],all((isInfixOfs).show)[1..1000]]!!0 Sep 30, 2018 at 19:53 # 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


# 05AB1E, 9 bytes and 1109 characters

₄FDNå_iNì


Outputs:

90990190089989088981980980880079979879078978878077977870970870770069969869769068968868768067967867767066966866760960860760660059959859759659058958858758658057957857757657056956856756656055955855755650950850750650550049949849749649549048948848748648548047947847747647547046946846746646546045945845745645545044944844744644540940840740640540440039939839739639539439038938838738638538438037937837737637537437036936836736636536436035935835735635535435034934834734634534434033933833733633533430930830730630530430330029929829729629529429329028928828728628528428328027927827727627527427327026926826726626526426326025925825725625525425325024924824724624524424324023923823723623523423323022922822722622522422320920820720620520420320220019919719619519419319219118918818718618518418318218017917817717617517417317217016916816716616516416316216015915815715615515415315215014914814714614514414314214013913813713613513413313213012912812712612512412312212011811711611511411311211110910810710610510410310210110099919089888079787770696867666059585756555049484746454440393837363534333029282726252423222018171615141312119876543210


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)


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

• ereg($i,$s) for 4 (I would also include <? in the byte count). Nov 19, 2016 at 12:38
• @primo I just noticed that this challenge is older than PHP 7. double thanks. :) Nov 19, 2016 at 12:52
• ereg was removed, presumably, because the function name is too short, and/or didn't contain enough underscores. That split was also removed is especially brilliant. Nov 19, 2016 at 13:01
• ereg was removed because POSIX only contains a subset of PCRE´s possibilities; and they probably didn´t want to maintain two different libraries. I´ll ask should I ever meet Rasmus Lerdorf again. split has been removed, but join remained (probably because it´s "only" an alias). Sorry for pedantry; but I know people who cannot recognice irony. Nov 19, 2016 at 13:44

# 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


# Game Maker Language, 1014 - String 1000

show_message(909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900)

Also:

## Ruby, 1003 - String 1000

p'909910010110210310410510610710810911121131141151161171181191201221231241251261271281291301321331341351361371381391401421431441451461471481491501521531541551561571581591601621631641651661671681691701721731741751761771781791801821831841851861871881891901921931941951961971981992002022032042052062072082092223224225226227228229230233234235236237238239240243244245246247248249250253254255256257258259260263264265266267268269270273274275276277278279280283284285286287288289290293294295296297298299300303304305306307308309333433533633733833934034434534634734834935035435535635735835936036436536636736836937037437537637737837938038438538638738838939039439539639739839940040440540640740840944454464474484494504554564574584594604654664674684694704754764774784794804854864874884894904954964974984995005055065075085095556557558559560566567568569570576577578579580586587588589590596597598599600606607608609666766866967067767867968068768868969069769869970070770870977787797807887897907987998008088098889890899900'