text:
Reinvent the For loop
For loops are used extensively in many languages, but what would you do if no languages supported them?
Create a way to execute a basic for loop without using any repetition structures (for, foreach, while, do, etc).
The basic for loop that you need to replicate is set up like this
for(i=0;i<1000;i++)

You must be able to replicate this without using repetition structures.  It must also execute code in your language that would be in the body of the loop.  Any form of eval is allowed, though it may not execute the for loop on its own.
You can test your code by having it print i with a space 100 times, add this test case to the end of your answer to verify your code with others.
There are no restrictions on what exactly it has to be, all it needs to do is replicate the for loop.
Winner will be decided based on upvotes at the time that it is chosen.

100 times or 1000? Or 100 000 times?

I find the problem too undefined. You say “without using any repetition structures” and only give examples (but not an extensive list) of such prohibited structures. The answers provided so far use recursion or goto, both of which I would classify as “repetition structures”, but it can be debated. Without a proper definition of what is allowed and what isn’t, this question is not interesting.

gotos, recursion...

I am voting to close this as off-topic because we require objective validity criteria for all challenges. As it stands, there is no clear way to determine the validity of a submission. Additionally, there is no specification of the behavior of a valid submission.

C, 45 chars without goto, if, for, ...
Not the smallest solution, but I find this way of doing it quite interesting in C :)
Doesn't use goto, if, for, or any other kind of control structures.
The function by itself (45 chars):
m(){int (*a[])()={m,exit};i++;(*a[i>999])();}

A compilable, working program:
#include <stdio.h>
#include <stdlib.h>

int i=0;
m(){int (*a[])()={m,exit};i++;printf("%i ",i);(*a[i>999])();}

int main()
{
  m();
}

A function call is a "control structure." Right?

@Denis Bueno: No, a control structure is stuff like while, do, for, if...

Can you please include an explanation? I got a bit lost.

This is a bit late, but @Rees: int (*a[])()={m,exit} is an array of function pointers. m is called which increments and prints i (set to 1, 2, 3, ...) and calls a function from the array of function pointers. The call (*a[i>999])(); will expand to (*a[0])(); or (*a[1])(); since C will use the value of i>999 as an integer depending on whether it is true or false (1 or 0). It'll call m until i>999 is true, then call exit. Nice use of function pointers.

You can remove that space.

Haskell, 33 chars
This is more like inventing the for loop, because there is no such nonsense in Haskell :P.
mapM_(putStr.(' ':).show)[0..999]

forM_ is just mapM_ with the arguments flipped, so this might be cheating. ;)

GCC - 106 95 chars
#define FOR(i,l,h)auto F();L(F,l,h);int F(i)
L(int f(int),int l,int h){l<=h?f(l),L(f,l+1,h):0;}

Unlike the other C solutions where you have to declare a callback, this one does it for you automagically:
FOR(i, 1, 10) {
    printf("%d\n", i);
}

It works by using GCC's nested function extension.  Namely, it forward-declares the nested function F, passes it to the looping function L, and then starts the definition of F, leaving the braces for the user to add.
One beautiful thing about nested functions in GCC is that they support downward funargs, meaning the illusion is nearly complete:
long n = 1;
FOR(i, 1, 10) {
    n *= i;
}
printf("%ld\n", n); // 3628800

There is one major caveat: if you use FOR twice in the same scope, you'll get a conflict (namely, it will compile, but all the FOR loops will share one loop body).  To allow multiple FOR loops in the same scope, we'll need 69 65 more characters:
175 160 chars:
#define FOR(i,l,h)F(i,l,h,__COUNTER__)
#define F(i,l,h,f)auto N(f)();L(N(f),l,h);int N(f)(i)
#define N(n)F##n
L(int f(int),int l,int h){l<=h?f(l),L(f,l+1,h):0;}

C, 21 characters
f(){if(c++<999)f();}

For example:
#include <stdio.h>
int c = 0;
f()
{
    printf("%d ", c);
    if (c++<999) f();
}
int main(void)
{
    f();
}

Outputs:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ... 998 999

Without a main() in the first block, the code won't link. Therefore I think it should be included in the entry.

@George: I think it's fair omitting main() in this case because the question says "Create a way to execute" not "make a complete program" as in other problems.

remove void  then it will be 26 characters only.

C# — no recursion, no goto
(using the Y combinator from lambda calculus)
class Program
{
    delegate Func<TInput, TResult> Lambda<TInput, TResult>(Lambda<TInput, TResult> f);

    static Func<TInput, TResult> Y<TInput, TResult>(Func<Func<TInput, TResult>, Func<TInput, TResult>> f)
    {
        Lambda<TInput, TResult> y = r => n => f(r(r))(n);
        return y(y);
    }

    static void Main()
    {
        Func<int, int> fibonacci = Y<int, int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
        Func<int, int> factorial = Y<int, int>(f => n => n == 0 ? 1 : n * f(n - 1));

        // Executes “fibonacci” 10 times, yielding 55
        Console.WriteLine(fibonacci(10));
        // Executes “factorial” 5 times, yielding 120
        Console.WriteLine(factorial(5));
    }
}

One might argue that the Y operator implements recursion…

x86 assembly, 12 11 bytes' worth of instructions
66 31 c0                xor    %ax,%ax
<body>                ; involving %ax
66 40                   inc    %ax
66 3d  e8 03            cmp    $1000,%ax
75 ??                   jne    <body>

A pity they're asked in ascending order... I'm pretty sure it would be shorter descending.

@J B: Yes -- in descending order, you'd normally use the loop instruction: mov cx, 1000\nx: ... loop x

Yet another Scala variant
Since Scala allows to use non-ASCII characters, we can implement real for :) (o is cyrillic).
def fоr(s:Unit,c: ⇒Boolean,e: ⇒Unit)(b: ⇒Unit):Unit=if(c){b;e;fоr(0,c,e)(b)}

Test:
var i:Int = _

fоr (i = 0, i < 1000, i += 1) {
  print(i + " ")
}

Ruby 1.9 - 51 characters
def f a,b,c,&d
a[]
k=->{d[];c[];redo if b[]}
k[]end

This is a lot larger than other entries, but I think it captures the essence of the question better.  In effect this allows you to write code almost exactly like the example:
def f a,b,c,&d
a[]
k=->{d[];c[];redo if b[]}
k[]end

i = 0 # Have to pre-declare i to have the closures work properly
f(proc{ i = 0 }, proc{ i < 1000 }, proc{ i += 1}) do
  p i
end

# Been a long time since I've actually used for's so took a long
# time to think of a non-trivial use.

j, sum = 0, 0 # Pre-declare variables for the closures

goal = 1000

f(proc{ j = 1; sum = 1 }, proc{ sum < goal }, proc{ j += 1 }) do
  sum = sum * j
end

puts "The next largest factorial after #{goal} is #{j-1}! at #{sum}"

JavaScript, 34 characters
This assumes the actual printing function is not part of the for loop.
parameterized recursion (43):
function f(i,m,c){if (i<m){c();f(++i,m,c)}}

function f(i, max, callback)
{
  if (i<max)
  {
    callback();
    f(++i,max,callback);
  }
}

reverse recursion (36):
assumes max >= 0
function f(m,c){if(m){c()
f(--m,c)}}

function f(max,callback)
{
  if(max)
  {
    callback();
    f(--max,callback);
  }
}

ternary operator (34)
function f(m,c)
{m?c()&f(--m,c):0}

function f(m,c){m&&c()&f(--m,c)} - You could make that 32 bytes :)

C#, 70 57 characters
C# isn't the weapon of choice for code golf, but I thought I'd try it out:
void f(int i,Func<int,bool>j,int k){if(j(i)) f(i+k,j,k);}

This doesn't only perform the task of counting up to 1000; rather, it attempts to actually replicate for loop behavior for any task. That seemed somewhat closer to the intent of the challenge, but maybe that's just me.
Expanded:
void f(int i, Func<int, bool> j, int k)
{
    if (j(i))
    {
        f(i + k, j, k);
    }
}

Usage is very close to for-loop syntax:
f(0, i => i < 1000, 1);

C: 33 chars for the base for loop (assuming goto is allowed)
int i=0;s:if(i<1000){/`*code inside for loop here`*/i++;goto s;}

int i=0;s:if(i<1000){printf("%d ",i);i++;goto s;}

Python
Specific case:
exec("print i,"+";")*1000

And in general:
exec("f"+";")*1000

where 'f' is your code. Proabably doesn't work for all cases.

NameError: name 'i' is not defined

I've kind of fixed it. Plus, I assumed that i was predefined.

If it's predefined, it's not going to change with the iteration.  That's not how a for loop works.

Fair point. I imagine it would need ;i=+1 after the comma. I did say it wouldn't work with all cases.

exec 'i=0;'+1000*'print i;i+=1;' would do the job.

PowerShell 18
filter p{$i=$_;$i}

1 - 10
PS C:\> (1..100 | p)-join' '
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 6
4 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

Yeah, it's completely useless and you have to rewrite the function to do anything useful. But isn't that kind of the point? :)

Prints newlines as delimiters? ... print i with a space 1 ... - disqualification. :)

filter p{"$_ "}   ---  :)

I'm not sure if this should be disqualified, as it's technically (ab)using the pipeline as if it was foreach.

I shall bear great shame for this, but here it is in Linux shell:
cat -An /dev/urandom|head -n1000|cut -f1

40 characters.

Prints linebreaks => disqualification! :)

Here's your loop using Brainfuck, which is probably cheating:
,[.,]

:) Unfair though.

C (No recursion, no goto's)
#include <stdio.h>

int main()
{
    puts("0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999");
    return 0;
}

Completely according to the definition, isn't it?

It replicates the output, but it does not really match the specification of a for loop. However, I think its nice :). But you should golf this.

Sorry, this is not code golf, haven't seen this yesterday...

Perl, 21 characters
map{print"$_ "}0..999

Mapping is a type of looping. Don't cheat! :-P

This comment is nonsense, since we have to write something which is equivalent to a for-loop. If we met the criteria, it will be always cheating, or what will make the difference? Explicit gotos? Recursion?

@Chris well I explicitely asked the OP in the chat before answering that one.

JavaScript - 39 characters in test case
Chrome, Opera, and IE: eval(s="i<1e3&&eval(s,print(i++))",i=0). This fails with "call stack size exceeded" on Safari and "too much recursion" on Firefox.
Firefox: (function f()i<1e3&&f(print(i++)))(i=0). This uses Mozilla's non-standard "expression closure" feature to eliminate a pair of curly braces.
Note: Change print(i++) to alert(i++) if you need to. You can change 1e3 to 100 to reduce the number of iterations for Safari.

Putting the print call inside the eval call is really clever.

QBasic (24 characters)
1?i:i=i+1:IF i<1E3THEN 1

expands to:
1 PRINT i: i = i + 1: IF i < 1000! THEN 1

Note: This assumes that i still has its original value of 0.

J, ?<10 chars
f^:1000

In J there are (almost) no loops; instead, one usually uses arrays and implicit loops through them. For example, to sum the integers 1..100, you apply (/) the "verb" plus (+) to the array 1..100 (i.101)
+/i.101
5050

To display the numbers 0..99, we just construct the array:
i.100
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...

^: is the "power" verb; f^:1000 is something like exec()*1000 in python.

C#, 58 characters
Update: D'oh...appears this is a virtually identical answer to Eelvex who beat me by a few minutes.
Not very clever - just simple recursion in .NET.
void f(int c,int m){Console.Write(c+" ");if(c++<m)f(c,m);}

Or taking out the body of the "for loop" (35 characters):
void f(int c,int m)if(c++<m)f(c,m);

Allows to seed the initial value and the max value.

Scala
Inspired from Nemo157's answer:
def myfor(test: =>Boolean, inc: =>Unit)(stmts: =>Unit) : Unit =
        if (test) {
                stmts
                inc
                myfor(test, inc)(stmts)
        }

And this can be used like this:
var i = 0
myfor(i<1000, i+=1) {
        print(i+" ")
}

Golfed (62) :
def f(t: =>Boolean,i: =>Unit)(s: =>Unit){if(t){s;i;f(t,i)(s)}}

Or:
def myfor[A](init: A, test: (A)=>Boolean, inc: (A)=>(A))(stmts: =>Unit) : Unit =
        if (test(init)) {
                stmts
                myfor(inc(init), test, inc)(stmts)
        }

myfor[Int](0, _<10, _+1) {
        println("loop")
}

Clojure
(map #(print (str % " ")) (range 1 (inc 100)))
Replace print with the function to execute.
Use (inc 100) or 101 for the last value.

Perl most simple - 18 chars (ok, cheating)
print"@{[0..999]}"

output:
    0 1 2 3  ... 998 999
but:
Perl regex/goatse op (real pseudoloop) - 39 (16) chars
()="@{[0..999]}"=~/\d+(?{print"$& "})/g

the 'base loop' beeing 16 chars
()=             =~/\d+(?{          })/g

output:
    0 1 2 3  ... 998 999
Regards
rbo

Javascript - 86 chars
e=eval,n=function(j,k,c){if(e(j))e(k),c(),n(j,k,c)},f=function(i,j,k,c){e(i),n(j,k,c)}

Maybe not the shortest javascript solution, but it replicates iterator declaration, iterator manipulation as well as a looping condition.
Example use case:
f('a = 0', 'a < 9', 'a++', function() {
    console.log(a);
});

C#, 70 chars
Enumerable.Range(0,999).ToList().ForEach(x=>Console.WriteLine(x+" "));

This can probably be golfed down, but it's the best I could come up with quickly.

Obviously never going to beat Perl, but I didn't see the Perl comment before I posted mine.

The code uses a foreach loop, which isn't allowed in the first post.

@Bass: no it doesn't. It calls a method that happens to be called ForEach.

@Martinho, so .each in Ruby and ForEach-Object in PowerShell is fine as well? There are languages that don't even have that many keywords, actually.

@Joey: look at how many existing answers use .each, map, range generators, etc. They're just black boxes. Who says they are not using gotos?

@Martinho: Well, that's the reason why I dislike this task. There are basically only three ways of solving it: Using an iterating primitive (keyword, function, ...), goto or recursion. And I'd understand the task so that the first kind of solution would be disallowed. It's a pretty boring task, imho :-)

@Joey: My solution uses no iterating primitive, goto or recursion.

This is wrong, this only prints 0 to 998. But it is also longer than necessary; Console.Write(string.Join(" ", Enumerable.Range(0, 1000))); is only 59 chars.

QuickBASIC, 103 characters
10 IF i < 1000 THEN PRINT MID$(STR$(i) + SPACE$(1), 2, ABS(i < 100) * 5); : i = i + 1: GOTO 10 ELSE END

Oh dear, after re-reading the requirements it looks like only the numbers 0 through 99 should be printed. Revised entry (and I think I'll have to take a shower after THIS hack): 10 IF i < 1000 THEN PRINT MID$(STR$(i) + SPACE$(1), 2, ABS(i < 100) * 5); : i = i + 1: GOTO 10 ELSE END

;; for (int index=1, result=1; !cmp(result, max); index=incr(index)) result=body(index,result);
((lambda (index result cmp max body incr)
   ((lambda (f n i)
      (if (cmp i max) n
          (f f (body i n) (incr i))))
    (lambda (f n i)
      (if (cmp i max) n
          (f f (body i n) (incr i)))) result index)) 1 1 > 1000 (lambda (i n) (printf "i:~a~nn:~a~n" i n) (* n i)) (lambda (x) (+ x 1)))

Please label the language used for this answer.

LISP, 91 characters
(defun m(x)(if(= 1000(length x))x(m(append x(list(1+(car(last x))))))))
(mapcar #'f(m'(0)))

It could be shorter with labels.
Example usage:
(defun f(x) (format t "~a " x))
(mapcar #'f (m '(0)))
0 1 2 3 4 5 6 7 8 9 10 11 12 ...  997 998 999

Perl (23 chars.):
print join " ",(0..999);*

or same Perl but in simpler yet more lengthy and recursive words:
sub i {($s,$e)=@_; return if $s==$e; print "$s "; i($s+1,$e)}

i(0,1000);

bash:
echo {1..1000}

14 chars.

Python3 - 27 chars
any(map(print,range(1000)))

Cool. For the nice output: print(" ".join(map(str,range(1000))))

Windows Batch File, 65
set I=%S%
:l
if %I% GEQ %E% goto :eof
call %C%
set /a I+=1
goto l

Test file:
@echo off
set S=0
set E=100
set "C=<nul set /p X=%%I%% "
call for.cmd

Can save two bytes if the loop always starts at 0.

sh
cat -An /dev/urandom|head -n1000|cut -f1|xargs

You can generate infinite lines with "yes".  Try "yes ''|head -n1000|cat -n|xargs"

Java with Lambda — 259 characters
I just built the prerelease Java langtools with the experimental lambda support that has recently been canceled for JDK 7 and pushed back until JDK 8 in 2012 (boo!) and wanted to try it out.
Formatted nicely, this version clocks in at 304 characters. If you reformat it so all the code of the interface is on one line and the class is on another, it gets down to 259 characters. I'm sure you could golf it down lower (shorten the identifiers, for starters), but Java is never going to be competitive at golf, so why obfuscate it.
interface Fore {
    void exec(int i);
}

public class ForLoop {
    public static void main(String[] args) {
        loop(1, 10, #{ int i -> System.out.println(i) });
    }

    public static void loop(int x, int max, Fore fore) {
        fore.exec(x);
        if (x < max) loop(x+1, max, fore);
    }
}

I just wanted to demonstrate what will be possible with lambdas in Java SE 8. The call to loop could be written with an anonymous inner class, instead:
loop(1, 10, new Fore() {
    public void exec(int i) {
        System.out.println(i);
    }
});

Yuck.
The syntax for lambdas in Java hasn't been settled yet; this is just what works with the current dev build of javac. Thanks to those who are working to make it happen. Java should have gotten lambdas and closures years ago. Alas.

C
(not really golfing, but fun)
#include <setjmp.h>
#include <stdio.h>

int main() {
    jmp_buf b;
    int i;
    if ((i = setjmp(b)) < 100) {
        printf("%d\n", i);
        longjmp(b, i + 1);
    }
}

At least it doesn't use goto.

JavaScript, 63 characters
(function i(s,r){r+=s+' ';s++<1e3?i(s,r):console.log(r)})(0,'')

with proper console output

Javascript  This one supports a few extra things, with plenty still missing.  Breaks after 3000 iterations cuz it's recursive.
function r(a,c,b,o,q,f) {var d=c=='<'?a<b:(c=='>'?a>b:(c=='=='?a==b:(c=='!='?a!=b:null)));if(d){f(a);a=o=='+'?a+q:(o=='-'?a-q:(o=='*'?a*q:(o=='/'?a/q:null)));r(a,c,b,o,q,f);}}
//params:  a = iterator start
// c = comparison type (supports >, <, ==, !=)
// b = iterator compare
// o = iterator operation (+, -, *, /)
// q = increment or whatever you call it
// f = function to execute each successful iteration

// from 0 to 99
r(0, '<', 100, '+', 1, function(i) {document.write(i + ' ');});
// from 100 to 1
r(100, '>', 0, '-', 1, function(i) {document.write(i + ' ');});
// powers of 10
r(1, '!=', 1000000, '*', 10, function(i) {document.write(i + ' ');});

R - 11 characters
General case:
f(1:1000)

Where f is your function.
Specific case:
cat(1:1000)

C 45 characters including printout
Compiles, links, and runs as-is; no need to define a separate function and then call it, adding to source size.
main(a){printf("%d ",a-1);a<1000&&main(a+1);}

Javascript (44 chars.):
Another rather pointless option, but then who said golf had to have a point :) Plus I gained something new... I never realised you could get away with i+++
eval(Array((i=0)+1e3).join('i+++" "+')+'i')

I also learned that running .map and .forEach on an initialised undefined filled Array does nothing... at least in FireFox anyway
Array(1000).forEach(function(){ /* this code is never executed :( */ })

From MDN - callback is invoked only for indexes of the array which have assigned values; it is not invoked for indexes which have been deleted or which have never been assigned values.

@Gareth yep thanks for the quote, I assumed as much, was just a little unexpected.. and rather annoying from a codegolf point of view :)

Javascript, 71. No if, for, or recursive function
function f(i,c,b){a=[]
eval(s=b+";a[++i]=s;a=a.slice(0,c);eval(a[i])")}

Test:
f(0,1000,'console.log(i)')

Spaghetti PHP 44
<?$i=0;a:if($i<1001){echo $i++." ";goto a;}

Python 2.7, 60 Bytes with command-line parameter
Prints 'O' to the console:
import sys
def l(t,m):
 print 'O'
  if t!=m:
   l(t+1,m)
l(0,int(sys.argv[0]))

EDIT: Realised it didn't work, so byte count has gone up to fix
On another note, here's a 127 byte version, including print function, that will let you actually call functions with one argument
import sys
def println(a):
print(a)
def l(t,m,f,a):
    f(a)
    if t!=m:
        l(t+1,m,f,a)
p=println
l(0,int(sys.argv[1]),p,"there")

Python 2.x - 17 chars
print range(1000)

You need a for loop: print " ".join(\i` for i in range(1000))`

@wok: the challenge is to not use for-loops.

Groovy, 32 bytes
(0..1000).each{ print "${it} " }

each is foreach => disqualified :) println is printing with newline, not space => disqualified. ;)

Which is silly.  Iteration is not a loop even though they contain 4 letters which are similar.  Iteration = processing data in memory = what computers are built to do.

Scala:
(1 to 100)mkString" "

21 chars
not that ugly:
(1 to 100) mkString " "

Language = C
just loop - 59 characters
(int(*)())\x66\x31\xc0\x66\x40\x66\x3d\xe8\x03\x75\xf8\xc3"

loop+call - 92 characters
(int(*)())"\x66\x31\xc0\x8b\x5c\x24\x04\x66\x40\x50\xff\xd3\x58\x66\x3d\xe8\x03\x75\xf4\xc3"

Example usage:
#include <stdio.h>

void disp(int n){printf("%d ", n&(0xffff));}

int main(){
    ((int(*)())"\x66\x31\xc0\x8b\x5c\x24\x04\x66\x40\x50\xff\xd3\x58\x66\x3d\xe8\x03\x75\xf4\xc3")(&disp);
    return 0;
}

This will only work on x86 machines. Tested with gcc (and works on codepad.org -> http://codepad.org/uyhFR9XU)
int fn(int n){ // n is at esp+4

    xor %ax, %ax ; zeros ax
    mov 4(%esp), %ebx ; saves esp+4 (addr of n) to ebx

    body:
    inc %ax ; add one to ax (this will print from 1 to 1000 instead of 0-999)
    push %eax ; pushes eax onto the stack
    call *%ebx ; calls n, which should contain &disp
    pop %eax ; pop eax off the stack assuming disp did not use eax
    cmp $1000, %ax ; compare
    jne body ; if not 1000, goto body

    ret
}

And probably should fail when DEP is enabled.

Can you include the char count and language?

K, information added

APL (26)
{(⊃⍵)>⊃⌽⍵:⍬⋄⍺⍺∇⍵+1 0⊣⍺⍺⊃⍵}

Usage:
<function> {(⊃⍵)>⊃⌽⍵:⍬⋄⍺⍺∇⍵+1 0⊣⍺⍺⊃⍵} <start> <end>

i.e.
{⍞←⍵ ' '} {(⊃⍵)>⊃⌽⍵:⍬⋄⍺⍺∇⍵+1 0⊣⍺⍺⊃⍵} 1 100

prints the numbers from 1 to 100.

VB11 (95c)
Dim F As Action(Of Integer, Integer, Action(Of Integer)) =
  Sub(i, m, a)
    If i > m Then Return
    a(i)
    F(i + 1, i, a)
  End Sub

And in use
 F(1, 1000, Sub(X) Console.WriteLine(X))

C# 52
f(int i,int m, action<int> a){if(i<=m){a(i);f(i-1,m,a);}

Python 2.6 (42)
def f(i,p,j=0):j<i and(p(j)or f(i,p,j+1))

# Test:
def do(i):
    print i
f(100,do)

This for-Function also includes the break command:
def do(i):
    print i
    if i==7:
        return True
        # break
f(100,do)

clang (152)
Tested with Apple clang version 4.0
bfor(int n,void(^b)(int)){
    __block void(^e)(int,int)=^(int l,int h){
        int m;
        h<l?:(m=(l+h)/2,e(l,m-1),b(m),e(m+1,h));
    };
    e(0,n-1);
}

Usage:
main(){
    bfor(100,^(int i){
        printf("%d ", i);
    });
    puts("");
}

The stack depth is log2 of the count due to the binary tree and thus it's unlikely to overflow due to recursion.

Nemerle  (?c)
macro for (init, cond, change, body)
syntax ("for", "(", init, ";", cond, ";", change, ")", body)
{
 <[
   $init;
   def loop () : void
   {
     if ($cond) { $body; $change; loop() }
        else ()
   };
   loop ()
  ]>
}

Usage
 for (mutable i = 0, i < 10, i++, printf ("%d", i))

Ti-84 Basic, 34
Here, > represents the calculator's STO-> button.
:-1>I:Lbl A:I+1>I:If I<1000:Goto A

Golf-Basic 84, 23 characters
:-1_Il`A:I++I@I<1000o`A

Lua, 59
local function f(x)if x<1000 then return f(x+1)end end f(0)

The loop body is located right after the then. This does not overflow stack because of the tail call optimization.
Test case:
local function f(x)if x<1000 then print(x)return f(x+1)end end f(0)

Same as @houbysoft, but in C++.
#include <iostream>
#include <vector>

int main(int argc, char *argv[])
{
    int i = 0;
    std::function<int()> m = [&i, &m]()->int {
        std::vector<std::function<int()>> functors;
        functors.push_back(m);
        functors.push_back([]()->int{return 0;});
        i++;
        std::cout << i << std::endl;
        functors[i>999]();
        return i;
    };
    m();
    return 0;
}

And Objective C (Just C using blocks, actually...)
#import <Foundation/Foundation.h>

int main(int argc, char *argv[])
{
    __block int i = 0;
    __block int (^m)();
    m = ^() {
        int (^a[])() = {m, ^(){return 0;}};
        i++;
        NSLog(@"i: %d", i);
        a[i>9]();
        return i;
    };
    m();
    return 0;
}

Objective-C 58 Characters (Or 45...)
int i;
-(void)f {
    NSLog(@"%d",i++);
    if (i<1000) [self f];
}

[self f];

*13 chars went on printing i, so only the for-loop is actually 45...

Lua (63 chars)
function F(n,f,...)if n>0 then f(...)return F(n-1,f,...)end end
Slightly longer, but more generic, than @mniip's version.  Use like F(1000,print,' ').

C - 48 characters
Compilable code.
main(int i){i^1002&&main(i+1);printf("%i",i-2);}

CPython 2, 158 bytes
(Yes, this is both implementation and version specific)
class K(object):
 def __init__(s,b,c,e,n):
  if not n:n={};exec b in n
  else:exec e in n
  s.n=n;s.c=c;s.e=e
 def __del__(s):eval(s.c,s.n)or K(0,s.c,s.e,s.n)

Example usage:
K('i=55','i<88','i+=1;print i`,0)


text:
Noughts and Crosses (aka Tic-Tac-Toe)
Write a Notes and Crosses application.
User interface is optional.
You can output the computers move in text: eg 1x1 (meaning center square)
The computer must play an intelligent (extra marks for optimal) game.
Apart from its first move which should be random.
Player computer take turns at first move.
First player to win two games in a row wins.
Score:

Lowest strokes wins.
If equal best computer move algorithm (as I see fit)
If equal submitted date.

I believe it's spelled tic-tac-toe or tic-tack-toe, minor issue but the tag should be properly spelled....

And in en-gb it's Nought's and Crosses.

@Peter: It's actually Noughts and Crosses, without the apostrophe.

@Chris, indeed. I'm not sure where the apostrophe came from.

Do you want full code version as well? I guess you do since you want to look at algorithm.

I wrote Tic Tac Toe in sed for fun, now I'm trying to post it here after I comply with the rules. I'm puzzled about why do you ask for the first computer move to be random? For optimal play it should be either in a corner or in the middle, depending if it's his turn or not.

I concur with @seshoumara, I believe that it is much more interesting to allow the computer to make a move that it thinks is optimal on its first turn, and forcing a random turn will pad the code due to the need for some conditional statement.

c99  -- 1229 characters (and needs nucrses)
#include <ncurses.h>
#include <string.h>
#define R return
#define A char
#define M mvprintw
#define I int
#define O "%c wins a game, press any key to %s."
A*s=" XOCHT";FILE *r;
I W(A*b){I i,p,q,r,w[]={0,1,2,0,3,6,0,2,3,3,3,1,1,1,4,2};if(!memchr(b,0,9))
R 3;for(i=0;i<16;i++){p=w[i/2];q=w[i/2+8];r=i%2+1;if((b[p]==r)&&(b[p+q]==r)
&&(b[p+q+q]==r))R r;}R 0;};
I C(A*b, I s){A c[9];for(I i=0;i<9;i++){memcpy(c,b,9);if(c[i]==0)c[i]=s;
if(s==W(c))R i;}R -1;};I P(A*b){I i;while(b[i=fgetc(r)%9]);R i;};
I D(A*b){A*p=" |-+";I i=0,j;for(;i<5;i++)for(j=0;j<5;j++)
mvaddch(i,j,p[2*(i%2)+j%2]);for(i=0;i<9;i++)mvaddch(2*(i/3),2*(i%3),
b[i]?s[b[i]]:'1'+i);refresh();};
I G(A m){I u=1,i,j;A b[9];memset(b,0,9);M(1,9,"Computer %c",s[m]);M(2,9,
"Human %c",s[m%2+1]);do{M(4,9,"Up %c",s[u]);D(b);if(u==m){if((i=C(b,m))<0&&(i=C
(b,m%2+1))<0)i=P(b);b[i]=m;}else{do{M(6,0,"your move ");refresh();scanw("%d",&i
);}while(i>10||i<1||b[i-1]!=0);b[i-1]=m%2+1;};u=u%2+1;}while(0==W(b));M(8,0,O,
s[W(b)],"continue");D(b);getch();M(8,0,"%44c",*s);R W(b)==3?5:u==m?4:3;}
I main(I c,A**v){A d=0, m=v[1][0]-'x'?2:1;r=fopen("/dev/random","r");
initscr();for(;;){c=G(m);if(c==d&&c-5)break;else M(4,25,"Previous winner %c",
s[c]),d=c;m=m%2+1;}M(9,0,O,c,"quit");getch();endwin();}

It gives away characters for the users convenience by using curses and having actual English prompts and informative lines. The obvious macro golfs have been made, but there are probably some comma and conditional operator improvements still available.
Is it smart? Well, it takes one move wins and blocks one move losses, but is otherwise quite random. (I may take the weekend to repair my interrupted CS education and learn about A* trees...) The "random first move" condition is met automatically as no one has the option to win at that point. Despite this obviously deficient AI I have yet to beat it when it holds X, so I have not defeated it by the "two in a row" rules.
Structurally we have a "is there a winner" function and a "can I win with a single play" function which works by coping the board and trying each position in turn with the isWon function. The single canWin function serves first to search for winning opportunities (by passing the computer's symbol) and then to search for things than need blocking (by passing the human's).
It declares Computer, Human, or Tie the winner on each game and only C or H for the series.
Now respects the spec as to winning conditions And plays well enough that you have to let it win or Ctrl-C to get out.
The version below differs from the above in prompts as well as macroization, but still represents the approach.
#include <ncurses.h>
#include <string.h>

char*s/*ymbols*/=" XOCHT";
FILE *r/*dev/random*/;

/* return the index of the side that wins, 0 if un-won or 3 if cat's game */
int W/*on*/(char*b){
  int i,p,q,r,w/*inning matrix*/[]={0,1,2,0,3,6,0,2,
                    3,3,3,1,1,1,4,2};
  if(!memchr(b,0,9))return 3; /* detect cat games by lack of open positions */
  for(i=0;i<16;i++){
    p=w[i/2];   /* starting position of the winning sequence to check */
    q=w[i/2+8]; /* step size of the winning sequence to check */
    r=i%2+1;  /* winning value to check */
    if( (b[p]==r) &&
    (b[p+q]==r) &&
    (b[p+q+q]==r) )
      return r;
  }
  return 0;
};
/* returns the first square in which the current side can win or -1 if none*/
int C/*an win?*/(char*b, int s/*ide to play*/){
  char c[9];
  for(int i=0;i<9;i++){
    memcpy(c,b,9);
    if(c[i]==0)c[i]=s;
    if(s==W(c))return i;
  }
  return -1;
};
/* returns a random unoccupied square */
int P/*ick a random move*/(char*b){
  /* assumes a move is possible and will loop forever if this
     condition is violated */
  int i;
  while(b[i=fgetc(r)%9])
    ;
  return i;
};
int D/*raw the board*/(char*b){
  char*p=" |-+";
  int i=0,j;
  for(;i<5;i++)
    for(j=0;j<5;j++)
      mvaddch(i,j,p[2*(i%2)+j%2]);
  for(i=0;i<9;i++)
    mvaddch(2*(i/3),2*(i%3),b[i]?s[b[i]]:'1'+i);
  refresh();
};

/* Play a single game with the computer taking s[m] and return the winner
 *
 *  3 -- computer
 *  4 -- human
 *  5 -- tie
 */
int G(char m){
  int u/*p*/=1,i,j;
  char b/*oard*/[9];
  memset(b,0,9); /* initalized to 0 (empty) */
  mvprintw(1,9,"Computer uses %c",s[m]);
  mvprintw(2,9,"Human uses %c",s[m%2+1]);
  /* main loop */
  do {
    mvprintw(4,9,"To play %c",s[u]);
    D(b);
    if(u==m){
      // my turn to move
      if( (i=C(b,m))<0 &&    /* move to win */
      (i=C(b,m%2+1))<0 ) /* 2%2+1 == 1,  1%2+1 == 2 so, the other side */
    i=P(b);
      b[i]=m;
    } else {
      // user's turn
      /* get user selection */
      do {
    mvprintw(6,0,"your move:\n");
    refresh();
    scanw("%d",&i);
      } while (i>10||i<1||b[i-1]!=0);
      b[i-1]=m%2+1;
    };
    u=u%2+1; /* Here u is switched to the *next* player, so if the
        game is one u denotes the *loser*  */
  } while(0==W(b));
  /* Print out the winner */
  mvprintw(8,0,"%c wins a game, press any key to continue.",s[W(b)]);
  D(b);
  getch();
  mvprintw(8,0,"%44c",*s);
  return W(b)==3?5:u==m?4:3;
}

/* first argument is required and expected to be x or o
 *
 * x always goes first
 */
int main(int c,char**v){
  char d=0, /* previous winner, starts on an impossible value */
    m=v[1][0]-'x'?2:1; /* select my symbol by index into s */
  /* /dev/random intialization */
  r=fopen("/dev/random","r");
  /* curses intialization */
  initscr(); /* start curses */
  for(;;){
    c=G(m);
    if (c==d&&c-5) // same *player* wins two in a row
      break;
    else
      mvprintw(4,25,"Previous winner %c",s[c]),d=c;
    m=m%2+1;
  }
  mvprintw(9,0,"Final winner is %c, press any key to quit.",c);
  getch();
  endwin();
}

Bash, 591 670, 812 (excluding #!/bin/bash)
x is computer. x goes first and then alternates with o for each new game. x never looses so game ends when x wins twice in a row.
UI is a simple 3x3 board. Positions are numbers from 0 to 8. Occupied positions are x's or o's. x (now) plays a boring game. Although x never looses, it will randomly pick between a set of best moves to be a little bit interesting.
The code:
W()for q in 1 28 55 3 12 21 4 20;{ [[ w**3 -eq B[f=q/8]*B[g=q%8]*B[g+g-f] ]]&&$r;}
B(){ local -i p R t=9 S;for((;p<9;p++)){ [[ B[p] -eq p ]]&&{ B[p]=w;W&&$e 98&&$r $p;R+=S[B[p]=p]=98-$(M+=-1;w=w^3;B);t=$((S[p]<S[t]?t:p));V=R/M;};};$e $V;$r $t;}
T()(for q in {1..9};{ $e -en ${P[B[q-1]]}${N[q%3]};};W=${P[w^=3]};q=$([ $w = 9 ]&&for((;B[q]!=q;)){ read -sn1 -p? q;}&&$e $q&&$r;[ $M = 9 ]&&$e $RANDOM||(B>1;$e $?))%9;B[q]=w;M+=-1;$e $W..$q;W&&$e $W!&&$r $w;[ $M = 0 ]&&$e Ty||T);P=({0..8} o x);N="\n";e=echo;r=return;declare -i V=49 q w=9 M=9 B=({0..8});for((;(J&(J=K))<9;w^=3)){ T;K=$?;};$e Won

I have just noticed that I use W as a function and variable. Bash does not seem to mind.
Dialogue is minimal:
? means it is waiting for o to play.
  means it is thinking about next move.
x! means X wins.
Ty means a Tie.

W determines if $w won.

It uses a code in $q to identify lines of positions to test. Let a line of positions be F, G, and H. Code is 8F+G. H can be derived from F and G: H=G+(G-F). eg. From 28, F=3, G=4, H=5. If board positions B[F]+B[G]+B[H]=3*w then $w has won
B $1 finds best move for player $1.
T controls a game and gets user move if $w is 0 or computer's move.

Full source code:
# Players
#   o is opponent
#   x is computer
#   Player symbols are stored in Player array.

# Board B has 9 board positions numbered 0 to 8
#   0-8=unoccupied
#   9=o in position
#   10=x in position

# Winning line encoding
#   if a winning row is positions f,g, and h then these are encoded as f*8+g
#   h is derived as g+(g-f)

Win()
  for q in 1 28 55 3 12 21 4 20;{                        # for each code
    [[ w**3 -eq B[f=q/8]*B[g=q%8]*B[g+g-f] ]] && return  # w won if 3 in row
  }

# F=49
# F sets a resolution for determining value of a move.
# Since AVG=sum(Score[*])/M then larger scores mean better fixed point real number.
# Score is 0 to 2F. Larger F, larger score accuracy.
#   F is set to largest number such that 2F is 2 digits.

# A move probability to win is returned in AVG.
#   AVG=0  o wins this move (if they play rationally)
#   AVG<F  means o more likely to win
#   AVG=F  means most likely a tie
#   AVG>F  means x more likely to win
#   AVG=2F means x wins

# p must be integer or it does not get initialised to 0
# R must be integer and it gets initialised to 0
# t needs a starting default value of 9 if there are no empty positions

Best(){  # here we have to silently play lots of games to choose best move
  local -i p R t=9 Score                         # save board and move count
  for((; p<9; p++)){
    [[ B[p] -eq p ]] && {                        # empty position
      B[p]=w                                     # occupy it
      Win && echo 98 && return $p                # if w won then restore board, set score to 2F
      R+=Score[B[p]=p]=98-$(M+=-1; w=w^3; Best)  # restore board, inc move & what is opponents best move?
      t=$((Score[p]<Score[t]?t:p))               # if score is better then restart list with this position
      AVG=R/M                                    # average scores
    }
  }
  echo $AVG                                      # set score
  return $t                                      # return first best position
}

# Take Turns.
#   Starting with other player (w^3), take turns and count down remaining turns.
#   Get a move from opponent or computer. Ensure opponent move is legal.
#   If there is a winner, return winner (9=o 10=x).
#   If game over, return tie (0)
#   Else take next turn
#   Changes w, W, M, B, p

Turn()(
  for q in {1..9};{
    echo -en ${Players[B[q-1]]}${N[q%3]}  # show position or player and newline every 3rd
  }
  W=${Players[w^=3]}                      # W is symbol of other player
  # if o, get move. else if game start, random move. else get best move for x
  q=$([ $w = 9 ]&&for((;B[q]!=q;)){ read -sn1 -p? q;}&&echo $q&&$r;[ $M = 9 ]&&echo $RANDOM||(Best>1;echo $?))%9
  B[q]=w                                  # move and occupy board position
  M+=-1                                   # dec move count
  echo $W..$q                             # show move
  Win        && echo $W! && return $w     # w has won
  [ $M = 0 ] && echo Ty  || Turn          # return 0 tie after 9 moves and no winner or another turn
)

# Play a game.
#   Board can be configured as you like. Ensure M represents number of moves remaining.
#   AVG is used by Best to return value of best move.

# Loop for competition to declare winner after 2 wins in a row.
#   Turn returns 9=o win, 10=x win, and 0=tie
#   w is non-starting player: 9=o 10=x
#   w swaps between 9 and 10 for subsequent games

# AVG is a global used to calculate/store average value of a move.
#   Since Best() is called in a subshell, it will always be 49.

# q is a globally used integer
# M is number of moves remaining. Starts at 9 and when 0 board is full and game over.

Players=({0..8} o x); N="\n";e=echo;r=return
declare -i AVG=49 q w=9 M=9 B=({0..8})  # player=H, empty board, 9 moves to go

for((; (J&(J=K))<9;w^=3)){              # start with X (9^3); while tie or not 2 in a row
  Turn
  K=$?                                  # K=who one
}
echo Won                                # I should cheat and just say x won to save more characters

Javascript 271
This is not a real entry in this competition, but i just wanted to share this interesting algorithm with the other (potentional) competitors.
b=[[8,8,8,8],[8,0,0,0],[8,0,2,0],[8,0,0,0]]
m=[2,2]
for(n=0;n<4;n++){
i=prompt(m).split(",")
r=+i[0]
c=+i[1]
b[r][c]=1
if(!b[r][c+1]){b[r][c+1]=2;m=[r,c+1]}
else if(!b[r][c-1]){b[r][c-1]=2;m=[r,c-1]}
else if(!b[r-1][c]){b[r-1][c]=2;m=[r-1,c]}
else{b[r+1][c]=2;m=[r+1,c]}}

It takes input of the form r,c where r is the row and c is the collumn, and it outputs in the same format. It does not output the last move since it's not a choice. This algorithm is
sooooo simple that you can probably implement it in less than 100 chars if you do it right! It works as follows:
1: The computer takes the first move (2,2)
2: The user makes any move
3: The computer checks if he can make a move on the square to the right of the user, if he can't he checks for the left, if he can't he checks for the square above and if he still can't he puts it on the square below.
4: Go to step 2
Try to beat it!

Trouble is this does not implement the question. 2) 2,2 (center square is not the best move (it is the simple move if you want to force a draw). But you can not force a win from that starting point. The best first move is a corner. If the second player makes a mistake on their first move you can force a victory (if they play anywhere but the center). If they play the center you can still force a draw.

@LokiAstari "This is not a real entry in this competition, but i just wanted to share this interesting algorithm with the other (potentional) competitors."

Asked 3 years ago and only had one response until yesterday.

@LokiAstari May have something to do with http://meta.codegolf.stackexchange.com/questions/1137/lets-go-on-a-mission

@LokiAstari, Actually I posted my entry on March 2.

Really nice... but why it has a 4x4 board? 3x3 is a classic. But, it actually made the game more fun :p

Java 1801 1691 1467
So yeah, this is definitely a revival, but as a new participant on codegolf I hope you won't hold it against me.
Edit: Changed from multidimensional array to single dimension array, also stripped out a bunch of unnecessary parenthesis. Next step will be to write a different "brain" for the computer. Even as it is, although not perfect, it does pretty well. I'm probably going to set up a version that has the computer play itself, for kicks. When I do, you can find it in my github.
Edit2: Replaced q and b methods with a single d method that performs all the work of q and b based on a flag passed in that chooses the "mode", 1 for win or block (prior q method), 0 for future-move-win choice (prior b method). Saved more than two hundred characters, hurray.
I spent some time golfing in Java, and this is what I came up with:
import java.util.*;class W{public static void main(String[]a){(new W()).t();}void p(String k,int i){System.out.print(k+(i<1?"":"\n"));}int[]M;int P;int c(){int m,a,b,i;for(a=b=i=0;i<3;i++){a=M[i*3];b=M[i];m=a==M[i*3+1]&&M[i*3+1]==M[i*3+2]&&a>0?a:b==M[i+3]&&M[i+3]==M[i+6]&&b>0?b:0;if(m>0){return m;}}m=M[4];return M[0]==m&&m==M[8]||b==m&&m==a?m:0;}void g(){for(int i=0;i<9;)p(w(M[i]),i++%3/2);p("",1);}int x(int i){return(new Random()).nextInt(i);}String w(int i){return(i<1)?".":((2*i-3)*P<0)?"X":"O";}int y(){return(new Scanner(System.in)).nextInt();}void Z(){int i;do{i=x(9);}while(!s(i,1));}int o(int a,int b,int c,int z,int x){return a==b&&c==x&&a==z?2:a==x&&b==c&&b==z?0:a==c&&b==x&&c==z?1:-1;}int d(int z,int y,int k){int i=0,j;for(;i<3;i++){if((j=o(M[i*3],M[i*3+1],M[i*3+2],z*k,z*(1-k)))>=0?s(k>0?i*3+j:i*3+2-j/2,y):(j=o(M[i],M[i+3],M[i+6],z*k,z*(1-k)))>=0?s(k>0?i+3*j:i+(2-j/2)*3,y):0>1)return 1;}if((i=o(M[0],M[4],M[8],z*k,z*(1-k)))>=0?s(k>0?i*4:8-(i/2)*4,y):(i=o(M[2],M[4],M[6],z*k,z*(1-k)))>=0?s(k>0?i*2+2:6-(i/2)*2,y):0>1)return 1;return 0;}void z(){if(!(d(1,1,1)>0||d(2,1,1)>0||s(4,1)||d(1,1,0)>0))Z();}boolean s(int i,int z){if(M[i]<1){p(w(z)+" to "+i%3+","+i/3,1);return(M[i]=z)==z;}return 0>1;}void t(){while(1>0){M=new int[9];int m=9,x;if(x(2)<1){P=1;Z();g();m--;}else P=-1;do{do{p("x?",0);x=y();p("y?",0);}while(!s(y()*3+x,2));m--;g();x=c();if(x>0||m<1)break;z();g();m--;x=c();}while(m>0&&x<1);if(x<1)p("No winner!",1);else p(w(x)+" wins!",1);}}}

Ungolfed, with comments (and perhaps some longer variables/method names):
import java.util.*;
public class TicTacToeGolf {
    public static void main(String[] args) {
        (new TicTacToeGolf()).start();
    }
    /** Wrap System.out.print to avoid all that typing */
    void p(String k, int i){
        System.out.print(k +((i<1)?"":"\n"));
    }
    /** Game board */
    int[][] gg;int P;
    /** Check all possibilities for winner, return 0 for no winner, 1 for X, 2 for O */
    int c(){
        for(int[]i:gg)
            if((i[0]==i[1])&&(i[1]==i[2])&&i[0]>0)
                return i[0];
        for(int i=0;i<3;i++)
            if ((gg[0][i]==gg[1][i])&&(gg[1][i]==gg[2][i])&&gg[0][i]>0)
                return gg[0][i];
        int m=gg[1][1];
        return (((gg[0][0]==m)&&(m==gg[2][2])||(gg[0][2]==m)&&(m==gg[2][0]))?m:0);
    }
    /** Print game board */
    void g(){
        for(int[]i:gg){
            for(int j:i)
                p(w(j),0);
            p("",1);
        }p("",1);
    }
    /** Generate a random value */
    int x(int i) {
        return (new Random()).nextInt(i);
    }
    /** Convert 1 to X, 2 to O */
    String w(int i) {
        return (i<1)?".":((2*i-3)*P<0)?"X":"O";
    }
    /** Get a number from the input */
    int y() {
        return (new Scanner(System.in)).nextInt();
    }
    /** Pick the next move for the computer */
    void Z() {
        int i,j;
        do{
            i=x(3);
            j=x(3);
        }while(!s(i,j,1));
    }
    /** Check for win or board condition for player z based on an ordered set of values a,b,c having one space with player x */
    int o(int a, int b, int c, int z, int x) {
        return (a==b&&c==x&&a==z)?2:(a==x&&b==c&&b==z)?0:(a==c&&b==x&&c==z)?1:-1;
    }
    /** Check for win over rows, cols, and grids for user z, place for user y based on findings.
     *  Means will block z if z != y */
    int q(int z,int y){
        int i=0,j;
        // check for win or block
        for (;i<3;i++){
            j=o(gg[i][0],gg[i][1],gg[i][2],z,0);
            if (j>=0){s(i,j,y);return 1;}
            j=o(gg[0][i],gg[1][i],gg[2][i],z,0);
            if (j>=0){s(j,i,y);return 1;}
        }
        i=o(gg[0][0],gg[1][1],gg[2][2],z,0);
        if (i>=0){s(i,i,y);return 1;}
        i=o(gg[0][2],gg[1][1],gg[2][0],z,0);
        if (i>=0){s(i,2-i,y);return 1;}
        return 0;
    }
    /** Check for placement options over rows, cols, and grids for user z, place for user y based on findings.
     *  Means will block z if z != y */
    int b(int z,int y){
        int i=0,j;
        // check for placement or block
        for (;i<3;i++){
            j=o(gg[i][0],gg[i][1],gg[i][2],0,z);
            if (j>=0){s(i,2-j/2,y);return 1;}
            j=o(gg[0][i],gg[1][i],gg[2][i],0,z);
            if (j>=0){s(2-j/2,i,y);return 1;}
        }
        i=o(gg[0][0],gg[1][1],gg[2][2],0,z);
        if (i>=0){s(2-i/2,2-i/2,y);return 1;}
        i=o(gg[0][2],gg[1][1],gg[2][0],0,z);
        if (i>=0){s(2-i/2,i/2,y);return 1;}
        return 0;
    }
    /** Pick the next move for the computer, smartly */
    void z() {
        // Check for win
        if (q(1,1)>0)return;
        // Check for block
        if (q(2,1)>0)return;
        // check for best
        if (s(1,1,1))return; // try to take center.
        // take whatever would win the subsequent turn if the other person is stupid.
        if (b(1,1)>0)return;
        Z(); // take anything.
    }
    /** Check if move is possible, if so do it, otherwise return false */
    boolean s(int i, int j, int z){
        if (gg[i][j]<1){
            p(w(z)+" to "+j+","+i,1);
            return (gg[i][j]=z)==z;
        }
        return 0>1;
    }
    /** Play the game, Computer gets first  move. */
    void start() {
        while(true){
            gg = new int[3][3];
            int moves=9,x;
            if (x(2)<1) { // Computer starts.
                P=1;
                Z();
                g();
                moves--;
            }else P=-1;
            do{
                do{
                    p("x?",0);
                    x=y();
                    p("y?",0);
                }while(!s(y(),x,2));
                moves--;
                g();
                if (c()>0||moves==0)
                    break;
                z();
                g();
                moves--;
            }while(moves>0&&c()==0);
            if(c()<1) p("No winner!",1);
            else p(w(c()) + " wins!",1);
        }
    }
}

Some usage notes:

50/50 chance for who takes first turn.
Move of "X" or "O" announced before displaying the game board.
Choice of cell is specified as column, then row, indexed from 0.
Entering something outside [0,2] will cause a index exception and end the game.
If computer goes first, takes a random move (no preference for any board location).
Computer will take one move wins, block one move losses, plays conservatively (prefers center if available), tries to set up a two-turn win (hope other player doesn't block), and if that fails? Picks a random spot. So doesn't play a perfect game, but plays a great game. I can force a win due to the random start possibilities, but computer will force a win as well if I start badly.
Wins are detected immediately.
Impossible-to-win is not detected; you must play every game to the end or let the other player win.
At the end of each game, a new game begins, again with a randomly chosen starting player.
Took a few hits to character length by including a usable UI.
Use Ctrl+c to end.

Example game (with computer starting, so first placement is random):
$ java W
X to 1,2
...
...
.X.

x?1
y?1
O to 1,1
...
.O.
.X.

X to 2,2
...
.O.
.XX

x?0
y?2
O to 0,2
...
.O.
OXX

X to 2,0
..X
.O.
OXX

x?2
y?1
O to 2,1
..X
.OO
OXX

X to 0,1
..X
XOO
OXX

x?0
y?0
O to 0,0
O.X
XOO
OXX

X to 1,0
OXX
XOO
OXX

No winner!

There's definitely room for improvement. One place is likely replacing the multi-dimensional array with a one-dimensional array(done), and replacing the more complex decision logic with either a reduced form of the same(done), or a more concise best-choice solver.
Play around with it and let me know what you think. I've got this hosted over on my github so feel free to fork, clone, and create pull requests with improvements.

Glad to see some competition. My answer should have been beaten ages ago.

Your answer is pretty golfed! But yeah, I was surprised to see so little attention to this problem, given the straightforward nature of the question.

Why import java.util.* when you can import java.*?

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/3.0/

sort: votes


text:
How would you count score in a Scrabble® game?
Let's say that we are programming a game that lets you play Scrabble®.

We have a board with tiles placed on it, and empty cells are either normal or have multiplier properties (double or triple the points for a word or for a single letter).
Each tile has a value and blank tiles have no value.

Thee goal here is to write a method that, given a new_word structure, will:

verify that this word can be placed onto the grid at the specified position (the originating rack has the missing letters, it is not out of board range, blank tiles will not be adjacent on the board)
return the number of points granted to the player.
letter multipliers have priority over word multipliers
all new words on the grid are counted (both horizontal and vertical)

Below are sample structures provided as an example.
// SCRABBLE® STRUCTURES

// a single Scrabble® tile.
struct tile
{
    // blank tiles are recognized by their value of 0.
    // The value of 'letter' is a space (L' ') until they
    // are positioned on the board. From that stage the
    // value of 'letter' contains what they represent.
    wchar_t      letter;
    unsigned int points;
};

// the bag with undrawed tiles
struct tile_bag
{
    // English version: 100 at start of game
    unsigned int  remaining_tiles;
    tile         *tiles;
};

// the content of a player rack
struct player_rack
{
    unsigned int     tile_count;
    tile            *tiles;
};

// a multiplier square
struct multiplier_cell
{
    enum
    {
        letter_scope,
        word_scope,
    } multiplier_scope;

    unsigned int multiplication_factor;
};

// a cell on the Scrabble® board
struct cell
{
    enum
    {
        normal,     // empty cell with no multiplier
        multiplier, // empty special cell, see multiplier_detail
        tile,       // cell with a tile on it, see tile_detail
    } cell_type;

    union
    {
        multiplier_cell multiplier_detail;
        tile            tile_detail;
    };
};

// a scrabble board;
struct board
{
    unsigned int width;  // usually 15
    unsigned int height; // usually 15
    cell **cells;
};

// a new word, placed on the grid
struct new_word
{
    // zero-terminated string representing the actual word.
    const wchar_t *zWord;

    // the same string, but with spaces for blanks that come
    // from the rack
    const wchar_t *zWord_with_blanks;

    // the rack the word originates from
    player_rack   *original_rack;

    // the cell position where the word begins
    unsigned int   verticalStart;
    unsigned int   horizontalStart;

    // the direction
    enum { vertical, horizontal, } direction;
};

// SCRABBLE® NUMERIC CONSTANTS

// how many tiles are allowed on the rack of a single player
// this is also the number of tiles that grant a bonus when
// placed onto the board at the same time.
// usually 7
extern const int max_allowed_tiles_on_a_rack;

// how many extra points are granted when scrabbling
// usually 50
extern const int scrabble_extra_points;

// GLOBAL VARIABLES

extern board        theBoard;
extern tile_bag     theBag;
extern int          theNumberOfPlayers;
extern player_rack *theRacks;

The spec needs fixing. At present all the tiles start out as blanks.

@Peter Taylor: Those are structures, which are not initialized here. Assume they have been initialized in another part of the code.

I was referring to "The value of 'letter' is a space (L' ') until they are positioned on the board."

@Peter Taylor: Oh, maybe the comment is not clear, but it is about the blank tiles. Once on the board we need to know what letter they represent if we want to check the words in a dictionary.

Haskell:
pointsFromWord :: [[Tile]] -> [Char] -> Word -> Maybe Int
pointsFromWord board rack (word, (x, y), Vertical) =
  pointsFromWord (transpose board) rack (Word word (y,x) Horizontal)
pointsFromWord board rack w@(word, (x, y), Horizontal) =
  if (validWord board w)
    then Just (wordScore board w)
    else Nothing

validWord :: [[Tile]] -> [Char] -> Word -> Bool
validWord board rack w@(word, (x, y), _) = x >= 0 && y >= 0 &&
  y < length board && (a + length word) < length (board!!y) &&
  foldl (\acc (c,t)->acc && characterFits t c) True (zip word wordLocation)
    where wordLocation = take (length word) (drop x (board!!y))
          characterFits (PlacedTile letter) c = letter == c
          characterFits _ c = contains rack c

wordScore :: [[Tile]] -> Word -> Int
wordScore board (word, (x, y), _) = (letterScore * multiplier) + scrabbleBonus
  where
    letterScore = foldl (\acc (c,t)->acc + value t c) 0 (zip word wordLocation)
    wordLocation = take (length word) (drop x (board!!y))
    value (LetterMultiplier mult) c = tileValue c * mult
    value (PlacedTile letter value) c = value
    value _ c = tileValue c

    multiplier = foldl (\acc t->acc * wordMultValue t) 1 wordLocation
    wordMultValue (WordMultiplier mult) = mult
    wordMultValue _ = 1

    scrabbleBonus = if length (filter fromRack wordLocation) == 7
                      then 50
                      else 0
    fromRack PlacedTile = False
    fromRack _ = True

A little longer than I'd like (especially the ton of where clauses on wordScore), but seems readable enough (at least to me).
I took a few liberties with the data structures themselves - transliterating the C structures into Haskell doesn't really work.
The board structure is a list of lists of tiles - a list of tiles forms a row, and a list of rows form a board.
Words contain, in order:

A [Char] containing the exact tiles used (including blanks where a blank will be used instead of a letter). I assume this is prescreened for the no-two-blanks-next-to-each-other condition, though I suppose I could validate that as well.
An (Int, Int) tuple specifying the location of the word
An Orientation type constructed with either Vertical or Horizontal, specifying the orientation of the word.

Additionally, the player's current rack of tiles is passed separately from the word being tested, because that makes more sense.
I also assume a tileValue function which takes a character (including space) and returns the standard value of a tile depicting that character.

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


text:
Golfed fixed point combinator
Write a fixed point combinator in as few characters as possible, in the language of your choice.

free form (i.e., whatever's shortest): whole program, actual function, code snippet
you may not use your standard library's if it has one
you may however extract it from other high-level functions it you'd rather do that than construct it from the bases

Please include a recursive factorial or Fibonacci that uses it as a demo.
In this question, self-reference is acceptable, the aim is solely to remove it from the recursive function it will apply to.

Is a lazy-language implementation ok? (Would you accept (define Y(lambda(f)(f(Y f)))) ?)

Any implementation you can demonstrate with one of the requested examples is ok.

If I'm not mistaken, strictly speaking, the term "Y combinator" refers specifically to a single fixpoint combinator discovered by Haskell Curry, λf.(λx.f (x x)) (λx.f (x x)) .

@Eelvex: Obviously both answers so far (including the OP's own answer) use the cheating way, so, I guess that makes it okay. :-P Personally, I'd rather go with @Joey's approach and say that only the real (non-self-referential) Y combinator will do. ;-)

@Chris: Oh my. That's what I had in mind initially, and then I... forgot along the way. It's kind of too late to change now, we'll have to open another question.

Haskell: 10 characters
y f=f$y f

Example of use to create recursive definitions of factorial or nth-Fibonacci:
> map ( y(\f n->if n <= 1 then 1 else n*f(n-1)) ) [1..10]
[1,2,6,24,120,720,5040,40320,362880,3628800]

> map ( y(\f n->if n <= 1 then 1 else f(n-1)+f(n-2)) ) [0..10]
[1,1,2,3,5,8,13,21,34,55,89]

Though, a more common way to use y would be to generate these sequences directly, rather than as functions:
> take 10 $ y(\p->1:zipWith (*) [2..] p)
[1,2,6,24,120,720,5040,40320,362880,3628800]

> take 11 $ y(\f->1:1:zipWith (+) f (tail f))
[1,1,2,3,5,8,13,21,34,55,89]

Of course, with Haskell, this is a bit like shooting fish in a barrel! The Data.Function library has this function, called fix, though implemented somewhat more verbosely.

Perl, 37
sub f{my$s=$_[0];sub{$s->(f($s),@_)}}

Factorial demonstration:
sub fact {
  my ($r, $n) = @_;
  return 1 if $n < 2;
  return $n * $r->($n-1);
}
print "Factorial $_ is ", f(\&fact)->($_), "\n" for 0..10;

Fibonacci demonstration:
sub fib {
  my ($r, $n) = @_;
  return 1 if $n < 2;
  return $r->($n-1) + $r->($n-2);
}
print "Fibonacci number $_ is ", f(\&fib)->($_), "\n" for 0..10;

GNU C - 89 chars
#define fix(f,z)({typeof(f)__f=(f);typeof(__f(0,z))x(typeof(z)n){return __f(x,n);}x(z);})

Example:
#define lambda2(arg1, arg2, expr) ({arg1;arg2;typeof(expr)__f(arg1,arg2){return(expr);};__f;})

int main(void)
{
    /* 3628800 */
    printf("%ld\n", fix(lambda2(
        long factorial(int n), int n,
            n < 2 ? 1 : n * factorial(n-1)
        ), 10));

    /* 89 */
    printf("%ld\n", fix(lambda2(
        long fibonacci(int n), int n,
            n < 2 ? 1 : fibonacci(n-1) + fibonacci(n-2)
        ), 10));

    return 0;
}

k2, 12 char
The obvious self-referential implementation is the shortest. This is a sign of good language design. Unfortunately, K isn't lazy, so we can only manage call-by-value.
Y:{x[Y[x]]y}

This definition should also work in k4 and q without trouble, though I assume k2 for the examples below.
  Y:{x[Y[x]]y}
  fac: {[f;arg] :[arg>0; arg*f[arg-1]; 1]}
  Y[fac] 5
120
  fib: {[f;arg] :[arg>1; f[arg-1] + f[arg-2]; arg]}
  Y[fib]' !10
0 1 1 2 3 5 8 13 21 34

A more modest 18 characters lets us exactly transcribe (λx. x x) (λxyz. y (x x y) z) into K.
{x[x]}{y[x[x;y]]z}

Maybe someday (k7?), this could look like Y:{x Y x}.

Python 3, 30 Bytes
Y=lambda f:lambda a:f(Y(f))(a)

Demo :
Y=lambda f:lambda a:f(Y(f))(a)
quicksort = Y(
lambda f:
    lambda x: (
        f([item for item in x if item < x[0]])
        + [y for y in x if x[0] == y]
        + f([item for item in x if item > x[0]])
    ) if x
    else []
)
print(quicksort([1, 3, 5, 4, 1, 3, 2]))

Credits : https://gist.github.com/WoLpH/17552c9508753044e44f

Python 3 has filter. Also I'm sorry I neglected to mark that comment as a joke

Python 3 's filter returns a filter object and not a list. It would be less readable or pythonic to use filter.

it would be less Pythonic, but more in line was [tag:functional-programming], which was my point

Wolfram Language (Mathematica), 16 bytes
v_//Z@g_=Z@g~g~v           (* golfed   *)
Z[g_][v_] = g[Z[g],v]      (* ungolfed *)

Try it online!
This definition of the Z combinator uses the Wolfram Language's pattern-matching to make sure that any expression of the form Z[g] remains unevaluated as long as the second argument is missing; only the two-argument form Z[g][v] matches the above pattern and is replaced by g[Z[g],v], which in turn contains the single-argument form Z[g] that remains unevaluated until later. This distinction between an inert single-argument form Z[g] and an automatically-substituted two-argument form Z[g][v] allows for a controlled recursion process that remains tied to the application of the second argument.
examples
factorial
fac[r_, n_] = If[n==0, 1, n*r[n-1]];
Table[Z[fac][i], {i, 0, 10}]
(*    {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}    *)

Same with an anonymous function:
Table[Z[If[#2==0, 1, #2*#1[#2-1]]&][i], {i, 0, 10}]
(*    {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}    *)

Same but using Mathematica's built-in self-reference operator #0: we don't actually need a combinator to define recursive anonymous functions,
Table[If[#1==0, 1, #1*#0[#1-1]]&[i], {i, 0, 10}]
(*    {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}    *)

Fibonacci sequence
fib[r_, n_] = If[n<=1, n, r[n-2]+r[n-1]];
Table[Z[fib][i], {i, 0, 10}]
(*    {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55}    *)

APL (Dyalog Unicode), 9 bytes
{∇(⍎⍺⍺)⍵}

Try it online!
An operator whose left operand is a string representing the function to be combinatorified and whose right argument is passed to the function once it is combinatorised. I think it's okay to pass the function as a string, but if not, I will delete this answer.
Explanation
{∇(⍎⍺⍺)⍵}
 ∇(⍎⍺⍺)     ⍝ Equivalent to f ( Fix f )
     ⍺⍺      ⍝ Left operand
   ⍎        ⍝ Evaluate to get monadic operator
 ∇           ⍝ Self-reference (Fix f). Pass as operand to f (or ⍎⍺⍺)
        ⍵    ⍝ Apply the derived function to the right argument ⍵

Java 8, 104 bytes
interface C{int t(int n);}interface F{C f();}interface P{C c(F f);static F g(P p){return()->p.c(g(p));}}

Based on @user's Java answer for the related Implement Fix2 combinator challenge.
Explanation:
interface C{       // Completed Function interface
  int t(int n);}   //  Using a function that transforms a given integer

interface F{       // Function interface
  C f();}          //  A wrapper to pass the 'Completed Function' as function

interface P{       // Program interface
  C c(F f);        //  Which takes a 'Function' as argument, and returns a 'Completed Function'

  static F g(P p){ //  Recursive function that accepts a 'Program' as argument, and returns a 'Function'
    return()->     //   Return a new function, which wraps:
      p.c(         //    A completed call to its own 'Program' interface
       g(          //     Using a recursive call to its own function
         p));}}    //     with the given 'Program' as argument

The method to call is P::g, which takes P as argument and returns F. To obtain a completed function C from an F, we can call F::f on it. P represents the function to be fixed, and its method c takes F as argument to prevent immediate evaluation, returning a C that represents a complete function to transform a given integer n with C's t(n).
Example Fibonacci implementation:
P fix = fibonacci -> n -> n>1? fibonacci.f().t(n-1)+fibonacci.f().t(n-2) : 1;
C func = P.g(fix).f();
int result = func.t(input);

Try it online.

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


text:
The Tic Tac Toe Dictionary
A TicTacToe game can be represented by a string denoting the sequence of positions as the players make their move.

0 1 2
3 4 5
6 7 8

Assume X always plays first.
So a string of "012345678" denotes the game

X O X
O X O
X O X

Notice, the game is already won when Player X marks 6, at that point the game ends, granting a win to X. (ie, ignore the remaining moves once a player wins)
Your challenge (code) is to print all the games (sorted order) and its results.
The Format
<movesequence>:<result>\n

eg:
012345678:X
012345687:X
012345768:X
...

Denote X for the 1st player winning, O for the second player, and D for Draws.
There will be 9! (362880) games.
Here is some data to verify your results.
'X' Wins: 212256
'O' Wins: 104544
Draws : 46080

This is a codegolf, and runtime should be within a minute. Have Fun!
EDIT: Removed excess details, and just print it on stdout. No need to create a file.

I'm getting different numbers here: 212256 wins for X, 104544 wins for O and 46080 draws (and Wikipedia seems to agree with me).

@Ventero, I'll recheck, but I don't see any reference to those numbers on the page.

@Ventero, You're right, i'll edit that part. will post the md5sum soon.

The Ruby answer isn't the shortest, so it should not be the accepted answer according to your scoring criteria (code-golf).

Ruby 1.9, 201 characters
r=*[*l=0..8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6].each_slice(3)
w=->a{r.any?{|b|b&a==b}}
[*l].permutation(9){|a|u=[[],[]];i=-1
u[i%2]<<a[i+=1]while !((x=w[u[1]])||o=w[u[0]])&&i<8
puts a*""+":#{x ??X:o ??O:?D}"}

Slightly golfed so far. Takes about 45 seconds to complete here.

Edit: (268 -> 249) Write to stdout instead of a file
Edit: (249 -> 222) Don't pre-fill the array with each player's moves.
Edit: (222 -> 208) Shorter way to find out if a player won
Edit: (208 -> 213) Back to 213, the previous solution was too slow.
Edit: (213 -> 201) Some rearrangements, removed whitespace

I edited the question a bit, you don't need to create a file now, just print it.

J, 124 chars
((],~':',~1":[){&'DOX'@(</+2*>/)@:(<./"1)@:(((2{m/.@|.),(2{m/.),m"1,>./)"2)@(<:@(>:%2|]),:(%(2|>:)))@(3 3$]))"1((i.!9)A.i.9)

X win, O win and Draw counts check out.
Was a bit painful to debug though. :)

Haskell, 224 222 characters
import Data.List
p=sort.permutations
a(e:_:z)=e:a z;a z=z
[c,d]%(e:z)|any((`elem`words"012 345 678 036 147 258 048 246").take 3).p.a.reverse$e=c|1<3=[d,c]%z;_%[]='D'
main=putStr$p['0'..'8']>>=(\s->s++':':"OX"%inits s:"\n")

Alas, the permutations function from Data.List doesn't produce permutations in lexographic order. So I had to expend 6 characters on the sort.

APL (139)
This can probably be shortened more, but it was hard enough as it is. Believe it or not, it runs in about 45 seconds on my computer (excluding the time it takes to output everything, when output to the screen).
↑{⊃,/(,/⍕¨⍵-1),':',{1∊T←↑{∨/↑{⍵∘{⍵≡⍵∧⍺}¨↓⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔'}¨↓(M∘.≥M)∧[2]M∊⍵}¨↓⍉5 2⍴0,⍨⍵:'XO'[1+</+/T]⋄'D'}⍵}¨↓{1≥⍴⍵:↑,↓⍵⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵}M←⍳9

Explanation:

M←⍳9: Store in M the numbers from 1 to 9. Internally, this program uses 1..9 instead of 0..8.
{...}: a function to get all permutations:

1≥⍴⍵:↑,↓⍵: if the length is smaller or equal to 1, return the argument as a matrix.
⋄↑⍪/⍵,∘∇¨⍵∘~¨⍵: otherwise, remove each character in ⍵ from ⍵, get the permutations of that, and add the character back in.

¨↓: for each permutation...
{...}: a function that gives the winner for that permutation:

⊃,/(,/⍕¨⍵-1),':',{...}⍵: get the permutation as a string, with all the numbers decreased by 1 (to get the required 0..8 output instead of 1..9), followed by a colon, followed by the character denoting the winner:

⍉5 2⍴0,⍨⍵: separate the moves by X from the moves by O. Because O has one move less than X, that space is filled by 0, which is unused and so does not influence the result.
{...}¨↓: for both the X board and the O board, run the following function which determines whether there is a win in one of the nine timesteps:

(M∘.≥M)∧[2]M∊⍵: Generate a bitboard from the move numbers, and and this bitboard with the bitstrings 100000000, 110000000 ... 111111111 to get the state of the board at each of the nine moments in time.
{...}¨↓: for each of these, run the following function:

⍉(9⍴2)⊤⎕UCS'㗀㐇㔤㑉㔑㑔': get the bitboards for each possible winning situation
⍵∘{⍵≡⍵∧⍺}¨↓: and each winning state with the current bitboard and check if said winning state is still there

∨/↑: or these together, giving whether there is a win on this bitboard

1∊T←↑: make a 9x2 matrix, with the 9 X-timesteps on the first row and the 9 O-timesteps on the second row. Store this in T. If there is a 1 in this matrix, someone has won.
:'XO'[1+</+/T]: If someone has won, give 'X' or 'O' depending on whose 1 was first.
⋄'D': If nobody has won, give 'D'.

↑: make a matrix out of these so that they are each displayed on a separate row.

Python 2.7 (237)
from itertools import*
for z in permutations('012345678'):
 k,F=0,[9]*9
 for h in z:
    F[int(h)]=k=1-k
    if any(sum(a)in(0,3)for a in(F[:3],F[3:6],F[6:],F[::3],F[1::3],F[2::3],F[::4],F[2:8:2])):break
 else:k=2
 print"".join(z)+':','OXD'[k]

JavaScript (V8), 174 bytes
f=(j,w,p,x,o)=>(A=[-1,7,56,73,84,146,273,292,448],g=n=>!A.every(q=>q&n^q),w=w||g(x)|2*g(o),x+o)^511?A.map((_,i)=>x+o>>i&1||f(!j,w,[p]+i,x|!j<<i,o|j<<i)):print(p+':','DXO'[w])

Try it online!
Or see the statistics
How?
We use 8 bit-masks stored in the array \$A\$ to identify all possible winning patterns. There's a dummy leading \$-1\$ in \$A\$ (which will always cause the test to fail) so that we have 9 entries. This allows us to re-use \$A\$ to iterate on all squares of the grid.
The bit-masks for X and O are stored in the variables \$x\$ and \$o\$ respectively. The variable \$j\$ is a flag telling which turn it is (false or undefined for X, true for O). The variable \$w\$ holds the winner (\$0\$ for draw, \$1\$ for X, \$2\$ for O) and may not be changed anymore once it's non-zero. The variable \$p\$ is the permutation of moves as a string.

Python 3 + golfing-shortcuts, 211 bytes
from s import*
for Z in Im('012345678'):
 K,F=0,[9]*9
 for H in Z:
    F[int(H)]=K=1-K
    if a(s(A)in(0,3)for A in(F[:3],F[3:6],F[6:],F[::3],F[1::3],F[2::3],F[::4],F[2:8:2])):break
 else:K=2
 p(sj('',Z)+':','OXD'[K])

A port of Daniel's answer.


text:
Mixed up output
Write a function or program that outputs the following lines <input> time:
Hello World. Dlrow Olleh. Hwlrod Eoll.
Big Brown Fox. Xof Nworb Gib. Bbfgox Iro.

EDIT: It's "B rown F ox" not "brown fox".
This is code-golf so the program with the shortest bytecount wins!

Can we ignore the capitalization?

I think in most languages the code to mix up the characters is larger than embedding the strings directly.

I can't even work out what algorithm is applied to get the third sentence.

@Peter: The first word is the odd characters of the original words, the second one is the even characters.

@Joey: surely not in Perl, Golfscript, J and maybe even others.

@Eelvex, then shouldn't the last one be Bbfgoxn Irow?

@Peter: It's up to the length of the smallest word but it would be fine if you want to implement it like "Bbfgoxn Irow".

@Peter @Eelvex ... careful ... that sounds like cursing :D

A 'code-challenge' should be challenging.

@boothby, I believe codegolfing this it's challenging enough.

Bbfgox Iro isn't even a permutation....................

@MagicOctopusUrn Take 1st character of each word: Bbf. 3rd character of each word: gox. There is no 5th character of "Big" and "Fox" so the first word is "Bbfgox". 2nd character of each word: "Iro". ...

Ruby - 84 chars
"Hello World. Dlrow Olleh. Hwlrod Eoll.
Big brown fox. Xof Nworb Gib. Bbfgox Iro."*n

vim - 82 strokes
oHello World. Dlrow Olleh. Hwlrod Eoll.
Big brown fox. Xof Nworb Gib. Bbfgox Iro.<ESC>

Type the number of repeats you want before entering this.

Python 110 105 Characters
exec"print'Hello World. Dlrow Olleh. Hwlrod Eoll.\\nBig brown fox. Xof Nworb Gib. Bbfgox Iro.';"*input()

you can take off 5 characters by using one print and \n to end the line

JavaScript - 100 characters
while(n--)print('Hello World. Dlrow Olleh. Hwlrod Eoll.\nBig brown fox. Xof Nworb Gib. Bbfgox Iro.')

D: 127 Characters
auto f(int n){return join(repeat("Hello World. Dlrow Olleh. Hwlrod Eoll.\nBig brown fox. Xof Nworb Gib. Bbfgox Iro.",n),"\n");}

More Legibly:
auto f(int n)
{
    return join(repeat("Hello World. Dlrow Olleh. Hwlrod Eoll.\nBig brown fox. Xof Nworb Gib. Bbfgox Iro.", n), "\n");
}

PowerShell: 95
"Hello World. Dlrow Olleh. Hwlrod Eoll.`nBig Brown Fox. Xof Nworb Gib. Bbfgox Iro.`n"*(read-host)

Read-Host prompts the user for input, then the string is multiplied by that value and printed. This will have an extra newline at the end, but I don't see that as a constraint in the challenge.

Whitespace, 761 724 bytes
[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_input_as_integer][T   T   T   _Retrieve_heap_at_0][S N
S _Duplicate][N
S S N
_Create_Label_LOOP][S N
N
_Discard_top][S S S T   N
_Push_1][T  S S T   _Subtract][S N
S _Duplicate_input][N
T   T   T   N
_Jump_to_Label_EXIT_if_negative][S S S N
_Push_0][S S T  T   S T T   S S T   N
_Push_-89_\n][S S T T   T   S T S T N
_Push_-53_.][S S S T    T   S S N
_Push_12_o][S S S T T   T   T   N
_Push_15_r][S S T   T   T   S T S N
_Push_-26_I][S S T  T   S S S S T   T   N
_Push_-67_space][S S S T    S T S T N
_Push_21_x][S S S T T   S S N
_Push_12_o][S S S T S S N
_Push_4_g][S S S T  T   N
_Push_3_f][S S T    T   N
_Push_1_b][S S T    T   S S S S T   N
_Push_-33_B][S T    S S T   T   S N
_Copy_6th_space][S S T  T   T   S T S T N
_Push_-53_.][S S T  T   N
_Push_1_b][S S S T  T   S N
_Push_6_i][S S T    T   T   T   S S N
_Push_-28_G][S T    S S T   S S N
_Copy_4th_space][S S T  T   N
_Push_-1_b][S S S T T   T   T   N
_Push_15_r][S S S T T   S S N
_Push_12_o][S S S T S T S S N
_Push_20_w][S S T   T   S T S T N
_Push_-21_N][S T    S S T   S T N
_Copy_5th_space][S S S T    T   N
_Push_3_f][S S S T  T   S S N
_Push_12_o][S S T   T   S T T   N
_Push_-11_X][S T    S S T   T   N
_Copy_3rd_space][S S T  T   T   S T S T N
_Push_-53_.][S S S T    S T S T N
_Push_21_x][S S S T T   S S N
_Push_12_o][S S T   T   T   T   S T N
_Push_-29_F][S T    S S T   S S N
_Copy_4th_space][S S S T    S T T   N
_Push_11_n][S S S T S T S S N
_Push_20_w][S S S T T   S S N
_Push_12_o][S S S T T   T   T   N
_Push_15_r][S S T   T   S S S S T   N
_Push_-33_B][S T    S S T   S T N
_Copy_5th_space][S S S T    S S N
_Push_4_g][S S S T  T   S N
_Push_6_i][S T  S S T   T   N
_Copy_3rd_B][S S T  T   S T T   S S T   N
_Push_-89_\n][S S T T   T   S T S T N
_Push_-53_.][S S S T    S S T   N
_Push_9_l][S N
S _Duplicate_9_l][S S S T   T   S S N
_Push_12_o][S S T   T   T   T   T   S N
_Push_-30_E][S T    S S T   S S T   N
_Copy_9th_space][S S S T    N
_Push_1_d][S T  S S T   T   N
_Copy_3rd_o][S S S T    T   T   T   N
_Push_15_r][S S S T S S T   N
_Push_9_l][S S S T  S T S S N
_Push_20_w][S S T   T   T   S T T   N
_Push_-27_H][S T    S S T   T   S N
_Copy_6th_space][S S T  T   T   S T S T N
_Push_-53_.][S S S T    S T N
_Push_5_h][S S S T  S N
_Push_2_e][S S S T  S S T   N
_Push_9_l][S N
S _Duplicate_9_l][S S T T   S T S S N
_Push_-20_O][S T    S S T   T   S N
_Copy_6th_space][S S S T    S T S S N
_Push_20_w][S S S T T   S S N
_Push_12_o][S S S T T   T   T   N
_Push_15_r][S S S T S S T   N
_Push_9_l][S S T    T   T   T   T   T   N
_Push_-31_D][S T    S S T   S T N
_Copy_5th_space][S S T  T   T   S T S T N
_Push_-53_.][S S S T    N
_Push_1_d][S S S T  S S T   N
_Push_9_l][S S S T  T   T   T   N
_Push_15_r][S S S T T   S S N
_Push_12_o][S S T   T   T   S S N
_Push_-12_W][S T    S S T   T   S N
_Copy_6th_space][S S S T    T   S S N
_Push_12_o][S S S T S S T   N
_Push_9_l][S N
S _Duplicate_9_l][S S S T   S N
_Push_2_e][S S T    T   T   S T T   N
_Push_-27_H][N
S S S N_Create_Label_PRINTER
][S N
S _Duplicate][N
T   S N_Jump_to_Label_LOOP_if_0
][S S S T   T   S S S T T   N_Push_99
][T S S S _Add][T   N
S S _Print_as_character][N
S N
S N
_Jump_to_Label_PRINTER]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.
Try it online (containing the raw spaces, tabs and new-lines).
Explanation in pseudo-code:
integer i = input_as_integer
Start LOOP
  i = i-1
  if i is negative:
    EXIT
  Call function PRINT

function PRINT
  Print "Hello World. Dlrow Olleh. Hwlrod Eoll.\n
         Big Brown Fox. Xof Nworb Gib. Bbfgox Iro.\n
         "
  Go to the next iteration of LOOP

Some things I did to golf it:

SNS (Duplicate) is used for repeated characters (ll)
99 is subtracted from every ASCII-value, which we'll add in the PRINT function to reduce loads of bytes. In Whitespace an integer/character is formed by using SS (Stack Manipulation: Push Number) + S or T (Positive or Negative) + some T / S (Binary representation of the number where T=1 and S=0) + N. So having lower binary values and adding the 99 in the PRINT function is shorter than using the large binary values directly.
Since creating the number for a space is 11 bytes (SSTTSSSSTTN), I copied the spaces from the last occurrences to the top of the stack instead. For example, after the first space is created in \n.orI xogfbB, I then use STSSTTSN (copy 6th to top) instead to copy the previous space. The largest distant between two spaces is 9, and since STSSTSSTN (copy 9th to top) is still 2 bytes shorter than SSTTSSSSTTN (create space) I've done this for all spaces to save bytes.
I did something similar as with the copying of spaces above for every character that has a distance of 3 or less. This applies to the B in Big B  and the o in od Eo (Note: The distance between both b in b. Bb is also three, but creating the number for b (SSTTN) is actually shorter than copying the 3rd value to the top of the stack (STSSTTN).)

Game Maker Language, 107
repeat argument0{return "Hello World. Dlrow Olleh. Hwlrod Eoll.#Big Brown Fox. Xof Nworb Gib. Bbfgox Iro."}

Java 8, 121 bytes
n->{for(;n-->0;System.out.println("Hello World. Dlrow Olleh. Hwlrod Eoll.\nBig Brown Fox. Xof Nworb Gib. Bbfgox Iro."));}

Explanation:
Try it online.
n->{           // Method with integer parameter and no return-type
  for(;n-->0;  //  Loop `n` times
    System.out.println("Hello World. Dlrow Olleh. Hwlrod Eoll.\n
                        Big Brown Fox. Xof Nworb Gib. Bbfgox Iro."));}
               //   And print this text + a trailing new-line that many times

Bleh, why bump a challenge like this?

@MagicOctopusUrn I'm just looking for old [tag:string] solutions to practice programming in Whitespace, and noticed this didn't had a Java answer yet either.. Also, golfing languages might be better suited to utilize the repeated characters in the challenge (although it's more likely they just use a text encryption for the entire text, so I understand the duplicated vote..)

@MagicOctopusUrn I've dupe-hammered it.

I mostly wanted to discuss: https://codegolf.meta.stackexchange.com/questions/8143/what-should-we-do-with-old-challenges-no-longer-on-topic but Dennis closed my meta because it already exists apparently. Odd how this predates that challenge though. Technically we should be closing the rickroll one.

"Odd how this predates that challenge though. Technically we should be closing the rickroll one." We don't always close the newer one as a dupe. Sometimes an older one is closed instead if the newer one is much better specified (if the author of the older challenge agrees). Here is a recent example of that, with Martin's reasoning and relevant meta-post at the top.

Oh, I agree, I wonder if there's a meta post on that.

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


text:
Implement cdbmake
Write the shortest program to build a cdb database, using the following syntax for input:

+klen,dlen:key->data

followed by a newline. Example:
+3,5:one->Hello
+3,7:two->Goodbye

(Unlike the real cdbmake, your program doesn't need to catch the empty-line-as-end-of-input case if you don't want to.) Your program needs to handle arbitrary strings (including NUL, newline, +, ,, :, and/or ->) in both the key and data correctly; therefore, using any kind of line-based input is likely to be wrong. You may assume the input is always valid, and you can assume that there is at most one instance of any key in the input.
The hash tables your program generates must behave like real hash tables. In other words, the hash tables should provide amortised constant-time lookups.
If your language provides built-in hash tables, you're allowed to use them, if they help any. However, do not use any cdb libraries or cdb programs to solve this question.
If your program writes the cdb to standard output, you may assume that it's redirected to a regular file. For example, you may seek or mmap it.
In the case of multiple shortest entries, the earliest-posted wins (as stipulated by the fastest gun in the west rule).

Here's a complete description of cdb's format as written by cdb's inventor:

A cdb is an associative array: it maps strings (keys) to strings
  (data).
A cdb contains 256 pointers to linearly probed open hash tables. The
  hash tables contain pointers to (key,data) pairs. A cdb is stored in
  a single file on disk:
+----------------+---------+-------+-------+-----+---------+
| p0 p1 ... p255 | records | hash0 | hash1 | ... | hash255 |
+----------------+---------+-------+-------+-----+---------+

Each of the 256 initial pointers states a position and a length. The
  position is the starting byte position of the hash table. The length
  is the number of slots in the hash table.
Records are stored sequentially, without special alignment. A record
  states a key length, a data length, the key, and the data.
Each hash table slot states a hash value and a byte position. If the
  byte position is 0, the slot is empty. Otherwise, the slot points to
  a record whose key has that hash value.
Positions, lengths, and hash values are 32-bit quantities, stored in
  little-endian form in 4 bytes. Thus a cdb must fit into 4 gigabytes.
A record is located as follows. Compute the hash value of the key in
  the record. The hash value modulo 256 is the number of a hash table.
  The hash value divided by 256, modulo the length of that table, is a
  slot number. Probe that slot, the next higher slot, and so on, until
  you find the record or run into an empty slot.
The cdb hash function is h = ((h << 5) + h) ^ c, with a starting
  hash of 5381.

Could you be more precise as to where the boundary is between hashes that are accepted and hashes that aren't?

@J B: Updated the question. :-) Basically, you need to provide amortised constant-time lookups. Once you get a small handful of collisions, it's time to expand the hash table!

@Chris but do we need to try and keep the table as small as possible?

My understanding of cdb format is that it doesn't offer constant-time lookups in the usual sense (i.e. "linearly probed open hash  tables"). The lookup time merely seems fairly constant because only 2 disk seeks are usually required, and the time spent linearly probing those data is insignificant because cpu+ram is much faster than a disk seek (for mechanical disks anyway)

Also, do read from stdin or a file?

@gnibbler: Actually, with a sufficiently sparse hash table, they are indeed amortised constant-time lookups. You want to minimise collisions as much as possible (i.e., find a value of n where (hash >> 8) % n is relatively unique for all elements in the same hash table). The way I understand the format, you can expect n to be somewhat larger than count(elements).

@Juan: No, you don't need to try to golf the hash tables. :-) Also, the input can be from a file or stdin, as you please. Just as the output can be to a file or stdout, as you please.

@gnibbler: Indeed, due to the "linearly probed" aspect (i.e., the slots are essentially all sized for a single element, with collisions spilling to the next slot), you cannot implement cdb with n < count(elements).

Python - 398 chars
import os;from struct import*
Q=256;S=[[]for x in' '*Q];D=[0]*Q;O=Q*8;R=os.read(0,1e9)[1:];J="".join
while R:
 i,R=R.split(":",1);l,m=map(int,i.split(','));k,v,R=R[:l],R[l+2:2+l+m],R[2+l+m:];R=R.partition("+")[2];D+=[pack("II",l,m)+k+v];h=5381
 for c in k:h=h*33^ord(c)%Q**4
 S[h%Q]+=[pack("II",h,O)];O+=len(D[-1])
for i,s in enumerate(S):D[i]=pack("II",O,len(s));D+=[J(s)];O+=len(D[-1])
print J(D)

Python - 552 characters
from sys import*
from struct import*
y=lambda f,i:stdout.write(pack(f,*i))
u=lambda i:y('<II',i)
i=stdin.read()
n=0
t=[[]for c in' '*256]
q=[]
m=[]
o=2048
w=list.append
while len(i)>n:
 d=i.find(':',n);f,g=map(int,i[n+1:d].split(','));n=d+1+f;k=i[d+1:n];d=i[n+2:n+2+g];h=5831;for c in k:h=(((h<<5)+h)^ord(c))&0xffffffff
 w(t[h%256],(h,o));o+=8+f+g;w(m,map(str,(f,g,k,d)));n+=3+g
for d in t:
 l=len(d)**2;t=[(0,0)]*l;u((o,l));o+=l*8
 for r in d:
  i=r[0]>>8
  while t[i%l][0]:i+=1
  t[i%l]=r
 w(q,t)
for v in m:y('<II'+zip(v,'ss'),v)
for t in q:map(u,t)

q=[]:m=[] can be shortened to q=m=[], no?

@Gaffi that would make them point to the same array, instead of two different instances