text:
Simulate a Minsky Register Machine (I)
There are many formalisms, so while you may find other sources useful I hope to specify this clearly enough that they're not necessary.
A RM consists of a finite state machine and a finite number of named registers, each of which holds a non-negative integer. For ease of textual input this task requires that the states also be named.
There are three types of state: increment and decrement, which both reference a specific register; and terminate. An increment state increments its register and passes control to its one successor. A decrement state has two successors: if its register is non-zero then it decrements it and passes control to the first successor; otherwise (i.e. register is zero) it simply passes control to the second successor.
For "niceness" as a programming language, the terminate states take a hard-coded string to print (so you can indicate exceptional termination).
Input is from stdin. The input format consists of one line per state, followed by the initial register contents. The first line is the initial state. BNF for the state lines is:
line       ::= inc_line
             | dec_line
inc_line   ::= label ' : ' reg_name ' + ' state_name
dec_line   ::= label ' : ' reg_name ' - ' state_name ' ' state_name
state_name ::= label
             | '"' message '"'
label      ::= identifier
reg_name   ::= identifier

There is some flexibility in the definition of identifier and message. Your program must accept a non-empty alphanumeric string as an identifier, but it may accept more general strings if you prefer (e.g. if your language supports identifiers with underscores and that's easier for you to work with). Similarly, for message you must accept a non-empty string of alphanumerics and spaces, but you may accept more complex strings which allow escaped newlines and double-quote characters if you want.
The final line of input, which gives the initial register values, is a space-separated list of identifier=int assignments, which must be non-empty. It is not required that it initialise all registers named in the program: any which aren't initialised are assumed to be 0.
Your program should read the input and simulate the RM. When it reaches a terminate state it should emit the message, a newline, and then the values of all the registers (in any convenient, human-readable, format, and any order).
Note: formally the registers should hold unbounded integers. However, you may if you wish assume that no register's value will ever exceed 2^30.
Some simple examples

a+=b, a=0

s0 : a - s1 "Ok"
s1 : b + s0
a=3 b=4

Expected results:
Ok
a=0 b=7

b+=a, t=0

init : t - init d0
d0 : a - d1 a0
d1 : b + d2
d2 : t + d0
a0 : t - a1 "Ok"
a1 : a + a0
a=3 b=4

Expected results:
Ok
a=3 b=7 t=0

Test cases for trickier-to-parse machines

s0 : t - s0 s1
s1 : t + "t is 1"
t=17

Expected results:
t is 1
t=1

and
s0 : t - "t is nonzero" "t is zero"
t=1

Expected results:
t is nonzero
t=0

A more complicated example
Taken from the DailyWTF's Josephus problem code challenge. Input is n (number of soldiers) and k (advance) and output in r is the (zero-indexed) position of the person who survives.
init0 : k - init1 init3
init1 : r + init2
init2 : t + init0
init3 : t - init4 init5
init4 : k + init3
init5 : r - init6 "ERROR k is 0"
init6 : i + init7
init7 : n - loop0 "ERROR n is 0"
loop0 : n - loop1 "Ok"
loop1 : i + loop2
loop2 : k - loop3 loop5
loop3 : r + loop4
loop4 : t + loop2
loop5 : t - loop6 loop7
loop6 : k + loop5
loop7 : i - loop8 loopa
loop8 : r - loop9 loopc
loop9 : t + loop7
loopa : t - loopb loop7
loopb : i + loopa
loopc : t - loopd loopf
loopd : i + loope
loope : r + loopc
loopf : i + loop0
n=40 k=3

Expected results:
Ok
i=40 k=3 n=0 r=27 t=0

That program as a picture, for those who think visually and would find it helpful to grasp the syntax:

If you enjoyed this golf, have a look at the sequel.

Does input come from stdin, from a file, or from some other place?

@Bass, from stdin.

You should add some test cases with the following difficult to handle issues: 1) messages with spaces, 2) messages with equal signs, 3) messages in inc_line, 4) messages in the first state of a dec_line, 5) messages in spaces in cases 3 & 4.

The grammar has an error: There needs to be a literal space between the two state_name entries in dec_line. It is also unclear if you mean to require people to accept multiple spaces between tokens in the input.

@MtnViewMark, good spot on the missing space in dec_line. It's only required to accept single spaces - that's why the grammar only has single spaces. Your case 1 is covered already by the Josephus problem. Your case 2 isn't required to be accepted because = is not alphanumeric or space. Good call on cases 3 and 4/5 (makes sense to inline them). Will think about suitable tests.

@Peter, thanks for the additional tests. I think your expected answer to #4 is wrong. It should be "t is nonzero" and "t=1"

Is outputting the register values with no names but keeping the order from the input human-readable enough?

@MtnViewMark, aargh, yes. I'm trying to think up something vaguely useful which terminates on the first state of a dec_line, but I messed up. I think it'll have to be something arbitrary.

@J B, no, because not all the registers have to be supplied in the input. And making the human work through the program to see in what order the uninitialised variables were first seen isn't friendly.

@Peter: +1 for a really meaty code-golf with good balance of specification and room to maneuver! Most questions here have been far too thin.

Perl, 166
@p=<>;/=/,$_{$`}=$' for split$",pop@p;$o='\w+';(map{($r
,$o,$,,$b)=$'=~/".*?"|\S+/g if/^$o :/}@p),$_=$o=($_{$r}
+=','cmp$o)<0?do{$_{$r}=0;$b}:$,until/"/;say for eval,%_

Run with perl -M5.010 file.
It started wildly different, but I'm afraid it converged with the Ruby solution in many areas towards the end.  Seems like Ruby's advantage is "no sigils", and Perl's "better regex integration".
A bit of detail from the innards, if you don't read Perl:

@p=<>: read the whole machine description to @p
/=/,$_{$`}=$' for split$",pop@p: for each (for) assignment (split$") in the last machine description line (@p), locate equal sign (/=/) then assign value $' to hask %_ key $`
$o='\w+': initial state would be first one to match Perl regex "word characters"
until/"/: loop until we reach a termination state:

map{($r,$o,$,,$b)=$'=~/".*?"|\S+/g if/^$o :/}@p: loop on machine description @p: when we're on the line matching current state (if/^$o :/), tokenize (/".*?"|\S+/g) the rest of the line $' to variables ($r,$o,$,,$b).  Trick: the same variable $o if used initially for label name and subsequently for operator.  As soon as the label matches, the operator overrides it, and as a label can't (reasonably) be named + or -, it never matches again.
$_=$o=($_{$r}+=','cmp$o)<0?do{$_{$r}=0;$b}:$,:- adjust target register $_{$r} up or down (ASCII magic: ','cmp'+' is 1 whereas ','cmp'-' is -1);- if the result is negative (<0?, can only happens for -)- then stay at 0 ($_{$r}=0) and return second label $b;- else return first (possibly sole) label $,
BTW, it's $, instead of $a so it can be glued to next token until with no whitespace in between.

say for eval,%_: dump report (eval) and contents of registers in %_

You don't really need the colon in /^$o :/. The caret alone is enough to ensure you're only looking at labels.

@Lowjacker I don't need it to determine I'm on the right label, but I need it to be kept out of $'.  It's one character in the regex, it would be three $c, to account for from outside.  Alternately some bigger yet change to the tokenizing regex.

Ruby 1.9, 214 212 211 198 195 192 181 175 173 175
*s,k=*$<
a,=s
b=Hash.new 0
eval k.gsub /(\w+)=/,';b["\1"]='
loop{x,y,r,o,t,f=a.scan /".*?"|\S+/
l=(b[r]-=o<=>?,)<0?(b[r]=0;f):t
l[?"]&&puts(eval(l),b)&exit
a,=s.grep /^#{l} /}

I'd expect this to fail on labels prefixes of one another.  Thoughts?

I can't seem to make it work with any other case than the examples.  What's wrong with this?

I think it's fixed now.

Haskell, 444 characters
(w%f)(u@(s,v):z)|s==w=(s,f+v):z|t=u:(w%f)z
(w%f)[]=[(w,f)]
p#(a:z)|j==a=w p++[j]&z|t=(p++[a])#z;p#[]=w p
p&(a:z)|j==a=p:""#z|t=(p++[a])&z
c x=q(m!!0)$map((\(s,_:n)->(s,read n)).break(=='=')).w$last x where
 m=map(""#)$init x
 q[_,_,r,"+",s]d=n s$r%1$d
 q[_,_,r,_,s,z]d|maybe t(==0)(lookup r d)=n z d|t=n s$r%(-1)$d
 n('"':s)d=unlines[s,d>>=(\(r,v)->r++'=':shows v" ")]
 n s d=q(filter((==s).head)m!!0)d
main=interact$c.lines
t=1<3;j='"';w=words

Man, that was hard! Proper handling of messages with spaces in them cost over 70 characters. Output formatting to be more "human readable", and match the examples cost another 25.

Edit: (498 -> 482) various small in-linings, and some of @FUZxxl's suggestions
Edit: (482 -> 453) switch back using actual numbers for the registers; many golf tricks applied
Edit: (453 -> 444) inlined output formatting and initial value parsing

I don't know Haskell, so I can't decipher all the syntax, but I can decipher enough to see that you're using lists for the register contents. I must say I'm surprised that that's shorter than using ints.

Putting the local bindings after where into a single line seperated by semicolons could save you 6 characters. And I guess you could save some chars in the definition of q by changing the verbose if-then-else to a pattern guard.

And also: Just blindly assume, that the third value is "-" in the definition of q and use an underscore instead.

I guess, you could save another char by changing line 8 to q[_,_,r,_,s,z]d|maybe t(==0)$lookup r d=n z d|t=n s$r%(-1)$d. But anyway, this program is golfed extremely good.

You can shorten the parsing code considerably by taking advantage of lex from the Prelude. For example something like f[]=[];f s=lex s>>= \(t,r)->t:f r will split a line into tokens while handling quoted strings correctly.

Delphi, 646
Delphi does not offer very much with regard to splitting strings and stuff. Luckily, we do have generic collections, which does help a bit, but this is still a rather largish solution :
uses SysUtils,Generics.Collections;type P=array[0..99]of string;Y=TDictionary<string,P>;Z=TDictionary<string,Int32>;var t:Y;l,i:string;j,k:Int32;q:P;u:Z;v:TPair<string,Int32>;begin t:=Y.Create;repeat if i=''then i:=q[0];t.Add(q[0],q);ReadLn(l);for j:=0to 6do begin k:=Pos(' ',l+' ');q[j]:=Copy(l,1,k-1);Delete(l,1,k)end;until q[1]<>':';u:=Z.Create;j:=0;repeat k:=Pos('=',q[j]);u.Add(Copy(q[j],1,k-1),StrToInt(Copy(q[j],k+1,99)));Inc(j)until q[j]='';repeat q:=t[i];i:=q[4];u.TryGetValue(q[2],j);if q[3]='+'then Inc(j)else if j=0then i:=q[5]else Dec(j);u.AddOrSetValue(q[2],j)until i[1]='"';WriteLn(i);for v in u do Write(v.Key,'=',v.Value,' ')end.

Here the indented and commented version :
uses SysUtils,Generics.Collections;
type
  // P is a declaration line, offsets:
  // 0 = label
  // 1 = ':'
  // 2 = register
  // 3 = operation ('-' or '+')
  // 4 = 1st state (or message)
  // 5 = 2nd state (or message)
  P=array[0..99]of string;
  // T is a dictionary of all state lines :
  Y=TDictionary<string,P>;
  // Z is a dictionary of all registers :
  Z=TDictionary<string,Int32>;
var
  t:Y;
  l,
  i:string;
  j,
  k:Int32;
  q:P;
  u:Z;
  v:TPair<string,Int32>;
begin
  // Read all input lines :
  t:=Y.Create;
  repeat
    // Put all lines into a record
    if i=''then i:=q[0];
    t.Add(q[0],q);
    // Split up each input line on spaces :
    ReadLn(l);
    for j:=0to 6do
    begin
      k:=Pos(' ',l+' ');
      q[j]:=Copy(l,1,k-1);
      Delete(l,1,k)
    end;
    // Stop when there are no more state transitions :
  until q[1]<>':';
  // Scan initial registers :
  u:=Z.Create;
  j:=0;
  repeat
    k:=Pos('=',q[j]);
    // Add each name=value pair to a dictionary :
    u.Add(Copy(q[j],1,k-1),StrToInt(Copy(q[j],k+1,99)));
    Inc(j)
  until q[j]='';
  // Execute the state machine :
  repeat
    q:=t[i];
    i:=q[4];
    u.TryGetValue(q[2],j);
    if q[3]='+'then
      Inc(j)
    else
      if j=0then
        i:=q[5]
      else
        Dec(j);
    u.AddOrSetValue(q[2],j)
  until i[1]='"';
  WriteLn(i);
  for v in u do
    Write(v.Key,'=',v.Value,' ')
end.

Stax, 115 100 bytes
╥áípßNtP~£G±☼ΩtHô⌐╒╡~·7╝su9êq7h50Z`╩ë&ñ╝←j╞.½5└∩√I|ù┤╧Åτ╘8┼ç╕╒Æ►^█₧♫÷?²H½$IG☺S╚]«♀_≥å∩A+∩╣Δ└▐♫!}♥swα

Run and debug it

JavaScript (V8), 300 bytes
p=>{g=p.split`
`;r=g[g.length-1].split` `.map(R=>R.split`=`);g.pop();l=g.map(L=>L.match(/\w+|[+-]|"[ \w]+"/g));t=l[0][0];for(;;){c=l.find(L=>L[0]==t);(e=r.find(R=>R[0]==c[1]))||r.push(e=[c[1],0]);t=eval(c[2]+c[2]+"e[1]")<0?e[1]++&&c[4]:c[3];if(t[0]==`"`)return t.slice(1,-1)+`
`+r.map(R=>R.join`=`)}}

Try it online!
I used a trick with eval to choose between ++e[1] and --e[1]... it only saved a few bytes but it's fun.

What's it like, coding in a refridgerator?

@Razetime Cold. But lots of food!

PHP, 446 441 402 398 395 389 371 370 366 characters
<?$t=trim;$e=explode;while($l=$t(fgets(STDIN))){if(strpos($l,"=")){foreach($e(" ",$l)as$b){list($k,$c)=$e("=",$b);$v[$k]=$c;}break;}list($k,$d)=$e(":",$l);$r[$z=$t($k)]=$t($d);$c=$c?:$z;}while($d=$e(" ",$r[$c],4)){$c=$v[$a=$d[0]]||!$d[3]?$d[2]:$d[3];if(!$r[$c]){eval("echo $c.'\n';");foreach($v as$k=>$c)echo$k."=".$c." ";die;}if(!$d[3]&&++$v[$a]||$v[$a]&&--$v[$a]);}

Ungolfed

<?php

$register = array();
$values = array();

while($line = trim(fgets(STDIN))){

    if(strpos($line, "=")){

        // Set each value and then continue to the calculations

        foreach(explode(" ", $line) as $var){
            list($key, $val) = explode("=", $var);

            $values[$key] = $val;
        }

        break;
    }

    list($key, $data) = explode(":", $line);

    // Add data to the register

    $register[$z = trim($key)] = trim($data);

    // Set the first register

    $current = $current?:$z;
}

while($data = explode(" ", $register[$current], 4)){

    // Determine next register and current register

    $current = $values[$target = $data[0]] || !$data[3]? $data[2] : $data[3];

    // Will return true if the register does not exist (Messages wont have a register)

    if(!$register[$current]){

        // No need to strip the quotes this way

        eval("echo$current.'\n';");

        // Print all values in the right formatting

        foreach($values as $key => $val)
            echo $key."=".$val." ";

        die();
    }

    // Only subtraction has a third index
    // Only positive values return true

    // If there is no third index, then increase the value
    // If there is a third index, increment the decrease the value if it is positive

    // Uses PHP's short-circuit operators

    if(!$data[3] && ++$values[$target] || $values[$target] && --$values[$target]);
}

Changelog

446 -> 441: Supports strings for the first state, and some slight compression
441 -> 402: Compressed if/else and assignment statements as much as possible
402 -> 398: Function names can be used as constants which can be used as strings
398 -> 395: Uses short circuit operators
395 -> 389: No need for the else part
389 -> 371: No need to use array_key_exists()
371 -> 370: Removed unneeded space
370 -> 366: Removed two unneeded spaces in the foreach

Groovy , 338
m={s=r=[:];z=[:]
it.eachLine{e->((e==~/\w+=.*/)?{(e=~/((\w+)=(\d+))+/).each{r[it[2]]=it[3] as int}}:{f=(e=~/(\w+) : (.*)/)[0];s=s?:f[1];z[f[1]]=f[2];})()}
while(s[0]!='"'){p=(z[s]=~/(\w+) (.) (\w+|(?:".*?")) ?(.*)?/)[0];s=p[3];a=r[p[1]]?:0;r[p[1]]=p[2]=='-'?a?a-1:{s=p[4];0}():a+1}
println s[1..-2]+"\n"+r.collect{k,v->"$k=$v"}.join(' ')}

['''s0 : a - s1 "Ok"
s1 : b + s0
a=3 b=4''':'''Ok
a=0 b=7''',
'''init : t - init d0
d0 : a - d1 a0
d1 : b + d2
d2 : t + d0
a0 : t - a1 "Ok"
a1 : a + a0
a=3 b=4''':'''Ok
a=3 b=7 t=0''',
'''s0 : t - s0 s1
s1 : t + "t is 1"
t=17''':'''t is 1
t=1''',
'''s0 : t - "t is nonzero" "t is zero"
t=1''':'''t is nonzero
t=0''',
'''init0 : k - init1 init3
init1 : r + init2
init2 : t + init0
init3 : t - init4 init5
init4 : k + init3
init5 : r - init6 "ERROR k is 0"
init6 : i + init7
init7 : n - loop0 "ERROR n is 0"
loop0 : n - loop1 "Ok"
loop1 : i + loop2
loop2 : k - loop3 loop5
loop3 : r + loop4
loop4 : t + loop2
loop5 : t - loop6 loop7
loop6 : k + loop5
loop7 : i - loop8 loopa
loop8 : r - loop9 loopc
loop9 : t + loop7
loopa : t - loopb loop7
loopb : i + loopa
loopc : t - loopd loopf
loopd : i + loope
loope : r + loopc
loopf : i + loop0
n=40 k=3''':'''Ok
i=40 k=3 n=0 r=27 t=0'''].collect {input,expectedOutput->
    def actualOutput = m(input)
    actualOutput == expectedOutput
}

I tested this but it doesn't seem to output anything to stdout. What do I need to add to see the results? (PS the spec says that the order of the registers in the output is irrelevant, so you can save 7 chars from .sort())

@Peter thanks for the tip - I'll have to add 8 chars for println - ah well!

Clojure (344 chars)
With a few linebreaks for "readability":
(let[i(apply str(butlast(slurp *in*)))]
(loop[s(read-string i)p(->> i(replace(zipmap":\n=""[] "))(apply str)(format"{%s}")read-string)]
(let[c(p s)](cond(string? s)(println s"\n"(filter #(number?(% 1))p))
(=(c 1)'-)(let[z(=(get p(c 0)0)0)](recur(c(if z 3 2))(if z p(update-in p[(c 0)]dec))))
1(recur(c 2)(update-in p[(c 0)]#(if %(inc %)1)))))))

Postscript () () (852) (718)
For reals this time. Executes all the test cases. It still requires the RM program to immediately follow in the program stream.
Edit: More factoring, reduced procedure names.
errordict/undefined{& " * 34 eq{.()= !{& " .(=). load " .( ).}forall ^()=
stop}{^ ^ " 0 @ : 0}ifelse}put<</^{pop}/&{dup}/:{def}/#{exch}/*{& 0
get}/.{print}/~{1 index}/"{=string cvs}/`{cvn # ^ #}/+={~ load add :}/++{1
~ length 1 sub getinterval}/S{/I where{^}{/I ~ cvx :}ifelse}/D{/? # :/_ #
cvlit :}/+{D S({//_ 1 +=//?})$ ^ :}/-{/| # : D S({//_ load 0 ne{//_ -1
+=//?}{//|}ifelse})$ ^ :}/![]/@{~/! #[# cvn ! aload length & 1 add #
roll]:}/;{(=)search ^ # ^ # cvi @ :}/${* 32 eq{++}if * 34 eq{& ++(")search
^ length 2 add 4 3 roll # 0 # getinterval cvx `}{token ^
#}ifelse}>>begin{currentfile =string readline ^( : )search{`( + )search{`
$ ^ +}{( - )search ^ ` $ $ ^ -}ifelse}{( ){search{;}{; I}ifelse}loop}ifelse}loop

Indented and commented with appended program.
%!
%Minsky Register Machine Simulation
errordict/undefined{ %replace the handler for the /undefined error
    & " * 34 eq{ % if, after conversion to string, it begins with '"',
        .()= !{ % print it, print newline, iterate through the register list
            & " .(=). load " .( ). % print regname=value
        }forall ^()= stop % print newline, END PROGRAM
    }{ % if it doesn't begin with '"', it's an uninitialized register
        ^ ^ " 0 @ : 0 %initialize register to zero, return zero
    }ifelse
}put
<<
/^{pop}
/&{dup}
/:{def} % cf FORTH
/#{exch}
/*{& 0 get} % cf C
/.{print} % cf BF

% these fragments were repeated several times
/~{1 index}
/"{=string cvs} % convert to string
/`{cvn # ^ #} % convert to name, exch, pop, exch
/+={~ load add :} % add a value to a variable
/++{1 ~ length 1 sub getinterval} % increment a "string pointer"

/S{/I where{^}{/I ~ cvx :}ifelse} %setINIT define initial state unless already done
/D{/? # :/_ # cvlit :} %sr define state and register for generated procedure
/+{D S({//_ 1 +=//?})$ ^ :} % generate an increment state and define
/-{/| # : D S({//_ load 0 ne{//_ -1 +=//?}{//|}ifelse})$ ^ :} % decrement state
/![] %REGS list of registers
/@{~/! #[# cvn ! aload length & 1 add # roll]:} %addreg append to REGS
/;{(=)search ^ # ^ # cvi @ :} %regline process a register assignment
/${ %tpe extract the next token or "string"
    * 32 eq{++}if %skip ahead if space
    * 34 eq{ %if quote, find the end-quote and snag both
        & ++(")search ^ length 2 add 4 3 roll # 0 # getinterval cvx `
    }{
        token ^ # %not a quote: pull a token, exch, pop
    }ifelse
}
>>begin

{
    currentfile =string readline ^
    ( : )search{ % if it's a state line
        `( + )search{ % if it's an increment
            ` $ ^ + %parse it
        }{
            ( - )search ^ ` $ $ ^ - %it's a decrement. Parse it
        }ifelse
    }{ % not a state, do register assignments, and call initial state
        ( ){search{;}{; I}ifelse}loop %Look Ma, no `exit`!
    }ifelse
}loop
init0 : k - init1 init3
init1 : r + init2
init2 : t + init0
init3 : t - init4 init5
init4 : k + init3
init5 : r - init6 "ERROR k is 0"
init6 : i + init7
init7 : n - loop0 "ERROR n is 0"
loop0 : n - loop1 "Ok"
loop1 : i + loop2
loop2 : k - loop3 loop5
loop3 : r + loop4
loop4 : t + loop2
loop5 : t - loop6 loop7
loop6 : k + loop5
loop7 : i - loop8 loopa
loop8 : r - loop9 loopc
loop9 : t + loop7
loopa : t - loopb loop7
loopb : i + loopa
loopc : t - loopd loopf
loopd : i + loope
loope : r + loopc
loopf : i + loop0
n=40 k=3

It's a while since I wrote any PostScript, but are you defining functions with names like regline? Can't you save a lot by calling them things like R?

Yes, definitely. But there's also a potential problem since all these definitions coexist with the state and register names in the same dictionary. So I've been trying to find punctuation chars with some mnemonic value (so I can still read it :). I'm also hoping to find more algorithmic reductions, so I didn't want to spend too much energy before I could look at it with fresh eyes.

AWK - 447
BEGIN{FS=":"}NF<2{split($1,x," ");for(y in x){split(x[y],q,"=");
g[q[1]]=int(q[2])}}NF>1{w=$1;l=$2;gsub(/ /,"",w);if(!a)a=w;for(i=0;;)
{sub(/^ +/,"",l);if(l=="")break;if(substr(l,1,1)=="\""){l=substr(l,2);
z=index(l,"\"")}else{z=index(l," ");z||z=length(l)+1}d[w,i++]=
substr(l,1,z-1);l=substr(l,z+1)}}END{for(;;){if(!((a,0)in d))break;h=d[a,0];
if(d[a,1]~/+/){g[h]++;a=d[a,2]}else{a=g[h]?d[a,2]:d[a,3];g[h]&&g[h]--}}
print a;for(r in g)print r"="g[r]}

This is the output for the first test:
% cat | awk -f mrm1.awk
s0 : a - s1 "Ok"
s1 : b + s0
a=3 b=4
^D
Ok
a=0
b=7


text:
Code golf: Distributing the balls (I)
Challenge

In this task you have compute the number of  ways we can
  distribute A balls into B
  cells with with every cell
  having at-least one ball.

The inputs A and B are given in a single line separated by a blank,the inputs are terminated by EOF.
You may like to check your solutions here.
Input
0 0
1 0
12 4
6 3
18 17
20 19
15 13
18 9
20 20
17 14
9 2
14 13
18 11

Output
1
0
14676024
540
54420176498688000
23112569077678080000
28332944640000
38528927611574400
2432902008176640000
21785854970880000
510
566658892800
334942064711654400

Constraints

Every A and B can be distinguishable.
0 <= A,B <= 20
You can use any language of your choice
Shortest solution wins!

Are there time limits?

@Tim Nordenfur:Updated :-)

That link is invalid for me.

@mellamokb:How about now?

I take it that the balls are unique? That is, placing ball x1 in bin y1 and ball x2 in bin y2 is different than x1 in y2 and x2 in y1?

@Yonatan: I believe that is what is meant by "Every A and B can be distinguishable."  That is the interpretation I used when developing my answer, which seems to at least agree with the examples given.

@Debanjan I don't like the idea of pasting questions from SPOJ here. People submit their code for competing there and it would be unfair to them.

@fR0DDY:It's my problem and you can see similar instances here and here.Anyways,just remove the redundant newline in your submission in SPOJ,to set a new record :-)

@Debanjan Even though it is your question, it is a challenge problem there. It is not a tutorial problem or from anagolf where answers are revealed.

SIZECON is in challenge.I was a bit bored yesterday,so I wrote this problem in here ... and then thought of adding in SPOJ and other sites so that it might reach to larger audience.Anyways,I will move it to tutorial if SPOJ users wants that.

You might want to add the test cases 0 0 gives 1, 1 0 gives 0, 0 1 gives 0.

@fR0DDY:Now it's a completely different problem with different test cases.

@Debanjan: Please add test cases for 0 0, 0 1 and 1 0. Also, is A > B always?

@Eelvex:Added and No.

@Peter Taylor:How can we distribute 0 balls into 0 cells in 1 way?

@Debanjan: by doing nothing. Compare with binomial(0, 0) = 1, the number of ways of selecting 0 balls from 0 balls; or stirling2(0, 0) = 1 (the number of ways of distributing 0 distinguishable balls into 0 indistinguishable cells).

@Peter Taylor:I am changing the test case to make it more general,however I would like to add that the The basis cases of Stirling numbers of the second kind are a bit messy: $S(n,1)=1$, $S(n,n)=1$, and  $S(n,m)=0$ if $n<m$ or $n=m=0$. (REFERENCE)

@Debanjan, I see your reference and raise you Mathworld (eqn. 5 says that S(n,0) is 1 if n=0 and 0 otherwise). If you want I can find a reference for the stronger statement that Stirling2 is in the associative subgroup of the exponential Riordan group.

@Peter Taylor:I didn't knew about exponential Riordan group,thanks for the update :-)

JavaScript (90 93)
function f(a,b){n=m=r=1;for(i=b;i>0;n*=-1){r+=n*m*Math.pow(i,a);m=m*i/(b-i--+1)}return--r}

http://jsfiddle.net/RDGUn/2/
Obviously, any math-based language such as APL will beat me because of syntax verbosity and lack of built-in mathematical constructs :)
Edit Also, I don't have any input-related functionality  except parameters passed into the function, not sure how to use standard input with JavaScript...
Edit: Move i-- into m=m* expression; move n*=-1 into for; start r=1 to  combine assignments and remove extraneous one on return. (save 3 chars)

You could use the spidermonkey shell - it at least has readline and print. I don't know what others here use.

@Jesse: Interesting.  I'm going to lose anyway lol.

prompt and alert are JavaScript's "standard" io, as they're the typical blocking io calls, despite the fact that you'd never typically use blocking io with JavaScript.

Golfscript - 56 50 49 48 41 40 38 37 chars
n%{~),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;}/

Note: this handles multiple lines of input, is fast (1/8 secs to do the test cases), and doesn't break for any legal input.
(The first version was also my first ever Golfscript program; thanks to eBusiness for pointing out several tricks I missed).
In order to make this a useful educational post too, here's an explanation of how it works. We start with the recurrence f(n, k) = k * (f(n-1, k) + f(n-1, k-1)). This can be understood combinatorically as saying that to place n distinguishable balls in k distinguishable buckets such that each bucket contains at least one ball, you pick one of the k buckets for the first ball (k *) and then either it will contain at least one more ball (f(n-1, k)) or it won't (f(n-1, k-1)).
The values resulting from this form a grid; taking n as the row index and k as the column index and indexing both from 0 it starts
1   0   0   0    0    0   0 ...
0   1   0   0    0    0   0 ...
0   1   2   0    0    0   0 ...
0   1   6   6    0    0   0 ...
0   1  14  36   24    0   0 ...
0   1  30 150  240  120   0 ...
0   1  62 540 1560 1800 720 ...
.   .   .   .    .    .   . .
.   .   .   .    .    .   .  .
.   .   .   .    .    .   .   .

So turning to the program,
n%{~ <<STUFF>> }/

splits the input into lines and then for each line evaluates it, putting n and k on the stack, and then calls <<STUFF>>, which is as follows:
),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;

This computes the first k+1 entries of the n+1th row of that grid. Initially the stack is n k.
), gives stack of n [0 1 2 ... k]
{!}% gives stack of n [1 0 0 ... 0] where there are k 0s.
\{ <<MORE STUFF>> }* brings the n to the top and makes it the number of times we execute <<MORE STUFF>>.
Our stack currently is a row of the table: [f(i,0) f(i,1) ... f(i,k)]
0.@ puts a couple of 0s before that array. The first one will be j and the second one will be f(i,j-1).
{ <<FINAL LOOP>> }/ loops through the elements of the array; for each one it puts it on top of the stack and then executes the loop body.
.@+2$*@)@ is boring stack manipulation to take ... j f(i,j-1) f(i,j) and yield ... j*(f(i,j-1)+f(i,j)) j+1 f(i,j)
;;] pops off the left-over k+1 f(i,k) and gathers everything into an array, ready for the next go round the loop.
Finally, when we've generated the nth row of the table,
)p; takes the last element, prints it, and discards the rest of the row.
For posterity, three 38-char solutions on this principle:
n%{~),{!}%\{0.@{.@+@.@*\)@}/;;]}*)p;}/
n%{~),{!}%\{0:x\{x\:x+1$*\)}/;]}*)p;}/
n%{~),{!}%\{0.@{@1$+2$*\@)}/;;]}*)p;}/

Pretty good for a beginner, there is a few possible small scale reductions, immediately I find [0] -> 1,, the space after zip can just be removed, and the other space can be removed if you just store in an operator instead of k. I haven't stepped through your code yet, but I suspect you might get away with just using a value without putting it in an array in some of the spots.

+1,I don't understand Golfscript but this looks sufficiently fast,and yet very short.

@eBusiness and @Peter Taylor:On a different note .. how much you guys rate Golfscript on the scale of easy to learn?

@Debanjan, depends on what you already know. It's a functional stack-based language. I've used a functional languages before (SML - plus I've written functional-style code in OO languages), and I've used stack-based languages before (Java bytecode assembled with Jasmin, PostScript), so the only real hurdle I face is learning what operators are available. If you only know languages from the Algol family (C, Java, etc) then you'll have three hurdles to jump at once.

@Debanjan - It's much easier than it looks, you can start writing code almost immediately, but of course it takes some time to learn all the little tricks.

@Peter Taylor:Well I am am comfortable with C,C++ and Python only.\

@eBusiness:Hm I that's almost true for every language I guess,but this one seems just dots and lines to me :/

@Debanjan As I said, it's easier than it looks, but you won't get far without reading some documentation http://www.golfscript.com

@Debanjan: I had never done GolfScript before this problem.  I took gnibbler's answer, and the documentation, and a command-line GolfScript executor for testing, and after about an hour-and-a-half I understood his code.  There's not very many operators, they're just short and powerful.  Like @eBusiness says, just start going through character by character with the documentation, and you'll begin to understand it.

@mellamokb and @eBusiness :Thanks,but I am an windows,I don't find the golfscript executor for the same?!

@Debanjan, I've been tempted for a while to post on meta asking whether anyone wants to port the Golfscript interpreter from Ruby to JavaScript so that those of us who can't install Ruby (e.g. on our work machines, so that we could golf over lunch) can still play around with it.

@Peter Taylor - GolfScript for a large part build on Ruby functionality, a JavaScript implementation would be considerably more complicated, and a lot slower. It would be cool to have, but if I were to spend my time on such a thing I'd probably be more inclined to make an interpreter for a language designed to provide a common ground for golfing with an absolute speed benchmark and a way of counting complexity rather than just characters.

@Debanjan: I'm on windows as well.  I installed Ruby to my C:\ drive, downloaded the golfscript.rb (http://www.golfscript.com/golfscript/golfscript.rb -> File, save as), and then you just run it from the command line: echo INPUT | ruby golfscript.rb myfile.gs from the directory where you installed Ruby. myfile.gs is your GolfScript code stored in a file (the name is arbitrary).

@eBusiness, you've got me thinking now about how creating a new language would allow fixing several problems in Golfscript. Alas, I don't have time to do more than muse on ideas at the moment.

@Peter Taylor - Completely unrelated, you got me thinking about how to get my solution below 37 characters :-P

Golfscript - 26 chars
Warning: The 12 4 case needs a lot of memory (although not as much as the answer below) and takes a quite a while to run
~:)\?:x,{x+)base(;.&,)=},,

Obviously this answer has some problems, but I will leave it here because the comments refer to it and mellamokb's answer is based off it.
Golfscript - 24 chars
Warning: The 12 4 case needs a lot of memory and takes a quite a while to run
~:o)\?,{o)base[0]-,o=},,

I can't figure how you came up with that code, not only will this method run out of memory for large inputs, I also can't figure what the increment operators are good for. That you actually hit the target for 6 3 seems to be nothing but luck.

That's no clown, that's my wife!

I don't understand Golfscript but as you said and I agree your approach is too slow.

What? 2 upvotes for this solution. Didn't I say it clear enough, it is WRONG, even for the smallscale cases that it can handle the results are wrong.

I ran for [4, 2] and the result is 24.  My code returns 14 for [4, 2].  Who's right?

@mellamokb:For input [4,2] the correct answer is 14.

I think this is a working solution: ):£\.(£\?:¢;?,{¢+}%{£base£,\-[0]=},, (i used ¢ and £ for variables so they wouldn't get parsed with the base keyword).

@eBusiness: The answer is on the right track, just had a few bugs which I worked out with my answer (with considerably more chars, never used GolfScript before :).  I think the idea for incrementing is so that the numbers use non-zero digits for representing what cell they are in, otherwise you have a problem with the base-k format starting with 0's, and they will be left out.  If it starts with 1 instead, those left-most digits will be included.

@mellamokb your solution ain't any better, if you want a solution of approximately that principle then here is one: ~:B\:A?,{B base.,A=[]0if+B,&,B=},,

@eBusiness: Except for the minor point that my solution works... lol.

Ah it does, (given one add the ~ that you forgot) but not so well in my UTF-8 encoded file. You should skip ASCII extension characters, just overload an operator if you need tight variable names.

@eBusiness: Thanks, fixed on both counts.  I haven't figured out why do you need ~?  If you run the code with the input prepended as numbers to the beginning, there's no reason to eval them.  Or how else do you give input to GolfScript code?  The documentation is very slim.

You get input as stdin, which is a string, so you basically eval that string to get the numbers written in it.

@eBusiness: Got it.  What do you think of my new solution (I posted a new answer).  It's slightly shorter than the one you proposed (by 2 chars I think).

It's still brute force, it can't handle the entire input spectrum. You ain't got a true solution until you go the mathematical way.

@mellamokb, good on you for working out how it was supposed to work :) It only took 2 extra chars to fix that bug. Now we are in the murky area where the shortest code may be correct but not practical. Code-golf is riddled with insanely inefficient answers but microseconds vs seconds usually doesn't matter. This one is an extreme case (lots of memory too). Debanjan has indicated that the answers need to be faster, but this site is not SPOJ, this question is tagged code-golf

@gnibbler: Suffers from the same problems as my current solution: 0 0 yields an error and n 1 for any n causes it to hang.

@mellamokb, I guess 0,0 should produce 0 and n,1 should produce 1?

@eBusiness: I tend to agree with gnibbler.  Part of the golfing excitement (to me) is finding a clever way to reduce the size of the code at the expense of performance.

@gnibbler, 0 0 should produce 1; 0 k for any other k should produce 0; n 1 for n > 0 should produce 1.

GolfScript - 45 38 36 characters
Medium-force dirty implementation recurrence relation (38 36 characters):
n%{~{.2$*{\(.2$f\2$(f+*}{=}if}:f~p}/

The recurrence relation I stole from Peter Taylors solution, it goes like this:
f(x, y) = y * ( f(x-1, y) + f(x-1, y-1) )
With special cases if either variable is 0.
My implementation does not reuse previous results, so each function call branch to two new calls, unless one of the zero cases have been reached. This give a worst case of 2^21-1 function calls which takes 30 seconds on my machine.
Light-force series solution (45 characters):
n%{~.),0\{.4$?3$,@[>.,,]{1\{)*}/}//*\-}/p;;}/

J, 40
4 :'|-/x(^~*y!~])i.1x+y'/&.".;._2(1!:1)3

E.g
4 :'-/((x^~|.@:>:)*y&(!~))i.y'/x:".>{.;:(1!:1)3
15 13
28332944640000

<1sec for all test cases.
Edits

(52 → 47) Reduce with -/ instead of alternating (1 _1)* (J-B's idea)
(47 → 53) Noticed multiline input requirement :-/
(53 → 48) Exploit symmetry of binomials.
(48 → 48) Make tacit!
(48 → 41)
(41 → 40) Squeeze increment+conversion into 1x+

Hey! That was my idea! O:-)

Ok, I'll steal that 1x+ then, but that only buys me back 1 character, whereas you took 5!

J, 38 to 42
Depending on your strictness preferences about interactive languages and output presentation, take your pick from the J spectre of solutions:

38 shortest interactive: 4 :'|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
Launch jconsole, enter it, then paste the input (end with C-d).  You'll notice the output is space-separated (J is a vector language, it performs the computation on the whole input as a whole and returns it as a 1D vector, whose default presentation is on a single line).  I consider that ok, the spirit of this problem is computation, not presentation.  But if you insist on having newlines instead:
39 longer interactive: 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3
Replacing Compose (&) with Under (&.) returns a vector of strings, whose presentation ends up on separate lines.
42 batch mode: 4 :'echo|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
Run from the command line as $ jconsole balls.ijs < balls.in

If you voted this up, you might want to go give Eelvex's solution some credit as well.

You need an Under &. for it to work properly on interactive mode.

@Eelvex you must have a different interpretation of "properly".  I start jconsole, paste code, paste input, C-d, and receive the output.  No under needed.  What's yours?

Our codes combined: 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3. 39 chars.

Without echo or Under I get the output in one line only (instead of multiple lines).

@Eelvex indeed, but that's not explicitely forbidden.

Common Lisp (83)
(defun b (x y)
  (if (= (* x y) 0)
      (if (= (+ x y) 0) 1 0)
      (* y (+ (b (decf x) y) (b x (1- y)))))))

It seems like there should be a shorter way to test the base cases, but nothing occurs to me offhand.

J, 55 characters
(wd@(4 :'(y^x)--/(!&y*^&x)|.i.y')/@".@,&'x');._2(1!:1)3

Passes current test cases. I think I understand the math...
j602, console only (wd). Input on stdin, output on stdout.

Bash test script:
jconsole disballs.ijs <<END
12 4
6 3
END

What does that j6xx's wd do?

I really meant j602... I'm guessing it's in j601 also. It's defined as echo, which is defined as 0 0&$@(1!:2&2). I'm not sure what that means, but it does something like pretty-print rank 1 items with a line break. (I'm just now noticing that uses 2 rather than 4... I think it still goes to stdout in console mode, at least.)

I'm having trouble running this code.  Do I just type it into the console?

@mellamokb I've using something like the test script above, with the program saved as disballs.ijs and the correct path to j602/bin/jconsole.

@Jesse: I'm running this on windows.  I get << was unexpected at this time.  Sorry I'm new to J input, I always used it in console mode.

@mellamokb: I've been running it under Windows in a Bash installed by msysgit. To run it otherwise, you'll have to modify the program to end with 2 toJ(1!:1)3 (add ' toJ' before (1!:1)3) and then run jconsole.exe disballs.ijs, and type in 12 46 3. There's probably an easy way to do this in Windows batch with an input file, but you might find it easier to get a Unix shell on there for compatibility with most of the golfers here.

dc, 100 chars
[0q]s5[1q]s6[l2l3>5l3 0>5l2 0=6l2 1-S2l3dS3 1-S3l1xL3s9l1xL2s9+L3*]s1[?z0=5S3S2l1xL3L2+s9fs9l4x]ds4x

Alas, dc doesn't seem to be supported by ideone. There may be a character or two still to squeeze out, but it's bedtime.
Note: this supports multiple lines of input, has sufficient precision to give the correct output even for 20 19 (curse you, Perl, for the time I wasted debugging my solution!), and gives the correct output for 0 0.
Suggestions from Nabb allow shortening at least as far as
[0q]sZ[1q]sI[?z0=ZSkSn[lnlk>Zlk0>Zln0=Iln1-SnlkdSk1-SklFxLks9lFxLns9+Lk*]dsFxfs9l4x]ds4x

at the cost of leaving junk in the register stacks (and thus running out of memory if we compute billions of answers).

Registers are always single characters (you can use any character, which will make the code more readable), so l11 is parsed as l1 1 (you can use K as a single character token for 0 if you aren't going to change precision anyway). You can change the input loop to ?[...?z1=4]. You can inline the macro in register 1. And you can probably save heaps more characters in general, but I'll wait for it to be shorter to comprehend it.

@Nabb, ah, I didn't read the man page carefully enough. I'm only using 8 or 9 registers, so I didn't run into the consequences of my misunderstanding. Thanks.

Python 140 Chars
import sys
f=lambda n,k:(n and k and n>=k and k*(f(n-1,k-1)+f(n-1,k)))or(n+k==0 and 1)or 0
for l in sys.stdin:print f(*(map(int,l.split())))

Golfscript (28 31 37)
~):$\.($\?:@;?,{@+}%{$base$,\-[0]=},,
Modification to gnibbler's GolfScript solution.  I think this is a working solution - tested with [3,2], [4,2], [6,3], and [9,2] with correct answers. (I used $ and @ for variables to tighten up space around the base keyword).
There are two problems with gnibbler's current solution.

Checking length after removing [0] does not guarantee a solution, because [1,1,1,1] would be valid for input [4,2], even though all 4 balls are in the same cell (1).  So I've modified to check also that all digits are used, i.e., the array contains 1-2, so each cell contains at least one ball.
In the case of input [4,2], the base-3 format of numbers 0-27 are less than 4 digits, and the left-most 0's are not included.  That means [1,1] is included as a valid solution, even though it is technically actually [0,0,1,1], which means the first two balls are not placed anywhere.  I fix by adding 3^3 to every entry (generically k^n-1 to the array of k^n entries) so that the first entries are shifted upward to having at least n-digits in  base-k format, and the last entries will automatically be invalid anyway and won't affect the solution (because the second digit will always be 0).

Edit
~:@\?:$,{$+}%{@base(;@,\-,0=},,
`~:@\?:$,{$+@base(;@,\-,0=},,`

Better solution yet!  No need to increment, just add to all of the numbers so they start with [1], and no digits will be missing (including the left-padding of 0's) once you decon that first digit.  This solution should work and has been tested with same entries above.  It's also a lot faster because we aren't incrementing before taking exponent to generate the array (but still suffers from same performance / memory problem for larger input).
Edit: Use gnibbler's idea of moving the addition of $ inside of the filter instead of as an extra step.  (save 3 chars).

Breaks on input 0 0.

Also appears to handle only one line of input.

And breaks on n 1 for any n, causes it to hang. hmm..

converting numbers to base 1 will do that :)

@gnibbler: Do you have any suggestions?  Will I just need to throw in some if statements at the beginning to catch those cases?  Seems like I'll lose a lot of ground that way.

05AB1E, 19 bytes
#D`ULX.Œʒ€gßĀ}gs_P+

NOTE: It's extremely slow, and already times out for 12 4. It is working as intended, though. Will see if I can come up with an alternative method which works for all test cases in a reasonable time. See below for a much faster version which runs all test cases in less than a second.
Try it online or verify a few more (of the smaller) test cases.
Explanation:
#               # Split the (implicit) input-string by spaces
 D              # Duplicate it
  `             # Push both values to the stack
   U            # Pop and store the second value in variable `X`
    L           # Create a list in the range [1,n] for the first value
     X.Œ        # Create a list of all possible ways to divide this list into `X` partitions
                # (including empty sublists, so we'll have to filter them out:)
        ʒ       # Filter this list of lists of partition-lists by:
         €g     #  Get the length of each partition-list
           ß    #  Get the minimum length
            Ā   #  Truthify; 0 remains 0 (falsey); anything else becomes 1 (truthy)
             }g # After the filter, take the length to get the amount left
 s              # Swap so the duplicated input-list is at the top of the stack again
  _             # Check for each value if they're equal to 0 (1 if truthy; 0 if falsey)
   P            # Take the product of the two to check if both input-values are 0
    +           # And add it to the earlier calculated product (edge case for [0,0] = 1)
                # (After which the result is output implicitly)

05AB1E, 29 bytes
Here a much faster version which works for all test cases in about 0.5 seconds on TIO:
Î#R`V©LRvyYmX*NÈ·<*+Xy*®y->÷U

Port of @mellamokb's JavaScript answer, so make sure to upvote him!
Try it online or verify all test cases.
Explanation:
Î                    # Push (result=) 0 and the input
 #                   # Split the input by spaces
  R`                 # Push the values to the stack reversed
    V                # Pop and store the first value in variable `Y`
     ©               # Store the second value in variable `®` (without popping)
      LRv            # Loop `y` in the range [`®`,1], with index `N` in the range [0,`®`):
         yYm         #  Calculate `y` to the power `Y`
            X*       #  Multiply it by `X`
                     #  (Note: `X` is 1 before setting it to another value initially)
              NÈ     #  Check if index `N` is even (1 if truthy; 0 if falsey)
                ·<   #  Double it; and decrease it by 1 (1 if truthy; -1 if falseY0
                  *  #  Multiply it to the earlier number
                   + #  And add it to the result
         Xy*         #  Push `X` multiplied by `y`
         ®y->        #  Push `®` - `y` + 1
             ÷       #  Integer divide them
              U      #  Pop and store it as new variable `X`
                     # (output the result at the top of the stack implicitly after the loop)

NOTE: Works for edge case 0 0 in this case (unlike the JavaScript answer I ported this method from), because the L builtin will create a list [0,1].

source: Stack Exchange

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

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

sort: votes


text:
Determine if a polygon is convex
Write a program to determine if the input polygon is convex.  The polygon is specified with one line containing N, the number of vertices, then N lines containing the x and y coordinates of each vertex.  The vertices will be listed clockwise starting from an arbitrary vertex.
example 1
input
4
0 0
0 1
1 1
1 0

output
convex

example 2
input
4
0 0
2 1
1 0
2 -1

output
concave

example 3
input
8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0

output
convex

x and y are integers, N<1000, and |x|,|y|<1000.  You may assume that the input polygon is simple (none of the edges cross, only 2 edges touch each vertex).  Shortest program wins.

"Simple" doesn't include "consecutive edges are non-collinear"?!
Also, a couple more test-cases: (0,0) (0,2) (2,2) (2,0) (1,1); and (1,1) (0,0) (0,2) (2,2) (2,0) - to test the cases where finding the concave vertex requires wrapping from the end back to the start.

This question is aging, but... Consider adding a concave example with two aligned segments, e.g. a modification of example 2:
(0,0),(2,1),(4,2),(1,0)(2,-1). I bring this up because I fudged around example 3 without realizing it.

J, 105
echo>('concave';'convex'){~1=#=(o.1)([:>-.~)(o.2)|3([:-/12 o.-@-/@}.,-/@}:)\(,2&{.)j./"1}.0&".;._2(1!:1)3

Passes all three tests above.
Edit: (111->115) Handle co-linear points by eliminating angles of pi. Gained a few characters elsewhere.
Edit: (115->105) Less dumb.
Explanation for the J-impaired:

(1!:1)3 read STDIN to EOF. (I think.)
0&".;._2 is a nice idiom for parsing this kind of input.
j./"1}. lop off first line of input (N 0) and convert pairs to complexes.
(,2&{.) tack first two points onto the end of the list.
3(f)\ applies f to  sliding window of length 3 (3 points for  an angle)
[:-/12 o.-@-/@}.,-/@}: is a verb that transforms each 3 points into an angle between -pi and pi.

-@-/@}.,-/@}: produces (p1 - p2),(p3 - p2). (Recall that these are complexes.)
12 o. gives an angle for each complex.
[:-/(...) gives the difference of the two angles.

(o.1)([:>-.~)(o.2)| mod 2 pi, eliminate angles of pi (straight segments), and compare to pi (greater than, less than, doesn't matter unless the points are supposed to be wound in one direction).
1=#= if all those comparison result 1 or 0 (With self-classify. This seems dumb.)
echo>('concave';'convex'){~ print convex.

Python - 149 chars
p=[map(int,raw_input().split())for i in[0]*input()]*2
print'ccoonncvaevxe'[all((a-c)*(d-f)<=(b-d)*(c-e)for(a,b),(c,d),(e,f)in zip(p,p[1:],p[2:]))::2]

I think you need <=, see example 3 I just added.

dammn, that slice...

Ruby 1.9, 147 133 130 124 123
gets
puts ($<.map{|s|s.split.map &:to_i}*2).each_cons(3).any?{|(a,b),(c,d),(e,f)|(e-c)*(d-b)<(d-f)*(a-c)}?:concave: :convex

scala: 297 chars
object C{class D(val x:Int,val y:Int)
def k(a:D,b:D,c:D)=(b.y-a.y)*(c.x-b.x)>=(c.y-b.y)*(b.x-a.x)
def main(a:Array[String]){val s=new java.util.Scanner(System.in)
def n=s.nextInt
val d=for(x<-1 to n)yield{new D(n,n)}print((true/:(d:+d.head).sliding(3,1).toList)((b,t)=>b&&k(t(0),t(1),t(2))))}}

You can shave of three chars by using def main(a:... instead of def main(args:....

Yes, I noticed myself, but 299 to 149 doesn't bring me in the area of someone else. Maybe if I find other improvements - ah, there is one: n is a function name (next) and a variable name.

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


text:
Fastest alphabetical list sort given the following limitations:
Your function must have an input that takes in an array containing 10000 random names, and must sort these names in alphabetical order. Names have a random length of up to 128 characters. ISO/IEC 8859-1 character set assumed to be used for the list of names.
Usable list of names can be found at http://www.opensourcecf.com/1/2009/05/10000-Random-Names-Database.cfm (firstNameFirst column).
You may not use any native sorting functions available to your language.
The winner will be based purely on speed.
Language used must be compilable/runnable on a standard *nix box.

So, simply sort a list of lines by byte values?  Or do we need to account for space between names or encodings?

@Joey Adams simply sort a list by byte values.

10000x128 isn't very much data.  LC_ALL=C sort randomNames.csv takes about 20 milliseconds on my system.  Any faster, and it would be nearly indistinguishable from cat.

@Joey Adams, was planning on running each function 100x for testing.

If anyone's interested in testing large inputs, here is a program that generates 1,000,000 lines (each no longer than 128 characters including newline) of ISO 8859-1 text.

When you say no native sorting functions, should I take it that comparison operators are included? Otherwise comparing 2 names is as simple as if(name1<name2)

@Gareth you may use comparison operators freely.

C - B-tree sort
This sorts randomNames.csv in about 5.8ms on my Core 2 T5500 @ 1.66GHz.  My testing utility is here.
It isn't the fastest algorithm for sorting this quantity of data, but I didn't feel like trieing.
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Btree Btree;

static void btree_insert(Btree **btree, const char *key);
static void btree_emit_and_free(Btree *btree, const char ***out);

void sort(const char **strings, size_t count, const char **out)
{
    size_t i;
    Btree *tree = NULL;
    const char **out_start = out;

    for (i = 0; i < count; i++)
        btree_insert(&tree, strings[i]);

    btree_emit_and_free(tree, &out);

    assert(out - out_start == (ssize_t) count);
}

/*
 * Maximum (U) and minimum (L) number of *keys* per B-tree node.
 *
 * The maximum number of *branches* a B-tree may have is U+1 :
 *
 *       KEY   KEY
 *     /     |     \
 * branch  branch  branch
 */
#define U 20
#define L (U / 2)

struct Btree {
    /* Number of keys (rather than branches). */
    unsigned char count;

    /* 0 if node is a leaf, 1 if it has leaf children, etc. */
    unsigned char depth;

    const char *keys[U];

    /* Allocated to U+1 items if this is an internal node. */
    Btree *branches[];
};

static Btree *allocLeaf(void)
{
    return malloc(sizeof(Btree));
}

static Btree *allocInternal(void)
{
    return malloc(sizeof(Btree) + (U+1) * sizeof(Btree *));
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr);
static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr);
static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x);

static void btree_insert(Btree **btree, const char *key)
{
    if (*btree == NULL) {
        Btree *root = allocLeaf();
        root->count = 1;
        root->depth = 0;
        root->keys[0] = key;
        *btree = root;
    } else {
        const char *new_x;
        Btree *new_xr;

        if (insert(*btree, key, &new_x, &new_xr)) {
            Btree *root = allocInternal();
            root->count = 1;
            root->depth = (*btree)->depth + 1;
            root->keys[0] = new_x;
            root->branches[0] = *btree;
            root->branches[1] = new_xr;
            *btree = root;
        }
    }
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr)
{
    unsigned int k = find_insertion_point(node->keys, node->count, x);
    Btree *xr;

    if (node->depth == 0)
        xr = NULL;
    else if (insert(node->branches[k], x, new_x, new_xr))
        x = *new_x, xr = *new_xr;
    else
        return false;

    return insert_item(node, k, x, xr, new_x, new_xr);
}

static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr)
{
    unsigned int i;
    bool internal = xr != NULL;

    if (node->count < U) {
        /* Enough case */
        for (i = node->count; i-- > k;)
            node->keys[i + 1] = node->keys[i];
        node->keys[k] = x;
        if (internal) {
            for (i = node->count + 1; i-- > k + 1;)
                node->branches[i + 1] = node->branches[i];
            node->branches[k + 1] = xr;
        }
        node->count++;
        return false;
    } else {
        Btree *r = internal ? allocInternal() : allocLeaf();

        node->count = L;
        r->count = L;
        r->depth = node->depth;

        if (k < L) {
            /* Left case */
            *new_x = node->keys[L - 1];
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            for (i = L - 1; i-- > k;)
                node->keys[i + 1] = node->keys[i];
            node->keys[k] = x;
            if (internal) {
                for (i = 0; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
                for (i = L; i-- > k + 1;)
                    node->branches[i + 1] = node->branches[i];
                node->branches[k + 1] = xr;
            }
        } else if (k == L) {
            /* Central case */
            *new_x = x;
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                r->branches[0] = xr;
                for (i = 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        } else {
            /* Right case */
            *new_x = node->keys[L];
            for (i = 0; i < k - L - 1; i++)
                r->keys[i] = node->keys[i + L + 1];
            r->keys[k - L - 1] = x;
            for (i = k - L; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                for (i = 0; i < k - L; i++)
                    r->branches[i] = node->branches[i + L + 1];
                r->branches[k - L] = xr;
                for (i = k - L + 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        }

        *new_xr = r;
        return true;
    }
}

static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x)
{
    unsigned int start = 0;
    unsigned int middle;

    while (count) {
        middle = count >> 1;
        if (strcmp(x, keys[start + middle]) < 0) {
            count = middle;
        } else {
            start += middle + 1;
            count -= middle + 1;
        }
    }

    return start;
}

static void btree_emit_and_free(Btree *btree, const char ***out)
{
    unsigned int i;

    if (btree->depth == 0) {
        for (i = 0; i < btree->count; i++)
            *(*out)++ = btree->keys[i];
    } else {
        for (i = 0; i < btree->count; i++) {
            btree_emit_and_free(btree->branches[i], out);
            *(*out)++ = btree->keys[i];
        }
        btree_emit_and_free(btree->branches[btree->count], out);
    }

    free(btree);
}

BTree wins it... by default.

@dqhendricks: You mean because nobody else posted an answer?  I know for a fact a faster solution is possible.

yeah, but no one wants to try

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


text:
Union of Intervals
Given a list of intervals, perform the union of them, and reduce overlaps.
That means, overlapping parts are reduced. ([a, b] U [c, d] = [a, d] if b > c)
Assuming all a < b in all intervals [a, b].
Implement as a function of a list of input intervals -> list of output intervals.
Shortest code wins. You cannot use any existing libraries.
Clarifications:

Open and closed intervals are not distinguished.
Intervals for real numbers, not integers. ([2, 3], [4, 5] -> [2, 3], [4, 5])
No need to sort output intervals
The order if inputs do not matter
Illegal inputs are only [a, b] where b >= a, it has nothing to do with the order of input intervals and the number of input intervals.
You do not need to show an error message on undefined behaviors

Examples (with number lines)
 [2, 4], [7, 9] --> [2, 4], [7, 9]
   234
        789
-> 234  789

 [1, 5], [2, 10] --> [1, 10] (overlapping [2, 5] reduced)

   12345
    234567890
-> 1234567890
 [2, 4], [3, 6], [8, 9] -> [2, 6], [8, 9]
   234
    3456
         89
-> 23456 89

 [4, 2], [2, 2] -> (undefined behavior: against the assumption)

Will the intervals always be sorted as they are in your examples?

bounds on the numbers?

Why don't [2, 3], [4, 5] overlap, or [2, 4], [4, 5] either?  They both yield 2345.

Are the intervals only on the set of integers?

We need some clarification: 1) Is [4,5],[1,2] legal input?   2) Should the output of [2,3],[4,5] be [2,5] or [2,3],[4,5]?   3) Should the output of [2,3],[3,4] be [2,4] or [2,3],[3,4]?

Thanks for clarifications, but "No need to sort" means what? That the output needn't be sorted? Or that the input is already sorted?

Wondering why you picked the Python entry? It wasn't the shortest.. what made it be the winner?

GolfScript, 32
[{1$1$*-2%~2->{*$[(\)\;]}{}if}*]

Add 2 characters if you prefer a
block, 4 if you prefer a named block.
Input and output are array of pairs, e.g. [[2 4] [3 5]]
Assumes that input is ordered by the first element.
Compacts "adjacent" ranges ([2 4][5 6] ->  [2 6])
First GolfScript effort. Advice & rotten fruit appreciated.

Full test program:
[~](;2/[{1$1$*-2%~2->{*$[(\)\;]}{}if}*]`

Example invocation:
ruby golfscript.rb intervals.gs <<EOF
3
2 4
3 6
8 9
EOF
# Expected output: [[2 6] [8 9]]

Haskell (103)
I think, it is way too verbose for Haskell. Thanks to Hoa Long Tam for his sorting function.
m%(x:y)|x>m=m:x:y|2>1=x:m%y;m%_=[m]
(x:y)?l|x`elem`l=y?l|0<1=x:y?(x:l);a?_=a
a∪b=foldr(%)[](a++b)?[]

In Haskell, an intervall from a to b is denoted by [a..b]. My notation is very similar to the mathematical notation. Use it like this:
[a..b] ∪ [c..d] ∪ ... ∪ [y..z]

Ok, here's my 250 character crack at it.
void n(int a[]){if(!a[2])return;if(a[2]<=a[1]){if(a[1]<a[3])a[1]=a[3];
int *b=a+2;while(*b=*(b+2))++b;n(a);}n(a+2);}
void m(int a[]){if(!a[2])return;if(a[0]>a[2]){int s=a[0],t=a[1];
a[0]=a[2];a[2]=s;a[1]=a[3];a[3]=t;m(a+2);m(a);n(a);}m(a+2);n(a+2);}

The function takes an int array, and operates on it in-situ. The array is terminated by a 0, and the intervals may be given in any order.
Sample output:
input list: (7,9) (5,6) (1,4) (15,18) (13,16) (2,3) (8,11)
output list: (1,4) (5,6) (7,11) (13,18)

Sample program:
#include <stdio.h>

void n(int a[]){if(!a[2])return;if(a[2]<=a[1]){if(a[1]<a[3])a[1]=a[3];
int *b=a+2;while(*b=*(b+2))++b;n(a);}n(a+2);}
void m(int a[]){if(!a[2])return;if(a[0]>a[2]){int s=a[0],t=a[1];
a[0]=a[2];a[2]=s;a[1]=a[3];a[3]=t;m(a+2);m(a);n(a);}m(a+2);n(a+2);}

/*
void n(int a[])
{
    if(!a[2])return;
    if(a[2]<=a[1]) {
        if(a[1]<a[3])
            a[1]=a[3];
        int *b=a+2;
        while(*b=*(b+2))++b;
        n(a);
    }
    n(a+2);
}

void m(int a[])
{
    if(!a[2])return;
    if(a[0]>a[2]) {
        int s=a[0],t=a[1];
        a[0]=a[2];a[2]=s;
        a[1]=a[3];a[3]=t;
        m(a+2);m(a);n(a);
    }
    m(a+2);n(a+2);
}
*/

void p(int a[])
{
    if(!*a) {
        printf("\n");
        return;
    }
    printf("(%d,%d) ",a[0],a[1]);
    p(a+2);
}

int main (int argc, const char * argv[])
{
    // Code golf entry
    // Interval Merging

    int a[] = {7,9,5,6,1,4,15,18,13,16,2,3,8,11,0};
    printf( "input list: " ); p(a);
    m(a);
    printf( "output list: " ); p(a);

    return 0;
}

perform the union of them should lead to (1,11) (13,18), shouldn't it?

@user unknown: I would have thought the same thing, but I guess the instructions say only combine if they overlap.  So (1, 4) (5, 6) are not combined according to the rule ([a, b] U [c, d] = [a, d] if b > c).  And for that matter, even (1, 5) (5, 6) would not be combined.

"Given a list of intervals, perform the union of them, and reduce overlaps" and reduce overlaps - not if they overlap. OK - the following that means ... points again in the opposite direction.

@user unknown: I agree. That's why I've commented about it on the question.  Hopefully the OP will respond :)

Python, 100 chars
def f(L):R=sorted(set(p for p in sum(L,[])if 1-any(x<p<y for x,y in L)));return zip(R[::2],R[1::2])
print f([[2, 4], [7, 9]])
print f([[1, 5], [2, 10]])
print f([[3, 6], [2, 4], [8, 9]])
print f([[1, 5], [3, 5], [4, 5]])

generates
[(2, 4), (7, 9)]
[(1, 10)]
[(2, 6), (8, 9)]
[(1, 5)]

Takes all the endpoints of the intervals, removes any that are strictly inside another interval, uniquifies & sorts them, and pairs them up.

98 bytes

Haskell, 55 characters
v(q@(a,b):p@(c,d):r)|c>b=q:v(p:r)|1<3=v((a,d):r);v x=x

If the input is unsorted, then 88 characters:
p@(a,b)§(q@(c,d):r)|b<c=p:q§r|a>d=q:p§r|1<3=(min a c,max b d)§r;p§_=[p]
u i=foldr(§)[]i

Test runs:
ghci> testAll v
pass: [(2,4),(7,9)] --> [(2,4),(7,9)]
pass: [(1,5),(2,10)] --> [(1,10)]
pass: [(2,4),(3,6),(8,9)] --> [(2,6),(8,9)]
ghci> testAll u
pass: [(2,4),(7,9)] --> [(2,4),(7,9)]
pass: [(1,5),(2,10)] --> [(1,10)]
pass: [(2,4),(3,6),(8,9)] --> [(2,6),(8,9)]

I'm assuming that "can't use any existing libraries" precludes importing List and calling sort. If that were legal, than the unsorted version would be only 71 characters.

importing List from package Haskell98 would be sufficient IMHO.

Scala, 272 characters
type p=List[(Int,Int)];def f(l:p):p={var(a,s,c,o)=(new Array[Int]((l map(x=>x._2)max)+1),0,0,List[Int]());l map(x=>(a(x._1)+=1,a(x._2)-=1));while(c<a.size){s+=a(c);if(a(c)==1&&s==1)o=o:+c;if(a(c)== -1&&s==0)o=o:+c;c+=1};return(o.grouped(2).map(x=>(x.head,x.last)).toList)}

Usage:
object Intervals2 extends Application
{
    type p=List[(Int,Int)];def f(l:p):p={var(a,s,c,o)=(new Array[Int]((l map(x=>x._2)max)+1),0,0,List[Int]());l map(x=>(a(x._1)+=1,a(x._2)-=1));while(c<a.size){s+=a(c);if(a(c)==1&&s==1)o=o:+c;if(a(c)== -1&&s==0)o=o:+c;c+=1};return(o.grouped(2).map(x=>(x.head,x.last)).toList)}

    print(f(List((1,2),(3,7),(4,10))))
}

Creates an array and inserts a 1 for every interval start and a -1 for every interval end. Then steps through the array adding the values to a counter outputting a start every time the counter steps from 0 to 1 and an end when it steps from 1 to 0. Probably unnecessarily complicated.
Output:
List((1,2), (3,10))

Perl (146) (92) (90)
golfed down to 90 chars, creatively using the regex engine

sub u{map$h[$_]=1,@$_[0]..@$_[1]for@_;$w.=$_+0for@h;push@r,$-[0],$+[0]-1while$w=~/1+/g;@r}

usage example:

my @out1 = u([1, 5], [2, 10]); # (1,10)
my @out2 = u([2, 4], [3, 6], [8, 9]); # (2, 6, 8, 9)

let's explain this code a bit.
this subroutine receives an array of arrayrefs, each aref pointing to an array containing two elements, start and end of the interval: ([2, 4], [3, 6], [8, 9])
for every aref, we generate an array of elements from first to last ($_->[0] .. $_->[1]).
then we use map to set elements of such indexes in @h to 1.

for (@_) {
    map {$h[$_] = 1} ($_->[0] .. $_->[1]);
}

after this, @h will contain either ones (for intervals) or undefs, depicted below as hyphens for clarity.

index: 0 1 2 3 4 5 6 7 8 9
@h:    - - 1 1 1 1 1 - 1 1

next we build a string from @h, adding 0 to replace undefs with something more useful (undef + 0 = 0).
$w .= $_+0 for @h;
$w contains 011111011 now.
it's time to abuse the regex engine a bit.
push @r, ($-[0], $+[0]-1) while $w=~/1+/g;
after successful matches, @- and @+ arrays contain respectively position of start and end of each match; 0th element is used for the entire match, first for $1, second for $2 and so on.
$+[0] actually contains the position of first non-matching char, so we have to substract one.
@r contains (2, 6, 8, 9) now.
@r
to make the sub return @r.

Doesn't work for real numbers [2,3],[4,5] yields 2 5

Scala  305  279 chars without invocation:
type I=(Int,Int)
def l(p:I,q:I)=if(p._1<q._1)true else if(p._1>q._1)false else p._2<q._2
def r(l:List[I]):List[I]=l match{case x::y::z=>{if(y._1<=x._2&&y._2>x._2)(x._1,y._2)::r(z)else
if(y._1<=x._2&&y._2<=x._2)x::r(z)else
x::r(y::z)}case _=>l}
def c(v:List[I])=r(v.sortWith(l))

invocation:
val i=List((7,9),(5,6),(1,4),(15,18),(13,16),(2,3),(8,11))
c(i)
res0: List[(Int, Int)] = List((1,4), (5,6), (7,11), (13,18))

Brachylog, 12 bytes
⟦₂ᵐcod~c~⟦₂ᵐ

Try it online!
A delightfully declarative solution, taking input as a list of lists through the input variable and outputting a list of lists through the output variable.
        ~⟦₂ᵐ    The output is a list of intervals, where each interval is a range in
      ~c        the smallest partition of
  ᵐ             each element of the input
⟦₂              converted to an inclusive range,
   c            concatenated,
    o           sorted,
     d          and deduplicated
        ~⟦₂ᵐ    for which each element of the partition is a range.

Clojure, 138 bytes
#(let[S(set(apply mapcat range(apply map list %)))Q(sort S)](map list(for[s Q :when(not(S(dec s)))]s)(for[s(map inc Q):when(not(S s))]s)))

This shortens to 119 bytes if the input is more flexible, namely a list of intervals' starting points AND a list of intervals' ending points:
#(let[S(set(mapcat range % %2))Q(sort S)](map list(for[s Q :when(not(S(dec s)))]s)(for[s(map inc Q):when(not(S s))]s)))

There has to be a better way.

Japt, 18 bytes
This feels far too long. I/O as sorted, 2D array of intervals.
c_ròÃòÈaY ÉÃ®g[TJ]

Try it

Jelly (fork), 11 bytes
r/€FṢQŒġ.ịⱮ

Try it online! or rather, don't
Outputs the ranges as [b, a] where \$b > a\$ (so the example [2, 4], [3, 6], [8, 9] is output as [6, 2], [9, 8])
How it works
r/€FṢQŒġ.ịⱮ - Main link. Takes a list of pairs on the left
  €         - Over each pair:
r/          -   Reduce into a range
   FṢQ      - Flatten, sort and deduplicate
      Œġ    - Group adjacent consecutive elements
        .ịⱮ - Select the first and last from each group

Perl 5 -MList::Util=max -n, 89 bytes
@r=/\S+/g;map{/ /;$`<=$r[1]?$r[1]=max@r,$'*1:(say"@r")|(@r=($`,$'))}sort{$a-$b}<>;say"@r"

Try it online!

Ruby, 75 bytes
->a{a.map{[*_1.._2]}.reduce(:|).sort.slice_when{_2-_1>1}.map{|a,*,b|[a,b]}}

Attempt This Online!

Mathematica, 18 bytes
List@@Interval@@#&

View it on Wolfram Cloud!


text:
Hangman wordgame golf
Inspired by reddit.
Write a program which plays Hangman.

The program chooses a random word from a list of N words, where N > 2.
The word list can be provided to the program in any way you choose.
At each iteration

Print out the state of the game using underscores for letters not yet discovered:

H _ N _ _ _ N

Print the number of remaining attempts

10

Read a letter from stdin, and update the state of the game, subtracting an attempt if they guess an incorrect letter.

A (input)
H A N _ _ A N
10

Repeat until all letters are guessed or attempts reaches 0

Use any language
Fewest number of characters wins.
Drawing the gallows is not necessary, but will earn you upvotes and kudos.

Can I let each word in the list be the same number of characters?

Do the letters in the output have to be separated by spaces?

@Peter Of The Corn: you should assume that the word list is arbitrary

@Lowjacker: the spaces improve the legibility of consecutive underscores, otherwise it's hard to count how many letters they represent.

Ruby 1.9, 134 132 120 117 108 107
Word list provided in ARGV. The words and the entered letters must match in case.
r=w=$*.sample
t=10
loop{puts [*w.tr(r,?_).chars]*' ',t
t>0&&r>''?w[l=STDIN.gets[0]]?r=r.tr(l,''):t-=1:exit}

Python 3.
from random,sys import *
w=choice(*argv)
L=set(w)
a=10
while L and a:
 print(" ".join("_"if x in L else x for x in w),a)
 try:L-=set(input()[0])
 except:a-=1

I prefer this one though: longer but nicer.
import random
w=random.choice(list(open("/usr/dict/words")))[:-1]
L=set(w)
a=10
while L and a:
 print(" ".join("_"if x in L else x for x in w),a)
 try:L.remove(input()[0])
 except:a-=1
print w

If I didn't have to print a as well, I could use the * twice: print(*("_"if x in L else x for x in w))

Darn, I thought it said "fewest number of lines wins." I'm not going to win any fewest-character contests here, but this Common Lisp program is only one line.
(let ((words (list "that" "help" "rent" "chair" "octopus" "monitor" "manual" "speakers" "onomatopoeia" "regardless" "irresponsible" "cornerstone"))) (let ((word (nth (random (length words)) words))) (format t "~a~%" (funcall (defun play (word current remaining-attempts) (progn (if (not (find #\_ current)) (return-from play "You win!")) (if (equalp remaining-attempts 0) (return-from play "You lose!")) (format t "~a~%~d~%" current remaining-attempts) (let ((guess (char (read-line) 0)) (index 0) (found nil)) (loop for letter across word do (if (equalp guess letter) (progn (setf (char current index) letter) (setf found t))) (setf   index (+ index 1))) (if found (play word current remaining-attempts) (play word current (- remaining-attempts 1)))))) word (map 'string #'(lambda (c) #\_) word) 10))))

I'm upvoting you because I'm pretty sure you're being intentionally humorous :-)

c++ (-headers)
struct h{h(char a):b(a){}char operator()(char c,char d){return d!='_'?d:c==b?c:'_';}char b;};

int main(int a,char**b){
srand(time(0));string c=*(b+rand()%(a-1)+1),d(c.size(),'_'),e;
char f=10,g;
while(f){
cout<<"> ";cin>>g;e=d;
transform(c.begin(),c.end(),d.begin(),d.begin(),h(g));if(e==d)--f;
cout<<d<<endl<<(int)f<<endl;if(d==c)break;
}return 0;}

cat /usr/dict/words | xargs hangman

The "> " prompt for input is not necessary for the solution, I just added it in the question to indicate that it was input, as many languages provide a prompt such as this.

@drspod You should edit the question to reflect that, then.

edited to clarify

Python
import random

DEFAULT_ATTEMPTS = 10

def print_word(word, uncovered):
    for c in word:
        if c not in uncovered:
            c = '_'
        print c,
    print ''

def get_letter():
    letter = None
    while letter is None:
        letter = raw_input('> ')
        if len(letter) != 1:
            print 'Letters must be 1 character.  Try again.'
            letter = None
    return letter

if __name__ == '__main__':
    import sys

    if len(sys.argv) != 2: sys.exit(1)
    with open(sys.argv[1], 'r') as f:
        words = [word.strip() for word in f.readlines() if word.strip()]

    word = random.choice(words)
    uncovered = set([' '])
    attempts = DEFAULT_ATTEMPTS

    while attempts > 0 and any(letter not in uncovered for letter in word):
        print_word(word, uncovered)
        print attempts

        letter = get_letter()
        if letter in uncovered:
            print 'You have already tried that letter.'
        elif letter in word:
            print 'You got it!'
        else:
            print 'Wrong!'
            attempts -= 1

        uncovered.add(letter)

    if attempts == 0:
        print 'You lose!',
    else:
        print 'You win!'
    print 'The phrase was "%s".' % word

I didn't really try for the fewest characters, just wanted to make it as small as possible without sacrificing anything.

@user: You may be interested in George Edison's wonderful user script for this site which puts your code (as copied here by badp) at 1225 characters.

I think that's cause I was using tabs and they were converted to spaces here.  wc says it's 1034 with tabs.

@user: Yes. A well known difficulty with python submissions.

Perl, 112 char.  I feel like I can do better - perhaps I'll try again later
$_=$ARGV[rand@ARGV];$a=10;while($a&&/[a-z]/){print map/[A-Z]/?$_:'_',split'';$x=<STDIN>;chop$x;s/$x/$x/ig||$a--}

Words are given on the command line, letters typed upper case

Down to 107
$_=$ARGV[rand@ARGV];$a=10;while($a&&/[a-z]/){$y=$_;$y=~y/a-z/_/;print$y;$x=<STDIN>;chop$x;s/$x/$x/ig||$a--}

You could just edit your original answer.

This doesn't display the number of remaining attempts.

Clojure
This is 400 bytes gzipped, which is still quite a lot, probably because of how Clojure handles mutable state.
(def m ["will" "work" "for" "food"])
(def w (nth m (rand-int (count m))))
(def *s* (atom (replicate (count w) "_")))
(def *a* (atom 10))

(defn g [s a]
  (str (apply str (interpose " " s)) "\n" a))

(loop [n (read-line)]
  (if (some (set n) w)
    (swap! *s* (fn [s]
                 (map
                   (fn [i]
                     (if (= n (str (nth w i)))
                       n
                       (nth s i)))
                   (range 0 (count s)))))
    (swap! *a* dec))

  (println (g (deref *s*) (deref *a*)))

  (if (and (< 0 (deref *a*)) (some #{"_"} (deref *s*)))
    (recur (read-line))))

C# 370
using System;namespace h{class P{static void Main(string[]a){int c=10,d,l;char y=' ';string w=a[new Random().Next(a.Length)];l=w.Length;char[]x=new char[l];for(d=-1;++d<l;x[d]='-');while(c>0){for(d=-1;++d<l;x[d]=(y==w[d]||x[d]!='-')?w[d]:x[d]);Console.WriteLine(new string(x)+" "+c);if(w==new string(x))return;y=Console.ReadKey(true).KeyChar;if(!w.Contains(y+""))c--;}}}

wordlist as argument

VB.NET
I haven't tried shrinking it yet, but:
First shrinking:
Second shrinking (3759 characters):
Module Hangman
    Sub Main()
        Dim m As Int32, w = "banana|apple|pear|dog|cat|orange|monkey|programming|hangman".Split("|")(New Random().Next(9)), g = "", e = "", x, c As Char, f As Boolean, r = Sub(z) Console.Write(z), p = Sub(y, h) Console.SetCursorPosition(y, h), a = Sub() Console.Clear(), q = Function() Console.ReadKey(1), d = Sub()
                                                                                r("       +--------+S       |        |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S                |S   ---------------------".Replace("S", vbCrLf))
                                                                                p(0, 2)
                                                                                r(String.Join(vbCrLf, "    /------\S    | O   O|S    \  ... /S     ------ S        |   S        |   S        |   S        |   S -------+-------S        |   S        |   S        |   S       / \  S      /   \  S     /     \  S    /       \  ".Split("S").Take(m * 4)))
                                                                                End Sub
        Console.CursorVisible = 0
        Do
            a()
            d()
            p(30, 10)
            f = 0
            For Each x In w
                If g.Contains(x) Then
                    r(x)
                Else
                    r(" ")
                    f = 1
                End If
                Console.CursorTop += 1
                Console.CursorLeft -= 1
                r("_")
                Console.CursorTop -= 1
                r(" ")
            Next
            If Not f Then
                a()
                d()
                p(30, 10)
                r("You win! Press any key to close.")
                q()
                End
            End If
            p(30, 13)
            r(e)
            Do
                c = q().KeyChar
            Loop Until Char.IsLetter(c)
            If g.Contains(c) Then
                e = "You have already guessed that letter."
            Else
                g &= c
                If w.Contains(c) Then
                    e = "There is a" & If("aehilmnorsx".Contains(c), "n", "") & " """ & c & """ in the word."
                Else
                    e = "There is no """ & c & """ in the word. Try again."
                    m += 1
                End If
            End If
        Loop Until m = 4
        a()
        d()
        p(30, 10)
        r("You lose! Press any key to close.")
        q()
    End Sub
End Module

Is all the indentation really required?

it makes it easier to read, doesn't it?

As in blocks? No, it's not required, but I don't count it as characters.

Powershell, 125 bytes
$w=$h=$args|random|% t*y
for($n=10){$w-replace"[ $h]",'_'-join' ';$n
if(!$h+!$n){break}$n-=($c=Read-Host)-notin$h
$h=$h-ne$c}

Less golfed test script:
$f = {

$word=$hidden=$args|random|% toCharArray    # let $word and $hidden are a random word chars
#$word                                      # uncomment this to cheating
for($n=10){                                 # forever for with init section
    $word-replace"[ $hidden]",'_'-join' '   # display the word with hidden letters
    $n                                      # display $n
    if(!$hidden+!$n){break}                 # break loop if hidden array is empty or n equal to 0
    $n-=($c=Read-Host)-notin$hidden         # input $c from user, decrease $n if $c does not in $hidden array
    $hidden=$hidden-ne$c                    # recreate $hidden array with removed $c
}

}

$words = gc .\wordlist.txt
&$f $words

Output example when the guessing player has lost:
_ _ _ _ _ _ _ _
10
i
_ _ _ _ _ _ _ _
9
e
_ _ e _ _ _ _ e
9
o
o _ e _ _ o _ e
9
a
o _ e _ _ o _ e
8
q
o _ e _ _ o _ e
7
q
o _ e _ _ o _ e
6
q
o _ e _ _ o _ e
5
q
o _ e _ _ o _ e
4
q
o _ e _ _ o _ e
3
q
o _ e _ _ o _ e
2
q
o _ e _ _ o _ e
1
q
o _ e _ _ o _ e
0

Output example when the guessing player has win:
_ _ _ _ _ _ _ _ _ _
10
e
_ _ _ _ e _ _ _ _ _
10
o
_ o _ _ e _ _ _ _ _
10
i
_ o _ _ e _ _ i _ _
10
a
_ o _ _ e _ _ i a _
10
l
_ o _ _ e _ _ i a l
10
c
c o _ _ e _ c i a l
10
m
c o m m e _ c i a l
10
t
c o m m e _ c i a l
9
r
c o m m e r c i a l
9