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

The optimal string is 1002 characters long.

@PeterTaylor I'm interested, how did you figure that out?

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.

But I want the string to contain 1, 2 or 56, not necessarily 001 002 and 056.

How you calculated that maximum 2907? (([*0..999]*'').size gives 2890 in ruby.)

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

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.

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

a String which contains every positive integer strictly below 1000 Did I approach the problem the wrong way?

nit-picking edit because I'm a LotR fan :P

this is more of a mathematics problem

Since this is code-golf the accepted answer should go to the shortest, which is currently Howard's and not mine.

@PeterTaylor ok, your answer was just more clever.

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

@Justin You can save 24 bytes ... the string only has to contain every positive integer strictly below 1000.

This contest would be cooler if it asked for the shortest [size of code] + [size of output].

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

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

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.

Can you get the optimal string shorter by not using leading zeros for numbers below 100?

@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".

Normally I don't upvote code I don't understand, but in this case I'm upvoting it because I don't understand.  Bravo.

Hmm... why should 999 characters be the minimum? you only need 899 3-character sequences and each 2 character-sequence is already contained in it, theoretically

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.

See also: https://en.wikipedia.org/wiki/De_Bruijn_sequence.

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.

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.

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

An excellent point! I had a different loop to begin with, I've amended this accordingly! Thanks!

If you use a non-alphabetic character for your variable can you remove the space?

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

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!

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

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?

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 http://ideone.com/d07bG2 (or write your own check)

Good catch. By default, DeBruijnSequence assumes cyclic wrapping. Prepending "79", the final two digits, solves the problem.

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, 51 chars
""<>Table[ToString/@({i,j,k}-1),{i,10},{j,i},{k,i}]

Output(1155 chars):
000100101110111200201202210211212220221222300301302303310311312313320321322323330331332333400401402403404410411412413414420421422423424430431432433434440441442443444500501502503504505510511512513514515520521522523524525530531532533534535540541542543544545550551552553554555600601602603604605606610611612613614615616620621622623624625626630631632633634635636640641642643644645646650651652653654655656660661662663664665666700701702703704705706707710711712713714715716717720721722723724725726727730731732733734735736737740741742743744745746747750751752753754755756757760761762763764765766767770771772773774775776777800801802803804805806807808810811812813814815816817818820821822823824825826827828830831832833834835836837838840841842843844845846847848850851852853854855856857858860861862863864865866867868870871872873874875876877878880881882883884885886887888900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999

What does it do?

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.

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

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`*(not`i`in s)`

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.

You can shorten that by one character by using range(999,99,-1) instead of range(1000)[::-1].

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

@filmor Made smaller, and smaller again by using 1e3 instead of 1000

I find the length of your first program is now 54, not 53, and the second one is 59, not 58. Also, range(999) is enough in the first one -- range(1000) (or range(1e3)) is not needed -- and the output length is 1133, not 1134.

range(1e3) does not work: Python 2.7:TypeError: range() integer end argument expected, got float. Python 3.2: TypeError: 'float' object cannot be interpreted as an integer

Also: The output length of your first script is 1133 and the second one is 1020.

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()!!

@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{...)

Yes I do. you can try with Java 6.

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.

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.

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((`isInfixOf`s).show)[1..1000]]!!0

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?

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

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)

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

@primo I just noticed that this challenge is older than PHP 7. double thanks. :)

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.

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.

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'

authors: Rγσ ξηg Lιαη Ημ 雷欧


text:
Convert 1 into any positive integer using only the operations *3 and /2
Any positive integer can be obtained by starting with 1 and applying a sequence of operations, each of which is either "multiply by 3" or "divide by 2, discarding any remainder".
Examples (writing f for *3 and g for /2):
4 = 1 *3 *3 /2 = 1 ffg
6 = 1 ffggf = 1 fffgg
21 = 1 fffgfgfgggf
Write a program with the following behavior:
Input: any positive integer, via stdin or hard-coded. (If hard-coded, the input numeral will be excluded from the program length.)
Output: a string of f's and g's such that <input> = 1 <string> (as in the examples). Such a string in reverse order is also acceptable. NB: The output contains only f's and g's, or is empty.
The winner is the entry with the fewest bytes of program-plus-output when 41 is the input.

How do you know this is true?

@marinus this is believed to be true ( but not proven yet). looking for some proof.

@marinus, you can prove that it's possible by descent (or equivalently by strong induction). Case-split on x mod 3: if x=3y construct y and then apply f; if x=3y+1 construct 2y+1 and apply f then g; if x=3y+2 then it gets complicated but essentially is recursive.

On a separate note, must the output be in application order or would composition order also be acceptable?

@PeterTaylor Either way is OK.

@marinus - See this question. For the purpose of this challenge, assume it's true.

Hi! Please clarify if the code and output need to include (and count for score) any characters preceding the string of f's and g's.  I'm seeing some solutions include the "1  " in their code, output, and character count while others don't.

@DarrenStone "a string of f's and g's" is a clear definition, isn't it?

@Howard, I was thrown by the full <input> = 1 <string> being written in "code font" in both the examples and output spec but upon another reading, you're absolutely right. Thanks! Code fixed.

GolfScript, score 64 (43-2+23)
0{)1.$2base:s{{3*}{2/}if}/41=!}do;s{103^}%+

(41 is hardcoded, therefore -2 characters for the score). The output is
fffgffggffggffgggffgggg

which is 23 characters (without newline). By construction the code guarantees that it always returns (one of) the shortest representations.

Quoting user Darren Stone in a suggested edit on this post: "I am unable to leave a comment here so I will leave an edit. This output does not include the first two characters "1 " nor are those reflected in score. Should be an easy fix and still an incredibly short solution. Cheers!" (I rejected, but thought I should carry the message)

@Doorknob The challenge states that the "1 " should not be included in the output.

We're getting dirty, friends!
JAVA 210 207  199 characters
public class C{public static void main(String[] a){int i=41;String s="";while(i>1){if(i%3<1){s+="f";i/=3;}else if(i%3<2){s+="g";i+=i+1;}else{s+="g";i+=i+(Math.random()+0.5);}}System.out.println(s);}}

non-golfed:
public class C {

    public static void main(String[] a) {

        int i = 41;
        String s = "";
        while (i > 1) {
            if (i % 3 == 0) {
                s += "f";
                i /= 3;
            } else {
                if (i % 3 == 1) {
                    s += "g";
                    i += i + 1;
                } else {
                    s += "g";
                    i += i + (Math.random() + 0.5);
                }
            }
        }
        System.out.println(s);
    }
}

output : depending on the faith of the old gods, the shortest i had was 30. Note that the output must be read from the right.
234
1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108
1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

edit 45
1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

points : 318 199+30 = 229
edit1 (2*i+1)%3==0 --> (2*i) % 3 ==1
Nota Bene if you use Java 6 and not Java 7 while golfing, you can use
public class NoMain {
    static {
        //some code
        System.exit(1);
    }
}

39 characters structure instead of a standard structure which is 53 characters long.

(2*i+1)%3==0 is equivalent to i%3==1

if(X){A}else{if(Y){B}else{C}} is longer than if(X){A}else if(Y){B}else{C}. Also you can replace your == conditions with shorter < conditions.

@PeterTaylor true, my solution still is ugly. I don't know if the random part makes the code shorter, but it sures makes the output crappier.

Your f/g strings begin with 'g' (which is supposed to stand for '/2'), so they will convert 1 to 0 instead of to 41. Changing the f's to g's and vice versa, also doesn't seem to give 41.

@r.e.s. Nah, the problem is that I put my chars in the wrong order (as I start with 41 and ends at 1). try fffgfgffgffgggggggfgfggfgfffggfgggfgfgfgg

OK, when I run your program, I do get valid answers. E.g., ggfgfgfgfggggfgggffgffgfgfff, i.e. fffgfgffgffgggfggggfgfgfgfgg in reverse order. (But the string you just quoted seems to be wrong.)

The core seems to work properly, I just need to reverse the output, gonna edit this.

Also, maybe you're including some trailing newline characters in your score? I find your current program length to be 204, so the output string I just quoted (of length 28) would give a score of 204 + 28 = 232.

I changed my source code many times, and the output is never the same (lowest I had was 30 chars long), so it's pretty sure the points aren't good right now

OK, but note that I commented earlier that either order is acceptable -- I'll edit the question to make that clearer.

If I'm correct, it's 229 points.

You may reduce the size considerably by converting the inner if/else into a ternary ?:. And you can use print instead of println.

Python, score 124 (90-2+36)
x=41;m=f=g=0
while(3**f!=x)*(m!=x):
 f+=1;m=3**f;g=0
 while m>x:m/=2;g+=1
print'f'*f+'g'*g

90 chars of code (newlines as 1 each) - 2 for hard-coded input numeral + 36 chars of output
Output:
ffffffffffffffffgggggggggggggggggggg

If you do m=f=0 you can make the outer loop while(n!=x)*(m!=x) and remove the breaks. Brings it to 95 chars of code.

@Daniel: You, sir, are a gentleman and a scholar.  Thanks!  Your submission is still safely 10 chars ahead of me.  :)

You can further save a bit if you replace all n by3**f.

@Howard: Thanks. Net 3 char savings. :)

For input = 1, your program generates an error ("name 'g' is not defined", due to not entering the outer while-loop).

Good catch, @r.e.s.  Thank you!  That case is fixed now and I've also dropped the leading "1 " from my output count. Dropped a few chars in the process.

You could cut out another character by writing print'f'*f+'g'*g, which would give a score of 90-2+36 = 124.

Python, score 121 (87 - 2 + 36)
t=bin(41)
l,n,f=len(t),1,0
while bin(n)[:l]!=t:f+=1;n*=3
print(len(bin(n))-l)*'g'+f*'f'

@Darren, I wasn't sure how to interpret the output description, but you're probably right. I added the '1'. Thanks!

You can drop the '1' (again!)  Your original interpretation of output description was correct. Enjoy the Python lead, again! :-)

If you combined your 2nd, 3rd, and 4th lines into l,n,f=len(t),1,0, and removed the '1', from the print statement, your score would be 87-2+36 = 121.

Thanks guys - I dropped the 1,. l,n,f=len(t),1,0 gives the same number of characters, right? (For each variable, an = and a newline is replaced with two ,s.)

If each newline is one character (e.g. UNIX-style LF), then the one-line and three-line versions have the same length. If each newline is two characters (e.g. MS Windows-style CR+LF), then the one-line version is two characters shorter than the three-line version. The score of 121 assumes one-character newlines.

True. I think LF and CRLF are both permissible in a sense since the Python interpreter accepts either... so I chose to use the shorter line break sequence :)

J, score 103 (82-2+23)
*Note: I named my verbs f and g, not to be confused with output strings f and g.
Hard-coded:
f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
'gf'{~#:(>:^:(41&~:@f@#:)^:_)1

General functions:
f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
g=:3 :'''gf''{~#:(>:^:(y&~:@f@#:)^:_)1'

Did away with operating on blocks of binary numbers, which was the most important change as far as compacting g. Renamed variables and removed some whitespace for the heck of it, but everything's still functionally the same. (Usage: g 41)
J, score 197 (174+23)
f =: 3 : 0
acc =. 1
for_a. y do. acc =. ((*&3)`(<.&-:)@.a) acc end.
)

g =: 3 : 0
f2 =: f"1 f.
l =. 0$0
i =. 1
while. 0=$(l=.(#~(y&=@:f2))#:i.2^i) do. i=.>:i end.
'fg'{~{.l
)

Output:
ffffffffggggggggfgffggg
f converts a list of booleans into number, using 0s as *3 and 1s as /2 (and floor). #:i.2^i creates a rank 2 array containing all the rank 1 boolean arrays of length i.

Perl, score 89 (63 - 2 + 28)
$_=41;$_=${$g=$_%3||$_==21?g:f}?$_*2+$_%3%2:$_/3while$_>print$g

Conjecture: If the naive approach described in my original solution below ever reaches a cycle, that cycle will be [21, 7, 15, 5, 10, 21, ...]. As there are no counter-examples for 1 ≤ n ≤ 106, this seems likely to be true. To prove this, it would suffice to show that this is the only cycle which can exist, which I may or may not do at a later point in time.
The above solution avoids the cycle immediately, instead of guessing (wrongly), and avoiding it the second time through.
Output (28 bytes):
ggfgfgfgfggfggfgfgfggfgfgfff

Perl, score 100 (69 - 2 + 33)
$_=41;1while$_>print$s{$_=$$g?$_*2+$_%3%2:$_/3}=$g=$_%3||$s{$_/3}?g:f

Using a guess-and-check approach. The string is constructed using inverse operations (converting the value to 1, instead of the other way around), and the string becomes mirrored accordingly, which is allowed by the problem specification.
Whenever a non-multiple of three is encountered, it will be multiplied by two, adding one if the result would then be a multiple of three. When a multiple of three is encountered, it will be divided by three... unless this value has previously been encountered, indicating a cycle, hence guess-and-check.
Output (33 bytes):
ggfgfgfgfggfggfgffgfgggfggfgfgfff

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Color RGB int to hex
Given three integers rgb, output hexadecimal representation as a string.
Input:          Output:
72 61 139       #483D8B
75 0 130        #4B0082
0 255 127       #00FF7F

Shortest most unorthodox code wins

Our FAQ says All questions on this site... should have an objective primary winning criterion, so that it is possible to indisputably decide which entry should win.. Shortest is objective, but "most unorthodox" is not. Also, the [tag:code-golf] tag should be used only if the winning condition is just the shortest code; and the [tag:code-challenge] tag should be used only if the [tag:code-golf] tag isn't.

and accept the winner before some time (in this case, wasn't even 24h) kind of discourages further contributions...

@PeterTaylor Sorry I will make sure to read the guidlines from now on :( I guess you are right unorthodox is very vague

Ruby: 19 characters
$_=?#+"%02X"*3%$F

Sample run:
bash-4.1$ ruby -pae '$_=?#+"%02X"*3%$F' <<< '72 61 139'
#483D8B

bash-4.1$ ruby -pae '$_=?#+"%02X"*3%$F' <<< '75 0 130'
#4B0082

bash-4.1$ ruby -pae '$_=?#+"%02X"*3%$F' <<< '0 255 127'
#00FF7F

Ruby
I was going more for the "unorthodox" part. ;)
10;a=    gets.   split
.  map  {|       x|  #x
"%02X"  %(  x.   to_i)
}; $>   <<   ?#  <rgb2hex
255 100 0
#FF6400

This is genius!

q/k (3 chars)
Not exactly unorthodox but quite short
4h$

Example
q)4h$ 72 61 139
0x483d8b

To match the output format in the question exactly, we can do (for 9 chars):
"#",/$4h$

This is missing the pound sign (#) required per the sample outputs in the question.

PowerShell: 71 52 51 41

Thanks to @manatwork for pointing out ForEach-Object can be used in place of a for loop.
  Thanks to @Joey for pointing out that I could use -join on the loop output, instead of having to put it into variables.

Golfed code:
'#'+-join(1..3|%{"{0:X2}"-f+(read-host)})

Note:
There's no error checking here for invalid inputs. The script will happily take 256, 4096, and 65536 as inputs, then output #100100010000 (which obviously won't work as RGB).
Ungolfed, with comments:
# Put a hashtag in front of the output.
'#'+

# Join the nested code into one string.
-join(

    # Pipe 1..3 to ForEach-Object to run a loop three times.
    1..3|%{

        # Take user input and format it as hex, with minimum two digits in output.
        "{0:X2}"-f+(read-host)
    }
)

Make the loop foreach($i in 1,2,3) to reduce it to 68 characters.

@manatwork I don't think that's the proper syntax for a foreach in PowerShell. (At least, I haven't been able to get some test runs to work.) However, using the right syntax, a built-in alias, and another PowerShell shortcut I recently discovered, I think I've got something better, shaving another 12 characters off your suggestion. (1..3)|%{...} (Insert bracketed statement from existing script in place of the ellipsis.) I still need to fully test this in the script, but thanks for pointing me in that direction!

No idea whether it's the proper syntax or not, but the SS64 reference for foreach mentions it and it works for me. (No idea about the version. The one which came with Windows 7.)

@manatwork That's interesting. I'd like to dig around and figure out what's wrong with that some more (I was getting "unexpected token 'in'..." errors.) some other time. It's possible the SS64 article was written for a different version of PowerShell - I'm not sure. For now, I've confirmed that (1..3)|% works and brings the script down to 56 characters. I'll edit that into the answer, and definitely credit you for the idea. Thanks again!

Probably some version incompatibility. http://i.stack.imgur.com/xvTAT.png Hopefully your even shorter code will work everywhere.

@manatwork Which version are you using? $PSVersionTable.psversion Also, I'm not sure about compatibility for this script with 3.0. I seem to recall they changed the way variables are scoped by default, so calling $1, $2, or $3 from outside the function in which they were created might not work without some additional code.

2, 0, -1, -1? (Now I realize I never seen a PowerShell version number before.) http://i.stack.imgur.com/mBwvT.png

let us continue this discussion in chat

Apparently, in some cases, foreach is not translated as an alias to ForEach-Object - it's its own loop construct. http://superuser.com/a/675488/50086

I was about to comment here, but then ended up writing my own implementation after noticing that the task is fairly trivial. You can at least drop the parentheses and the 0 around the Read-Host. +$foo is the same as (0+$foo) (a trick I shared in Tips for golfing in PowerShell, too :)). You can then drop the quotes around $_ as well. Which then brings you down to 46.

Oh, dang. You can get this to 41 by using -join: '#'+-join(1..3|%{"{0:X2}"-f+(read-host)}).

bash 22 21 chars
(Thanks @manatwork for 1 char using \ instead of double-quotes)
printf \#%02X%02X%02X 12 12 12
#0C0C0C

or reading STDIN in a loop: 48 chars:
while read f;do printf "#%02X%02X%02X\n" $f;done <<<$'72 61 139\n75 0 130\n0 255 127'
#483D8B
#4B0082
#00FF7F

Added 2015-10-06:  bash (more unorthodox method) 84 83 chars
c=({0..9} {a..f}) d=\#;for b;do for a in / %;do d+=${c[$b$a 020]};done;done;echo $d

I know, it could be 82 chars if 020 where written 16, but I prefer this... Or maybe d+=${c[$b$a 0x10]} which was first post.
hexcolor() {
    local a b c=({0..9} {a..f}) d=\#
    for b ;do
        for a in / % ;do
            d+=${c[$b$a 0x10]}
        done
    done
    echo $d
}
hexcolor 72 61 139
#483d8b
hexcolor 75 0 130
#4b0082
hexcolor 0 255 127
#00ff7f

Another bash approach
#!/bin/bash
browser=firefox   #  google-chrome iceweasel
url="data:text/html;charset=UTF-8,"
url+="

"
input="%s:<input type='text' size='5' value='200'"
input+=" onKeyDown='k(event)' onChange='m()' id='%s' />"
for c in R G B ;do
    printf -v add "$input" $c $c
    url+="$add"
  done
$browser "$url"

This will display a browser window, with:

Where you could roll the mousewheel to change values (with shift key holded for step by 15)...

Actually the terminating newline was not requested and only “#” needs escaping, so printf \#%02X%02X%02X is enough.

Added a more unorthodox method :

Lol. That inner loop is indeed shockingly unorthodox.

@manatwork thanks, I find d+=${c[$b$a 0x10]} something sexy!

... or maybe d+=${c[$b$a 020]} will do the job and look nice

Perl, 31 characters
perl -nE 'say"#",map{unpack H2,chr}split'

It's hard to make such a short program unorthodox, but I think this works.

I like this answer :) a few more and I think I might settle on this if nothing better rolls around.

Cool! Just an unpack question: can you make the hexadecimal a..f uppercase, like in the question?

@manatwork I tried to find a way to do it inside of unpack, but no luck. One way is to use sprintf instead of unpack, but that's longer and completely orthodox. The other way is to just modify the string to uppercase : map{uc unpack H2,chr}, at a cost of three characters.

Thank you, @breadbox. Those tricky little pack and unpack never get into my coding style. So its unorthodox enough for me.

Wrong count. This make 30 char!

@F.Hauri The -n option counts as one character, so the total is 31. The rules for counting option characters are described here: http://meta.codegolf.stackexchange.com/questions/273/on-interactive-answers-and-other-special-conditions/274#274.

><> 103 60
"#"or>1[:82*%:}-82*,86*+:"9"v
    ;^?l ]o+*7)"9":+*68o+*7)<

Made use of the wasted white space, and moved some code into it
Run with command line inputs:
python fish.py generateHex.fish -v 255 36 72

output:
"#FF2448"

Will provide explanation on request. If you can figure it out I'd rather not bother

Perl 24 chars
perl -ne 'printf"#"."%02x"x3,split'
13 31 133
#0d1f85

Sorry, it's not as sexy than using unpack, but shorter!
More obscure version:
But if you really prefer to use unpack, then you could:
$==24;s/\d+[\n ]*/{$=-=8;($&<<$=).do{rand>.5?qw<+>[0]:"|"}}/eg;$_=
pack("N",eval($_.587.202.560));say$1,unpack("H6",$2)if/^(.)(.*)$/s

For sample, it's not the shorter version, but I like it! ( Note the use of rand for randering this :-)
perl -nE '
    $==24;s/\d+[\n ]*/{$=-=8;($&<<$=).
    do{rand>.5?qw<+>:"|"}}/eg;$_=pack(
    "N",eval($_.587.202.560) );say $1,
    unpack("H"."6",$2) if /^(.)(.*)$/s
  ' <<< $'72 61 139\n75 0 130\n0 255 127'
#483d8b
#4b0082
#00ff7f

Action Script 3 | 43 characters
trace("#"+(72<<16|61<<139|b).toString(16));

Output: #483D8B

Can you not drop a lot of white space here? I don't know Action Script, but they don't look required

@Cruncher yeah sorry, one of my first answers here.

Kill the semicolon at the end to save a char

JavaScript, 89 chars
console.log('#' + ('00000' + eval('256*(256*(' + DEC.replace(/ /g, ')+')).toString(16)).slice(-6))

Converts 72 61 139 to 256*(256*(72)+61)+139 and evals it.

Nice one, but fails on the 3rd sample posted in the question.

Ah, good call. Fixed.

Using eval('(('+DEC.replace(/ /g,'<<8)+')) instead of eval('256*(256*('+DEC.replace(/ /g,')+')) let you save 5 chars!

PowerShell, 45
'#'+-join(-split(read-host)|%{'{0:X2}'-f+$_})

Or, if it can be used by piping in the data, you can just use
'#'+-join(-split"$input"|%{'{0:X2}'-f+$_})

which brings it down to 42.

Nice work! Shows I still have much to learn about golfing!

Oh, your idea with the variables was clever too; would have never crossed my mind. It just so happens that it's longer than my usual favourite: -split and -join.

C (67 chars no main boilerplate)
int r,g,b;
scanf("%d %d %d",&r,&b,&g);
printf("#%06x",r<<16|g<<8|b);

the bog standard printf & bit twiddler usage

Wait, readf? Shouldn't that be scanf?

@breadbox ah yeah I spent too much time in D; either way no difference in char count

Forth, 62 characters
: D 0 <<# # # #> TYPE #>> ; 35 EMIT HEX SWAP ROT D D D DECIMAL

doesn't work for 1 1 1 which should output #010101

Hi @ratchetfreak. It works for me. Just tested with gforth. Giving it 1 1 1 outputs #010101. Any other values 0-255 also work. What environment or forth are you using?

Dc: 35 32 characters
[#]n16o?ShShSh[Lhd16/n16%n]ddxxx

Sample run:
bash-4.1$ dc -e '[#]n16o?ShShSh[Lhd16/n16%n]ddxxx' <<< '72 61 139'
#483D8B

bash-4.1$ dc -e '[#]n16o?ShShSh[Lhd16/n16%n]ddxxx' <<< '75 0 130'
#4B0082

bash-4.1$ dc -e '[#]n16o?ShShSh[Lhd16/n16%n]ddxxx' <<< '0 255 127'
#00FF7F

Dc: 27 24 characters
(But needs the input numbers on separate lines.)
[#]n16o[?d16/n16%n]ddxxx

Sample run:
bash-4.1$ dc -e '[#]n16o[?d16/n16%n]ddxxx' <<< $'72\n61\n139'
#483D8B

bash-4.1$ dc -e '[#]n16o[?d16/n16%n]ddxxx' <<< $'75\n0\n130'
#4B0082

bash-4.1$ dc -e '[#]n16o[?d16/n16%n]ddxxx' <<< $'0\n255\n127'
#00FF7F

There are not enough dc answers on this website.

powershell 37
saved one byte thanks to TimmyD
cat rgb2hex.ps1
$args|%{$o+="{0:X2}"-f[byte]$_};"#$o"
wc -c rgb2hex.ps1
38 rgb2hex.ps1
powershell -f .\rgb2hex.ps1 72 61 139
#483D8B
powershell -f .\rgb2hex.ps1 0 255 127
#00FF7F

You can save a couple bytes by getting rid of the [byte] since we're given the input as integers, and edit your output to be "#$o" -- that gives 31 bytes for $args|%{$o+="{0:X2}"-f$_};"#$o"

@TimmyD   dont know if removing [byte] works correctly in all version in a version in which i tested (iirc 2.0 in xp ) without [byte] it was not concatenating as hex but as ints ie 72 61 139 was #7261139 not #483d8b "#$o" inside quotes isnt a string literal but evaluated string nice to know  thanks comments about hex conversion will be appreciated

It's apparently a difference between PowerShell v2 and v3 -- must be something in how the corresponding .NET version handles hexadecimal conversion, but I can't find documentation on it.

R, 16 bytes
That's it. Use the built in.
rgb(r,g,b,m=255)

Python 2.7 (80 Characters)
x=lambda y: ("0"+hex(int(y))[2:])[-2:]
print "#"+''.join(map(x,input().split()))

I'm looking for a better way to handle the single digit hex values. Any ideas?

Maybe use format strings? '%02x' seems to be what everyone else has done.

C, 67 73 Characters (65 Chars excluding main)
main(){int a,b,c;scanf("%d%d%d",&a,&b,&c);printf("#%02X%02X%02X",a,b,c);}

Boring C program - very orthodox.

doesn't work with a b or c smaller than 16

Changed %X to %02X.

Befunge-98, 45 characters
Bleh, duplicated code. Oh well. Just a straightforward implementation of radix conversion.
"#",v
7*+,>#@&:97+/"0"+:"9"`7*+,97+%"0"+:"9"`

Sample run
% cfunge tohex.98 <<<'72 61 139'
#483D8B
% cfunge tohex.98
#75 0 130
4800820 255 127
00FF7F

(Note: prints '#' before reading input---the task doesn't forbid this; given three numbers on stdin it produces the right output on stdout. It also doesn't bother with newlines, and as you can see it doesn't add '#' properly when run "interactively".)

Game Maker Language, 175 (Error at position 81)
Prompts for 3 to 9-digit RGB. Returns hexadecimal with GML hexadecimal sign, $
d=get_string('','')if(d=='')e=""else e="00"h="0123456789ABCDEF"while(d!=''){b=d&255i=string_char_at(h,byte div 16+1)l=string_char_at(h,byte mod 16+1)e+=i+l;d=d>>8}return '$'+e

Make this a script. Also, compile with uninitialized variables treated as 0.
Source

Gema, 93 characters
\B=@set{x;0123456789abcdef}\#
<D>=@substring{@div{$1;16};1;$x}@substring{@mod{$1;16};1;$x}
?=

Sample run:
bash-4.3$ gema '\B=@set{x;0123456789abcdef}\#;<D>=@substring{@div{$1;16};1;$x}@substring{@mod{$1;16};1;$x};?=' <<< '0 255 127'
#00ff7f

Burlsque, 12 bytes (10 bytes for lower-case)
If lower-case is allowed as well then 10 bytes:
psb6\['#+]

Usage:
blsq ) "72 61 139"psb6\['#+]
"#483d8b"

If you desperately need upper-case, add ZZ:
blsq ) "72 61 139"psb6\['#+]ZZ
"#483D8B"

If you don't receive the integers as in a string then go with:
blsq ) {72 61 139}b6\['#+]
"#483d8b"

Explanation:
ps -- parse string
b6 -- to hex
\[ -- concat
'#+] -- prepend #

Try online here.
Bonus:
To convert it back use this:
blsq ) "#483d8b"[-2cob6
{72 61 139}

Powershell, 28 bytes
'#{0:X2}{1:X2}{2:X2}'-f$args

Test script:
$f = {

"#{0:X2}{1:X2}{2:X2}"-f$args
}

@(
    ,('#483D8B',72, 61, 139)
    ,('#4B0082',75,  0, 130)
    ,('#00FF7F',0 ,255, 127)
) | % {
    $e,$a = $_
    $r = &$f @a
    "$($r-eq$e): $r"
}

Output:
True: #483D8B
True: #4B0082
True: #00FF7F

Python3.3 @ 60 chars
print("#"+3*"%.2X"%tuple(int(n) for n in input().split()))

Couldn't resist:
[dan@danbook:code_golf/int_to_hex]$ python3.3 int_to_hex.py
176 11 30
#B00B1E

JavaScript: 99 chars (110 Thanks @manatwork):
function h(i){x=(i*=1).toString(16);return 16>i?"0"+x:x}function c(r,g,b){return"#"+h(r)+h(g)+h(b)}

Sample:
#!/usr/bin/smjs

function h(i){x=(i*=1).toString(16);return 16>i?"0"+x:x}
function c(r,g,b){return"#"+h(r)+h(g)+h(b)}

if (typeof(arguments[2]) != "undefined" )
    print(c(arguments[0],arguments[1],arguments[2]));

var line;
while (line=readline()) {
    var a=line.split(" ");
    print(c(a[0],a[1],a[2]));
};

In action:
rgb.js 14 15 16 <<< $'15 16 17\n16 17 18'
#0e0f10
#0f1011
#101112

JS Snippet (216)

function h(i){x=(i*=1).toString(16);return 16>i?"0"+x:x}
function c([r,g,b]){return"#"+h(r)+h(g)+h(b)}
function d(){o.innerHTML="";t.value.split("\n").forEach(
function(l){o.innerHTML+=c(l.split(" "))+"
"; })};d()
<textarea id="t" onkeyup="d()">72 61 139
75 0 130
0 255 127</textarea>

You are multiplying i by 1 twice. Better do i*=1 once. And choose a different name for the local variable, so you can leave out the var keyword. I don't have smjs, but function h(i){x=(i*=1).toString(16);return 16>i?"0"+x:x}function c(r,g,b){return"#"+h(r)+h(g)+h(b)} should do the same in 99 characters.

@manatwork smjs is the binary tool from spidermonkey, also available as standard Debian packakge.

Oops. Actually I know+use+enjoy that interpreter, but I always met it with then name js.

javascript (ES6), 55
alert('#'+(r<<16|g<<8|b).toString(16).padStart(6,'0'))

You may want to place a # before your language name and byte count to make it a header. Also, is this ES6?

Clojure 76 Characters
This might be late, for the sake of completeness:
(defn hexy [r g b] (reduce str (cons "#" (map #(format "%02X" %) [r g b]))))

Example calls:
(hexy 0 255 127)
"#00FF7F"

Mathematica, 40 characters
f = StringJoin["#", IntegerString[#, 16, 2]] &

rgbs = {{72, 61, 139}, {75, 0, 130}, {0, 255, 127}}

f /@ rgbs // Column

#483d8b
#4b0082
#00ff7f

Common Lisp, 39 characters
(format()"#~@{~2,'0x~}"#1=(read)#1##1#)

Read three integers, return a string.

Javascript ES6, 63 bytes
h=>'#'+h.split` `.map(x=>(x<16?0:'')+(x*1).toString(16)).join``

Coincidentally, I ended up writing almost exactly the same thing as you before I saw yours. Very nice =) They're close enough that I won't post mine, but you can save a few bytes on your mapping with this: x=>(x<16?0:'')+x.toString(16)

Also, no need to include the r= at the beginning. It still counts as a function even as an anonymous function, since you can invoke it without having to assign anything.

Whoops. Meant the map to be: x=>(x<16?0:'')+(x*1).toString(16) Yours and my first one there currently give wrong values for x>9.

This currently returns #7261139 instead of #483D8B for the first test case.

Python (55 chars)
'#'+''.join([hex(int(i))[2:].upper() for i in input()])

Python 2, 40 bytes
s='#';exec's+="%02X"%input();'*3;print s

Reads the input from three separate lines. Abuses exec and string multiplication.
Example usage:
$ python2 rgbint.py
72
61
139
#483D8B

$ python2 rgbint.py
75
0
130
#4B0082

$ python2 rgbint.py
0
255
127
#00FF7F

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Shortest implementation of a linked list, stack and queue
Challenge
Write the shortest program that implements the minimum requirements for a linked list, stack and queue.
Minimum requirements

Functions that allow the user to add and remove elements from the linked list, stack and queue.
Any data type can be added to the linked list, stack and queue (string, int, etc.).
One special function (e.g. sort letters alphabetically).
The program must work (compile without errors and operations and results should make sense in the context of linked lists, stacks and queues)!
Lastly, this program must be hard-coded.  Arrays, however, are allowed (please refer to the restrictions section).

Winning criteria

Standard Codegolf rules.
Number of characters based on the summation of characters for linked list, stack and queue.

Restrictions

No trivial answers (i.e. 0 or 1 for a stack based language).
You are allowed to write the program in any language except for stack-based languages (let me know if this is unfair).
You cannot simply use the functions of another class.  If a language (like Ruby) already has push and pop functions in arrays or any other class, you must write your own push and pop functions.

Little blurb: If this code golf challenge is too simple, I will add more requirements.  I'm also open to any suggestions.

Mhh, not really clear. What prevents me from doing class A extends java.util.Stack {}?

@JohannesKuhn Good point, updated.

what if, for example, in Ruby arrays have push, pop, and shift, so technically arrays are stacks and queues. They behave like linked lists, because linked lists are basically just arrays, so the default array already pretty much meets these requirements...

@Doorknob So "hard-coded functionality" would be better wording for this question?  I guess restricting trivial answers is too generic... I'll think of a better way to word "trivial".

I don't know how I could do this without using arrays...

@Doorknob You can. I want people to write their own push and pop functions, not use the defaults already implemented in the language.

So, we only need to write push, pop, and shift functions? I'll do it now

@Doorknob Hmm, this question sounded a lot better in my head... Oh well.  At least it will be good practice for beginners.

@Doorknob But in that case you just have a single Deque/List hybrid, not
a separate list, stack, and queue (though the question doesn't seem to specify that they have to be separate)

Haskell, 81 69 characters
data L a=N|a:~L a
N~:z=z:~N
(a:~b)~:z=a:~(b~:z)
r N=N
r(a:~z)=r z~:a

This code makes use of no preexisting functions at all. The push operation is :~, the enqueue operation is ~:. Both pop and dequeue are via pattern match against :~. The extra operation r is reverse.
Stacks:
ex1 =
    let stack0 = N                      -- empty stack
        stack1 = 'a' :~ stack0          -- push 'a'
        stack2 = 'b' :~ stack1          -- push 'b'
        first :~ stack3 = stack2        -- pop
        second :~ stack4 = stack3       -- pop
    in mapM_ print [first, second]

—
λ: ex1
'b'
'a'

Queues:
ex2 =
    let queue0 = N                      -- empty queue
        queue1 = queue0 ~: 'x'          -- enq 'x'
        queue2 = queue1 ~: 'y'          -- enq 'y'
        queue3 = queue2 ~: 'z'          -- enq 'z'
        next0 :~ queue4 = queue3        -- deq
        next1 :~ queue5 = queue4        -- deq
        next2 :~ queue6 = queue5        -- deq
    in mapM_ print [next0, next1, next2]

—
λ: ex2
'x'
'y'
'z'

List reverse operation:
ex3 =
    let list = "alpha" :~ ("beta" :~ ("gamma" :~ N)) -- a list
        tsil = r list                   -- reverse the list
        native N = []                   -- convert to native list
        native (a:~z) = a : native z    -- for easy printing
    in mapM_ (print . native) [list, tsil]

—
λ: ex3
["alpha","beta","gamma"]
["gamma","beta","alpha"]

Ruby, 123
class S
def initialize
@a=[]
end
def u n
@a[@a.size]=n
end
def o
@a.slice! -1
end
def s
@a.slice!0
end
def j x
@a*x
end
end

Example:
s = S.new     # initialize
s.u 5         # push 5
s.u 10        # push 10
s.u [1,2,3]   # push [1,2,3]
s.u "test"    # push "test"
s.u "test2"   # push "test2"
puts s.s      # shift - queue behaivior (remove and return first element, 5)
puts s.o      # pop - stack behaivior (remove and return last element, "test2")
puts s.j ", " # join - special behavior (join elements with argument, "10, 1, 2, 3, test")

C, 659 bytes
Try Online
typedef M;typedef struct M{int d;M*n;M*p;}Q;typedef struct{Q*f;Q*e;}L;Q*t;x;
Q*F(L**l){return*l?(*l)->f:0;}
Q*E(L**l){return*l?(*l)->e:0;}
N(Q**t){*t=*t?(*t)->n:0;}
P(Q**t){*t=*t?(*t)->p:0;}
A(L**l,int d){Q*t=(Q*)malloc(sizeof(Q));t->d=d;if(*l)(*l)->f->p=t,t->n=(*l)->f,(*l)->f=t;else(*l)=(L*)malloc(sizeof(L)),(*l)->f=t,(*l)->e=t;}
B(L**l){if(*l)t=(*l)->f,(*l)->f=t->n,(*l)->f->p=0,x=t->d,free(t);if(!(*l)->f)free(*l);return x;}
C(L**l,int d){t=(Q*)malloc(sizeof(Q));t->d=d;if(*l)(*l)->e->n=t,t->p=(*l)->e,(*l)->e=t;else (*l)=(L*)malloc(sizeof(L)),(*l)->f=t,(*l)->e=t;}
D(L**l){if(*l)t=(*l)->e,(*l)->e=t->p,(*l)->e->n=0,x=t->d,free(t);if(!(*l)->e)free(*l);return x;}

Detailed github
typedef _LNode; typedef struct _LNode{ void* d; _LNode* n; _LNode* p; } LNode;
typedef _List; typedef struct _List{ LNode* f; LNode* e; int size; } List;

LNode* list_begin(List** l){ return *l?(*l)->f:0; }
LNode* list_end(List** l){ return *l?(*l)->e:0; }

void list_iterator_next(LNode** t){ *t = *t?(*t)->n:0; }
void list_iterator_prev(LNode** t){ *t = *t?(*t)->p:0; }

int list_size(List** l){ return *l?(*l)->size:0; }

void list_push_front(List** l, void* d)
{
    LNode*t = (LNode)malloc(sizeof(LNode));
    t->d = d;

    if(*l)
        (*l)->f->p = t,
        t->n = (*l)->f,
        (*l)->f = t;
    else
        (*l)=(List*)malloc(sizeof(List)),
        (*l)->f = t,
        (*l)->e = t;

    (*l)->size++;
}

void list_push_back(List** l, void* d)
{
    LNode*t = (LNode)malloc(sizeof(LNode));
    t->d = d;

    if(*l)
        (*l)->e->n = t,
        t->p = (*l)->e,
        (*l)->e = t;
    else
        (*l)=(List*)malloc(sizeof(List)),
        (*l)->f = t,
        (*l)->e = t;

    (*l)->size++;
}

void* list_pop_front(List** l)
{
    LNode* t = 0;
    void* d = 0;

    if(*l)
        t = (*l)->f,
        (*l)->f = t->n,
        (*l)->f->p = 0,
        d = t->d,
        free(t),
        (*l)->size--;

    if(!(*l)->f) free(*l);

    return d;
}

void* list_pop_back(List** l)
{
    LNode* t = 0;
    void* d = 0;

    if(*l)
        t = (*l)->e,
        (*l)->e = t->p,
        (*l)->e->n = 0,
        d = t->d,
        free(t),
        (*l)->size--;

    if(!(*l)->e) free(*l);

    return d;
}

I think you can ditch the casts before malloc(). Also, you can replace sizeof(Q) with sizeof*t

JavaScript, 188
function L(){N=null;E=[N,N];t=this;h=E;t.u=i=>h=[i,h];
t.o=_=>h==E?N:h[+!(h=h[1])];t.e=(i,l)=>h=(l||h)==E?[i,
E]:[(l||h)[0],t.e(i,(l||h)[1])];t.s=_=>{o="";while(i=t.o())
{o+=i+","}return o}}

(Line breaks added for readability, not needed for answer or counted as bytes)
Usage
Methods

u(item): Push
o() -> item: Pop (or dequeue)
e(item): Enqueue
s() -> string: Convert to a string

Example
let failed = _ => { throw Error(); };
let list = new L();

// Stack
list.u(1);
list.u(3);

list.o() === 3 || failed();
list.u(2);
list.o() === 2 || failed();
list.o() === 1 || failed();
list.o() === null || failed();

// Queue

list.e(1);
list.e(2);

list.o() === 1 || failed();
list.e(3);
list.o() === 2 || failed();
list.o() === 3 || failed();
list.o() === null || failed();

// Reverse
list.u(1);
list.u(2);
list.u(3);

list.s() === "3,2,1," || failed();

Explanation
function L(){
    N=null; // end marker
    // a node has the format [item, rest]
    E=[N,N]; // end marker, is a node
    t=this;
    h=E; // head of list, is a node

    t.d = _ => JSON.stringify(h);

    t.u=i=>h=[i,h]; // push

    t.o=_=> // pop/deque
        h==E?
        N:
        h[+!(h=h[1])]; // set head to rest, return item (index into zeroth index by casting an assignment to a value to a bool to a float)

    // t.e acts recursively, we use `||` to set a default for when the user calls
    t.e=(i,l)=> // enqueue (user caller leaves `l` undefined)
        h=
            (l||h)==E?
                [i, E]: // if at end, insert new item right before
                [(l||h)[0],t.e(i,(l||h)[1])]; // else keep current value and process rest recursively

    t.s=_=>{
        o="";
        while(i=t.o()) {
            o+=i+","
        }
        return o
    }
}

Notes
List can't store anything JavaScript casts to false (null, false, 0, [], etc.). Repeated pop operations on an empty list have no effect. Ignore the return values of push and enqueue. Because I use global variables to reduce character count, only one list can be created.