text:
Calculate pi to 5 decimals
This comes from http://programmers.blogoverflow.com/2012/08/20-controversial-programming-opinions/
"Given that Pi can be estimated using the function \$4 \times (1 - 1/3 + 1/5 - 1/7 + \cdots)\$ with more terms giving greater accuracy, write a function that calculates Pi to an accuracy of 5 decimal places."

Note, the estimation must be done by calculating the sequence given above.

You should probably add some more rules, otherwise you will get answers like (python) p=lambda:3.14159

Have you seen http://codegolf.stackexchange.com/questions/506/calculate-500-digits-of-pi , which is very similar? At the very least, trig functions should be banned for this problem because they allow for trivial solutions such as this QBASIC program: ?INT(4E5*ATN(1))/1E5

I think you should require that the algorithm be one of successive approximation: the longer you compute, the closer you get to pi.

@DavidCarraher, although that's mathematically inevitable using this series, from a numerical analytical point of view it's highly dubious. A slowly converging alternating series is a poster child for loss of significance.

@PeterTaylor "Slowly converging" is an understatement. It took roughly one million places to attain the desired precision!

huh, a friend of mine posted something about this problem on facebook last night.  he didn't golf it though.

Dupe, but it's so old it's not here: http://stackoverflow.com/q/407518/12274

Later near-duplicate: http://codegolf.stackexchange.com/q/22009

"It can be answered in about 10 lines with c#" someone please beat that

I’m voting to close this question because use of a specific algorithm is impossible to objectively validate

JavaScript, 46 58 56 45 bytes
ES6 update: Turns out there's more features available to us now that five years have passed.
let f=(i=0,a=0)=>i>1e6?a:f(i+4,a+8/-~i/(i+3))

This version (45 bytes; yes, the let is required) works in ES6 strict mode in theory.  In practice, you can run it in V8 (e.g. with node) with --use-strict --harmony-tailcalls; the Proper Tailcalls feature isn't widely implemented yet, alas.  However, it's specified behaviour, so it should be fine.
If we want to stick to what's widely implemented, and not require strict-mode, we can simply use the ES6 fat-arrow syntax for functions but otherwise retain the same implementation as before (suggested by Brian H) for a cost of 48 bytes.
a=>{for(a=i=0;i<1e6;a+=8/++i/~-(i+=3));return a}

The choice of name for the single parameter doesn't really matter, but we might as well pick one of the names we use so as to minimise the global-scope pollution.

function(){for(a=i=0;i<1e6;a+=8/++i/~-(i+=3));return a}

This version is a function expression; add two characters (e.g. " f") if you want it named.  This version clobbers the globals a and i; this could be prevented if we added "a,i" to the parameter list.
Makes use of a reformulated version of the algorithm in order to circumvent the need for subtraction.
 1/1 - 1/3  +   1/5 - 1/7   +    1/9 - 1/11  + ...
(3/3 - 1/3) + (7/35 - 5/35) + (11/99 - 9/99) + ...
    2/3     +      2/35     +       2/99     + ...
  2/(1*3)   +    2/(5*7)    +     2/(9*11)   + ...

Here's a "plain" version without this adjustment:
function(){for(a=0,i=1;i<1e6;i+=2)a+=[,4,,-4][i%4]/i;return a}

which clocks in at 64 62 characters.
Thanks to @ardnew for the suggestion to get rid of the 4* before the return.

History
function(){for(a=i=0;i<1e6;a+=8/++i/~-(i+=3));return a}     // got rid of `i+=4`; restructured
// Old versions below.
function(){for(a=0,i=1;i<1e6;i+=4)a+=8/i/-~-~i;return a}    // got rid of `4*`
function(){for(a=0,i=1;i<1e6;i+=4)a+=2/i/-~-~i;return 4*a}

o.O  very nice job, factoring out the subtraction.

great work, but needs to be written as a proper function

@ardnew: Thanks, I must've missed that detail when I read the problem description.  I've updated it, and it's now a callable function expression (lambda); not sure if this is allowed or if it has to be given a name.  If that's the case, it's just an additional two characters anyway.

@FireFly you can also shave off 2 chars by changing a+=2/i/-~-~i;return 4*a to a+=8/i/-~-~i;return a

@ardnew: oh, awesome; didn't think of that. :D

using arrow notation you can get it down to this: a=x=>{for(a=i=0;i<1e6;a+=8/++i/~-(i+=3));return a} and it's a named function now, to make it anonymous just get rid of the first 2 chars. (x is an unused parameter, it saves one byte against using ())

@BrianH. Heh, this answer predates ES6, so fat-arrow functions didn't exist yet. Hmm, let me ponder this a bit and update with an ES6 version, I have some ideas…

omg, didnt notice the date lol

Python 59 bytes
print reduce(lambda x,p:p/2*x/p+2*10**999,range(6637,1,-2))

This prints out 1000 digits; slightly more than the required 5. Instead of using the prescribed iteration, it uses this:
pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + 5/11*(2 + ...)))))

The 6637 (the innermost denominator) can be formulated as:
digits * 2*log2(10)
This implies a linear convergence. Each deeper iteration will produce one more binary bit of pi.
If, however, you insist on using the tan-1 identity, a similar convergence can be achieved, if you don't mind going about the problem slightly differently. Taking a look at the partial sums:
4.0, 2.66667, 3.46667, 2.89524, 3.33968, 2.97605, 3.28374, ...
it is apparent that each term jumps back and forth to either side of the convergence point; the series has alternating convergence. Additionally, each term is closer to the convergence point than the previous term was; it is absolutely monotonic with respect to its convergence point. The combination of these two properties implies that the arithmetic mean of any two neighboring terms is closer to the convergence point than either of the terms themselves. To give you a better idea of what I mean, consider the following image:

The outer series is the original, and the inner series is found by taking the average of each of the neighboring terms. A remarkable difference. But what's truly remarkable, is that this new series also has alternating convergence, and is absolutely monotonic with respect to its convergence point. That means that this process can be applied over and over again, ad nauseum.
Ok. But how?
Some formal definitions. Let P1(n) be the nth term of the first sequence, P2(n) be the nth term of the second sequence, and similarly Pk(n) the nth term of the kth sequence as defined above.
P1 = [P1(1), P1(2), P1(3), P1(4), P1(5), ...]
P2 = [(P1(1) +P1(2))/2, (P1(2) +P1(3))/2, (P1(3) +P1(4))/2, (P1(4) +P1(5))/2, ...]
P3 = [(P1(1) +2P1(2) +P1(3))/4, (P1(2) +2P1(3) +P1(4))/4, (P1(3) +2P1(4) +P1(5))/4, ...]
P4 = [(P1(1) +3P1(2) +3P1(3) +P1(4))/8, (P1(2) +3P1(3) +3P1(4) +P1(5))/8, ...]
Not surprisingly, these coefficients follow exactly the binomial coefficients, and can expressed as a single row of Pascal's Triangle. Since an arbitrary row of Pascal's Triangle is trivial to calculate, an arbitrarily 'deep' series can be found, simply by taking the first n partial sums, multiply each by the corresponding term in the kth row of Pascal's Triangle, and dividing by 2k-1.
In this way, full 32-bit floating point precision (~14 decimal places) can be achieved with just 36 iterations, at which point the partial sums haven't even converged on the second decimal place. This is obviously not golfed:
# used for pascal's triangle
t = 36; v = 1.0/(1<<t-1); e = 1
# used for the partial sums of pi
p = 4; d = 3; s = -4.0

x = 0
while t:
  t -= 1
  p += s/d; d += 2; s *= -1
  x += p*v
  v = v*t/e; e += 1

print "%.14f"%x

If you wanted arbitrary precision, this can be achieved with a little modification. Here once again calculating 1000 digits:
# used for pascal's triangle
f = t = 3318; v = 1; e = 1
# used for the partial sums of pi
p = 4096*10**999; d = 3; s = -p

x = 0
while t:
  t -= 1
  p += s/d; d += 2; s *= -1
  x += p*v
  v = v*t/e; e += 1

print x>>f+9

The initial value of p begins 210 larger, to counteract the integer division effects of s/d as d becomes larger, causing the last few digits to not converge. Notice here again that 3318 is also:
digits * log2(10)
The same number of iteratations as the first algorithm (halved because t decreases by 1 instead of 2 each iteration). Once again, this indicates a linear convergence: one binary bit of pi per iteration. In both cases, 3318 iterations are required to calculate 1000 digits of pi, as slightly better quota than 1 million iterations to calculate 5.

That's much better than my solution: 4 * sum(1/(1+i*2) if not i%2 else -1/(1+i*2) for i in xrange(places*10**(places)))

This is very similar to my approach, which happens to be a different form of yours. In mine, as k → ∞, f(-1,k) approaches your Euler-sum.

Very cool; awesome analysis and explanation, thank you.

Just a small thing. Didn't you mean after the P_1 = ..., P_2 = ..., P_3 = ..., P_4 = ..., "...multiply each by the corresponding term in the kth row of Pascal's Triangle, and dividing by 2^{k-1}.", instead of nth row and 2^{n-1}?.

@jeremyradcliff I did, yes. Thanks for the correction.

Mathematica 42 39 34 33 31 26 32
Archimedes' Approach 26 chars
N@#*Sin[180 Degree/#]&

This reaches the criterion when input is 822.
Question: Does anyone know how he computed the Sin of 180 degrees? I don't.

Leibniz' Approach (Gregory's series) 32 chars
This is the same function the problem poser gave as an example.
It reaches the criterion in approximately one half million iterations.
N@4Sum[(-1)^k/(2k+1),{k,0,10^6}]

Madhava-Leibniz Approach 37 chars
This variation uses a few more characters but converges to criterion in only 9 iterations!
N@Sqrt@12 Sum[(-1/3)^k/(2k+1),{k,0,9}]

those all compute it by the algorithm given in the problem definition?

@acolyte  Leibniz' approach (now the first one listed) is indeed the one mentioned in the description of the problem. It's very slow to converge.  A slight variation on it (Madhava-Leibniz) converges very quickly.

Sine of 180° is pretty easy.  It's 180°/N that can get tricky outside of the usual suspects for N.

Please explain, @J.B. Tricky to measure?

This entry should state "32" because only Leibniz' approach fulfils the requirements (counting the characters in the code as given, I get 34, but both spaces may be safely removed, giving indeed a length of 32).

@celtschk You appear to be correct.  Thanks.

Java (67 chars)
float r(){float p=0,s=4,i=1E6f;while(--i>0)p+=(s=-s)/i--;return p;}

Note that this avoids loss of significance by adding the numbers up in the correct order.

this is fully compliant C code too. if posted as C, you could change while(--i>0) to while(i--) and save 2 chars

@ardnew, true, but with C there are much more interesting tricks to play...

Haskell, 32
foldr(\k->(4/(2*k+1)-))0[0..8^7]

GHCi> foldr(\k->(4/(2*k+1)-))0[0..8^7]
  3.141593130426724

Counting a function name it's
34
π=foldr(\k->(4/(2*k+1)-))0[0..8^7]

APL (14)
4×-/÷1-⍨2×⍳1e6

13, --/4÷1-2×⍳1e6

R - 25 chars
sum(c(4,-4)/seq(1,1e6,2))

J, 26 chars
+/+/_2((4 _4)&%)>:+:i.100
Moved from 100 items of sequence to  1e6 items. Also now it's a code tagged and could be copypasted from browser to the console without errors.
+/+/_2((4 _4)&%)\>:+:i.1e6

-/4%>:2*i.1e6 -- 13 characters. (Thanks to b_jonas in #jsoftware for making me realise that -/ works to compute a sum with alternating sign.  [This is since all operators in J are of equal precedence and right-associative, so -/ 1 2 3 4 <=> 1 - (2 - (3 - 4)) <=> 1 - 2 + 3 - 4.])

that's neat and twice as awesome. Or even 2^10 more awesome!

@FireFly that is beautiful

C (GCC) (44 chars)
float p(i){return i<1E6?4./++i-p(++i):0;}

That's 41 chars, but it also has to be compiled with -O2 to get the optimiser to eliminate the tail recursion. This also relies on undefined behaviour with respect to the order in which the ++ are executed; thanks to ugoren for pointing this out. I've tested with gcc 4.4.3 under 64-bit Linux .
Note that unless the optimiser also reorders the sum, it will add from the smallest number, so it avoids loss of significance.
Call as p().

Your recursive call is q(), not p(). And I don't think -O2 should be counted (but if you do count it, it's 4 chars because of the required space).

Also: 1. gcc 4.1.1 doesn't optimize the recursion (and I don't see how it could), so the stack overflows. 2. it should be called as p(0). 3. Save a char by return++i.... 4. Two ++i makes undefined behavior.

@ugoren, thanks for your comments. In order: q - that'll teach me to double-check after renaming. I think I'm following normal practice in counting -O2 as 3 chars, but we can open it up on meta if you want; http://meta.codegolf.stackexchange.com/questions/19 is the only relevant discussion I can find. I've added the version of gcc which I'm using, and which allows me to call it as p(). Saving the char stops the optimiser and gives segfault. I will clarify that I'm using undefined behaviour, as per http://meta.codegolf.stackexchange.com/questions/21

I added an answer to the meta question about flags. About p() - are you sure calling p() from any context would work? Or is it just what happened to be on the stack in your test?

@ugoren, maybe I got lucky consistently. Even if I call it twice in a row, the second one still returns the correct value. gcc does seem to produce slightly different code for p() vs p(0), but I don't know what behaviour it documents and I'm not really a C programmer.

Clojure - 79 chars
(fn [](* 4(apply +(map #(*(Math/pow -1 %1)(/ 1.0(+ 1 %1 %1)))(range 377000)))))

This creates a function of no arguments which will calculate a float which approximates pi correctly to five decimal places. Note that this does not bind the function to a name such as pi, so this code must either be evaluated in place with eval as (<code>) or bound to a name in which case the solution is
(defn p[](* 4(apply +(map #(*(Math/pow -1 %1)(/ 1.0(+ 1 %1 %1)))(range 377000)))))

for 82 chars
About
(defn nth-term-of-pi [n] (* (Math/pow -1 n) (/ 1.0 (+ 1 n n))))
(defn pi [c] (* 4 (apply + (map nth-term-of-pi (range c)))))
(def  pi-accuracy-constant (loop [c 1000] (if (< (pi c) 3.14159) (recur (inc c)) c)))
; (pi pi-accuracy-constant) is then the value of pi to the accuracy of five decimal places

Javascript - 33 Characters
p=x=>4*(1-(x&2))/x+(x>1?p(x-2):0)

Call p passing a positive odd number x and it will calculate Pi with (x-1)/2 terms.

Ruby - 82 chars
def f(n,k=n)k>0?(f(n,k-1)+f(n+1,k-1))/2:n<0?0:f(n-1,0)+(-1)**n/(2*n+1.0)end;4*f(9)

Try it : https://repl.it/LQ8w
The approach uses the given series indirectly using a numerical acceleration approach. The resulting output is
pi ≈ 3.14159265161
vs.
pi = 3.14159265359
It starts with
f(n,0) = 1/1 - 1/3 + 1/5 - ... + ((-1)**n)/(2*n+1)

And then, since this is alternating, we can accelerate the convergence using
f(n,1) = (f(n,0) + f(n+1,0))/2

And it repeatedly applies this:
f(n,k) = (f(n,k-1) + f(n+1,k-1))/2

And for simplicity, f(n) = f(n,n).

Ruby - 50 chars
If you don't mind running for a really long while, then you could simply use
def f(n)n<0?0:f(n-1)+(-1)**n/(2*n+1.0)end;4*f(1e7)

or
a=0;for k in 0..1e7 do a+=(-1)**k/(2*k+1.0)end;4*a

VBA - 80 105 characters
From the VBE immediate window:
s=-1:x=1:i=3:While Left(4*x,7)<>3.14159:x=x+((1/i)*s):s=-s:i=i+2:Wend:Debug.?4*x

Using Left() instead of Round() saves a character but also makes it more accurate to the definition of the challenge.
I'm getting my character count from Notepad++.  I do see that other systems may count differently.
The algorithm below is easier to read:
Sub p
    s=-1:x=1:i=3
    While Left(4*x,7)<>3.14159
        x=x+((1/i)*s)
        s=-s
        i=i+2
    Wend
    Debug.?4*x
    Debug.?"Pi to 5 places solved in ";(i-1)/2;" steps."
End Sub

If you want to test this code and have Microsoft Excel, Word, Access, or Outlook installed (Windows only), press Alt+F11 to open the VBA IDE. Insert a new code module (Alt+I,M) and clear out Option Explicit if shown at the top. Then paste in the code and press F5 to run it. The results should appear in the Immediate Window (press Ctrl+G if you don't see it).

Great solution, but you have some room for improvement. It looks like you have overcounted your solution, as is, I see 97 bytes of code. You can also drop the () from the sub call. If you are willing to make it an immediate window solution you can further knock it down to s=-1:x=1:i=3:While Round(4*x,5)<>3.14159:x=x+((1/i)*s):s=-s:i=i+2:Wend:?4*x for 75 bytes.

Thanks for the tip.  I wrote a minify algorithm for VBA and have updated it.  I'm guessing that TIO counts CrLf different than Notepad++ but it's not something I am worried about.  I had fun playing this round of code golf.

Perl - 43 39 chars
not sure the rules on anonymous subroutines, but here's another implementation using @FireFly's series construction
sub{$s+=8/((4*$_+2)**2-1)for 0..1e6;$s}

sub p{$s+=(-1)**$_*4/(2*$_+1)for 0..1e6;$s}

C, 69 chars
float p,b;void main(a){b++<9e6?p+=a/b++,main(-a):printf("%f\n",4*p);}

Run with no command line parameters (so a is initialized to 1).
Must be compiled with optimization.
void main is strange and non-standard, but makes things work. Without it, the recursion is implemented as a real call, leading to a stack overflow. An alternative is adding return.
Two characters 4* can be saved, if running with three command line parameters.

You could shorten that to int main(a) or even main(a), GCC only gives a warning. And it will give a warning for void main anyway, and maybe even because you have only one argument to main.

PHP - 56 55 chars
<?for($j=$i=-1;1e6>$j;){$p+=($i=-$i)/($j+=2);}echo$p*4;

I don't know that I can get it much smaller without breaking the algorithm rule.

How about this for 45? <?for(;1e6>$j;)$p+=($i=-$i|4)/~-$j+=2;echo$p;

I was trying to come up with that, but couldn't get the bitwise ops to work. Thanks for the suggestion!

You can remove the last semicolon to save 1 character.

Python - 56 chars
Meh, My python-fu is not strong enough. I couldn't see any more shortcuts but maybe a more experienced golfer could find something to trim here?
t=s=0
k=i=1
while t<1e6:t,s,i,k=t+1,k*4./i+s,i+2,-k

You could use Python 3 to save one byte for the float division (4. -> 4). In other news, I just found a case where Python 3 actually beats Python 2 in code golf!

Python (49)
print 4*sum((-1)**i/(2*i+1.)for i in range(9**6))

3.14159453527

Befunge, 129 bytes
p08p109p^v*86%+55:<$$$<
\$\>:#,_@>+\55+/:#^_"."
v>p"~"/:"~"%08p"~"/00p:2\4%-*"(}"
8^90%"~":+2:+g90*+g80*<
>*:**\/+>"~~"00g:"~"`!|

Try it online!
In case anyone is wondering, it's an elephant.

Husk, 16 bytes
*_4ṁ\↑^9 9z*İ_İ1

Try it online! using series of only 6561 (9^4) terms (times-out on TIO for longer series).
Output is a rational number expressed as a fraction: TIO header multiplies by 100,000 and rounds to nearest integer.
*_4ṁ\↑^9 9z*İ_İ1
*_4                 # multiply by -4:
   ṁ                # sum of series of
    \               # reciprocals of
     ↑^9 9          # first 387420489 (9^9) terms of
          z*        # pairwise products of
            İ_      # powers of -1 (-1,1,-1,1,...) and
              İ1    # odd numbers (1,3,5,7,9,...)

jq, 34 characters
[range(1;1e6;4)|1/.-1/(.+2)]|add*4

Sample run:
bash-5.2$ jq -n '[range(1;1e6;4)|1/.-1/(.+2)]|add*4'
3.1415906535898936

Try it online!

Java - 92 84 chars
I cannot beat by far Peter Taylor's result, but here is mine:
double d(){float n=0,k=0,x;while(n<9E5){x=1/(1+2*n++);k+=(n%2==0)?-x:x;}return 4*k;}

Ungolfed version:
double d() {
    float n = 0, k = 0, x;
    while (n < 9E5) {
        x = 1 / (1 + 2 * n++);
        k += (n % 2 == 0) ? -x : x;
    }
    return 4 * k;
}

Edit: Saved a few characters using ternary operator.

Ruby - 54 chars
def a()p=0;1000000.times{|i|p+=8/(4*i*(4*i+2))};p;end;

My first try on console
def a()i=1;p=0;while i<2**100 do p+=8/(i*(i+2));i+=4;end;p;end;

63 chars.

You can save a byte by using def a; instead of def a().

Another one by removing the last semicolon.

k (25 chars)

    4*+/%(i#1 -1)'1+2!i:1000000

Slightly shorter:
+/(i#4 -4)%1+2*!i:1000000

Can save 6 bytes by doing -4*{y-x}/%1+2*!_1e6 (assuming a k where monadic % is inverse).

Can trim another byte by doing {y-x}/-4%1+2*!_1e6 (and avoid the monadic % issue).

Perl (76 chars)
$y=1e4;for$x(0..1e4-1){$y--while sqrt($x**2+$y**2)>1e4;$a+=$y}print 4*$a/1e8

(Result: 3.14159052)
Not the shortest possible solution, but maybe interesting. It's a geometrical one. I calculate the area under a circle.
I got another funny approach, but it's really slow. It counts the number of discrete points in a square that are below a quarter circle and calculates pi from it:
$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2

It expects the number of iterations as command line argument. Here you can see how run time relates to accuracy. ;)
$ time perl -e '$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2' 100
3.1796
real    0m0.011s
user    0m0.005s
sys 0m0.003s

$ time perl -e '$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2' 1000
3.14552
real    0m0.354s
user    0m0.340s
sys 0m0.004s

$ time perl -e '$i=shift;for$x(0..$i){for$y(0..$i){$h++if sqrt($x**2+$y**2)<$i}}print$h*4/$i**2' 10000
3.14199016
real    0m34.941s
user    0m33.757s
sys 0m0.097s

CJam - 21
1e6{WI#4d*I2*)/}fI]:+

Pretty straightforward calculation of the given series.
CJam is http://sf.net/p/cjam

Julia - 30 characters
sum(4./[1:4:1e6] - 4./[3:4:1e6])

SQL, 253 bytes
DECLARE @B int=3, @A varchar(max), @C varchar(max)='1'
WHILE @B<100000
BEGIN
SELECT @C=@C+(select case when (@B-1)%4=0 then'+'else'-'end)+
(SELECT cast(cast(1.0/@B as decimal(9,8)) as varchar(max)))
SELECT @B=@B+2
END
EXECUTE('SELECT 4*('+@C+')')

I would provide a SQL Fiddle, but this goes too many loops deep finding the 1/3 1/5 1/7 etc. fractions and gives errors lol. However, if you change @B<100000 to 1000 then it runs (obviously not to the same number of digits of accuracy).

GolfScript, 25 bytes
7.?,{2*)2.-1??./\/\-}*)4*

Try it online!
7.?                         # Push 7^7=823543, we just need an odd number bigger than 136120
   ,{               }*      # For every number k from 1 to 823542
     2*)                    # 2*k+1
        2.-1??./            # sqrt(2)/sqrt(2)=1.0 this number is just 1, but it is a float
                \/          # 1.0 / (2*k+1)
                  \-        # Subtract the sequence from this number
                      )     # Add 1 because 1/1 was skipped
                       4*   # Multiply by 4

Output:
3.141593867855424

Desmos, 30 bytes
4\sum_{n=0}^{9^6}(-1)^n/(1+2n)

Try it on Desmos
Pretty self-explanatory coding of the sequence. An array-based method, while it sounds like it should be more efficient, runs into Desmos' limitations on array length.

CJam, 20 bytes
V4e5{4T2*)d/WT#*+}fT

Try it online!
One byte shorter than aditsu's answer. ;)
Alternate 20-byter
4_e5,f{_2*)W@#*d/}:+

Try it online!
Does the same thing, but I like this better for some reason.

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


text:
Lightbox Generator
Warning: this is a complex challenge.
Overview
A lightbox, in the context of computing, is a visual effect used in image sites. A list of thumbnail images is displayed; each image can be selected and will be displayed on top of the contents of the page either at full size or to fill the screen.
The task is to generate a (fairly) self-contained web page which will display specified images in a lightbox.
Input
The input will be from stdin and will specify (one item per line):

The number of images (n)
A pattern for transforming an image name into its thumbnail (substitution described in detail further down)
A list of n images, each consisting of a URL for the full-sized image and a one-line description. You may assume that each URL ends with an extension (e.g. .jpg), although you cannot assume any extension in particular.

Sample input:
4
*_thumb.jpg
DSCF0001.jpg
My family
DSCF0002.jpg
Other animals
crop/DSCF0017.jpg
Aren't they cute?
http://www.example.com/fx.jpg
The bestest picture on the whole Internet!!!

Note: when the URLs are relative (the first three in this example), you may assume that they are relative to the current working directory. This is probably only relevant if you want to load them in your program to find their sizes.
Substitution into the thumbnail pattern works by removing the file extension from the base URL and replacing the * in the pattern. So for the four images in the example above, you would get
DSCF0001_thumb.jpg
DSCF0002_thumb.jpg
crop/DSCF0017_thumb.jpg
http://www.example.com/fx_thumb.jpg

If the pattern were thumbs/*.jpg you would get
thumbs/DSCF0001.jpg
thumbs/DSCF0002.jpg
thumbs/crop/DSCF0017.jpg
thumbs/http://www.example.com/fx.jpg

The fact that the last one there is clearly nonsense would be a bug in the input rather than in your program.
Output
The output must include some HTML, and may additionally include some other files (e.g. separate JavaScript, CSS, or images). You may emit the main HTML to stdout or to a file named index.html. Please state which you choose to do.
The HTML must include a doctype and be valid for that doctype (I suggest using HTML5!). When it loads, it must display the thumbnails, which must have some separation (margin or padding) between them, and should not be one per line. Each thumbnail must either have a title attribute or be in an element with a title attribute which displays the corresponding image description. It must also have an alt attribute which is the same description.
Clicking on a thumbnail must open the lightbox. This consists of a translucent black overlay covering the entire screen, on top of which the following are displayed in a white rectangle with a padding of at least 8px:

The full image (scaled as required - see below)
The image description
Buttons or links to go forward and back, and to close the lightbox

It is up to you whether you overlay the description and buttons over the image or put them in the margin around it.
If everything fits within the browser's viewport with the image at full size, it should be displayed at full size. Otherwise it should be scaled down, preserving aspect ratio, so that everything fits.
The forward and back (or next and previous - your choice) buttons must load the corresponding images. It is your choice as to whether they loop or stop at the ends. There should be a simple but smooth transition between the images - if the (scaled) images are different sizes, then it shouldn't jump, and you should use some kind of fade or sweep.
The following features of many lightboxes are not required:

Closing if the user clicks on the translucent black overlay
Resizing everything correctly if the browser window is resized

Permitted external resources
Use of external resources is restricted to using at most one of the following JavaScript libraries:

jQuery
Prototype
mootools

You may assume that it is in the same directory as the output html, but if you do so you should document the name which you expect it to have and the version which you require.
Compatibility
Compatibility with IE is nice, but this is a code golf, and apart from that it's not something which is easily tested without a Windows machine, so it is not a requirement. Please state which browser(s) you have tested with in your answer. I will test with Chromium, and I also have Firefox 3.6 and Konqueror available at home (plus various versions of IE, Win Safari and Opera in my lunchtimes at work, so if you want me to test on one of those, say so).

Note: this question has been sitting in the Sandbox for two weeks, so if you think there's a problem with the specification, please make it a habit to comment on questions over there.

I guess that the reason nobody wants to tackle this is because it's too much work involved. You basically want participants to develop a lightbox as a product of solving quiz with all things considered such as a programming language, css, javascript, html, and more. It sounds a full-time job for me.

I think that if you can allow to include jquery ui, there might be some to try it out.

@Paul, it's only been two days. For all you know, someone is already working on an answer. The intention was to post a more meaty challenge than the majority.

Just one quick question - can I assume that jQuery is in the same directory as the page or do I need to include it from a CDN like Google's?

@Gareth, good question. Assume that it's in the same directory and give it a short name if you want - but document the assumption clearly.

How does a web page read from stdin?

@mehaase, the web page isn't reading from stdin. The program you write, which produces the web page as output, reads from stdin.

PHP, HTML, CSS and jQuery, 1551 1482 1511 characters
<?while($x=fgets(STDIN))$i[]=chop($x)?><!doctype html><title></title><?for(;$l<$i[0]*2;$l+=2){$a=str_replace('"','"',$i[2+$l]);$b=$i[3+$l];echo'';}?>

I've assumed that the jQuery library is available in the same directory as this file, and that it is named a. The HTML takes advantage of the fact that a lot of the tags are optional but at it's base it is only:
<!doctype html>
<title></title>

...more images here...

which is considered valid by the w3c validator.
The CSS still contains some repeated styles which probably offers some room for further compression.
I've created a jsFiddle which demonstrates the lightbox functionality for those who wish to try it. One time when I ran it there was a glitch with the images when they were first loaded - please let me know if it's a regular thing so I can have a look into it.
I've only tested it in Chrome on Mac OSX (using the above jsFiddle), and on Chrome on Windows XP using the php to generate the page (php -q lb.php > lb.html) with the following input:
4
http://lorempixel.com/60/60
http://lorempixel.com/250/250
My family
http://lorempixel.com/300/300
Other animals
http://lorempixel.com/350/350
Aren't they cute?
http://lorempixel.com/400/400
The bestest picture on the whole internet!!!

which generates the following page source:
<!doctype html><title></title>

I've fixed a few issues that weren't apparent in the jsFiddle testing - the only real issue I'm aware of now is that in Chrome the > button gets quotes put around it because I'm using the q tag. Not sure if the default styles in Firefox, Opera and IE do the same.
I think I've met all the requirements - again let me know if I've missed anything.
Edit:
I've removed all the ul and li stuff because it wasn't necessary, saving about 70 characters.
Here's the code (of the previous version with ul and lis) with some line-breaks and indentation to aid readability, and a Google CDN jQuery link:
<?while($x=fgets(STDIN))$i[]=chop($x)?>
<!doctype html>
<title></title>

<?for(;$l<$i[0]*2;$l+=2)
{
    $a=$i[2+$l];
    $b=$i[3+$l];
    echo"
";
}?>

@PeterTaylor Oops. Swapped the images round.

@PeterTaylor I've fixed a number of bugs and layout issues and compressed the JS correctly now (I think there was a missing ; or two in the previous version).

It's not quite correct. It seems to work fine for small images, but for larger ones it isn't scaling them to fit the viewport. Also the changes have made the HTML invalid - the W3C validator complains about having multiple elements with id=t. Also your example demonstrates that the description needs escaping - look what happens to the description with an apostrophe.

@PeterTaylor I've fixed the multiple id issue at a cost of 3 characters, and the quote escaping at a cost of 26 characters. I thought using max-height and max-width would handle the scaling requirement for me. I won't have time to have a look at that problem for a couple of days now, unfortunately.

source: Stack Exchange

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

sort: votes


text:
Help johnny to solve this Puzzle
Scenario
Little Johnny wants to play with his friends today. But his babysitter won't let him go! After a lot of begging, the heartless nanny gives him her brand new electronic puzzle and says: "If you solve the puzzle then you are free to go". Not being aware of Little Johnny's IT skills, the nanny leaves the kid alone.
Rapidly, Little Johnny sends you an e-mail asking for your help.
The puzzle consists of three hexagons as shown in the figure. Each vertex is painted black or white. Some of them belong to just one hexagon and some of them belong to more than one. Exactly four of them are painted black, and the other nine are white. The goal is to make the shared vertexes black by means of allowed moves: rotating a hexagon 60 degrees clockwise or counter-clockwise.
Can you help Little Johnny?
Input

Input starts with an integer T, the number of puzzles to solve
  (1<=T<=100). T lines follow, each one having 13 binary digits,
  corresponding to the top-down, left to right labeling of the vertexes
  in the puzzle. A '0' means the i-th vertex is painted white, while a
  '1' means it is painted black.

output

For each test case output M on a single line, the minimum number of
  moves required to solve the puzzle. Then print M lines, each one
  describing a move in the following manner: two space separated
  integers H and C, the rotated hexagon (upper left is 0, upper right
  is 1, lower one is 2) and the direction (0 for counter-clockwise, 1
  for clockwise). If there is more than one solution, any will suffice.

Example
Input sample:
1
0000000101011
output sample:
3
2 0
2 0
1 1
source Limit
50000 Bytes

time limit
1 sec

Winning constrain
shortest code with specified time limit wins!
I leave the question for five days to decide winner future answers after five days too welcome

Source. I'm not sure what the general feeling is about posting puzzles from other sites here, but at the very least you should give credit to the originator.

@Gareth I like to share the knowledge with them here ,since the site which i copied was opensource community and i like to get different answers which might help me and other users of this site to think some interesting things ..if i am wrong please forgive me ..and if this is wrong notify me

Is this a code-golf or a code-challenge ? It's currently tagged as both. As for attribution, it's just common courtesy to cite the source of something that you have copied, even if it's in the public domain

@Gareth In this case, revealing the source would also provide links to solutions. I wonder whether this may have motivated the SO not to linking to the source.

@DavidCarraher Possibly, but the solutions there are not required to be golfed whereas this is marked as [code-golf]. Also, if someone is waiting for a way to solve the puzzle they only need to wait for the first answer to arrive here.

Good points to consider.

Similar to http://codegolf.stackexchange.com/questions/586, http://codegolf.stackexchange.com/questions/693 , http://codegolf.stackexchange.com/questions/2478 , http://codegolf.stackexchange.com/questions/3474 , http://codegolf.stackexchange.com/questions/3524 , http://codegolf.stackexchange.com/questions/4084 , http://codegolf.stackexchange.com/questions/4619

Wait, if he's emailing people, then he has access to the internet.  which means that there's absolutely 0 reason to go outside.  ever.

Python, 307 chars
S={'0001001011000':[]}
for i in[0]*7:
 for s in dict(S):
  for m in range(6):S.setdefault(''.join(s[int(x,16)]for x in['2150483769abc','3106428759abc','0326159487abc','0421753986abc','01234587a6c9b','012345976b8ca'][m]),[m]+S[s])
for j in[0]*input():
 L=S[raw_input()];print len(L)
 for m in L:print m/2,m%2

Computes S which is a mapping from a state (a string just like the input) to a list of move numbers which solve the state.  Generates a complete S on startup (only 715 states), then looks up each input and prints the answer.
Moves are implemented using a string of hex digits indicating where each result vertex comes from.
Takes about 0.15 seconds regardless of how big the input is.

715 states seems like such a small number given there are 13 positions and four fillers.  Even with symmetry taken into account.  I'll have to give this more thought.

(13 choose 4) = 715 http://en.wikipedia.org/wiki/Combination.

Yes. I didn't do the math.  Just assumed it was much larger.

I cannot figure out how you managed to tackle such a big problem with so little code!

Mathematica 831
This was a very demanding challenge that took me several days to work out and streamline, far more than a typical challenge.
This graphs all the nodes, where each node corresponds to one arrangement of 4 black hexagon vertices.  Then we find the shortest distance from an input vertex to the solution vertex, {4, 7, 9, 10}.
c = Complement; h = {{7, 9, 6, 3, 1, 4}, {7, 4, 2, 5, 8, 10}, {7, 10, 12, 13, 11, 9}}; i = {4, 7, 9, 10};l = RotateLeft; n = Module; q = Sort; r = RotateRight; s = Flatten;

p[v_, x_, r_] := Block[{d}, n[{d = v \[Intersection] x},If[d != {}, {v, (r[x][[Position[x, #][[1, 1]]]] & /@ d) \[Union] c[v, d], {x /. {h[[1]] -> 0, h[[2]] -> 1, h[[3]] -> 2}, r /. {r -> 0, l -> 1}}}, {}]] /. {{a_, b_, c_} :>   {q@a \[DirectedEdge] q@b, q@a \[DirectedEdge] q@b -> c}}]

o[e_, t_] := Cases[s[Outer[p, {#}, h, {l, r}, 1]~s~2 & /@ e, 1], {a_ \[DirectedEdge] w_, b_} /; \[Not] MemberQ[t, w] :> {a \[DirectedEdge] w, b} ]

m[{g_, j_, _, b_}] :=n[{e, k, u, z},{e, k} = Transpose[o[c @@ g, g[[2]]]];z = Graph[u = Union@Join[e, j], EdgeLabels -> k];{Prepend[g, c[VertexList[z], s[g, 1]]], u, z, Union@Join[k, b]}]

t[j_] :=n[{r, v, y, i = {4, 7, 9, 10}},z = Nest[m, {{{i}, {}}, {}, 1, {}}, 7];v = FindShortestPath[z[[3]], i, Flatten@Position[Characters@j, "1"]];y = Cases[z[[4]], Rule[DirectedEdge[a_, b_], k_] /; MemberQ[v, a] && MemberQ[v, b]];r = Reverse[y[[Cases[Flatten[Position[y, #] & /@ v, 1], {a_, _, 1} :> a]]]] /. (_ \[DirectedEdge] _ -> k_) :>  k ;Grid@Join[{{Length[r]}}, r]]

Usage
t["0100000100011"]

Timing
The search space loads at the when the code is read for the first time.
A solution takes approximately .32 seconds, regardless of the distance from the solution node.
Note: [Intersection], [Union], and [DirectedEdge] are single, dedicated characters in Mathematica.

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


text:
Help Alice in giving candies
Alice is a kindergarden teacher. She wants to give some candies to the children in her class.  All the children sit in a line and each  of them  has a rating score according to his or her usual performance.  Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.
Input
The first line of the input is an integer N, the number of children in Alice's class.
Each of the following N lines contains an integer indicates the rating of each child.

Ouput
Output a single line containing the minimum number of candies Alice must give.

Sample Input
3
1
2
2

Sample Ouput
4

Explanation
The number of candies Alice must give are 1, 2 and 1.

Constraints:
N and the rating  of each child are no larger than 10^5.

Language Restrictions:
C++/Java/C#

The task seems fine, but what's your justification for the language restriction? Such restrictions are generally frowned upon here, unless there is a particular reason why it has to be some particular language. And what's the winning criterion, anyway? Is this code golf?

What precisely does "Alice wants to give at least 1 candy for each child" mean? That the answer cannot be less than N, but that some children can receive 0?

yeah... I smell an interview question what with the language restriction.

@leftaroundabout This appears to have come from Interviewstreet, so I'd imagine the best algorithm would be the goal. How we'd measure that effectively though, I'm not sure. Comp-sci people, any suggestions? Also I'm not sure why the languages have been narrowed down, Interviewstreet appears to take entries in PHP, Python, Ruby, Perl, Haskell...

Unless I am misunderstanding the spec, the test case is wrong. Taking "3" to mean the worst student in the class, he is ensured one candy. The two twos are adjacent and rank lower than the one, and so should get less candy than the one, who must get more than the three. The three, with his one, provides a basis for solving this constraint system giving the trivial distribution [1 2 1 1], (+ 1 2 1 1) => 5 != 4

@rmckenzie I thought that the example was wrong the same as you, but after rereading the question saw that the first number in the input is the number of children in the class.

.... ah languages that need an input length specification.

Ok, so two more questions. Firstly, am I correct to assume that higher number is higher rating, or is rmckenzie correct to assume that lower number is higher rating? Secondly, how is 1 2 1 a solution to children 1 2 2? The 2s are equal, so unless they get the same number of candies one will be jealous of the other.

@PeterTaylor: 2 is not higher than 2.

@KeithRandall That would mean children 2 & 3 should have the same number of candies.

@MrZander: Well, I agree with you in the real world of children, but the OP's spec makes no mention of a restriction if neighboring children are equal in rating.

@KeithRandall, if you take that approach then surely it's invalid input, because "the one with the higher rating" implies existence.

Also a duplicate of: http://stackoverflow.com/questions/11292913/candies-interviewstreet

Java
import java.io.*;
class Alice {
  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(r.readLine());
    int[] ratings = new int[n];
    for (int i = 0; i < n; i++) ratings[i] = Integer.parseInt(r.readLine());
    System.out.println(minCandies(ratings));
  }
  private static int minCandies(int[] ratings) {
    int n = ratings.length;
    int[] reverseRatings = new int[n];
    for (int i = 0; i < n; i++) reverseRatings[n-1-i] = ratings[i];
    int[] forwardRun = findRunLengths(ratings);
    int[] reverseRun = findRunLengths(reverseRatings);
    int sum = 0;
    for (int i = 0; i < n; i++) sum += Math.max(forwardRun[i], reverseRun[n-1-i]);
    return sum;
  }
  private static int[] findRunLengths(int[] ratings) {
    int lastInRun = -1;
    int runLength = 0;
    int[] runs = new int[ratings.length];
    for (int i = 0; i < ratings.length; i++) {
      int r = ratings[i];
      if (r > lastInRun) {
        lastInRun = r;
        runLength++;
      } else {
        runLength = 1;
        lastInRun = r;
      }
      runs[i] = runLength;
    }
    return runs;
  }
}

Uses the fact that a kid will need C candies iff there is a strictly increasing run of C ratings in either direction that ends at that kid.  Just walks the array in each direction looking for runs and keeps the length of the run found ending at each kid.  O(n) time.

Not that my solution is correct for this case, but it fails the input "5\n3\n2\n1\n\4\n4\n", being the ordering 3, 2, 1, 4, 4. In this case, 3 gets 1, 2 gets 2, 1 gets 3, and the fours get one each for a total of 8. Your program claims that three is sufficient in this case.

@rmckenzie: first, I'm printing the max number any kid gets, not the total.  I'll have to fix that.  But also I'm treating higher rankings as better, you are doing the opposite.

If you do that then the only provided test case is incorrect. The twos rank higher than the one, giving the candy count [1 2 2] for a total of five, not the four given in the spec.

@rmckenzie: no, the kids can be satisfied with [1 2 1].

Oh yeah... OP never came back on that one. Yay bad spec!

OK, fixed to print the total candies needed across all kids.

+1 Hooray for breaking the rules! ... which clearly weren't justified.

Clojure - 2495
(ns alice)

(defn invert-derivative [d]
  (cond (= d <=) >=
        :else <= ))

(defn chunk-by-derivative [ivec]
  (loop [prev-seqs []
         prev-els  [(first ivec)]
         cur-derivative (if (<= (first ivec) (second ivec)) <= >=)
         remainder (rest ivec)]
    (let [cursor (first remainder)
          holds-trend (cur-derivative (last prev-els) (if (nil? cursor) 0 cursor))]
      (cond (empty? remainder)
                (conj prev-seqs prev-els)

            holds-trend
                (recur prev-seqs
                       (conj prev-els cursor)
                       cur-derivative
                       (rest remainder))
            :else
                (recur (conj prev-seqs prev-els)
                       [cursor]
                       (invert-derivative cur-derivative)
                       (rest remainder))))))

(defn candy-delta [ivec]
    (reduce (fn [pr c]
              (let [{:keys [value candies] :as previous
                     :or {:value 0 :candies 1}} (last pr)]
                (conj pr
                      (cond (empty? pr) {:candies 1 :value c}
                            (= value c)    previous
                            (> value c)    {:value c :candies (inc candies)}
                            (< value c)    {:value c :candies (dec candies)}))))
            [] ivec))

(defn simple-min-candy [ivec]
  (let [m (apply min (map #(:candies %1) ivec))]
    (if (> 1 m)
      (map #(assoc %1 :candies (+ (:candies %1) (- 1 m))) ivec)
      ivec)))

(defn subseq-concat [s1 s2]
  (let [s1-l-candies (:candies (last s1))
        s1-l-value   (:value   (last s1))

        s2-f-candies (:candies (first s2))
        s2-f-value   (:value   (first s2))]
    (cond (and (> s1-l-value   s2-f-value)
               (< s1-l-candies s2-f-candies))
              (recur (let [delta (- s2-f-candies s1-l-candies)]
                       (map #(assoc %1 :candies (+ delta (:candies %1))) s1))
                     s2)
          :else (concat s1 s2))))

(defn join-subseqs [subseqs]
  (if (<= 2 (count subseqs))
    (reduce subseq-concat
            (first subseqs)
            (rest subseqs))
    (first subseqs)))

(defn pipeline [v]
  (->> v
      (chunk-by-derivative)
      (map candy-delta)
      (map simple-min-candy)
      (join-subseqs)
      (map #(:candies %1))
      (apply +)
      (println)))

(defn -main [& args]
  (let
    [line-count (read)
     v (map (fn [x] (read)) (range line-count))]
    (pipeline v)))

(-main)

Assumptions

That the children numbered "2" rank below the child ranked "1"
That two adjacent children of equal number should receive the same number of candies. Easy to change but until the OP clarifies the spec I'm keeping it that way.

General Algorithm
This solution is based on problem decomposition and composition of functions via the ->> operator.
The approach is to "chunk" the ordering of students into sub-orders which are increasing or decreasing. Using the simple approach outlined below which is correct in these cases, a partial candy count can be generated for each of these subsequences which is absolutely minimum for that sequence as argued below. Subsequences can then be joined by comparing the last value of the sequence to concatenate to and the first value of the sequence to be added, and if necessary adding a constant C to all elements of the sequence to be added to in order to ensure that the rank-based order property between children is maintained.
This approach is correct for the multi-delta case as it will consider the ordering [3 2 1 4 4] to be the two sequences [3 2 1] which is strictly increasing and receive respectively [1 2 3] pieces of candy and the sequence [4 4] which will receive the candy [1 1]. The concatenation of [1 2 3] and [1 1] respects the order property that child 1 receive more candy than any child 4 so the order is correct.
Algorithm for individual derivative constant sequences
This algorithm first generates a series of pairs [d, v] starting with [1, (first input value)] where the first element is the candy count of that child, being +1, +0, -1 from the last child. Note that these are ordered by the input (or seating) order, and thus correctly represent the minimum correct candy change between any pair of consecutive children [c, c'].
As the goal is to produce the number of total candies required, the first element of each pair is then taken to create a new sequence of numbers representing the candy count taken in comparison to the candy count of the child who happened to be seated first.
The last step then is to compute the final number of candies with regard to the child seated first. There are three cases here, all of which can be identified by the minimum number of candies given out to any one child.

The minimum is less than one. As all children must receive one or more candies all the children must gain K candies where K is 1 - (min chindren), thus guaranteeing that the bottom child receives exactly one candy.
The minimum is greater than one. An unreachable case, as the worst possible cases in terms of candy consumed are the increasing and decreasing sorts by rank. The decreasing sort would be handled by case 1, and the increasing sort would have a minimum value of 1 and require no further analysis.
The case where the minimum is one, so no further processing is required.

Correctness for all strictly increasing cases
For any strictly increasing ordering of children (c0 c1 c2 ... cn) the ith [counting from 0th] child will receive i + 1 pieces of candy. Consequently increasing the count of candy by one in the case of an increase in rank from [c -> c'] is necessarily correct.
Correctness for all strictly decreasing cases
By a similar argument, for any case where [c -> c'] is always decrease the subtraction of one candy from each child to the next is the minimum possible delta. The first biasing case then kicks in to ensure that the result guarantees one candy per child.
Correctness for all mixed cases
Any mixed sequence can be expressed as the composite of at least two sequences with different trends (being decreasing or increasing). By breaking such composite sequences into the trend-based subsequences, application of the known correct increasing/decreasing algorithm is trivially correct for all subsequences and a join of all subsequences which guarantees that the rank order property is preserved ensures that all resulting sequences are also minimal.
Test Cases
3
1
2
2

=> 4 being [2 1 1]
7
1
2
3
4
3
4
5

=> 20 being [5 4 3 2 3 2 1]
8
1
2
1
2
1
2
1
2

=> 12 being [2 1 2 1 2 1 2 1]
Bugs
If there are any please smack me upside the head for being a cocky jerk. This composition of functions should be generally correct but I do not doubt my capacity for overlooking my own errors.


text:
How can I make this program smaller?
I am trying my hand at writing super small programs. I wrote a simple "tree" display program for showing a graphical representation of a folder hierarchy. I have made it small in all the ways I can think of. I was just wondering if you guys had more creative ways to "minify" it further. Here is the small version as well as a human-readable version.
import os,os.path as p
def w(c,d,s):
    a=os.listdir(c);s=s+'|';i=0
    for f in a:
        print s+'--'+f;j=p.join(c,f);
        if p.isdir(j):w(j,d+1,s[:-i==len(a)-1]+'  '*(d+1));i=i+1
def t(c):print c;w(c,0,'')
t(p.curdir)

That's a total of 236 bytes
import os

def treeWrap(curdir,depth,pipeStr):
    files = os.listdir(curdir)
    pipeStr = pipeStr + '|'
    for f in files:
        print pipeStr + '--' + f
        if os.path.isdir(os.path.join(curdir,f)):
            dir = os.path.join(curdir,f)
            if files.index(f) == (len(files)-1):
                treeWrap(dir,depth+1,pipeStr[:-1] + '  '*(depth+1))
            else:
                treeWrap(dir,depth+1,pipeStr + '  '*(depth+1))

def tree(curdir):
    print curdir
    treeWrap(curdir,0,'')

tree(os.path.curdir)

Oh, in addition, does anyone know how I can use the unicode ├,└,─ in this program? Whenever I use them they appear as garbage in the console and the idle interpreter.

A bunch of generic minifying python techniques are here: http://codegolf.stackexchange.com/questions/54/tips-for-golfing-in-python

p=os.path is 3 characters shorter than os.path as p.

Probably belongs on http://codereview.stackexchange.com ?

I believe you got advised to try this here on Stack Overflow, but the person who suggested that wasn't entirely familiar with our FAQ. Each "question" here is expected to pose a game or challenge with a well defined winning criteria and enough flexibility to be fun for participants. This is not a site for general question (with the special exception of the "hints" questions).

There is a bug with your minified version: s[:-0] gives you the empty string, not the complete string as you anticipate with s[:-i==len(a)-1]. To rectify this, you will need to either ignore preceding bars or calculate the a little more thoroughly. The shorter version would be to ignore preceding bars and not worry about passing spacing to further recursions. Since it permits the removal of several variables, I worked your code to do this
Your tree function is only called once, I removed it.
s=s+'|' and i=i+1 can be collapsed into s+='|' and i+=1
os.path as p can become p=os.path (Thanks James)
p.join(c,f) can become c+'/'+f (Thanks beary605)
New version:
import os,p=os.path
def w(c,d):
    for f in os.listdir(c):
        print '  '*(d+1)+'|--'+f;j=c+'/'+f
        if p.isdir(j): w(j,d+1)
z=p.curdir;print z;w(p.curdir,0)

If you really wanted to go crazy, you can make put this all on one line and get it down to 143 bytes (on linux)
import os,p=os.path
def w(c,d):
 for f in os.listdir(c):print'  '*(d+1)+'|--'+f;j=c+'/'+f;w(j,d+1)if p.isdir(j)else 0
z=p.curdir;print z;w(z,0)

Remove unecessary whitespace (5chars), and also replace p.join(c,f) with c+'/'+f (4chars): for f in os.listdir(c):print'  '*(d+1)+'|--'+f;j=c+'/'+f;w(j,d+1)if p.isdir(j)else 0

@beary605 Will c+'/'+f yield the same result as p.join(c,f) on a windows box?

It will, does it not on Linux?

The docs say os.path.join uses os.sep which "is '/' for POSIX and '\\' for Windows".

It works in Windows. Windows is pretty lenient with their file paths.


text:
Lego gear ratios
I'm building a giant lego robot and I need to generate some particular gear ratios using a set of gears.  I have lots of gears with the common lego gear sizes: 8, 16, 24, or 40 teeth.  Write a program I can use where I input a gearing ratio and the program tells me what combination of gears I should use to get the requested ratio.
The input ratio will be specified on standard input (or your language's equivalent) with two integers separated by a colon.  A ratio of a:b means that the output shaft should turn a/b times as fast as the input shaft.
The output to standard output should be a single line containing a space-separated list of gear ratios, in the form of x:y where x is the size of the gear on the input shaft and y is the size of the gear on the output shaft.  You must use the minimum possible number of gears for the given ratio.  Each x and y must be one of 8,16,24,40.
examples:
1:5 -> 8:40
10:1 -> 40:8 16:8
9:4 -> 24:16 24:16
7:1 -> IMPOSSIBLE
7:7 ->
6:15 -> 16:40

If the desired gear ratio is impossible, print "IMPOSSIBLE".  If no gears are required, print the empty string.
This is code golf, shortest answer wins.

Aren't the ratio of teeth inversely proportional to the angular velocity?  So, for example if the desired input output velocity is 1:5, shouldn't the ratio be 40:8 instead of 8:40?  Or is the left-hand ratio the effective gear teeth to actual gear teeth ratio you want?

Interesting question... 1:5 -> 8:40 and 10:1 -> 40:8 make sense but the others not so much.

@DavidCarraher: I guess you can define it either way.  I tried to be internally consistent.  1:5 means the output shaft turns 5 times slower, and an 8 tooth gear on the input and a 40 tooth gear on the output makes that happen.

@MikeDtrick: well, 10:1 -> 40:8 16:8, not what you said.  What about the others confuses you?  9:4 is implemented doing 3:2 twice.  3:2 is implemented using 24:16.

If one gear has 40 teeth and the other has 8 teeth, isn't the ratio 5:1?  The second example is confusing me... 7:7 yields impossible, correct?

@MikeDtrick: Yes to your first question.  To get 10:1 you can do 5:1 (using 40 teeth / 8 teeth) and then 2:1 (using 16 teeth / 8 teeth).  7:7 is the same as 1:1, so it requires no gears to implement.

Isn't 7:1 possible with infinitely many gears... ?

Python - 204
Ok, I'll go first:
def p(n,a=[1]*9):
 n=int(n)
 for i in(2,3,5):
    while n%i<1:n/=i;a=[i]+a
 return a,n
(x,i),(y,j)=map(p,raw_input().split(':'))
print[' '.join(`a*8`+':'+`b*8`for a,b in zip(x,y)if a!=b),'IMPOSSIBLE'][i!=j]

edit:

To 'optimize' the output, this can be added before the print statement,
for e in x:
 if e in y:x.remove(e);y.remove(e)

bringing the total up to 266 characters, I believe.

<1 can replace ==0. Also, if b:a=...return a can be return b and...or a.

Doesn't work for, e.g., 23:12.

Well spotted. It goes through since 12 is dividable. Adding elif i!=1:return[] to the original solves the problem but introduces another one. $ python gears.py <<< 21:28 => 24:16.. I'm gonna look into it. Looks like the problem wasn't so simple after all :D I Think the code has to be even longer, or I need another approach.

There you go; I think this one works as expected. Even made it smaller :)

Looks pretty good, but it isn't optimal.  6:15 can be done with 16:40 but your code returns 24:40 16:24.

Now with 'optimization' ;)

Perl - 310 306 294 288 272
I'm a little rusty with perl and never did a code-golf... but no excuses. Char-count is without line-breaks. Using perl v5.14.2 .
($v,$n)=<>=~/(.+):(.+)/;
($x,$y)=($v,$n);($x,$y)=($y,$x%$y)while$y;
sub f{$p=shift;$p/=$x;for(5,3,2){
while(!($p%$_)){$p/=$_;push@_,$_*8}}
$o="IMPOSSIBLE"if$p!=1;
@_}
@a=f($v);@b=f($n);
if(!$o){for(0..($#b>$#a?$#b:$#a)){
$a[$_]||=8;
$b[$_]||=8;
push@_,"$a[$_]:$b[$_]"}}
print"$o@_\n"

I'm looking forward to critics and hints. It's not so easy to find tips and tricks for code-golf (in perl).

You can save 9 chars by removing $1:$2 -> , it is not required in the output.

Oh, I misread the spec. Thanks.

You can reduce statements like $a[$_]=8 if!$a[$_]; to $a[$_]||=8;

Newlines count as one character.

The first line can be abbreviated to ($v,$n)=split/:|\s/,<>; (untested).

= associates rightward, so you can fold the first two lines together as ($x,$y)=($v,$n)=.... And you should I think be able to skip the sigils.

@Timtech The newlines are only there for human readability.

Okay. +1 btw :)

C, 246 216 213 bytes
In a (futile) attempt to beat my own Prolog solution, I completely rewrote the C solution.
b,c,d;f(a,b,p){while(c=a%5?a%3?a%2?1:2:3:5,d=b%5?b%3?b%2?1:2:3:5,c*d>1)c<2|b%c?d<2|a%d?p&&printf("%d:%d ",8*c,8*d):(c=d):(d=c),a/=c,b/=d;c=a-b;}main(a){scanf("%d:%d",&a,&b);f(a,b,0);c?puts("IMPOSSIBLE"):f(a,b,1);}

My original C solution (246 bytes):
#define f(c,d) for(;a%d<1;a/=d)c++;for(;b%d<1;b/=d)c--;
b,x,y,z;main(a){scanf("%d:%d",&a,&b);f(x,2)f(y,3)f(z,5)if(a-b)puts("IMPOSSIBLE");else
while((a=x>0?--x,2:y>0?--y,3:z>0?--z,5:1)-(b=x<0?++x,2:y<0?++y,3:z<0?++z,5:1))printf("%d:%d ",a*8,b*8);}

It was a nice exercise to prove it can be done without building lists.

swi-prolog, 324 250 248 204 bytes
Prolog does pretty well at solving a problem like this.
m(P):-(g(P,L),!;L='IMPOSSIBLE'),write(L).
g(A:A,''):-!.
g(A:B,L):-A/C/X,C>1,B/C/Y,!,g(X:Y,L);A/C/X,!,B/D/Y,C*D>1,g(X:Y,T),format(atom(L),'~D:~D ~a',[C*8,D*8,T]).
X/Y/Z:-(Y=5;Y=3;Y=2;Y=1),Z is X//Y,Y*Z>=X.

Input is passed as a term parameter to predicate m. Output is written to stdout. Sorry about the trailing 'true'; that's just the interpreter's way of letting me know everything was fine.
?- m(54:20).
24:40 24:16 24:8
true.

?- m(7:7).
true.

?- m(7:1).
IMPOSSIBLE
true.

Pyth, 101 bytes
D'HJH=Y[)VP30W!%JN=/JN=Y+NY))R,YJ;IneKhm'vdcz\:J"IMPOSSIBLE").?V.t,.-Y.-hK=J.-hKYJ1In.*Npj\:m*8d_Np\

An implementation of @daniero' python answer but semi-optimised for Pyth.
D'H                               - Define a function (') which takes an argument, H.
   JH                             - J = H (H can't be changed in the function)
     =Y[)                         - Y = []
         V                        - For N in ...
          P30                     - Prime factors of 30 (2,3,5)
             W!%JN                - While not J%N
                  =/JN            - J /= N
                      =Y+NY       - Y = N + Y
                           ))R,YJ - To start of function, return [Y,J]

ENDFUNCTION

If
         cz\:  - Split the input by the ':'
     m'vd      - ['(eval(d)) for d in ^]
   Kh          - Set K to the first element of the map (before the :)
  e            - The second returned value
             J - The second returned value after the : (The variables are globals)
 n             - Are not equal

Then
"IMPOSSIBLE" - Print "IMPOSSIBLE"

Else
V                                      - For N in
 .t                1                   - transpose, padded with 1's
             .-hKY                     - 1st function first return - 2nd function first return
           =J                          - Set this to J
       .-hK                            - 1st function first return - ^
    .-Y                                - 2nd function first return - ^
   ,              J                    - [^, J]
                                         (Effectively XOR the 2 lists with each other)
                    I                  - If
                     n.*N              - __ne__(*N) (if n[0]!=n[1])
                         pj\:m*8d_N    - print ":".join([`d*8` for d in reversed(N)])
                                   p\  - print a space seperator

Try it here
Or test every case

ES6, 230 bytes
x=>([a,b]=x.split`:`,f=(x,y)=>y?f(y,x%y):x,g=f(a,b),d=[],a/=g,f=x=>{while(!(a%x))a/=x,d.push(x*8)},[5,3,2].map(f),c=d,d=[],a*=b/g,[5,3,2].map(f),a>1?'IMPOSSIBLE':(c.length<d.length?d:c).map((_,i)=>(c[i]||8)+':'+(d[i]||8)).join` `)

One of my longest golfs, so I must have done something wrong... Ungolfed:
x => {
    [a, b] = x.split(":");
    f = (x, y) => y ? f(y, x % y) : x; // GCD
    g = f(a, b);
    f = x => {
        r = [];
        while (!(x % 5)) { x /= 5; r.push(5); }
        while (!(x % 3)) { x /= 3; r.push(3); }
        while (!(x % 2)) { x /= 2; r.push(2); }
        if (x > 1) throw "IMPOSSIBLE!";
        return r;
    }
    c = f(a);
    d = f(b);
    r = [];
    for (i = 0; c[i] || d[i]; i++) {
        if (!c[i]) c[i] = 8;
        if (!d[i]) d[i] = 8;
        r[i] = c[i] + ":" + d[i];
    }
    return r.join(" ");
}

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


text:
The GolfScript Meta Par Hole
Seem like GolfScript wins all of these. So you can't beat them, join them.
Write an Self-Contained Golfscript Interpreter
I'm using the definition of self-contained to mean, a single program:- So no passing the buck to some external program to do the work for you.

Test Cases:
Strings and blocks are represented as lists of ASCII codes. Types are not checked with these tests, but should be right anyway.
test("[50] [60]+", [[50, 60]]);
test("{a} {b}+", [[97, 32, 98]]);
test("'a' 'b'+", [[97, 98]]);

test("' ' 0+", [[32, 48]]);
test("' ' [50]+", [[32, 50]]);

test("{a} 0+", [[97, 32, 48]]);
test("{a} [50]+", [[97, 32, 53, 48]]);

test("5 ~", [-6]);
test('"1 2+"~', [3]);
test('{1 2+}~', [3]);
test('[1 2 3]~', [1, 2, 3]);

test('1`', [[49]]);
test("[1 [2] 'asdf']`", [[91, 49, 32, 91, 50, 93, 32, 34, 97, 115, 100, 102, 34, 93]]);
test('"1"`', [[34, 49, 34]]);
test("{1}`", [[123, 49, 125]]);

test("0!", [1]);
test("[]!", [1]);
test("{}!", [1]);
test("''!", [1]);

test("5!", [0]);
test("[[]]!", [0]);
test("{{}}!", [0]);
test("'asdf'!", [0]);

test("1 2 3 4 @", [1, 3, 4, 2]);

test("1 # 2", [1]);

test("1 2 3 4 5 1 $", [1, 2, 3, 4, 5, 4]);
test("'asdf' $", [[97, 100, 102, 115]]);
test("[5 4 3 1 2]{-1*}$", [[5, 4, 3, 2, 1]]);

test("5 7 +", [12]);
test("'a'{b}+", [[97, 32, 98]]);
test("[1 2 3][4 5]+", [[1, 2, 3, 4, 5]]);

test("1 2-3+", [1, -1]);
test("1 2 -3+", [1, -1]);
test("1 2- 3+", [2]);
test("[5 2 5 4 1 1][1 2]-", [[5, 5, 4]]);

test("2 4*", [8]);
test("2 {2*} 5*", [64]);
test("[1 2 3]2*", [[1, 2, 3, 1, 2, 3]]);
test("3'asdf'*", [[97,115,100,102,97,115,100,102,97,115,100,102]]);

test("[1 2 3]' '*", [[49, 32, 50, 32, 51]]);
test("[1 2 3][4]*", [[1,4,2,4,3]]);
test("'asdf'' '*", [[97,32,115,32,100,32,102]]);
test("[1 [2] [3 [4 [5]]]]' '*", [[49, 32, 2, 32, 3, 4, 5]]);
test("[1 [2] [3 [4 [5]]]][6 7]*", [[1, 6, 7, 2, 6, 7, 3, [4, [5]]]]);

test("[1 2 3 4]{+}*", [10]);
test("'asdf'{+}*", [414]);

test("7 3 /", [2]);
test("[1 2 3 4 2 3 5][2 3]/", [[[1], [4], [5]]]);
test("[1 2 3 4 5] 2/", [[[1, 2], [3, 4], [5]]]);

test("0 1 {10<} { .@+ } /", [8, [1, 1, 2, 3, 5, 8]]);
test("[1 2 3]{1+}/", [2, 3, 4]);

test("7 3 %", [1]);

test("'assdfs' 's'%", [[[97], [100, 102]]]);
test("'assdfs' 's'/", [[[97], [], [100, 102], []]]);

test("[1 2 3 4 5] 2%", [[1, 3, 5]]);
test("[1 2 3 4 5] -1%", [[5, 4, 3, 2, 1]]);
test("[1 2 3] {1+}%", [[2, 3, 4]]);

test("5 3 |", [7]);
test("[5 5 1] [1 3] |", [[5, 1, 3]]);

test("5 3 &", [1]);
test("[1 1 2 2][1 3]&", [[1]]);

test("5 3 ^", [6]);
test("[1 1 2 2][1 3]^", [[2, 3]]);

test("1 2 [\\]", [[2, 1]]);

test("1 2 3 \\", [1, 3, 2]);
test("1 2 3; ", [1, 2]);

test("3 4 <", [1]);
test('"asdf" "asdg" <', [1]);
test("[1 2 3] 2 <", [[1, 2]]);
test("{asdf} -1 <", [[97, 115, 100]]);

test("3 4 >", [0]);
test('"asdf" "asdg" >', [0]);
test("[1 2 3] 2 >", [[3]]);
test("{asdf} -1 >", [[102]]);

test("3 4 =", [0]);
test('"asdf" "asdg" =', [0]);
test("[1 2 3] 2 =", [3]);
test("{asdf} -1 =", [102]);

test("3,", [[0,1,2]]);
test("10,,", [10]);
test("10,{3%},", [[1, 2, 4, 5, 7, 8]]);

test("1 2 .", [1,2,2]);

test("2 8?", [256]);
test(" 5 [4 3 5 1] ?", [2]);
test(" 6 [4 3 5 1] ?", [-1]);

test("[1 2 3 4 5 6] {.* 20>} ?", [5]);

test("5(", [4]);
test("[1 2 3](", [[2, 3], 1]);

test("5)", [6]);
test("[1 2 3])", [[1, 2], 3]);

test("5 {1 0/} or", [5]);
test("5 {1 1+} and", [2]);
test("0 [3] xor", [[3]]);
test("2 [3] xor", [0]);

test("5{1-..}do", [4, 3, 2, 1, 0, 0]);
test("5{.}{1-.}while", [4, 3, 2, 1, 0, 0]);
test("5{.}{1-.}until", [5]);

test("1 2 3 if", [2]);
test("0 2 {1.} if", [1, 1]);

test("[[1 2 3][4 5 6][7 8 9]]zip", [[[1, 4, 7], [2, 5, 8], [3, 6, 9]]]);

test("[1 1 0] 2 base", [6]);
test("6 2 base", [[1, 1, 0]]);

Warning to anyone who would try this: it's a very big task if you're not using a language closely related to Ruby.

@PeterTaylor Where would you say the best documentation is for someone attempting this task? Is it the golfscript.com site, or would it be better to just dig into the golfscript.rb source itself?

Would you get extra points for writing it in Golfscript?

@Gareth, http://www.golfscript.com/golfscript/builtin.html and the source.

You know, for a task this complex the question-asker really ought to post a good set of test cases...

Do we have to support ruby's string evaluation, like "The time is #{Time.now}" ? How about arbitrary precision numbers ?

Ruby, 5490 bytes
Well, I can golf the GolfScript interpreter from 8283 bytes down to 5490 ...
$m=[];class G;def g;$k<<self;end;def v;@v;end
'+-|&^'.each_byte{|i|eval'def%c(r);if r.class!=self.class
a,b=u(r);a%c b;else;f(@v%c r.v);end;end'%([i]*3)}
def==(r);@v==r.v;end;def eql?(r);@v==r.v;end;def hash
@v.hash;end;def<=>(r);@v<=>r.v;end;end;class H<G;def
initialize(i);@v=case i;when true then 1;when false then 0
else;i;end;end;def f(a);H.new(a);end
def t;J.new(@v.to_s);end;def to_int#for pack
@v;end;def s;t;end;def N;0;end;def u(b);[if b.class==I
I.new([self]);elsif b.class==J;t;else#K
t.to_s.w;end,b];end;def~;H.new(~@v);end;def R;H.new(@v==0)
end;'*/%<>'.each_byte{|i|eval'def%c(r);H.new(@v%c r.v)
end'%[i,i]};def E(r);H.new(@v==r.v);end;def q(b)
H.new(@v**b.v);end;def B(a);if I===a;r=0;a.v.each{|i|r*=@v
r+=i.v};H.new(r);else;i=a.v.abs;r=[];while i!=0;r.unshift
H.new(i%@v);i/=@v;end;I.new(r);end;end;def n;H.new(@v-1);end;def
p;H.new(@v+1);end;end;class I<G;def initialize(a);@v=a;end;def
f(a);I.new(a);end;def t;@v.inject(J.new("")){|s,i|s+i.t};end
def F#maybe name to_a ?
I.new(@v.inject([]){|s,i|s+case i;when J then i.v;when H then[i]
when I then i.F.v;when K then i.v;end});end;def s
J.new('[')+I.new(@v.map{|i|i.s})*J.new(' ')+J.new(']');end;def
g;$k<<self;end;def N;1;end;def u(b);if b.class==H
b.u(self).reverse;elsif b.class==J;[J.new(self),b];else
[(self*J.new(' ')).to_s.w,b];end;end;def n;[f(@v[1..-1]),@v[0]]
end;def p;[f(@v[0..-2]),@v[-1]];end;def*(b);if b.class==H
f(@v*b.v);else;return b*self if self.class==J&&b.class==I;return
self/H.new(1)*b if self.class==J;return;b.f([])if@v.size<1
r=@v.first;r,x=r.u(b)if r.class!=b.class#for size 1
@v[1..-1].each{|i|r=r+b+i};r;end;end;def/(b);if b.class==H
r=[];a=b.v<0 ?@v.reverse: @v;i=-b=b.v.abs
r<<f(a[i,b])while(i+=b)<a.size;I.new(r);else;r=[];i=b.f([])
j=0;while j<@v.size;if@v[j,b.v.size]==b.v;r<<i;i=b.f([])
j+=b.v.size;else;i.v<<@v[j];j+=1;end;end;r<<i;I.new(r);end;end
def%(b);if b.class==H;b=b.v
f((0..(@v.size-1)/b.abs).inject([]){|s,i|s<<@v[b<0 ?i*b-1:i*b]})
else;self/b-I.new([I.new([])]);end;end;def R;H.new(@v.empty?)
end;def q(b);H.new(@v.index(b)||-1);end;def E(b);b.class==H ?
@v[b.v] : H.new(@v==b.v);end;def<(b);b.class==H ? f(@v[0..b.v]):
H.new(@v<b.v);end;def>(b);b.class==H ?
f(@v[[b.v,-@v.size].max..-1]) : H.new(@v>b.v);end;def sort
f(@v.sort);end;def T;r=[];@v.size.times{|x|@v[x].v.size.times{|y|
(r[y]||=@v[0].f([])).v<<@v[x].v[y]}};I.new(r);end;def~;v;end;end
class J<I;def initialize(a);@v=case a;when String then
a.unpack('C*').map{|i|H.new(i)};when Array then a;when I then
a.F.v;end;end;def f(a);J.new(a);end;def t;self;end;def s
f(to_s.inspect);end;def to_s;@v.pack('C*');end;def N;2;end
def u(b);b.class==K ? [to_s.w,b]:b.u(t).reverse;end;def q(b)
if b.class==J;H.new(to_s.index(b.to_s)||-1);elsif b.class==I
b.q(t);else;H.new(@v.index(b)||-1);end;end;def~;to_s.w.g;nil;end
end;class K<I;def initialize(a,b=nil);@v=J.new(b).v
@n=eval("lambda{#{a}}");end;def g;@n.call;end;def f(b)
J.new(b).to_s.w;end;def N;3;end;def t;J.new("{"+J.new(@v).to_s+"}")
end;def s;t;end;def u(b);b.u(self).reverse;end;def+(b);if
b.class!=self.class;a,b=u(b);a+b;else
J.new(@v+J.new(" ").v+b.v).to_s.w;end;end;def*(b);if b.class==H
b.v.times{g};else;z b.v.first;(b.v[1..-1]||[]).each{|i|$k<<i;g}
end;nil;end;def/(b);if b.class==I||b.class==J;b.v.each{|i|z i;g}
nil;else#unfold
r=[];loop{$k<<$k.last;g;break if y.R.v!=0;r<<$k.last;b.g}
y;I.new(r);end;end;def%(b);r=[];b.v.each{|i|m=$k.size
$k<<i;g;r.concat($k.slice!(m..$k.size))};r=I.new(r)
J==b.class ? J.new(r):r;end;def~;g;nil;end
def sort;a=y;a.f(a.v.sort_by{|i|z i;g;y});end
def C(a);a.f(a.v.C{|i|z i;g;y.R.v==0});end
def q(b);b.v.find{|i|z i;g;y.R.v==0};end;end
class NilClass;def g;end;end
class Array;def^(r);self-r|r-self;end;include Comparable;end
e=gets(nil)||'';Q=$stdin;$_=Q.isatty ? '':Q.read;$k=[J.new($_)]
$l={};def x(name,v=nil);eval"#{s="$_#{$l[name]||=$l.size}"}||=v"
s;end;$j=0
class String;def W;K.new(self);end;def X;('a=y;'+self).W;end
def Y;('b=y;a=y;'+self).W;end;def Z;('c=y;b=y;a=y;'+self).W;end
def o;('b=y;a=y;a,b=b,a if a.N<b.N;'+self).W;end;def
w(a=scan(/[a-zA-Z_][a-zA-Z0-9_]*|'(?:\\.|[^'])*'?|"(?:\\.|[^"])*"?|-?[0-9]+|#[^\n\r]*|./m))
b=a.dup;c="";while t=a.slice!(0);c<<case t
when"{"then"$k<<"+x("{#{$j+=1}",w(a));when"}"then break
when":"then x(a.slice!(0))+"=$k.last"
when/^["']/ then x(t,J.new(eval(t)))+".g"
when/^-?[0-9]+/ then x(t,H.new(t.to_i))+".g"
else;x(t)+".g";end+"\n";end
d=b[0,b.size-a.size-(t=="}"?1:0)]*"";K.new(c,d);end;end
def y;($m.size-1).downto(0){|i|break if$m[i]<$k.size;$m[i]-=1}
$k.pop;end;def z a;$k.push(*a)if a;end
x'[','$m<<$k.size'.W;x']','z I.new($k.slice!(($m.pop||0)..-1))'.W
x'~','z~a'.X;x'`','z a.s'.X;x';',''.X;x'.','$k<<a<<a'.X
x'\\','$k<<b<<a'.Y;x'@','$k<<b<<c<<a'.Z;x'+','z a+b'.Y
x'-','z a-b'.Y;x'|','z a|b'.Y;x'&','z a&b'.Y;x'^','z a^b'.Y
x'*','z a*b'.o;x'/','z a/b'.o;x'%','z a%b'.o;x'=','z a.E(b)'.o
x'<','z a<b'.o;x'>','z a>b'.o;x'!','z a.R'.X
x'?','z a.q(b)'.o;x'$','z(a.class==H ? $k[~a.v]:a.sort)'.X
x',','z case a;when H then I.new([*0...a.v].map{|i|H.new(i)})
when K then a.C(y);when I then H.new(a.v.size);end'.X
x')','z a.p'.X;x'(','z a.n'.X
x'rand','z H.new(rand([1,a.v].max))'.X;x'abs','z H.new(a.v.abs)'.X
x'print','print a.t'.X;x'if',"#{x'!'}.g;(y.v==0?a:b).g".Y
x'do',"loop{a.g;#{x'!'}.g;break if y.v!=0}".X
x'while',"loop{a.g;#{x'!'}.g;break if y.v!=0;b.g}".Y
x'until',"loop{a.g;#{x'!'}.g;break if y.v==0;b.g}".Y
x'zip','z a.T'.X;x'base','z b.B(a)'.Y
'"\n":n;{print n print}:puts;{`puts}:p;{1$if}:and;{1$\if}:or;{\!!{!}*}:xor;'.w.g
e.w.g;z I.new($k);'puts'.w.g

Javascript, 2227 bytes
@Peter Taylor: Challenge Accepted!
_='S=b9b?b^3?"{"+)+"}":\'"\'+)+\'"\':"["+b6SB" ")+"]":""+b};$=b||!b99b:[b]b6$B""L;M=b9$(bb+""};A=b?(gb.charCodeAt(0)A(b1))v=g,v=3,g,v};C=b9(k=b6Ck=b,kb};a=g,s,O,r=Wj,uX,d,c,i,yPb=(b?$(bb+"").match(/\'(.|[^\'])*\'|"(.|[^"])*"|-?\\d+|\\043[^\\n]*|[a-z_]\\w*|./imgFi=y=0;z=b[i++];)"{"Yz?!y++Zk=iy?"}"Yz!--yZe=A(bk,i-1B""))e=4\'"\'YzQ?A(eval(z.replace("\\n","n")))"\'"YzQ?A(z1,-1).replace(/(|\')/g,"$1"))":"Yz?r[b[i++]]=(d=s[s-1])^4?S(dd:r[z]?r[z]z+"."-0.1?eval(z)eval("//~t;t98?ts=st~t\\140A(S(G)))//[O.uns]JEt,u@`vEuX,v%`I!u)t%u!tPt3?[32]:[]Xu+tV-5!~tc)RcL# q-t/`I!u)Math.floot/u)!tPv=0;j%tY0ZvRvv,vvcdvLu^4Pp=1 ITPFd;\'.\'u;)ds[s-1]tGdL#{D;HL//*7I!t)q*t!uPFd;u--;)T?td=dCUd=8;T||dL8^4P!u8Zu6M)6A)d=dC(j?t:[]cd=8;GdL#{q.)HL//zipt;Fv=c;v--;)!d[v]Zd[v]d[v]c[v]?7IT)HG)Zcu# t9tuMath.pow(uX)$t;u=0;t9(T?(u=t,G)t).sort(uZaua,bubb-a}C(s~t)Q)=`t!9ut)Q:0|$(u)Y$U>N$U|0:t0Xu>t|0V)K()]:[t+1](K.)]:[t-1]&5v;~tc)vc   &t|5dvt |t^5v;k,ut!~tc)^!~kc)vc ^tif`v=?u:t;v^4?A(S(v)v!+!randMath.random()*G)|0)".split("//"+z)[1]L,\'{1$if}:and{1$if}:or{!!{!}*}:xor{..0sZOQ=sFfoGs(HctIif(Js.splice(O.))Kt;s=st9[tXL)}N`q9t9$(u)P){Q[0]RdT8>3U(t)V8//Wfunction(b,X,tY==Z(`;qu';for(Y=0;$='q`ZYXWVUTRQPNLKJIHGFEDB98765#  '[Y++];)with(_.split($))_=join(pop());eval(_)
Note: Contains some control characters, nothing outside of ASCII though. Here's a direct link to the file: gs.js. The code provides a function a which takes the Golfscript code as a single parameter and returns the resulting stack as an array, with strings and blocks represented as ASCII.
Differences from the official interpreter:

Numbers have only 53 bits precision
No exact output and no direct print (would be easy to add though)
Double quoted strings are parsed using Javascript's eval, which might work different than Ruby's. Also no access to Ruby functions via strings
Undefined behaviour (I tried my very best)

I've also made a bunch of test cases and set up a small form for running Golfscript code: http://copy.sh/golfscript/
Here are some examples:

pi, phi
fizzbuzz
primality test
a quine

This is my standard Golfscript library, suggestions are welcome:
{1$if}:and
{1$\\if}:or
{\!!{!}*}:xor
{..0<2**-}:abs
{\{!}+\while}:until
{0$}:.
"\n":n
{\.[]*{0{2$*\(@+1$}do@;\;}{[{.@.@\\%@@.@\/.}do;;]-1%}if}:base
];

;[1 2]{+}* seems to loop forever rather than evaluating almost instantly to 3. Everything else I've tried so far has worked. Will do some more testing later.

;[1 2]{+}* works for me (also all of the test cases pass), but this bug might appear because of global state. I'm looking into it ...

And a small issue that numbers are not treated as variables: 11:10 10 * does not show 121 as it should. Also it seems to handle the empty stack inconsistently: ;5 p 4 * p should not work at all but gives 20.

@Howard numeric variables should work now. The other thing does not run as expected because p is not defined


text:
Given a fair coin as input, generate any particular unfair outcome
It is easy to generate a fair coin using a unfair coin, but the reverse is harder to accomplish.
Your program will receive one number X (between 0 and 1, inclusive) as input. The input must not simply be hard-coded as a number in the middle of the source code. It must then return a single digit: a 1 with a probability of X and a 0 otherwise.
Your program is only allowed to use one form of random number generator in the source code: int(rand(2)) (or an equivalent), which returns either a zero or a one with equal probability. You can include or access this function as many times as you wish in your code. You also have to provide the function yourself as part of the code.
Your program is not allowed to use any other random number generating functions or external sources (such as time and date functions) that could function as a random number generating function.  It also cannot access any external files or pass the job along to external programs.
This is code golf, the shortest answer wins.

What form does the input take? If we're guaranteed that it's an IEEE-754 floating point number of a given size, then this is actually pretty easy.

Perl, 37 42 char
($d/=2)+=rand>.5for%!;print$d/2<pop|0

Takes arbitrary probability as a command line argument. Builds a uniform random number in $d and compares it to the input.
Earlier, 52 char solution
$p=<>;do{$p*=2;$p-=($-=$p)}while$--(.5<rand);print$-

I'm impressed that you came back 6 years later to optimize this solution.

Python, 81 chars
import random
print(sum(random.randint(0,1)*2**-i for i in range(9))<input()*2)+0

Can be off by a bit, but never more than 1%.

Looks much better than 1% to me. I ran your program 100,000 times for probabilities of [0,1] with a step of 0.01 and compared this with random.random() < desiredProbability using this script: https://gist.github.com/3656877 They match up perfectly http://i.imgur.com/Hr8uE.png

Although, as expected, random.random() < x is considerably faster.

Mathematica 165
Not streamlined, but some may find the algorithm of interest:
d = RealDigits; r = RandomInteger;
f@n_ := If[(c = Cases[Transpose@{a = Join[ConstantArray[0, Abs[d[n, 2][[2]]]], d[n, 2][[1]]],
         RandomInteger[1, {Length@a}]}, {x_, x_}]) == {}, r, c[[1, 1]]]

Usage
f[.53]

1

Check
Let's see if f[.53] really produces the value 1 around 53%  of the time.
Each test calculates the % for samples of 10^4.
50 such tests are run and averaged.
Table[Count[Table[f[.53], {10^4}], 1]/10^4 // N, {50}]
Mean[%]

{0.5292, 0.5256, 0.5307, 0.5266, 0.5245, 0.5212, 0.5316, 0.5345,
  0.5297, 0.5334, 0.5306, 0.5288, 0.528, 0.5379, 0.5293, 0.5263, 0.539,
  0.5322, 0.5195, 0.5208, 0.5382, 0.543, 0.5336, 0.5305, 0.5303,
  0.5297, 0.5318, 0.5243, 0.5281, 0.5361, 0.5349, 0.5308, 0.5265,
  0.5309, 0.5233, 0.5345, 0.5316, 0.5376, 0.5264, 0.5269, 0.5295,
  0.523, 0.5294, 0.5326, 0.5316, 0.5334, 0.5165, 0.5296, 0.5266, 0.5293}
0.529798

Histogram of results

Explanation (spoiler alert!)
The base 2 representation of .53 is

.10000111101011100001010001111010111000010100011110110

Proceeding from left to right, one digit at a time:
If RandomInteger[] returns 1, then  answer = 1,
Else If second RandomInteger[] returns 0, then answer = 0,
Else If third RandomInteger[] returns 0, the answer = 0,
Else....
If, when all digits have been tested, there is still no answer,
then answer = RandomInteger[].

Haskell, 107 chars:
import System.Random
g p|p>1=print 1|p<0=print 0|1>0=randomIO>>=g.(p*2-).f
f x|x=1|1>0=0.0
main=readLn>>=g

Wolfram Language (Mathematica), 42 bytes
RandomInteger[]/.⌈1-2#⌉:>#0@Mod[2#,1]&

Try it online!
This is a recursive approach. Ungolfed, the algorithm is:

If the input probability p is less than 1/2, then when the coinflip comes up 0, return 0. Otherwise, recurse on 2p; assuming correctness, the overall probability of getting 1 is half of 2p or p.
If the input probability p is greater than 1/2, then when the coinflip comes up 1, return 1. Otherwise, recurse on 2p-1; assuming correctness, the overall probability of getting 0 is half of 1-(2p-1) or 1-p.

To make it shorter, we start with the random coinflip, which, in either branch, gets returned half the time. If the coinflip does not match the case when we're supposed to return it, replace it by the result of recursing on 2p modulo 1. (That is, when p is less than 1/2, replace 1; when p is greater than 1/2, replace 0. This is equivalent to replacing ⌈1-2p⌉.)