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:
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.
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:
- 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.
- 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.
- 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
@Justin You can save 24 bytes ... the string only has to contain
every positive integer strictly below 1000
. – Titus – 2016-11-19T11:37:28.85711The optimal string is 1002 characters long. – Peter Taylor – 2013-11-05T10:43:41.657
1@PeterTaylor I'm interested, how did you figure that out? – Fabinout – 2013-11-05T10:45:35.313
8
Basically you're asking for a de Bruijn sequence
– Peter Taylor – 2013-11-05T10:52:24.900B(10, 3)
, but because you don't allow cyclic wrapping it's necessary to repeat the first two characters.3But I want the string to contain 1, 2 or 56, not necessarily 001 002 and 056. – Fabinout – 2013-11-05T11:09:21.427
How you calculated that maximum 2907? (
([*0..999]*'').size
gives 2890 inruby
.) – manatwork – 2013-11-05T11:15:00.030@manatwork I just added every 1 digit number, 2-digit numbers and 3-digit numbers, but I failed terribly at calculating it in my head (I counted 99 2-digit numbers, and 9 mono-digit numbers) – Fabinout – 2013-11-05T11:19:27.363
You're right, it should be possible to shorten the output string to 999 chars by picking the lexicographically first de Bruijn sequence, moving two leading zeroes to the end, and removing the remaining leading zero. – Peter Taylor – 2013-11-05T11:28:31.983
6Your problem is impossible to solve because you said number not integer. The string would have to be of infinite length to accommodate all the positive numbers below 1000. – Ramchandra Apte – 2013-11-05T13:40:26.583
@RamchandraApte True, everybody else understood it anyway ;) .I'll fix this. – Fabinout – 2013-11-05T13:42:13.333
11@RamchandraApte And still any string even with infinite length would be missing most numbers ;-) – Howard – 2013-11-05T13:49:43.210
nit-picking edit because I'm a LotR fan :P – Doorknob – 2013-11-06T02:51:09.790
this is more of a mathematics problem – Math chiller – 2013-11-06T07:15:01.560
@Doorknob Ah ah ah, it's ok! – Fabinout – 2013-11-06T08:51:38.653
Since this is code-golf the accepted answer should go to the shortest, which is currently Howard's and not mine. – Peter Taylor – 2013-11-06T09:44:35.830
@PeterTaylor ok, your answer was just more clever. – Fabinout – 2013-11-06T09:51:50.300
This contest would be cooler if it asked for the shortest [size of code] + [size of output]. – Heimdall – 2017-10-26T11:25:10.247
#Java-134 chars class a{public static void main(String[]a){System.out.println("a String which contains every positive integer strictly below 1000");}} Output (66 chars):
The following is also an interesting approach, and technically not correct in terms of the question, as it is not complying to the maximum 1500 characters condition, and the output string is not human-readable. Using old-school methods that I figured out when I was hacking Civilization I maps (hehehe), I found that, for example, if you had 4000 gold in your treasury, this was stored in 2 digits only, namely, 1 digit representing 15 * 256, and another digit representing the modulus of 4000 by 15, namely 160. So, using this algorithm, you can store each number in 1 digit from 0 until you get to – Kobus Myburgh – 2013-11-07T08:49:40.070