text:
Hard Code Golf: Create a Chatroom
Cue Storyline:  It is the early 21st century, and most things have become a thing of the past.  You and your fellow code-golf-eteers, however, are on a quest to reenact the 1990s.  As a part of this challenge, you must recreate a minimalistic chatroom.
The Goal:  To create a chatroom with as few bytes as possible.  The program(s) that you write shall function as a simple server, which serves a webpage, which allows users to post text onto the screen.
The Actual Goal:  To actually host a working chatroom from your own computer.  You don't have to do this, but it is a lot more fun this way.
Requirements:

Users should be able to give themselves a username that lasts for the session
Users should be able to repeatedly type and submit text, which will be displayed to other users
Each user should be able to see the text that is submitted by all users, along with the usernames of the submitters, and the information should be displayed in chronological order
The page should also display the number of people online and a list of their usernames
Your chatroom should be accessible to anyone on the internet who knows where to find it (such as knowing the IP address).
It should function in modern web browsers.

All else is up to you!
Submissions:

Should include the source code, or a link to the source code
Should include screenshots of the functional chatroom
Should include the total size, in bytes, of all of the programs/files that you have written that are required to make it work.

This challenge has been in the sandbox for a while now, so hopefully all of the kinks have been worked out.

would it be allowable if we forced the chatters to type each of their responses within nine seconds?

I think that 9 seconds is probably too short.  Something like 99 seconds could probably work, though.  I never thought of putting time limits on the chatters.

define "online". Do we need to post back on before unload, 5s timeout will suffice, or are we even allowed to claim people never log off?

are we allowed to allow HTML-injection and other stuff that could break the chatroom (as long as we don't hurt our own computer)?

Actually, can you clarify "type each of their responses within nine seconds?"
By "online," I would mean a list of people who are currently viewing the chatroom, such as having the chatroom open in a browser window.  A timeout will be fine.

PHP + JQuery + HTML + CSS, 1535 bytes
This is a submission leaning more towards what the OP deemed as 'the actual goal'. That is, a fully functional chat server, which may be hosted on just about any web server anywhere.
Functionality includes:

Notifications when users enter or leave the chat room.
Notifications when users change their alias.
Real time polling for new messages, without generating excess server traffic, or server load.
Layout and usability strongly resembling existing chat clients, such as X-Chat.

To being a session, enter an alias in the appropriate box, and press Tab or Enter to submit. If the alias is already in use, you will be notified. Sending messages is also done via Enter.

For your convenience, an archive of all files may be found here: chat.zip (choose Download from the File menu). To install, unpack to a web directory on any server running PHP 5.4 or higher.
Caveats:

IE 8 or lower will spin into an infinite loop while polling, because for some reason unknown to humanity, all Ajax requests are cached by default. It also prevents you from sending the same message twice, and updating the user list properly. This could be fixed by adding cache:false to every Ajax request.
In all version of IE, messages will not be sent by pressing Enter, because the change event is not triggered (pressing Tab, however, does work). This could be fixed by adding an onkeypress handler, checking if the key was Enter, and then calling $(v).blur().focus().

In short, IE is not supported.

Client
Positioning of elements could be a bit more robust, but it should look alright with a minimum window size of about ~800x600.
chat.htm (190 bytes)

<link rel=stylesheet href=c.css>
<select id=u multiple></select>

<input id=n onchange=u()><input id=v onchange=s()>

c.css (136 bytes)
i{color:#999}
#u{float:right;height:100%;width:200px;margin-left:10px}
#o{border:1px solid #999;height:93%;overflow-y:scroll}
#v{width:54%}

c.js (435 bytes)
var l
(function p(){
  $.ajax({url:'p.php',data:{n:$('#n').val()},success:function(d){
    $('#o').html(d).scrollTop(1e4);$('#u').load('n.php');
  },complete:p,timeout:2e4})
})()
function s(){
  $.get('s.php',{n:$(n).val(),v:$(v).val()})
  $(v).val('')
}
function u(){
  $.get('u.php',{l:i=l,n:l=$(n).val()}).fail(function(){
    alert("This name is already in use!")
    $(n).val(l=i)
  })
}
$(window).on('unload',function(){$.ajax({url:'l.php',data:{l:l},async:false})})

Server
I apologize for the server being broken up into so many tiny chunks. The alternative would be to use an adequate message protocol (via JSON encode/decode), or having a large if ... elseif ... according to which post variables are present. Making separate scripts, an just requesting from the one you need is a lot shorter, and perhaps simpler than both.
o.php (119 bytes) Opens as connection to the 'database'
<?$m=array_slice(unserialize(file_get_contents(m)),-300);
$u=unserialize(file_get_contents(u));$t=time();extract($_GET);

c.php (57 bytes) Commits changes to the 'database'
<?foreach([u,m]as$c)file_put_contents($c,serialize($$c));

p.php (151 bytes) Polls for new messages
<?for($t=time();@filemtime(m)<$t;usleep(1e3))clearstatcache();include('o.php');
foreach($m as$v)if($n&&$v[0]>=$u[$n])echo@date("[H:i]",$v[0])."$v[1]\n";

s.php (62 bytes) Send a message to the server
<?include('o.php');$m[]=[$t,"$n: $v"];include('c.php');

u.php (222 bytes) User registration or alias change
<?include('o.php');if(!trim($n)||$u[$n])exit(header('HTTP/1.1 418'));
$m[]=[$t,$u[$l]?
"$l is now known as $n.":
"$n has entered the chat."];
$u[$n]=$u[$l]?:$t;unset($u[$l]);include('c.php');

n.php (65 bytes) Retrieves the list of user names
<?include('o.php');foreach($u as$k=>$v)echo"<option>$k</option>";

l.php (98 bytes) User has left (closed their browser)
<?include('o.php');$m[]=[$t,"$l has left the chat."];
unset($u[$l]);include('c.php');

I think you can do onchange=u without the parentheses. You won't get a consistent context, however, but you don't need it anyways.

Can you make the tutorial a bit more detailed? I want to set this up on a Mac.

@Peanut I typed up some instructions: http://codepad.org/UKGwb4g2. I'm working blind, but this will probably work.

Python, 230
This is fairly minimal, but it seems to be up to spec.  Users are counted as "viewing the page" if they've chatted in the last 99 seconds.
import cherrypy as S,time
@S.quickstart
@S.expose
def _(n='',p='',l=["<form%sn value='%s'%sp%s'' type=submit>"],u={},t="><input name="):u[n]=time.time();l+=p and[n+':'+p];return'
'.join([k*(u[n]-99<u[k])for k in u]+l)%(t,n,t,t)

This uses one of my very favorite tricks in python: default values are just references to whatever you passed in.  If it's a mutable object, it just comes along for the ride.
Another I don't get to use often -- currying!
Running the Server:
Run the chat script from python (for example, python chat.py) and then point your browser at http://localhost:8080 to see something like

Python, 442
This one is actually nice to use.  This is golf, so I consider this a less-satisfactory solution.  Now, I abuse an iframe and a form with keyhandling... and a meta refresh to poll for new content.
import time,cherrypy as S
class C:
 c=S.expose(lambda s:"<form action=w target=t method=post><input name=n><input name=p onkeyup='if(event.keyCode==13){this.form.submit();this.value=\"\"}'>
")
 @S.expose
 def w(s,n='',p='',l=[],u={}):u[n]=time.time();l+=p and[n+':'+p];return'<meta http-equiv=refresh content="1;url=w?n=%s">'%n+','.join(k for k in u if(u[n]-9<u[k])*k)+'
'+'
'.join(l[::-1])
S.quickstart(C())

I doubt I can point my browser at http://localhost:8080/c
and access your HTTP server

@JanDvorak That's why I didn't make that a link.

For those who already have a service running on port 8080, you may prepend the following to use a different port: S.config.update({'server.socket_port':8090})

How difficult would it be to update the chat window when anybody sends a new message, and not just the user? (In its current form, in order to check if there are any new messages, you need submit a blank message before your window is updated.)

@primo "Submitting" a blank message doesn't actually post text

@boothy but it did refresh the message window. No longer necessary in your new version, though.

@primo Right!  That's how you check to see if people have said something.  The problem said to reenact the 90's.  And back then, expecting your users to accept the interface suggested by the simplest code was still cool.  HP gave us RPN, and we liked it.  Thinking like a 201*-er gets you 1280 characters of bloat.

I suppose you have a point. If you give people what they want, they'll be willing to put up with a lot of crap. Internet advertising is based largely on that principle.

@primo hah!  Just saved another 20 characters.  I bet your server can't be killed by a user sending a name or message containing a %.  Bug?  I say "feature"!

Node/Meteor javascript + html + css + websocket: 1,105 bytes
Here's one using node.js/meteor. Obviously written in js, realtime, and using websockets.  Uses meteor's default built-in packages.
It could be a lot smaller.  Also it's persistent by way of the included mongo (not that that is a good thing).
A working screenshot:

To execute, install meteor.
Linux:
curl https://install.meteor.com | /bin/sh`

Windows: win.meteor.com
Clone my repo and execute meteor:
git clone http://github.com/bradgearon/meteor-chat
cd meteor-chat
meteor

point your browser to localhost:3000
chat.js: 703 bytes (client/server):
l='subscribe',d=[],n='n',i='i',b='b',c='click #',r='return ',u='u',y=0
f=Function,m=Meteor,o=m.Collection,p=new o(b),t=new o(u)
w=f('t.remove({i:d.pop()})'),g=f('_(d.length).times(w)')
m.isClient&&(h=Template.h,e=h.events={},m[l](b),m[l](u),s=Session,
w=f(r+'s.get(i)'),h.p=f(r+'p.find()'),h.t=f(r+'t.find()'),a=f('a','a','y=$("#3").val(),s.set(i,1)'),
e[c+'2']=f('p.insert({c:(y||"?")+": "+$("#l").val()})'),
e[c + '4'] = f('w()||m.call("x",$("#3").val(),t._connection._lastSessionId,a)')
)||(
m.startup(f('t.remove({}),p.remove({}),m.setInterval(g,100)')),j=f('h=this.id;h&&d.push(h)'),
m.methods({x:f('k','d','s=m.default_server.sessions[d].socket,s.on("close",j),t.insert({n:k,i:s.id})')}))

chat.css: 132 bytes
g{display:block;overflow-y:scroll;margin:10px;}
n{float:right;width:40%;min-height:100%;}
d{float:left;width:60%;min-height:100%;}

chat.html: 270 bytes

    {{> h}}

<template name="h">
<d>
<g>{{#each p}}{{c}}
{{/each}}</g>
<input id=l>{{this.k}}</input>
<input type=submit id=2 />
</d>
<n>
<g>{{#each t}}{{n}}
{{/each}}</g>
<input id=3 />
<input type=submit id=4 />
</n>
</template>

Welcome to codegolf! That file chat.html seems to only have 254 bytes.  Note that browsers aren't terribly picky -- I don't bother to close tags, and you definitely don't need the slash at the end of tags (unless node requires it?).  Also, kill more whitespace!  I see a couple in the javascript, and way too much in the html.

Meteor: 575 characters
I had a lot of fun with this one! The application is live at http://cgchat.meteor.com/.
chat.html: 171 characters
{{>b}}<template name="b">{{#if l}}Online: {{#each u}}{{n}}, {{/each}}
{{#each m}}{{n}}: {{t}}
{{/each}}
<input>{{else}}Name: <input>{{/if}}</template>

lib/chat.js: 45 characters
c=Meteor.Collection;u=new c('u');m=new c('m')

client/client.js: 359 characters
j=$.now;s=Session;t=Template.b;t.events({'change input':function(){v=$('input').val();s.get('u')?(m.insert({n:s.get('u'),t:v}),u.update(u.findOne({n:s.get('u')})._id,{$set:{l:j()}})):(s.set('u',v),u.insert({n:v,l:j()}))}});t.l=function(){return !!s.get('u')};t.u=function(){return u.find({l:{$gt:(j()-20000)}}).fetch()};t.m=function(){return m.find().fetch()}

Link is now dead.


text:
highest common factor-fewest iterations
Find the highest common factor of two(positive integer) input numbers (not greater than 5000) in the minimum number of iterations.
If you use a loop, it should increment a counter, starting at 0 for the first run. The counter should be the first statement in the loop. If you use more than one loop, they too should have a similar counter.
So
counter_1=0;
counter_2=0;
...
loop{
    counter_1=counter_1 + 1;
    ...
    code
    ...

    loop_nested{
        counter_2=counter_2 + 1;
        ...
        code
        ...
    }
}
total_count=counter_1 + counter_2 + ...

Test cases
first-number second-number-->expected-output
450 425-->25
27 23-->1
1000 1001-->1
36 54-->18
2 4000-->2
4000 2500-->500
2000 4000-->2000
99 75-->3
584 978-->2
3726 4380-->6
The code with the lowest sum of all counters for all test cases wins.
There is no restriction on program length. Of course, you can't use any standard functions. There is no restriction on the language that you use.
Also, please write the sum of counters that your code produces.

In array-oriented languages like APL, J or R, this could be done without writing any (overt) loops at all, even without using the built-in GCD function.

Heck, it can be done even in GolfScript without any explicit loops!

Voting to close because without a clear definition of "standard function" or "loop" (does recursion count? period-n quines? etc.).

C, no loops -> 0 iterations
#include <stdlib.h>
#include <stdio.h>

#define Q(n) (a % (n) == 0 && b % (n) == 0) ? (n) :
#define R(n) Q((n)+9) Q((n)+8) Q((n)+7) Q((n)+6) Q((n)+5) Q((n)+4) Q((n)+3) Q((n)+2) Q((n)+1) Q(n)
#define S(n) R((n)+90) R((n)+80) R((n)+70) R((n)+60) R((n)+50) R((n)+40) R((n)+30) R((n)+20) R((n)+10) R(n)
#define T(n) S((n)+900) S((n)+800) S((n)+700) S((n)+600) S((n)+500) S((n)+400) S((n)+300) S((n)+200) S((n)+100) S(n)
#define U(n) T((n)+4000) T((n)+3000) T((n)+2000) T((n)+1000) T(n)

int main (int argc, char *argv[]) {
  int a, b, gcd;
  if (argc <= 2) {
    fprintf(stderr, "Usage: %s <num1> <num2>\n", argv[0]);
    return 1;
  }

  a = atoi(argv[1]);
  if (a < 1 || a > 5000) {
    fprintf(stderr, "Input %d out of range!\n", a);
    return 1;
  }

  b = atoi(argv[2]);
  if (b < 1 || b > 5000) {
    fprintf(stderr, "Input %d out of range!\n", b);
    return 1;
  }

  gcd = U(1) 0;

  if (gcd) {
    printf("The greatest common divisor of %d and %d is %d.\n", a, b, gcd);
  } else {
    fprintf(stderr, "Unable to find gcd of %d and %d! Inputs out of range?\n", a, b);
  }
  return 0;
}

Given that you've specified an upper limit of 5000 on the input values, this challenge can be solved in any language without any (runtime) loops just by taking a trivial solution using a single trial-division loop and unrolling it 5000 times.
I've chosen to use C, since the C macro preprocessor allows the solution to be written in a compact manner.  The macros will be expanded at compile time into a single huge nested ternary ?: expression.
(If you consider the compile time macro expansion to be a loop in disguise, feel free to run the code above through the C preprocessor and consider the expanded output — which is also a valid C program — to be my solution.  I won't include the expanded version in this post, though, since it's huge.)

Along similar lines to Ilmari's solution, but slightly shorter (comparing expanded versions):
#include <stdlib.h>
#include <stdio.h>

#define D(pn, p) (a%(pn) + b%(pn) ? 1 : (p))
#define P(p) D(p, p)
#define P2(p) D(p, p) * D(p*p, p)

int main (int argc, char *argv[]) {
    int a, b, t, gcd;
    if (argc != 3) return 1;

    a = atoi(argv[1]);
    b = atoi(argv[2]);
    if (a < 1 || a > 5000 || b < 1 || b > 5000) return 1;

    // Force an order: a <= b
    if (a > b) {
        t = a; a = b; b = t;
    }

    gcd = (a == b || a*2 == b || a*3 == b || a*4 == b || a*5 == b ||
           a*3 == b*2 || a*5 == b*2 || a*4 == b*3 || a*5 == b*3 ||
           a*6 == b*5) ? a :
            ((a|b) & -(a|b)) *
            P(3) * D(9, 3) * D(27, 3) * D(81, 3) * D(243, 3) * D(729, 3) *
            P(5) * D(25, 5) * D(125, 5) * D(625, 5) *
            P(7) * D(49, 79) * D(343, 7) *
            P2(11) * P2(13) * P2(17) * P2(19) * P2(23) *
            P(29) * P(31) * P(37) * P(41) * P(43) * P(47) * P(53) * P(59) *
            P(61) * P(67) * P(71) * P(73) * P(79) * P(83) * P(89) * P(97) *
            P(101) * P(103) * P(107) * P(109) * P(113) * P(127) * P(131) *
            P(137) * P(139) * P(149) * P(151) * P(157) * P(163) * P(167) *
            P(173) * P(179) * P(181) * P(191) * P(193) * P(197) * P(199) *
            P(211) * P(223) * P(227) * P(229) * P(233) * P(239) * P(241) *
            P(251) * P(257) * P(263) * P(269) * P(271) * P(277) * P(281) *
            P(283) * P(293) * P(307) * P(311) * P(313) * P(317) * P(331) *
            P(337) * P(347) * P(349) * P(353) * P(359) * P(367) * P(373) *
            P(379) * P(383) * P(389) * P(397) * P(401) * P(409) * P(419) *
            P(421) * P(431) * P(433) * P(439) * P(443) * P(449) * P(457) *
            P(461) * P(463) * P(467) * P(479) * P(487) * P(491) * P(499) *
            P(503) * P(509) * P(521) * P(523) * P(541) * P(547) * P(557) *
            P(563) * P(569) * P(571) * P(577) * P(587) * P(593) * P(599) *
            P(601) * P(607) * P(613) * P(617) * P(619) * P(631) * P(641) *
            P(643) * P(647) * P(653) * P(659) * P(661) * P(673) * P(677) *
            P(683) * P(691) * P(701) * P(709) * P(719) * P(727) * P(733) *
            P(739) * P(743) * P(751) * P(757) * P(761) * P(769) * P(773) *
            P(787) * P(797) * P(809) * P(811) * P(821) * P(823) * P(827) *
            P(829);

    printf("The greatest common divisor of %d and %d is %d.\n", a, b, gcd);
    return 0;
}

Ruby
def gcd(a,b)
  ('x'*a+' '+'x'*b).gsub(/^(.*)\1* \1+$/,'\1').length
end

A completely different solution - no explicit loops either.

Tcl, 0 loops.
Some languages don't even have loops, they use recursion.
Note: if you don't use Tcl 8.6, replace tailcall with return [...]
proc gcd {a b} {
    if {$b > $a} {tailcall gcd $b $a}
    if {$b == 0} {return $a}
    tailcall gcd $b [expr {$a % $b}]
}

Well, and here for the people that said recursion is a loop:
proc gcd2 {a b {i 0}} {
    if {$b > $a} {lassign [list $a $b] b a}
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
}

Tail reucrsion is a form of looping, really :)

Well, because of the upper limit of 5000, I could replace the tail recursion with the procedure itself.

APL (0 loops)
All right, after some people have posted even smarter ideas I might as well post this one, which I wrote to support my comment. It has no loops or recursion expressed in it.
∇GCD;divs;gcd
  divs ← {A/⍨A=⌈A←⍵÷⍳⍵}
  gcd  ← {⊃A/⍨(A←divs⍺)∊divs⍵}
  ⎕ ← ⎕ gcd ⎕
∇

For people who are not familiar with reading APL, I'll give all explict looping constructs that I know of below:

:For ... :EndFor (for loop)
:While ... :EndWhile (while loop)
fn¨list (apply fn to each element in list)
fn⍣N (apply fn N times)
fn⍣condfn (apply fn, until (condfn( x, fn( x ) ) is true)
{...∇...}: recursion ({...} is a function, ∇ refers to the function it is used in)

Explanation of the program:

divs: (get divisors of a number, in descending order)

A/⍨A=⌈A: select from A those elements where A is equal to ceil(A)
A←⍵÷⍳⍵: ...where A is the right argument (⍵) divided (÷) by the numbers from 1 to ⍵ (⍳⍵)

gcd: (get the greatest common denominator of two numbers)

⊃: get the first (thus, biggest, see above) element of:
A/⍨: the elements selected from A, where...
(A←divs⍺): A, which is the divisors of the left argument,
...∊divs⍵: ...is a member of the divisors of the right argument.

⎕ ← ⎕ gcd ⎕: output (⎕ ←) the GCD of input (⎕) and input (⎕).

Hi marinus, some of the characters are rendering as the 'not found' square when I look at this on Safari (OS X) – is there any chance you could clarify?

source: Stack Exchange

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

sort: votes


text:
Build a perfect AI for the game 15
In the game 15, two players take turns selecting numbers from 1 to 9 (without choosing any number that either player has already selected). A player wins if he or she has three numbers that add up to 15. If all the numbers have been selected and no combination of either player's adds up to 15, then the game is a tie.
Your task is to build a function that takes the state of a game of 15 (represented in any form you like) and returns which number to move next, which will act as an AI to play the game with another player. You may assume that the position is legal (no player has more than one number more than the other player, and no player already has three numbers that add up to 15).
The AI must be perfect - that is, if it's given a winning position, it must force a win, and if it's given a non-losing position (a position where its opponent does not have a winning strategy), it must not allow its opponent to give it a losing position (which is possible, as 15 is a solved game).
The shortest code wins.
(note: I will accept the currently shortest answer and change it if a shorter answer appears.)

Do I understand correctly we are allowed to lose if we get into a winnable position that our AI couldn't have got into?

Yes, that is correct. If the AI is presented with a game state that it cannot win or tie (e.g. a double trap), then it is allowed to lose. However, the AI should never allow the game to get into said losing state from an empty board.

do I assume correctly the AI is always the first to play?

No, the AI can play second as well, but either way the game is solved (with perfect play, the game will always end in a tie).

hmm... it seems we are allowed to draw even if we can force a win. Is that true?

Well, I guess it should win if given the opportunity.

well, mine does :-)

I should clarify: "the AI should never allow the game to get into said losing state from an empty board" or from any other non-losing position.

"Do I understand correctly we are allowed to lose if we get into a winnable position that our AI couldn't have got into?" – Jan Dvorak yesterday
"Yes, that is correct. ..." – Joe Z. yesterday

I think I misunderstood your question then. What I meant is, if the AI is presented initially with a position that's "winnable" from the other side, it's allowed to lose because the other side has a winning strategy and there's absolutely nothing the AI can do. Otherwise the AI must prevent a loss if possible, including taking full advantage of the other player screwing up a winning position by making a wrong move.

what is the intention of the word "initially" in that statement? I will update my answer, however

If the AI is given a garbage input like [6 7 9][1 2 4 8] (in which case 3 and 5 is a double trap) without having made any moves itself (but just having [6 7 9][1 2 4 8] as a starting position), that's considered an "initial losing position". Then it's allowed to make a losing move because it has no other choice. But from an empty board, the AI should never allow [6 7 9][1 2 4 8] to be reached.

Hah.  I just learned about this game, and the first thing when I got home was to post it here.  Alas, I've been beaten to it.

GolfScript (129 86 81 85 75 chars)
{:C[{.`{1$-\{+15\-}+%}:T+/}/10,1>C~+-:^{.{^T&}+C/,2<*T}/5^{1&}$][]*^&0=}:N;

Expected input format: [[int int ...][int int ...]] where the first list is my numbers and the second list is my opponent's numbers. For interactive testing, add ~N to the end of the script and supply a string in that format: e.g.
$ golfscript.rb 15.gs <<<"[[5][2 8]]"
9
$ golfscript.rb 15.gs <<<"[[2][5 8]]"
6

Heuristics:

If I can win this turn, do it
If opponent would win next turn, block
If I can force opponent to a square which prevents them from creating a fork, do it
5 is the only number which can contribute to winning in 4 ways, so grab it if available.
Favour evens over odds

Test framework:
{:Set;[1 5 9 1 6 8 2 4 9 2 5 8 2 6 7 3 4 8 3 5 7 4 5 6]3/{.Set&=},!!}:isWin;
{
    # Mine His
    .isWin{
        "Lost "@`@`++puts
    }{
        # If there are available moves, it's my move.
        # If I won before my move, I've still won after it.
        1$1$+,9<!!{
            # my move
            1$1$[\\]N 2$\+
            # Mine His Mine'
            .isWin!{
                # his move
                10,1>2$2$+-{
                    2$\+1$\
                    # Mine His Mine' Mine' His'
                    fullTest
                    # Mine His Mine'
                }/
            }*;
        }*;;
    }if
}:fullTest;
# I move first
'[][]fullTest'puts [][]fullTest
# He moves first
'[][1]fullTest'puts [][1]fullTest
'[][2]fullTest'puts [][2]fullTest
'[][5]fullTest'puts [][5]fullTest

Can you run this input through for me: [5][3] (should return either 4 or 8).

9 - but then you seem to have changed the rules.

Also, why only 4 or 8?

Oh wait, never mind, I was wrong. Anything except for 7 should work, so 9 is acceptable.

Also, I didn't mean to change the rules; it's just that I'd phrased them wrong the first time around.

@JoeZ., including a good set of test cases is a good way to ensure that if you misphrase something it gets picked up early.

Alright, I'll include the test suite that I personally use as a strategy for 15.

Ruby, 330 315 341 characters
def m i
$_=i.join
l='159258357456168249267348'.scan /(.)(.)(.)/
return 1 if /^5(28|46|64|82)$/
return 4 if /^[258]{3}$/
return 2 if /^[456]{3}$/
i.each{|i|l.map{|l|return l if(l-=i).size==1&&!/[#{l=l[0]}]/}}
.map{|i|l.map{|m|l.map{|l|return (l&m)[0] if(z=l-i|m-i).size==3&&l!=m&&!/[#{z.join}]/}}}
"524681379".chars{|z|return z if !/#{z}/}
end

I'll withhold the details for now, but let's say that it is based on the optimal algorithm to a similar problem that has been solved as well and whose optimal algorithm happened to work just as fine here. Assumptions have been made - this will choose bad moves in situations that cannot be produced by this algorithm playing against another player, only by two players against each other.
Input: an array of two arrays of one-digit strings. Each array represents the values taken by one player - the first one is the AI, the second one is the opponent.
Output: either a number, or a single-digit string. They are semantically equivalent. Normalisation to strings would cost 8 characters.
Three more characters can be saved if we assume the order of numbers given by the caller - change the regex in L5 to /^285$/ or /^258$/ depending on the order produced from the game (opponent)5-(ai)2-(opponent)8.

Looks like you have an easy saving in the last three lines by simply moving 5 to the start of your preference order.

@ah, yes, thanks. I had another step in between that I removed (special-cased to the top) and I forgot to merge the surrounding steps. I'll edit when I get home (unless you volunteer to before).

GolfScript (90 85 84 chars)
{.~.,3/*..2%.@^++3*3/{~++15=},,*10,1>2$~+-@`{([2$+]+v[0=~)\]}+%[1,]or$0=+}:v{1=}+:N;

This takes a completely different approach, but is potentially susceptible to optimisations to beat the heuristic one. Here we do a full game tree analysis, incredibly slowly. (No, I mean it. It takes several hours to run the full test, mainly because of the `{...}+ which adds the current state to the next-move loop). Note that the hard part is identifying a winning state (a third of the code, at present).
There are some ugly hacks in the non-recursive sections. In particular, when the position is identified as a losing one we take our positions as the [value move] array, relying on the move being irrelevant and the value being non-zero.

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


text:
Build a NAND gate using multiple NAND gates
A question that had popped up in my head once - how many NAND gates would it take to build a larger, "meta-NAND" gate?
Your task is to build a black-box circuit that takes two input wires A and B and returns one output wire that satisfies A NAND B, subject to the following restrictions:

You must use at least two NAND gates in this construction (and no gates other than NAND).
You may not have null configurations of gates - that is, systems of gates that are equivalent to a gateless wire. (For example, two NOT gates in series are a null configuration.)
You cannot have any stray wires (discarded values or constants).

Fewest gates wins.

4 gates
(A NAND B) AND-using-NAND (A NAND B)
A---NAND        _
 \ /    \      / \
  X      NAND-<   NAND-->
 / \    /      \_/
B---NAND

Three gates.  Compute (((A nand A) nand B) nand B).  Unlike the four-gate solution above in which three of the four gates compute A nand B, two of them simultaneously, and substituting one of the simultaneous outputs for the other would yield two consecutive inverters, the three-gate solution uses the three gates to compute different functions: "not A", "A or not B", and "A nand B".  Only the last gate computes the desired function.

3 gates
   /-----------\
A-<             \
   \-----\       \
          \       NAND--
           NAND--/
B-<NAND---/

Duplicate of this answer, (but with A and B switched)


text:
Simulate a battle between two creatures
Welcome, brave code golfer! Today you will stand in the midst of a great battle between a goblin and an elf!
    goblin attacks elf!
    elf dodges!
    elf attacks goblin!
    elf hits goblin for 13 damage!
    goblin has 37 health left.
    goblin attacks elf!
    goblin hits elf for 1 damage!
    elf has 49 health left.
    elf attacks goblin!
    elf hits goblin for 19 damage!
    goblin has 18 health left.
    goblin attacks elf!
    goblin hits elf for 26 damage!
    elf has 23 health left.
    elf attacks goblin!
    elf hits goblin for 20 damage!
    goblin has been slain!

The Challenge
Your challenge is to simulate a battle, like the above one. You will recieve input in this form:
creatureName health strength defense accuracy agility

For example, the battle between the goblin and elf would be:
goblin 50 40 35 3 2 elf 50 35 30 4 5

The first and second creatures will alternate attacks.

Print 'creatureName attacks otherCreatureName!'
Check to see if the creature dodges. The creature will dodge an attack if (its agility times rand() divided by 2) is greater than (the attacker's accuracy times rand()).

If the creature dodges, print 'creatureName dodges!'
Otherwise, calculate the damage dealt by subtracting (the attacker's strength times rand()) and (the defender's defense times rand() divided by 2). Minimum damage is 1. Print 'creatureName hits otherCreatureName for (x) damage!' Then print 'creatureName has (x) health left.' unless the creature's health is 0 or less, in which case...

If the creature's health is 0 or less, print 'creatureName has been slain!' and end the program.

Rules

Shortest code wins.
Don't literally print 'creatureName,' but replace it with the creature's name. Don't print '(x) damage' or '(x) health;' replace them with the actual amount. (I have to specify this because some people are very creative with bending the rules. :P)

Why complicate the spec by halving the agility and defence?

@Peter Because otherwise the battles took too long.

My point was: why not change the input e.g. to goblin 50 40 18 3 2 elf 50 35 15 4 5?

@Peter Meh, that just seemed too odd - why would the defense be so much lower? Anyway, it is a puzzle; no reason not to :P

I think it's not clear whether 'creatureName has (x) health left.' should be printed on the last round (when the creature is slain), and in case it should (i assumed it shouldn't) if (x) should be always 0 or it can be a negative number.

@epid See sample output.

@Doorknob, yes; i was referring to the battle steps' description. But you're right, it's clear from the sample output.

@epid Yes, the steps were unclear; I tried to clarify them a bit.

btw, nice challenge =)

I squeezed 4 from my solution by switching to raw_input, but this means the input now needs to be quoted. Not sure if this means I need to add 2 to the score for the quotes or not.

@Lego Meh, some programs are run much more verbosely; I'd consider that as part of the execution. Don't add 2.

APL (249 244 242)
Procedural style this time, so (in Dyalog at least) you have to paste this into an editor window. I named it G (the first line is the name, I've included it because that's how it shows up in the editor window so it should probably be counted).

G
⎕ML←3
D A←{(⊂↑⍵),⍎¨1↓⍵}¨↓2 6⍴A⊂⍨' '≠A←⍞
→5
⎕←(↑D)'dodges!'
A D←D A
⎕←(↑A)'attacks','!',⍨↑D
→4/⍨>/?A[6],D[5]
⎕←A[1],'hits',D[1],'for','damage!',⍨D[2]-←1⌈-/?A[3],⌈D[4]÷2
→12/⍨D[2]≤0
⎕←D[1],'has',D[2],'health left!'
→5
⎕←D[1],'has been slain!'

(edit: used numeric GOTOs instead of line labels. Turns out that (in Dyalog at least) all defining a label X: does is set X to the line number, so might as well use the numbers directly.)

Perl, 254 + 1
for((@a[0..5],@b)=split;$a[1]>0;@c=@a,@a=@b,@b=@c){say"$a[0] attacks $b[0]!\n",rand$b[5]/2<rand$a[4]?do{($==rand($a[2])-rand$b[3]/2)<1and$==1;"$a[0] hits $b[0] for $= damage!\n$b[0] has ",($b[1]-=$=)>0?"$b[1] health left.":"been slain!"}:"$b[0] dodges!"}

Run with perl -nM5.010 (or perl -nE '<code>').  Per meta, the -n switch counts as one extra character.
No fancy golfing tricks in this code, except maybe the use of $= as the damage variable to save an int.
Edit: Hopefully, the damage calculation is correct now.

Ruby, 292 264
v=$*
def p*a;puts a*' 'end
loop{a,b=v[0],v[6]
w=v.map &:to_i
p a,:attacks,b+?!
w[11]*rand/2>w[4]*rand ? (p b,:dodges!):(h=v[7]=w[7]-=d=[rand(w[2])-rand(w[9])/2,1].max
p a,:hits,b,:for,d,:damage!
p b,:has,h<1?"been slain!":"#{h} health left."
h<1&&exit)
v.rotate!6}

My first code golf entry; how that method definition parses is beyond me :)
Is it OK to read the input from command-line parameters (e.g. ruby battle.rb goblin 50 40 35 3 2 elf 50 35 30 4 5)?
Ideone run

Yes, that is okay.

CoffeeScript 454 432
Pass a string to b to get the results.  I thought it would be more fun to have a graphic animated output, so I put a demo together.  Just change the input box to change statistics and names.  The pictures from from jpg.to which is the unofficial google-images API.
Super Action Demo

b=(s)->
 r=Math.random
 p=s.split ' '
 n=p.map Number
 l=''
 o=(x...)->l+=x.join(' ')+'!\n'
 while 1|i=!i
  c=(x)->n[i*6+x]*r()
  d=(x)->n[(i||6)+x]*r()
  t=->d(4)/2>c 5
  h=->Math.max c(2)-d(3)/2,1
  a=p[i*6]
  b=p[6+i*-6]
  o a,'attacks',b
  if c(5)/2>d 4
   e=Math.ceil h()
   q=n[(i||6)+1]-=e
   o a,'hits',b,'for',e,'damage'
   o b,'has',q,'health left'if q>0
  else
   o b,'dodges'
  if q<1
   o b,'has been slain'
   break
 l

Recommended Inputs (suggest your own):
charmander 50 40 25 3 2 bulbasaur 90 30 40 4 5
voldemort 9999 10 5 1 1 batman 20 50 10 1010 30

Wow, that's great! :D I would accept this answer if I could accept two, but I said in the rules that the shortest would be accepted, and I can only accept one answer :( So +1. And voldemort 9999 haha :D

@Doorknob, as an extra bonus, you can give it numbers like 10e42, but your browser may freeze...

JavaScript; 347 341 333
As I always do, I shall start off with my own solution:
for(m=prompt().split(' '),r=Math.random,a=console.log,c=0,d=6;;){if(a(m[c]+' attacks '+m[d]+'!'),r()*m[c+4]>r()*m[d+5]/2){if(a(m[c]+' hits '+m[d]+' for '+(h=Math.max(~~(r()*m[c+2]-r()*m[d+3]/2),1))+' damage!'),(m[d+1]-=h)<1){a(m[d]+' has been slain!');break}a(m[d]+' has '+m[d+1]+' health left.')}else a(m[d]+' dodges!');t=c;c=d;d=t}

EDIT: apparently assigning console.log to a variable breaks on some browsers, so here's the same code with a function declaration instead:
for(m=prompt().split(' '),r=Math.random,a=function(x){console.log(x)},c=0,d=6;;){if(a(m[c]+' attacks '+m[d]+'!'),r()*m[c+4]>r()*m[d+5]/2){if(a(m[c]+' hits '+m[d]+' for '+(h=Math.max(~~(r()*m[c+2]-r()*m[d+3]/2),1))+' damage!'),(m[d+1]-=h)<1){a(m[d]+' has been slain!');break}a(m[d]+' has '+m[d+1]+' health left.')}else a(m[d]+' dodges!');t=c;c=d;d=t}

I was thinking of changing it to alert, but that would just be evil :P

i get a Uncaught TypeError: Illegal invocation because of a=console.log. would'nt you have to bind the console object  as context, e.g a=console.log.bind(console)?

@C5H Hmm, that's odd. It works for me.

Just checked it in Firefox,Safari and Chrome, in Firefox it works =) Chrome gives me above, and Safari a TypeError

@C5H :( Maybe I could replace it with alert, but that would be very annoying :P

:P Yes that would be indeed annoying, but at least it would save "6" characters and avoids the TypeError =)
But i guess its Ok, at least it runs on Firefox =)

JavaScript: 340 306
339:
for(m=Math.random,a=prompt().split(" "),c=[a,a.splice(6)],e;0<+c[0][1]&&0<+c[1][1];)c.reverse(),console.log(c[0][0]+" attacks "+c[1][0]+"!\n"+(c[0][4]*m()<c[1][5]*m()/2?c[1][0]+" dodges!":c[0][0]+" hits "+c[1][0]+" for "+(e=1+(c[0][2]*m()-c[1][3]*m()/2|0))+" damage!\n"+c[1][0]+" has "+(0>(c[1][1]-=e)?"been slain!":c[1][1]+" health left.")))

306:
for(var m=Math.random,a=prompt().split(" "),b=a.splice(6),d,e;0<+a[1]&&0<+b[1];d=a,a=b,b=d)console.log(a[0]+" attacks "+b[0]+"!\n"+(a[4]*m()<b[5]*m()/2?b[0]+" dodges!":a[0]+" hits "+b[0]+" for "+(e=a[2]*m()-b[3]*m()/2|0,e<=0?e=1:e)+" damage!\n"+b[0]+" has "+(0>(b[1]-=e)?"been slain!":b[1]+" health left.")))

Sample output:
goblin attacks elf!
elf dodges!
elf attacks goblin!
elf hits goblin for 21 damage!
goblin has 29 health left.
goblin attacks elf!
elf dodges!
elf attacks goblin!
elf hits goblin for 15 damage!
goblin has 14 health left.
goblin attacks elf!
goblin hits elf for 1 damage!
elf has 49 health left.
elf attacks goblin!
elf hits goblin for 16 damage!
goblin has been slain!

Edit notes: +1 character, i missed the "!" after "dodges" Oh and i forgot to actually put an output after "Sample output"Changed the header to JavaScript, as @tbodt suggests

Why don't you call it JavaScript to avoid confusing people?

@tbodt I didn't thought it would confuse people =) Changed it to Javascript instead

Python: 393
I squeezed a little harder, if I had 3 I could probably do print = p to shorten it by a few more, but I don't think there is much left in this one.
393:
from random import randrange as r
x = input().split()
t=range
a,b=6,0
for i in t(1,6)+t(7,12):x[i]=int(x[i])
while x[b+1] > 0:
 a,b=b,a;print x[a]+" attacks "+x[b]
 if r(x[a+5]/2)>r(x[b+5]):print x[a]+' dodges!';continue
 d=max(r(x[a+2])-r(x[b+3]/2),1);print x[a]," hits ",x[b]," for ",d," damage!";x[b+1]-=d
 if x[b+1]>0:print x[b]," has ",x[b+1]," health left."
print x[b]," has been slain"

399:
from random import randrange as r
x = raw_input().split()
t=range
a,b=6,0
for i in t(1,6)+t(7,12):x[i]=int(x[i])
while x[b+1] > 0:
 a,b=b,a;print x[a]+" attacks "+x[b]
 if r(x[a+5]/2) > r(x[b+5]):print x[a]+' dodges!';continue
 d=max(r(x[a+2])-r(x[b+3]/2),1);print x[a]," hits ",x[b]," for ",d," damage!";x[b+1]-=d                        if x[b+1]>0:print x[b]," has ",x[b+1]," health left."
print x[b]," has been slain"

I think people are skipping that if you have a good condition in the loop, you don't need to check if the target is below health.

I check the health twice, in the loop header to end the battle, and in the loop to print either "has been slayed" or "hits ...", because the double health check is shorter than an extra console.log

R: 387 characters
a=scan(,"");i=as.integer;r=runif;C=cat;X=data.frame(i(a[2:6]),i(a[8:12]));z=1;Y=c(a[1],a[7]);repeat{p=1+z%%2;n=X[,p];m=X[,-p];N=Y[p];M=Y[-p];C(N,"attacks",M,"\n");if(r(1)*n[5]<r(1)*m[5]/2){C(M,"dodges!\n")}else{C(N,"hits",M,"for",d<-max(round(n[2]*r(1)-m[3]*r(1)/2),1),"damages!\n");h=max(m[1]-d,0);if(h){C(M,"has",X[1,-p]<-h,"health left\n")}else{C(M,"has been slained!");break}};z=z+1}

Or fully-developed, with indentations and comments, to make things clearer:
a=scan(,"")                        # Read stdin as character vector
i=as.integer
r=runif
C=cat
X=data.frame(i(a[2:6]),i(a[8:12])) # Data frame with opponents stats
z=1                                # Turn counter
Y=c(a[1],a[7])                     # Vector of opponents name
repeat{                            # shorter than while(T)
    p=1+z%%2                       # R indexing starts with 1 not 0
    n=X[,p]                        # Attacking opponent stats
    m=X[,-p]                       # Defending opponent stats
    N=Y[p]                         # Attacking opponent name
    M=Y[-p]                        # Defending opponent name
    C(N,"attacks",M,"\n")          # By default, cat separates elements with a space
    if(r(1)*n[4]<r(1)*m[5]/2){
        C(M,"dodges!\n")
    }else{
        C(N,"hits",M,"for",d<-max(round(n[2]*r(1)-m[3]*r(1)/2),1),"damages!\n")
        h=max(m[1]-d,0)            # Health after the strike
        if(h){                     # If health is not 0
            C(M,"has",X[1,-p]<-h,"health left\n")
        }else{                     # If it is
            C(M,"has been slained!")
            break
            }
    }
    z=z+1
}

C# - 464 453 chars
After a couple of nights on this I can't seem to get even close to the other entries (not that surprising for C#). Still room for improvement I suspect. No especially clever tricks.
using System;using System.Linq;class P{static void Main(string[]a){int D,h=1,z=6;
var n=a.Select(x=>int.TryParse(x,out D)?D:0).ToList();var r=new Random();Func<int>
R=()=>r.Next(101);for(;h>0;z=z>0?0:6){D=(n[8-z]*R()-n[3+z]*R()/2)/100;var d=n[5+z]
*R()/2>n[10-z]*R();h=d?h:n[1+z]-=D=D<1?1:D;Console.Write("{0} attacks {1}!\n"+(d?
"{1} dodges!\n":"{0} hits {1} for {2} damage!\n")+(d?"":"{1} has {3}\n"),a[6-z],a
[z],D,h>0?h+" health left.":"been slain!");}}}

Commented:
using System;
using System.Linq;
class P
{
    static void Main(string[] a)
    {
        int D, // string to int parsing and attack damage
            h = 1, // health
            z = 6; // index

        // painful requirement to convert the input strings to integers
        var n = a.Select(x => int.TryParse(x, out D) ? D : 0).ToList();

        // set up a function to return a new random number
        var r = new Random();
        Func<int> R = () => r.Next(101);

        // we'll exit the loop when the defender's health (h) is <= 0.
        // z is used as an index offset to get values out of the list, it flips between 0 an 6 each round
        for (; h > 0; z = z > 0 ? 0 : 6)
        {
            // calculate damage
            D = (n[8 - z] * R() - n[3 + z] * R() / 2) / 100;

            // see if defender dodges
            var d = n[5 + z] * R() / 2 > n[10 - z] * R();

            // subtract health from defender if necessary. store health of defender in h
            h = d ? h : n[1 + z] -= D = D < 1 ? 1 : D;

            // print the round
            Console.Write(
                "{0} attacks {1}!\n" + (d ? "{1} dodges!\n" : "{0} hits {1} for {2} damage!\n") +
                (d ? "" : "{1} has {3}\n"), a[6 - z], a[z], D, h > 0 ? h + " health left." : "been slain!");
        }
    }
}

Python 3, 314
from random import*
r=random
p=print
I=input().split()
H=1
while H>0:s,a,H,D,G=map(int,I[2:5:2]+I[7::2]);N=I[6];p(I[0],"attacks",N+"!");I=I[6:]+I[:6];X=max(int(s*r()-D*r()/2),1)*(G*r()/2<a*r());I[1]=H=H-X;X<1and p(N,"dodges!")or p(I[6],"hits",N,"for",X,"damage!\n"+N,"has",["been slain!","%s health left."%H][H>0])


text:
Code that changes itself
Forward:
Depending on what language you use and what user you are logged in as this challenge could be dangerous so proceed with Caution!  You could delete something, fork bomb yourself, or worse...
Challange:
Write a program of n bytes which creates n copies of itself on disk, modifies the first byte of the first copy to an 8-bit value of your choosing,  modifies the second byte of the second copy to an a bit-value of your choosing, ... , modifies the nth byte of the nth copy of the program to an 8-bit value of your choosing, and then executes all n of the modified copies synchronously starting with the first and ending with the last, the program should print "alive", then program should then exit.
Scoring: Lowest Score Wins
Score = (-1 * (Number of times "alive" is printed)) + number of bytes in your program
RULES

Infinite loops in the program or one of its creations will disqualify an answer.
Number of times alive is printed has to be less than 1024.

Why this interests me:
I think a lot about the relationships between biology and analogies between living things and computer programs.  One of the qualities of living things is that they know how to reproduce.  One of the factors of replication that make evolution possible is that the replication is not perfect.  If one were to design artificial life it should have a very compact method of reproducing itself.  This is why I am turning to the code golf community to see what sort of strange ideas are out there.  Sorry for all the edits to this question.

So does “infinite loop” here mean “infinite loop given infinite memory”, or…? And is a program allowed to print “alive” as many times as it wants?

If you hover over the language-agnostic tag then you'll see that it says "This tag should not be used". Unfortunately we don't seem to have any active moderators to kill it with fire. I've replaced it with code-challenge because the question has to be tagged with something.

Are we allowed to replace some of the bytes with themselves? Makes it pretty easy if so.

You can replace the bytes with anything you wish.  My original thought was to replace the code with random bytes to replicate non perfect children found in genetics.  But you could seriously damage your computer.

@histocrat - It is wrong idea to replace some byte with itself.  Exact copy of main program can not be created as it will lead to never-ending recursion.

this is a lot harder than i have given it credit for... still struggling with it.

@EgorSkriptunoff Actually, the duplicate programs would probably be almost exactly identical to the original one, just with one constant declaration or #DEFINE directive tweaked a little bit.

Doesn't changing random bytes in the program (any program for that matter) lead to random errors when executing and cause the program to crash ? It this is the case then, wont the execution of the program be based solely on what 8-bit character you replace a byte with? @histrocrat : As Egor rightly mentiones, replacing a byte with itself might lead to infinite recursion. Oscar: A very interesting question though.

The question says you can change a byte to a value of your chosing not a random byte.

I have a handful of solutions that work if the programs are run sequentially. :/

overpopulation is just the human race fork bombing its operating system.

Perl, 167 - 973 = -806 142 - 55 = 87
Here's an entry in the proper spirit of this code challenge:
if($ARGV[0]=~s/r/X/){open F,$0;for(@x=split//,join"",<F>){
$c=$_++;open F,">$0~".++$x;print F@x;$_=$c}sleep 1;
fork||exit exec"perl $0~$_ @ARGV"for 1..@x}print"alive\n"

I forkbombed myself a few times in the process of writing this script. As a result, this version comes with a couple of safety features. First off is the sleep 1 just before the spawning loop. That leaves enough idle processing time to allow one to type killall perl, if and when such measures become necessary. The second safety feature is that the spawn loop is disabled by default. To run in full power, you need to supply the word reproduce as an argument on the command line.
(Seriously, it's embarrassing to acknowledge the number of times I've had to do a hard reboot today because of some bug in my script, before I finally got the balance right.)
The program ends up producing several thousand imperfect copies of itself, from which about one in eight succeeds in printing alive. Most of the copies have syntax errors and so don't get run. A handful of scripts run but produce invalid output.
Here's a sample test run. (Note that, due to the sleep, it takes several seconds before the spawning finally grinds to a halt and all the scripts stop running.)
$ mkdir run
$ cp changer run/
$ cd run
$ ls -l
total 4
-rw-r--r-- 1 breadbox breadbox 167 2013-07-19 21:35 changer
$ perl changer
alive
$ perl changer reproduce 2> /dev/null >> out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 2608 2013-07-19 21:35 out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 6404 2013-07-19 21:35 out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 9370 2013-07-19 21:35 out
$ ls -l out
-rw-r--r-- 1 breadbox breadbox 9370 2013-07-19 21:35 out
$ ls -l | wc -l
7691
$ grep -c alive out
973
$ cd ..
$ rm -r run/
$

Finally, I should note that the script has a bit of nondeterminism -- a common enough circumstance when starting up lots of child processes. As a result, the number of alives that get output varies a bit with each run. The highest count I've seen so far is 984, so I believe that it's not in any danger of exceeding the 1024 limit.

Here is my submission:
It's a program of o Bytes.  It created 0 copies of itself and modified all 0 bytes.  It prints out Alive 0 times for a total socre of -1*0+0=0
Feel free to smack me for this submission :)

This seems to be compliant with the rules as currently written. Carry on.

This site makes me laugh... have a look at this answer: http://codegolf.stackexchange.com/a/11797/8501

authors: Воля Або Смерть


text:
Strings: Microsoft interview
You are given an array of strings , you have to construct a single array containing all of them so that the same array of strings can be reconstructed from the large array. The strings may contain any ASCII character. How to determine length of the single large array?
Example= let a = ["asd";"dfg";"rew"]. Problem is to combine them in a single string in such a way that it can reconstructed. How to figure out the size of the string which will store the concatenation ?

Why is it even an array? Shouldn’t the result just be one string?

Simple - since ASCII is only 7 bits you can just use a value > 127 as a separator character between strings and some other value > 127 as a final terminator.

What are you actually asking for? A program? A mathematical expression of the output size as a function of input size? (The latter would seem to be ill-defined, because there are an infinite number of injections from arrays of strings to strings).

This was a very common in style in Apple ][ binaries. The high bit of the first character of each word was set. You know you can do this since ASCII was specifically mentioned and the high bit is never set for ASCII. This technique relies on strings that know their own length. We can assume this is the case, since the strings can "contain any ASCII" characters, so C style (null terminated) strings can't work.
For your example, using Python
>>> a = ["asd", "dfg", "rew"]
>>> ''.join(chr((ord(s[0])) | 128) + s[1:] for s in a)
'\xe1sd\xe4fg\xf2ew'

converting back to the original list
>>> (''.join('\x80'+chr((ord(c)) & 127) if c>'\x7f' else c for c in '\xe1sd\xe4fg\xf2ew')).split('\x80')[1:]
['asd', 'dfg', 'rew']

JavaScript, 6
This evaluates to a function. Works in Firefox.
uneval

More portably: JSON.stringify

@recursive: Oh, I missed that this wasn’t code golf.


text:
Flipping pancakes
In pancake sorting the only allowed operation is to reverse the elements of some prefix of the sequence.
Or, think of a stack of pancakes: We insert a spatula somewhere in the stack and flip all the pancakes above the spatula.
For example, the sequence 6 5 4 1 2 3 can be sorted by first flipping the first 6 elements (the whole sequence), yielding the intermediate result 3 2 1 4 5 6, and then flipping the first 3 elements, arriving at 1 2 3 4 5 6.
As there is only one operation, the whole sorting process can be described by a sequence of integers, where each integer is the number of elements/pancakes to include pr flip. For the example above, the sorting sequence would be 6 3.
Another example: 4 2 3 1 can be sorted with 4 2 3 2. Here's the intermediate results:
         4 2 3 1
flip 4:  1 3 2 4
flip 2:  3 1 2 4
flip 3:  2 1 3 4
flip 2:  1 2 3 4

The task:
Write a program which takes a list of integers and prints a valid pancake sorting sequence.
The list to sort can either be a space separated list from stdin, or command line arguments. Print the list however it is convenient, as long as it's somewhat readable.
This is codegolf!
Edit:
As I said in the comments, you don't need to optimize the output (finding the shortest sequence is NP-hard). However, I just realized that a cheap solution would be to throw out random numbers until you get the desired result (a [new?] type of bogosort). None of the answers so far have done this, so I now declare that your algorithm should not rely on any (pseudo-)randomness.
While you're all kicking yourselves, here's a bogopancakesort variant in Ruby 2.0 (60 characters), to rub it in:
a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort

Any valid sequence, or should it be a minimal length one?

Tiny typo: the second example shows 4 3 2 1 instead of 4 2 3 1

(My internet went down as I tried to edit this, so I post it again) @PeterTaylor I was tempted to include some sort of optimization into this, but chose not to. Finding the length of the minimal sequence is actually NP-hard, while the simplest, straight-forward algorithm can find a solution that at most will be 2n long. I don't really know how I would judge this as a code-challenge/optimal output thing, and I just like plain codegolf more :)

I wonder if anyone will post their entry from this challenge.

Does the sequence have to be contiguous values? Is 2 7 5 a valid input?

@hatchet No, it doesn't; 2 7 5 is valid input. There may also be duplicate values, e.g., 2 7 5 5.

ok, that wasn't obvious from the question. I think some of the answers don't handle those non-contiguous inputs correctly.

GolfScript, 34 / 21 chars
(Thanks @PeterTaylor for chopping 4 chars off)
~].{,,{1$=}$\}2*${.2$?.p)p.@\-+}/,

Online test
A shorter, 21 character version works for lists with unique items only
~].${.2$?.p)p.@\-+}/,

Online test
Both versions produce sub-optimal solutions.

Explanation for the shorter solution:
~]         # read input from stdin
.$         # produce a sorted copy from lowest to highest
{          # iterate over the sorted list
  .2$?     # grab the index of the element
  .p       # print the index
  )p       # increment and print the index
  .@\-+    # move the element to the front
}/
,          # leave the length of the list on the stack
           # this flips the reverse sorted list to become sorted

This uses a different algorithm to most of the others posted. Basically it grabs the smallest element of the list, and with two flips moves it to the front, preserving the other elements' order.
To move the nth element to the front:
1 2 3 4 5 6 7   # let's move the 3rd (0-based) element to the front
# flip the first 3 elements
3 2 1 4 5 6 7
# flip the first 3+1 elements
4 1 2 3 5 6 7

It repeats this operation for each element in order, and ends up with a reverse sorted list. It then flips the whole list to leave it fully sorted.

In fact the algorithm is a variation of a 90-char Python solution (my own, of course):
d=map(int,raw_input().split());i=0
while d:n=d.index(max(d));d.pop(n);print n+i,n-~i,;i+=1

I see you haven't come across one of GolfScript's useful quirks: you can use any token as a variable. You're not using & anywhere, so you should be able to replace s while & and remove the whitespace.

@PeterTaylor huh, I was wondering why you could use ^ as a variable in the fibonacci challenge ;) Thanks for the tip!

For input 3 2 1 I get 131211 which is not correct.

@Howard got it to work now

@Volatility The last change was a bit too much ;-) E.g. lists like 2 1 1 cannot be sorted any more.

@Howard ahh, dammit. Almost thought I had the lead there! ;)

Python, 91 90 chars
L=map(int,raw_input().split())
while L:i=L.index(max(L));print-~i,len(L),;L=L[:i:-1]+L[:i]

Flip the biggest pancake to the top, then flip the whole stack.  Remove the biggest pancake from the bottom and repeat.
i is the index of the biggest pancake.  L=L[:i:-1]+L[:i] flips i+1 pancakes, flips len(L) pancakes, then drops the last pancake.

I thought you were only allowed to make flips. (That is, I didn't think you could drop pancakes from the stack). Did I misunderstand the rules? Hmm. goes to read wiki page again Regardless, nice job :) Less than 100 characters is pretty amazing to me!

@WendiKidd Actually, what he means is that after flipping the biggest one to the bottom, he's just ignoring it and concerning himself with the pancakes on top of it.

@AJMansfield Ah, I see! Thanks, that makes sense. I can't read the code (I'm too new to Python) so I misunderstood the explanation :)  Thanks!

Pretty much an evolution of what I wrote before. I didn't think of removing elements because in the beginning I had to check for correctness of the output(i.e. is the list sorted afterwards?). By the way: I believe removing the comma from the print wont render the output unreadable(1 byte saved :)

@WendiKidd actually, on further inspection, it does indeed remove the pancakes; it only needs to figure out what the sequence of flips is, not actually sort the array.

print i+1 can be shortened to print-~i.

Ruby 1.9 - 109 88 79 characters
Much more compact version based on Keith's great python solution:
a=$*.map &:to_i;$*.map{p v=a.index(a.max)+1,a.size;a=a[v..-1].reverse+a[0,v-1]}

Original version:
a=$*.map &:to_i
a.size.downto(2){|l|[n=a.index(a[0,l].max)+1,l].map{|v|v>1&&n<l&&p(v);a[0,v]=a[0,v].reverse}}

If you don't care about spurious operations (reversing stacks of size 1, or reversing the same stack twice in a row) you can make it a bit shorter (96 chars):
a=$*.map &:to_i
a.size.downto(2){|l|[a.index(a[0,l].max)+1,l].map{|v|p v;a[0,v]=a[0,v].reverse}}

Takes the unsorted list as command-line args.  Example usage:
>pc.rb 4 2 3 1
4
2
3
2

GolfScript, 31 29 characters
~].${1$?).p.2$.,p>-1%\@<+)}%,

Another GolfScript solution, can also be tested online.
Previous version:
~].$-1%{1$?).2$>-1%@2$<+.,\);}/

How does it work: it flips the largest item to the top and then to the last place in the list. Since it is now in the correct position we can remove it from the list.
~]         # Convert STDIN (space separated numbers) to array
.$-1%      # Make a sorted copy (largest to smallest)
{          # Iterate over this copy
  1$?)     # Get index of item (i.e. largest item) in the remaining list,
           # due to ) the index starts with one
  .        # copy (i.e. index stays there for output)
  2$>      # take the rest of the list...
  -1%      # ... and reverse it
  @2$<     # then take the beginning of the list
  +        # and join both.
           # Note: these operations do both flips together, i.e.
           # flip the largest item to front and then reverse the complete stack
  .,       # Take the length of the list for output
  \);      # Remove last item from list
}/

Perl, 103 100 characters
Expects input on the command line.
for(@n=sort{$ARGV[$a]<=>$ARGV[$b]}0..$#ARGV;@n;say$i+1,$/,@n+1)
{$i=pop@n;$_=@n-$_-($_<=$i&&$i)for@n}

The solutions it prints are decidedly sub-optimal. (I had a program with much nicer output about 24 characters ago....)
The logic is kind of interesting. It starts by cataloguing the index of each item, were it in sorted order. It then iterates through this catalog from right to left. So applying a flip involves adjusting indexes below the cutoff value, instead of actually moving values around. After some finagling I also managed to save a few characters by doing both flips per iteration simultaneously.

Python - 282 characters
import sys
s=sys.argv[1]
l=s.split()
p=[]
for c in l:
 p.append(int(c))
m=sys.maxint
n=0
while(n==(len(p)-1)):
 i=x=g=0
 for c in p:
  if c>g and c<m:
   g=c
   x=i
  i+=1
 m=g
 x+=1
 t=p[:x]
 b=p[x:]
 t=t[::-1]
 p=t+b
 a=len(p)-n;
 t=p[:a]
 b=p[a:]
 t=t[::-1]
 p=t+b
 print p
 n+=1

My first ever code golf; I'm under no illusions I'll win, but I had a lot of fun. Giving everything one-character names sure makes it frightening to read, let me tell you! This is run from the command line, sample implementation below:
Python PancakeSort.py "4 2 3 1"
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]

There's nothing particularly special or inventive about the way I've gone about this, but the FAQ suggests posting a non-golfed version for interested readers, so I've done so below:
import sys

pancakesStr = sys.argv[1]
pancakesSplit = pancakesStr.split()
pancakesAr = []
for pancake in pancakesSplit:
    pancakesAr.append(int(pancake))

smallestSorted = sys.maxint
numSorts = 0

while(numSorts < (len(pancakesAr) - 1)):
    i = 0
    biggestIndex = 0
    biggest = 0
    for pancake in pancakesAr:
        if ((pancake > biggest) and (pancake < smallestSorted)):
            biggest = pancake
            biggestIndex = i
        i += 1

    smallestSorted = biggest  #you've found the next biggest to sort; save it off.
    biggestIndex += 1   #we want the biggestIndex to be in the top list, so +1.

    top = pancakesAr[:biggestIndex]
    bottom = pancakesAr[biggestIndex:]

    top = top[::-1] #reverse top to move highest unsorted number to first position (flip 1)
    pancakesAr = top + bottom   #reconstruct stack

    alreadySortedIndex = len(pancakesAr) - numSorts;

    top = pancakesAr[:alreadySortedIndex]
    bottom = pancakesAr[alreadySortedIndex:]

    top = top[::-1] #reverse new top to move highest unsorted number to the bottom position on the unsorted list (flip 2)
    pancakesAr = top + bottom   #reconstruct list

    print pancakesAr    #print after each flip

    numSorts += 1

print "Sort completed in " + str(numSorts) + " flips. Final stack: "
print pancakesAr

The basic algorithm I used is the one mentioned in the wiki article linked in the question:

The simplest pancake sorting algorithm requires at most 2n−3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes.

Some tips for golfing: four spaces for indentation is wasteful. Better: use one space; even better: combine tabs and spaces to cut back even more.

t=p[:x] t=t[::-1] (16+indentation) can be reduced to t=p[:x][::-1] (13), or even t=p[x-1::-1] (12). Inline everything you can: p=p[x-1::-1]+p[x:]

Use negative indices to count from the back. len(a)-n becomes -n; p=p[-n-1::-1]+p[-n:]. Further golf by using the right operations: p=p[~n::-1]+p[-n:]

Umm... you are supposed to print the entire flipping sequence, not just the end result.

What Jan Dvorak said. Welcome to codegolf by the way. You can easily cut the character count to a half by some simple measures; some of them has been mentioned. Also, intermediate variables are no good. List comprehension is nice. But if you're using sys.argv you may as well let each number of the input be an argument, then map(int,sys.argv[1:]) does what your 6 first lines does now. i=x=g=0 works, but you should cut the amount of variables anyways. I'll give you one thing though: This is the one python entry of which I understand the least :D

I'm giving you a -1 until the program produces right output, to sort of promote other answers that actually work correctly.

@daniero Hey, thanks to you and everyone else for the tips! Sorry for misunderstanding the rules, I thought it was just supposed to write the end output. In addition to being new to code golf, I'm pretty new to python; this is my 2nd python program, and I pretty much went along thinking "Okay, now I want to do [x]. Let's google the python syntax for that." ;) But thanks; I'll take a look at all the tips here, and I'll fix the output to match the rules (sorry for misunderstanding!) Also I thought you had to tab-indent in python; good to know a space works!

@daniero Okay, output fixed to match rules! And I cleared up the whitespace and shaved off 100 characters :D I haven't gone through and added all of the suggestions you guys made because I want to thoroughly understand them before I do (otherwise it feels like cheating!) but I had a lot of fun with this, so thanks for posing the problem! As for your comment about understanding it, I just read the wiki article you linked and followed the logic it gave :) I'm a python newbie so maybe read it as pseudocode instead of python and it will make more sense! ;)

@WendiKidd Aaaactually that's not quite the desired output either;) See The first example in the question and the part in italics. Or, the output from [http://codegolf.stackexchange.com/a/12029/4372](chron's answer). I guess this is close enough though... Codegolf is a great way to learn the details of a new language by the way!

Python 2 (254)
Simple BFS-search, some stuff is inlined, probably could be compressed more without changing the search style. Hopefully this shows maybe how to start golfing a bit (too much to be in a simple comment).
Use:
python script.py 4 2 3 1

(2 spaces = tab)
import sys
t=tuple
i=t(map(int,sys.argv[1:]))
g=t(range(1,len(i)+1))
q=[i]
p={}
l={}
while q:
 c=q.pop(0)
 for m in g:
  n=c[:m][::-1]+c[m:]
  if n==g:
   s=[m]
   while c!=i:s+=[l[c]];c=p[c]
   print s[::-1]
   sys.exit()
  elif n not in p:q+=[n];p[n]=c;l[n]=m

You can replace sys.exit() with 1/0 (in codegolf you never care for what gets printed in stderr...).

Sure, I could do print s[::-1];1/0 to shave a few chars.

The BFS is very interesting, but running it with 4 2 3 1 gives  2 3 2 4, which actually is invalid.

@daniero How is that output invalid? 4 2 3 1 -> 2 4 3 1 -> 3 4 2 1 -> 4 3 2 1 -> 1 2 3 4

@Gareth I have no idea! And I even checked it twice.. Oh well, nevermind then :) Nice solution, miles t.

Python2: 120
L=map(int,raw_input().split())
u=len(L)
while u:i=L.index(max(L[:u]))+1;L[:i]=L[i-1::-1];L[:u]=L[u-1::-1];print i,u;u-=1

It's not efficient: it wont find the best sorting sequence, and the given sequence can even contain no-ops(i.e. flipping only the first element), nevertheless the output is valid.
The output is given in the form:
n_1 n_2
n_3 n_4
n_5 n_6
...

Which should be read as the sequence of flips: n_1 n_2 n_3 n_4 n_5 n_6 ....
If you want to obtain an output like:
n_1 n_2 n_3 n_4 n_5 n_6 ...
Simply add a comma in the print statement.

[:i][::-1] -> [i-1::-1], [:u][::-1] -> [u-1::-1], saves 2 chars

In fact, L[:i]=L[i-1::-1];L[:u]=[u-1::-1] saves another 3 chars

@Volatility Thanks for the tips. Included.

Perl 5.10 (or higher), 66 bytes
Includes +3 for -n
The use 5.10.0 to bring the language to level perl 5.10 is considered free
#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Run with the input as one line on STDIN:
flop.pl <<< "1 8 3 -5 6"

Sorts the list by repeatedly finding any inversion, flipping it to the front then flipping the inversion and flipping everything back to its old position. And that is equivalent to swapping the inversion so I don't need to reverse (which is awkward on strings since it would reverse the digits of the values converting e.g. 12 to 21)

Haskell, 72 71 bytes
h s|(a,x:b)<-span(<maximum s)s=map length[x:a,s]++h(reverse b++a)
h e=e

Try it online! Finds the maximum, flips it to the back and recursively sorts the remaining list.
Edit: -1 byte thanks to BMO

C# - 229
using System;using System.Linq;class P{static void Main(string[] a){
var n=a.ToList();Action<int>d=z=>{Console.Write(z+" ");n.Reverse(0,z);};
int c=n.Count;foreach(var s in n.OrderBy(x=>0-int.Parse(x))){
d(n.IndexOf(s)+1);d(c--);}}}

readable version
using System;
using System.Linq;
class P {
    static void Main(string[] a) {
        var n = a.ToList();
        Action<int> d = z => { Console.Write(z + " "); n.Reverse(0, z); };
        int c = n.Count;
        foreach (var s in n.OrderBy(x => 0 - int.Parse(x))) {
            d(n.IndexOf(s) + 1); d(c--);
        }
    }
}