text:
Conversion to palindrome with minimal points used
Input: a word (2-100 characters)
Convert this word to a palindrome:

delete character - 13 points
add character - 12 points
increase character - 5 points ('d' > 'e')
decrease character - 4 points ('n' > 'm')
switch 2 characters - 7 points

What is the minimal points needed to make the word palindrome? (C++/C#)
Output: Minimal points needed to convert the word
Winning criteria: fastest algorithm

Why is it restricted to C and C++?

@userunknown so I can understand the algorithm :)

And what is the objective winning criteria?

@userunknown sorry, I'm new in codegolf.SE, and I thought that with the code-challenge tag it was obvious, since I don't want to see backtracking algorithms ^^

Meh. Graph search.

There is a meta page to prepare questions, and the chat, and the FAQ. 2) You're free to restrict solutions to C and C#, but this will cost you much audience. 3) A code-challenge may still have some guidelines, and should have a date, when the decision is made.

how many points for replacing a character? The same as switch?

Also, no points for comparing two characters?

Can you switch any two characters or just adjacent ones?

@hammar you can switch any two characters

@elssar replacing means that you remove one, then add a new one

Well I'm replacing with another character of the string, so it's like half a swap.

Spent about an hour and got a working solution that I believe should give an optimal result:
public class PalindromeFinder : IComparer<Tuple<int,string>>
    {
        public PalindromeFinder()
        {
            heap = new IntervalHeap<Tuple<int, string>>(this);
            handles = new Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>>();
        }

        private readonly IntervalHeap<Tuple<int, string>> heap;
        private readonly Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>>  handles;

        public int FindMinValue(string startingWord)
        {
            AddWord(startingWord,0);
            while(!heap.IsEmpty)
            {

                var item = heap.DeleteMin();
                var word = item.Item2;
                var value = item.Item1;
                handles.Remove(word);
                if(IsPalindrome(word))
                {
                    return value;
                }
                for(int i = 0; i<word.Length; i++)
                {
                    //decrease
                    var decreased = word.ToCharArray();
                    if (decreased[i] > 'a')
                    {
                        decreased[i]--;
                        AddWord(new string(decreased), value + 4);
                    }
                    //switch
                    for(int j = i+1; j<word.Length; j++)
                    {
                        if (word.Count(x => x == word[i]) >= 2 || word.Count(x => x == word[j]) >= 2)
                        {
                            var swap = word.ToCharArray();
                            var tmp = swap[i];
                            swap[i] = swap[j];
                            swap[j] = tmp;
                            AddWord(new string(swap), value + 7);
                        }
                    }
                    //add character before (only add characters already present)
                    foreach (char c in word.Distinct())
                    {
                        var added = word.Insert(i, c.ToString());
                        AddWord(added, value+12);
                    }
                }
                //add character at end of word
                foreach (char c in word.Distinct())
                {
                    var added = word + c.ToString();
                    AddWord(added, value + 12);
                }
            }
            return int.MaxValue;
        }

        private void AddWord(string word, int value)
        {
            var min = int.MaxValue;
            if(handles.ContainsKey(word))
            {
                var tuple = heap.Delete(handles[word]);
                min = tuple.Item1;
                handles.Remove(word);
            }
            IPriorityQueueHandle<Tuple<int, string>> handle = null;
            heap.Add(ref handle,new Tuple<int, string>(Math.Min(min, value), word));
            handles[word] = handle;
        }

        private bool IsPalindrome(string word)
        {
            int left = 0;
            int right = word.Length - 1;
            while(left<right)
            {
                if (word[left] != word[right]) return false;
                left++;
                right--;
            }
            return true;
        }

        public int Compare(Tuple<int, string> x, Tuple<int, string> y)
        {
            return x.Item1 - y.Item1;
        }
    }

Uses priority queue implementation from C5 collections. This is basically the brute force best-first search solution to the problem. It runs out of memory pretty fast, and is less efficient than is probably possible. I could fix that by implementing a better data structure like a DAWG, but out of time for now. Maybe later.It does work well for short words, and even for long ones that are within a few steps of a palindrome already.
Edit:
Made some improvements on Peter's suggestion, but the complexity is still too high. On input: "superman", runs for about a minute until it runs out of memory with over 11 million items in heap and a max value of 42 reached. Still a bit off from being a viable general solution.

You've got a copy-paste bug in the decrease case. Although it would be "better" to reuse the char[] and just do increased[i]-=2;.

Also, you can limit the memory required to some extent by setting a bound. Anything which takes more than 13*(startingWord.Length-1) can be discarded in AddWord.

Good catch on the bug. edited in. I think that optimization would not help very much though. There are a ton of possibilities with scores far lower than 13N. For "superman", it runs out of memory when the maximum value in the heap is only 38, with 11 million entries. I think to improve this I need to do some sort of estimation and apply A* to the search. Having trouble deciding on a consistent heuristic though.

On further thought, incrementing a character is never going to be optimal (decrementing the one it matches is better), and deleting a character is never going to be optimal (inserting one to match it is better), and there's no point doing a swap unless one of the characters you swap is present in multiple copies. Those should reduce the branching factor considerably.

I hadn't considered those. I figured maybe a swap-increment sequence might lead to something, but there would indeed be a corresponding decrement-swap sequence.

C++
Made this under the assumption that simply changing the character costs the same as switching two characters(7 points) & that comparing costs 0 points. A pretty basic & dumb solution, but it works.
int main(int argc, char *argv[]) {
    int c, l, p;
    p = 0;
    if(argc != 2) {
        cout<<"Incorrect arguments\n";
        return 1;
    }
    else if(strlen(argv[1])<2 || strlen(argv[1])>100) {
        cout<<"Not a valid string(between 2 & 100 characters)\n";
        return 1;
    }
    l = strlen(argv[1]);
    c = l/2;
    for(int i=0;i<c;i++) {
        if(argv[1][i] != argv[1][l-i-1]) {
            argv[1][i] = argv[1][l-i-1];
            p+=7;
        }
    }
    cout<<argv[1]<<endl<<p<<endl;
    return 0;
}

if the string is "abcddba", the cost is 4

@e-MEE yeah that's the minimum required. My algorithm is not that elegant. Will have to do a complete rewrite to get that kind of efficiency


text:
Fastest Sort in BrainF***
After having implemented QuickSort in BrainF***, I realized it probably wasn't that quick.  Operations that are O(1) in normal languages (like array indexing) are significantly longer in BF.  Most of the rules for what makes an efficient sort can be thrown out the window when you are coding in a Turing tarpit.
So here is a challenge to implement the "Fastest BrainF*** Sort Routine Ever".   I will time all entries using the interpreter below.  The intepreter uses a 16K tape of unsigned characters.  Both the tape and the cells wrap when advanced/incremented past the limits. Reading the EOF puts a 0 in the current cell.  The measured time includes both the time to parse the source file and the time to process all input files.   Fastest code wins.
The test vector will be a set of Ascii files designed to test sorting edge cases, including

An already sorted list: "ordered"
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

A reverse sorted list: "reverse"
~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!

A file consisting of many copies of a few unique values: "onlynine"
ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiuk

A completely random ascii file: "random"
'fQ`0R0gssT)70O>tP[2{9' 0.HMyTjW7-!SyJQ3]gsccR'UDrnOEK~ca 'KnqrgA3i4dRR8g.'JbjR;D67sVOPllHe,&VG"HDY_'Wi"ra?n.5nWrQ6Mac;&}~T_AepeUk{:Fwl%0`FI8#h]J/Cty-;qluRwk|S U$^|mI|D0\^- csLp~`VM;cPgIT\m\(jOdRQu#a,aGI?TeyY^*"][E-/S"KdWEQ,P<)$:e[_.`V0:fpI zL"GMhao$C4?*x

A random file over the range 1..255:  "wholerange"
öè—@œ™S±ü¼ÓuÇ¯ŠfÎ€n‚ZÊ,ˆÖÄCítÚDý^öhfF†¬I÷xxÖ÷GààuÈ©ÈÑdàu.y×€ôã…ìcÑ–:*‰˜IP¥©9Ä¢¬]Š\3*\®ªZP!YFõ®ÊÖžáîÓ¹PŸ—wNì/S=Ìœ'g°Ì²¬½ÕQ¹ÀpbWÓ³
»y  »ïløó„9k–ƒ~ÕfnšÂt|Srvì^%ÛÀâû¯WWDs‰sç2e£+PÆ@½ã”^$f˜¦Kí•òâ¨÷ žøÇÖ¼$NƒRMÉE‹G´QO¨©l¬k¦Ó

Each input file has at most 255 bytes.
Here is the interpreter. It's written for console-mode Windows, but should be easy to port: just replace read_time() and sysTime_to_ms() with platform-specific equivalents.
Usage:  bftime program.bf infile1 [infile2 ...]
#include <windows.h>
#include <stdio.h>

#define MS_PER_SEC  1000.0f
#define MAXSIZE  (0x4000)
#define MAXMASK  (MAXSIZE-1)

typedef  __int64 sysTime_t;
typedef unsigned char Uint8;
typedef unsigned short Uint16;

typedef struct instruction_t {
   Uint8 inst;
   Uint16 pair;
} Instruction;

Instruction prog[MAXSIZE] = {0};
Uint8 data[MAXSIZE] = {0};
const Uint8 FEND = EOF;

sysTime_t read_time() {
    __int64 counts;
    QueryPerformanceCounter((LARGE_INTEGER*)&counts);
    return counts;
}

float sysTime_to_ms(sysTime_t timeIn) {
    __int64 countsPerSec;
    QueryPerformanceFrequency((LARGE_INTEGER*)&countsPerSec);
    return (float)timeIn * MS_PER_SEC / (float)countsPerSec;
}

int main(int argc, char* argv[])
{
   FILE* fp;
   Uint8 c;
   Uint16 i = 0;
   Uint16 stack = 0;
   sysTime_t start_time;
   sysTime_t elapsed=0,delta;

   if (argc<3) exit(printf("Error: Not Enough Arguments\n"));
   fp = fopen(argv[1],"r");
   if (!fp) exit(printf("Error: Can't Open program File %s\n",argv[1]));

   start_time=read_time();
   while (FEND != (c = fgetc(fp)) && i <MAXSIZE) {
      switch (c)  {
      case '+': case '-': case ',': case '.': case '>': case '<':
         prog[++i].inst = c;
         break;
      case '[':
         prog[++i].inst = c;
         prog[i].pair=stack;
         stack = i;
         break;
      case ']':
         if (!stack) exit(printf("Unbalanced ']' at %d\n",i));
         prog[++i].inst = c;
         prog[i].pair=stack;
         stack = prog[stack].pair;
         prog[prog[i].pair].pair=i;
         break;
      }
   }
   if (stack) exit(printf("Unbalanced '[' at %d\n",stack));
   elapsed = delta = read_time()-start_time;
   printf("Parse Time: %f ms\n", sysTime_to_ms(delta));

   for (stack=2;stack<argc;stack++) {
      Instruction *ip = prog;
      fp = fopen(argv[stack],"r");
      if (!fp) exit(printf("Can't Open input File %s\n",argv[stack]));
      printf("Processing %s:\n", argv[stack]);
      memset(data,i=0,sizeof(data));

      start_time=read_time();
      //Run the program
      while (delta) {
         switch ((++ip)->inst) {
         case '+': data[i]++; break;
         case '-': data[i]--; break;
         case ',': c=getc(fp);data[i]=(FEND==c)?0:c; break;
         case '.': putchar(data[i]);  break;
         case '>': i=(i+1)&MAXMASK;   break;
         case '<': i=(i-1)&MAXMASK;   break;
         case '[': if (!data[i]) ip = prog+ip->pair; break;
         case ']': if (data[i])  ip = prog+ip->pair;  break;
         case 0: delta=0; break;
         }
      }
      delta = read_time()-start_time;
      elapsed+=delta;
      printf("\nProcessing Time: %f ms\n", sysTime_to_ms(delta));
   }
   printf("\nTotal Time for %d files: %f ms\n", argc-2, sysTime_to_ms(elapsed));
}

Results So Far
Here's the average time of 5 runs of the complete set of vectors:
 Author    Program      Average Time    Best Set          Worst Set
 AShelly   Quicksort    3224.4 ms       reverse (158.6)   onlynine (1622.4)
 K.Randall Counting     3162.9 ms       reverse (320.6)   onlynine  (920.1)
 AShelly   Coinsort      517.6 ms       reverse  (54.0)   onlynine  (178.5)
 K.Randall CountingV2    267.8 ms       reverse  (41.6)   random     (70.5)
 AShelly   Strandsort    242.3 ms       reverse  (35.2)   random     (81.0)

What is the range of the input elements?

It is the range of the cells, except 0:  1-255.

you should retime mine, I made it quite a bit faster.

It does appear to be more than 2x faster than my most recent - I'll do the official timing when I'm back on the machine I used for the others.

>>+>,[->+>,]<[<[<<]<[.<[<<]<]>>[+>->]<<]

I don't remember whose idea this algorithm was. Maybe Bertram Felgenhauer's? It came from discussions around Brainfuck Golf contest #2, over a decade ago.
This is the fastest one yet on the sample inputs.
It's also not limited to inputs of length <256, but can handle arbitrarily long inputs.
Both these things were also true of Albert's answers, below. The nice thing about this one is that the running time is O(N) in the input length. Yes, this thing actually runs in linear time. It already ate a constant factor of 255 as a snack.

Here's a sort that is at least 6x faster than my quicksort.  It's an algorithm that would make little sense in a traditional language, since it's O(N*m) where m is the maximum input value.  After collecting the input, it passes through the array, counting cells > 0 and then  decrementing each one.  It then adds 1 to the first count cells in the result vector.  It repeats the passes until the count is 0.
BF:
Get Input
>,[>>+>,]
Count values GT 0 and decrement each
<[<[<<<+>>>-]<[-<<+>>>]>[<]<<]
While count: add 1 to results
<[[[<<+>>-]<+<-]
Seek back to end of input
>[>>]>>>[>>>]
Repeat counting step
<<<[<[<<<+>>>-]<[-<<+>>>]>[<]<<]<]
Seek to far end of results and print in reverse order
<[<<]>>[.>>]

C equivalent algorithm:
 uchar A[MAX]={0}; uchar R[MAX]={0}; int count,i,n=0;
 while (A[n++]=getchar()) ;
 do {
   count = 0;
   for (i=0; i<n; i++) count += (A[i]) ? (A[i]-->0) : 0;
   for (i=0; i<count; i++) R[i]++;
 } while (count>0);
 for (i=0; R[i]; i++) ;
 for (i--; i>=0; i--) putchar(R[i]);

Here's one that's 2x as fast.  It's based loosely on "spaghetti sort": it lays down a string of 1s as long as each input.  The value in each cell represents the number of strands at least that long.   (So [3,2,1,2] becomes |4|0|3|0|1|0|0|).  Then it starts 'measuring' the strands and prints out the length every time it finds the end of one.
>,[ [-[>>+<<-]>+>] <[<<]>,]   build strand of 1s for each input
+>[>+<-]>[                    while there are strands
  >[>+<<->-]                  do any strands end here?
  <[<<.>>-]                   print length of all that do
  <<[>>+<<-]>>+>>]            shift right 1; inc length

Raw:
>,[[-[>>+<<-]>+>]<[<<]>,]+>[>+<-]>[>[>+<<->-]<[<<.>>-]<<[>>+<<-]>>+>>]

Don't knock counting sort!  It's my favorite sort, due to a massive win I got from it one time: if m is known to be small, you can get huge speedups over otherwise "fast" algorithms.  Similarly, bubble sort beats quicksort on mostly-sorted data.  No one ___ algorithm is the best for every context.

I don't think this is exactly a counting sort.  Your comment forced me to do some more research.  I think this is more like a bead sort.  But I'm not even sure that's right.

No, you're right.  This is a strange sort.  Could be useful for some application involving lists of linked lists... but I'm dubious of even that.

The physical analogy is that you have N stacks of coins of different sizes. Set aside space for another N stacks. You take one coin off the top of each stack that has coins, and then add 1 to each stack in the new set from right to left until your hand is empty.  Repeat until all original stacks are empty.  Now  the new set is sorted ascending left to right.

A simple counting sort implementation.  Each bucket is 3 cells wide, containing the current input, a marker, and the count of the number of times the counter appears in the input.
process input
,[

while input is not zero
[

decrement input
-

copy input over to next bucket
[->>>+<<<]

mark next bucket as not the first
>>>>+<

repeat until input is zero
]

increment count for this bucket
>>+

rewind using markers
<[-<<<]<

process next input
,]

generate output
>+[>[<-.+>-]<[->>>+<<<]>>>+]

without comments:
,[[-[->>>+<<<]>>>>+<]>>+<[-<<<]<,]>+[>[<-.+>-]<[->>>+<<<]>>>+]

>,[>+>,]+[<[<-<]>>[<[>>]>[<->[>>]<.<[<<]]>>]<<<<<+]

>>+>,[>+>,]<[[<-<]>+>+[>]>[[-<<[[>>+<<-]<]>>]>-.+[>]>]<<]

source: Stack Exchange

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

sort: votes


text:
"First time" test
What is the shortest C expression that is defined to evaluated to false the first time and true for every time after that:
Reference implementation:
bool b = false;  // you get this for free.

(b ? true : b = true, false)  // only this line is measured.

Since the task description in fact states that it should return true for every time after the initial false, I'd say that solutions that work only a limited time (even if it's 500+ years) don't count as correct solutions.

3 chars:
As Keith Randall suggested in a comment, if we can use floats or doubles, this should do the trick:
float b = 0;  // free

b++

Eventually, as b is incremented repeatedly, two things may happen: either the addition overflows (and thus evaluates to HUGE_VAL, which may be infinite or a large positive value) or, more likely, the roundoff step size simply grows larger than one, turning the increment into a no-op.  In either case, the expression should continue to evaluate as true.

That will happen at ~1/ε  http://en.wikipedia.org/wiki/Machine_epsilon

I think that is valid and I don't think anything smaller is going to work (there are no mutating single char unary operators). OTOH coercion a floating point to bool offends my sensibilities (as well as FP-ops being slower than int-ops).

To be precise, b stops growing at 16777216.0 (=2^24), as there are only 23 bits of mantissa in a float.

BTW: I'm not sure but ++ on a bool might work as well: http://stackoverflow.com/a/3450554/1343

6 characters
int i = 0; //free
i||i++

OTOH: I like Peter Taylor's solution as it has no branch so it may be faster (depending on compiler details).
p.s. I came up with that after posting the question (honest!).

After the first time, the left side of the || will be true and short-circuit evaluation will prevent the right side from getting evaluated so nothing gets updated.

Argh, indeed. I take that back :)

With:
long long b = 0;

then three characters are enough for many applications:
b++

Evaluates false first and true for a long time thereafter ;-)

I'd say it'll be true for a long, long time.

It evaluates true only 18446744073709551614 times, not forever :-/

Use a double and it will be true forever!

And unless you make that unsigned, it is undefined behavior.

18446744073709551614 times.  Assuming we could perform this operation 1 billion times per second, it would take about 585 years.

-1: Does not follow specs true for every time after that.

I flagged it for deletion.

7 characters
As Peter Taylor suggested, still int a = 2;
!(a/=2)

8 characters (old)
Start with int a = 2;
!(a>>=1)

Another version of this: int b = 0x40000000;
!(b<<=1)

The first one is portable. The second isn't. But doesn't !(a/=2) work?

@PeterTaylor yeah, you're right. Thinking too complicated ...

The left shift works and is defined if you go with unsigned ints and use 0xD... which I think you can get in a portable way via ~((~0u)>>2).

@BCS thanks for the info, but I'll just leave it at that because the other two versions are shorter anyway.

9 chars:
b=0;//free
(b&(b=1))

at least if it's valid c (not undefined behavior)
12 chars
(b?b:!(b=1))

this is valid c

int b=1; // for free
!b|(b=0)

bit-wise or works as well since in first trial 0|0 yields 0 and in other trials !0|0 yields !0 which is guaranteed to be true. It is also ANSI-compliant, I've tried the following code with GCC 4.6.1 with -ansi flag:
#include <stdio.h>
main () {
  int b=1, i=0;
  for (;i<5;++i)
    printf ("%d",!b|(b=0));
}

This is undefined behavior. The compiler could evaluate b=0 first and !b later, making it true the first time.

11 10 chars
I can't beat the three char approach, but make it different:
int b = 0;  // free

b?b:0*(b=1) // 11 characters
b||0*(b=1)  // one character less thanks to breadbox

That wound count as 11 and doesn't work as it is two different expressions.

@BCS I thought the first initialization was for free (so, the chars do not count), and the second one is an expression to be evaluated. I fail to see why wouldn't it work.

I was summing you were considering the expression in the first line to be the "gives false" and the other to be the "gives true". ---- The expression will evaluate to 1 (i.e. true) every time, including the first. The spec is that the expression is true the first time and false there after.

@BCS Got it! Will update now to reflect your correction and will think a little bit about it. I'll see if I can give it a twist. Thanks!

b?b=1:0*(b=1) actually works.

@walpen Thanks! I had completely forgotten about this answer. I've updated based on your comment, reducing out the first b=1 to b, as it would be already 1 in that case, right? (Or is there something else I am overseeing?)

You don't need the ternary operator; b||0*(b=1) would also work.

APL (5 or 6)
If I'm only allowed to initialize the variable to 0, it's 6 characters:
A←0    ⍝ free
⊃A←⍴⍴A

How it works: ⍴A is the size of A (which is the empty list the first time around, because 0 is a scalar), so ⍴⍴A is the size of the size of A (which is [0] the first time, because a one-dimensional empty list has zero values in one dimension). This is then assigned to A (A←) and the first element is returned (⊃).

A is 0, ⍴A is [], then A is set to ⍴⍴A which is [0], and the first element is returned (0).
A is [0], ⍴A is [1], then A is set to ⍴⍴A which is [1], and the first element is returned (1).
A is [1], so ⍴A remains [1], so A is set to ⍴⍴A which remains [1] and it returns 1.

If I'm allowed to initialise the variable to anything I want, I can set it to the empty list and drop one of the ⍴s to make it 5 characters:
A←⍬    ⍝ free, set to empty list
⊃A←⍴A

What about this:
bool b = false;

!b+b++

I think that is undefined behavior (and it will overflow and reset)

Why do you think so? What exactly is undefined? plusplusing a boolean? Or the priority of post-increment operation?

The value depends on order of evaluation which is undefined behavior. 2) Either that will eventually overflow (and both hit undefined behavior as well as return false) or the 3 char solution (b++) works with bool as well: http://stackoverflow.com/a/3450554/1343

The answer in the link you provided quotes C++03 standard. Does this standard apply to C99 as well?

I'm reasonably sure that it is undefined in C as well.

9 chars
b=1; //free
!b||(b=0)

edited: no longer undefined behavior

that very similar to a=a++ which is undefined

now defined, +3 chars :(

bool b = false; // for free?
b = b?b:!b;

1 Character
Since you didn't specify which compiler and/or which command line options are to be used, here's my 1 character solution:
bool b = false;

X

Compile with
gcc -DX='(b ? true : b = true, false)'

As a general rule, codegolf counts special command-line options towards the score. So this would be 41+ characters.

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


text:
Text compression and decompression — "Nevermore."
With the recent discussion about the use of compression tools in code golf, I thought it would be a nice challenge to write your own text compressor and decompressor.
Challenge:
Write two programs: one to compress ASCII text into a sequence of bytes, and another to decompress it.  The programs need not be in the same language.
The first program should read a piece of ASCII text (from a file or from standard input, or using whatever mechanism is most natural to the language) and output a compressed version of it.  (The compressed output may consist or arbitrary bytes; it need not be readable.)  The second program should read the output of the first and recreate the original input text.
Scoring:
The score of a solution will be the sum of the following three counts:

The length of the compressor program in characters.
The length of the output of the compressor, given the test input below, in bytes.
The length of the decompressor program (if different from the compressor) in characters.

You should note all three counts and their sum in your answer.  Since this is code golf, the lower the score, the better.
Rules and restrictions:

You may not use any pre-existing compression or decompression tools or libraries, even if they come bundled with your chosen language.  If in doubt about whether a given tool or function is allowed, please ask.
Your compressor program must be capable of handling input consisting of any printable ASCII text, including tabs (ASCII 9) and line feeds (ASCII 10).  You may, but are not required to, handle arbitrary Unicode and/or binary input.
Your decompressor program must produce exactly the same output as was given to the compressor as input.  In particular, take care not to output a trailing line feed if the input did not have one.  (The test input below does have a trailing line feed, so you'll need to test for this separately.  Tip for GolfScript: '':n.)
Your compressor and decompressor may be the same program (with the appropriate mode selected e.g. with a command line switch).  In that case, its length is only counted once.
The programs should not be exceedingly slow or memory-hungry.  If either compressing or decompressing the test input takes more than a minute on my not-so-new desktop (2.2GHz AMD Athlon64 X2) or consumes more than a gigabyte of RAM, I'm going to rule the solution invalid.  These limits are deliberately lax — please try not to push them. (See amendment below: you need to be able to handle at least 100 kB of input within these limits.)
Even though only the test input matters for scoring, you should at least make an effort at compressing arbitrary input text.  A solution that achieves a decent compression ratio only for the test input, and for nothing else, is technically valid but isn't going to get an upvote from me.
Your compressor and decompressor programs should be self-contained.  In particular, if they depend on being able to read some file or network resource that is not part of your chosen language's standard runtime environment, the length of that file or resource should be counted as part of the length of the program(s).  (This is to disallow "compressors" that compare the input to a file on the web and output zero bytes if they match.  Sorry, but that's not a new trick anymore.)

Amendments and clarifications:

Your compressor must be able to handle files consisting of at least 100 kB of typical English text within reasonable time and memory usage (at most one minute and one GB of memory).  Your decompressor must be able to decompress the resulting output within the same limits.  Of course, being able to handle files longer than that is perfectly fine and commendable.  It's OK to split long input files into chunks and compress them individually, or to use other means to trade off compression efficiency for speed for long inputs.
Your compressor may require its input to be given using your preferred platform's native newline representation (LF, CR+LF, CR, etc.), as long as your decompressor uses the same newline representation in its output.  Of course, it's also fine for the compressor to accept any kind of newlines (or even only Unix newlines regardless of platform), as long as your decompressor then outputs the same kind of newlines as in the original input.

Test input:
To judge the compression efficiency of the answers, the following test input (The Raven by Edgar Allan Poe, courtesy of Project Gutenberg) will be used:
Once upon a midnight dreary, while I pondered, weak and weary,
Over many a quaint and curious volume of forgotten lore,
While I nodded, nearly napping, suddenly there came a tapping,
As of some one gently rapping, rapping at my chamber door.
"'T is some visiter," I muttered, "tapping at my chamber door--
                                          Only this, and nothing more."

Ah, distinctly I remember it was in the bleak December,
And each separate dying ember wrought its ghost upon the floor.
Eagerly I wished the morrow:--vainly I had sought to borrow
From my books surcease of sorrow--sorrow for the lost Lenore--
For the rare and radiant maiden whom the angels name Lenore--
                                          Nameless here for evermore.

And the silken sad uncertain rustling of each purple curtain
Thrilled me--filled me with fantastic terrors never felt before;
So that now, to still the beating of my heart, I stood repeating
"'T is some visiter entreating entrance at my chamber door
Some late visiter entreating entrance at my chamber door;--
                                          This it is, and nothing more."

Presently my soul grew stronger; hesitating then no longer,
"Sir," said I, "or Madam, truly your forgiveness I implore;
But the fact is I was napping, and so gently you came rapping,
And so faintly you came tapping, tapping at my chamber door,
That I scarce was sure I heard you"--here I opened wide the door;--
                                          Darkness there, and nothing more.

Deep into that darkness peering, long I stood there wondering, fearing,
Doubting, dreaming dreams no mortal ever dared to dream before;
But the silence was unbroken, and the darkness gave no token,
And the only word there spoken was the whispered word, "Lenore!"
This I whispered, and an echo murmured back the word, "Lenore!"
                                          Merely this and nothing more.

Back into the chamber turning, all my soul within me burning,
Soon again I heard a tapping, somewhat louder than before.
"Surely," said I, "surely that is something at my window lattice;
Let me see, then, what thereat is, and this mystery explore--
Let my heart be still a moment and this mystery explore;--
                                          'T is the wind and nothing more!"

Open here I flung the shutter, when, with many a flirt and flutter,
In there stepped a stately Raven of the saintly days of yore.
Not the least obeisance made he; not a minute stopped or stayed he;
But, with mien of lord or lady, perched above my chamber door--
Perched upon a bust of Pallas just above my chamber door--
                                          Perched, and sat, and nothing more.

Then this ebony bird beguiling my sad fancy into smiling,
By the grave and stern decorum of the countenance it wore,
"Though thy crest be shorn and shaven, thou," I said, "art sure no craven,
Ghastly grim and ancient Raven wandering from the Nightly shore,--
Tell me what thy lordly name is on the Night's Plutonian shore!"
                                          Quoth the Raven, "Nevermore."

Much I marvelled this ungainly fowl to hear discourse so plainly,
Though its answer little meaning--little relevancy bore;
For we cannot help agreeing that no living human being
Ever yet was blessed with seeing bird above his chamber door--
Bird or beast upon the sculptured bust above his chamber door,
                                          With such name as "Nevermore."

But the Raven, sitting lonely on the placid bust, spoke only
That one word, as if his soul in that one word he did outpour.
Nothing further then he uttered--not a feather then he fluttered--
Till I scarcely more than muttered, "Other friends have flown before--
On the morrow _he_ will leave me, as my hopes have flown before."
                                          Then the bird said, "Nevermore."

Startled at the stillness broken by reply so aptly spoken,
"Doubtless," said I, "what it utters is its only stock and store,
Caught from some unhappy master whom unmerciful Disaster
Followed fast and followed faster till his songs one burden bore--
Till the dirges of his Hope that melancholy burden bore
                                          Of 'Never--nevermore.'"

But the Raven still beguiling all my sad soul into smiling,
Straight I wheeled a cushioned seat in front of bird and bust and door;
Then, upon the velvet sinking, I betook myself to linking
Fancy unto fancy, thinking what this ominous bird of yore--
What this grim, ungainly, ghastly, gaunt and ominous bird of yore
                                          Meant in croaking "Nevermore."

This I sat engaged in guessing, but no syllable expressing
To the fowl whose fiery eyes now burned into my bosom's core;
This and more I sat divining, with my head at ease reclining
On the cushion's velvet lining that the lamplight gloated o'er,
But whose velvet violet lining with the lamplight gloating o'er
                                          _She_ shall press, ah, nevermore!

Then, methought, the air grew denser, perfumed from an unseen censer
Swung by seraphim whose foot-falls tinkled on the tufted floor.
"Wretch," I cried, "thy God hath lent thee--by these angels he hath sent thee
Respite--respite and nepenthe from thy memories of Lenore!
Quaff, oh quaff this kind nepenthe, and forget this lost Lenore!"
                                          Quoth the Raven, "Nevermore."

"Prophet!" said I, "thing of evil!--prophet still, if bird or devil!--
Whether Tempter sent, or whether tempest tossed thee here ashore,
Desolate yet all undaunted, on this desert land enchanted--
On this home by Horror haunted--tell me truly, I implore--
Is there--_is_ there balm in Gilead?--tell me--tell me, I implore!"
                                          Quoth the Raven, "Nevermore."

"Prophet!" said I, "thing of evil--prophet still, if bird or devil!
By that Heaven that bends above, us--by that God we both adore--
Tell this soul with sorrow laden if, within the distant Aidenn,
It shall clasp a sainted maiden whom the angels name Lenore--
Clasp a rare and radiant maiden whom the angels name Lenore."
                                          Quoth the Raven, "Nevermore."

"Be that word our sign of parting, bird or fiend!" I shrieked, upstarting--
"Get thee back into the tempest and the Night's Plutonian shore!
Leave no black plume as a token of that lie thy soul hath spoken!
Leave my loneliness unbroken!--quit the bust above my door!
Take thy beak from out my heart, and take thy form from off my door!"
                                          Quoth the Raven, "Nevermore."

And the Raven, never flitting, still is sitting, still is sitting
On the pallid bust of Pallas just above my chamber door;
And his eyes have all the seeming of a demon's that is dreaming,
And the lamplight o'er him streaming throws his shadow on the floor;
And my soul from out that shadow that lies floating on the floor
                                          Shall be lifted--nevermore!

The correct test input (encoded with Unix-style LF newlines) should be 7043 bytes long, and have the hexadecimal MD5 hash 286206abbb7eca7b1ab69ea4b81da227.  (md5sum -t should produce the same hash value even if you use CR+LF newlines on DOS/Windows.)  The output of your decompressor should have the same length and hash.
Ps. Keep in mind that this challenge is only as hard as you make it.  Really, anything under 7043 counts as a good score.  (At the other end of the scale, I'll be extremely impressed if anyone achieves a score under 2500.)

So I take it you don't want to see any lossy compression?

Preemptive note for people who can't get the MD5 hash to match: the text file has Unix newlines for line enders.  Also, be sure you have the final newline in the file for the full 7043 byte length.

@GigaWatt: Yeah, I should've been more explicit about the newlines. Since I've restricted the input to ASCII text only, I guess I could allow people to use whatever newline convention feels most natural for them, as long as they use it consistently. I'll try to think of a nice way to phrase that in the challenge. And no, the compressor should not be lossy.

How about file length, is it required to run (in acceptable time) only for files in the order of size of the example, or also for much bigger files (>some MB)?

@leftaroundabout: I'll... actually have to think about that a bit more. My first impulse was to say that only the test input matters, but that's not really where I want to go with this challenge. I think I'll set some reasonable minimum input length that you must be able to handle, maybe something like 100 kB or 1 MB. Of course, you could always split long input files into chunks of manageable size and compress them separately; that's what many general purpose compressors do.

If the output is given as a program in the same language as the compressor, can we count the length of the decompressor as zero?

@PeterTaylor: That seems reasonable enough.

Perl, 3502 = 133 + 3269 + 100
The encoder:
#!/usr/bin/perl -0
$_=<>;for$e(map{~chr}0..255){++$p{$_}for/..|.\G./gs;
%p=$s=(sort{$p{$a}<=>$p{$b}}keys%p)[-1];$d.=/\Q$e/?$/:s/\Q$s/$e/g&&$s}print$_,$d

And the decoder:
#!/usr/bin/perl -0777
sub d{($p=$d{$_})?d(@$p):print for@_}
sub r{%d=map{chr,ord($c=pop)&&[pop,$c]}0..255;&d}r<>=~/./gs

For purists who prefer to avoid using command-line switches: You can remove the shebang line and add $/=chr; to the encoder and $/=$,; to the decoder to get the same effect. (This would bring the score up to 3510.)
This code uses a very primitive compression scheme:

Find the two-char bigram that appears most frequently in the source text.
Replace the bigram with a currently-unused byte value.
Repeat until there are no more repeated bigrams (or no more unused byte values).

Someone out there may recognize this as a simplified version of "re-pair" compression (short for recursive pairs).
It's not a very good general compression scheme. It only does well with things like ASCII text, where there are a lot of unused byte values, and even then it typically gets no more than a 45-50% ratio. However, it has the advantage of being implementable with a minimum of code. The decompressor in particular can be quite compact. (Most of the chars in my decoder script are for retrieving the bigram dictionary.)
Here's an ungolfed version of the code:
#!/usr/bin/perl
use strict;
use warnings;
# Run with -d to decode.
if ($ARGV[0] eq "-d") {
    shift;
    $_ = join "", <>;
    my @in = split //;
    my %dict;
    foreach my $n (0 .. 255) {
        my $c = shift @in;
        $dict{chr $n} = [ $c, shift @in ] if ord $c;
    }
    sub decode {
        foreach (@_) {
            if ($dict{$_}) {
                decode(@{$dict{$_}});
            } else {
                print $_;
            }
        }
    }
    decode @in;
} else {
    $_ = join "", <>;
    my @dict;
    for (my $n = 255 ; $n >= 0 ; --$n) {
        my $symbol = chr $n;
        if (!/\Q$symbol/) {
            my %pop;
            ++$pop{$_} for /../gs, /(?!^)../gs;
            my $str = (sort { $pop{$b} <=> $pop{$a} } keys %pop)[0];
            s/\Q$str/$symbol/g;
            $dict[$n] = $str;
        }
    }
    for (0..255) { $dict[$_] ||= "\0" }
    print @dict, $_;
}

One expression in the golfed encoder requires explanation, I think, and that is (sort{$p{$a}<=>$p{$b}}keys%p)[-1], to get the key with the highest value. That looks like it should be written as (sort{$p{$b}<=>$p{$a}}keys%p)[0], which does the same thing and is one character shorter. The reason I didn't write it that way is that it alters the selected key in the case when there are multiple keys with the highest value. By sheer chance, this caused the resulting output for the test input to be 10 bytes longer. I hated to take on the useless extra character, but not enough to sacrifice 9 points from my score.
In your face, Golfscript! (Haha, Golfscript would totally come over here and kick my ass if it could hear me.)

Wow, that's pretty impressive! Ps. This seems to be the generally accepted answer regarding the counting of command line switches.

Dang, I read that earlier but I failed to notice that bit in the middle. It sounds like the upshot is that: you don't count the initial hyphen character (because you can just add it to the -e option bundle), unless your code contains a single-quote character, in which case you do count the hyphen (because now you have to run it from a file with a shebang line to avoid paying for escaping the single-quote on the command-line).

Technique is also called Byte pair encoding. Nice implementation

@roblogic Thanks for the reference; that's good to know.

Python, 3514 = 294 + 2894 + 326
Basically a bzip2 implementation.  It does a Burrows-Wheeler transform, a move-to-front transform, a simple Huffman encoding into a bit stream, converts that bit stream to an integer and writes out bytes.
Encoder:
import sys
S=range(128)
H={0:'0'}
for b in range(7):
 for i in range(1<<b,2<<b):H[i]='1'*b+'10'+bin(i)[3:]
I=sys.stdin.read()+'\0'
N='1'
for x in sorted(I[i:]+I[:i]for i in range(len(I))):i=S.index(ord(x[-1]));N+=H[i];S=[S[i]]+S[:i]+S[i+1:]
N=int(N,2)
while N:sys.stdout.write(chr(N%256));N>>=8

S is the move-to-front queue, H is the Huffman encoder, and N is the bitstream.
The encoding reduces the test input to about 41% of its original size.
Decoder:
import sys
N=0
b=1
for c in sys.stdin.read():N+=ord(c)*b;b<<=8
N=bin(N)[3:]
S=range(128)
L=''
while N:
 n=N.find('0')
 if n:i=2**n/2+int('0'+N[n+1:2*n],2);N=N[2*n:]
 else:i=0;N=N[1:]
 L+=chr(S[i]);S=[S[i]]+S[:i]+S[i+1:]
S=''
i=L.find('\0')
for j in L:S=L[i]+S;i=L[:i].count(L[i])+sum(c<L[i]for c in L)
sys.stdout.write(S[:-1])

I was tempted to implement the BWT and do a true form of compression but got too lazy.  :P

8086 Assembler / MS_DOS
Compressor: 155
jNiAxBCO2I7AM/+9/QW5AAGK2TPAq4rDqv7D4va6AQkz9lK0BrL/zSFadDK7
/f+DwwM733QNOTd19ThHAnXwid7r34k1iEUC6BMAtACKRQJr8AODxwPryrQC
zSHrxFIz0ovGuwMA9/Nai9iKztPL0ePQ0nMWgPr+cgtSsv60Bs0hWoDq/rQG
zSGyAf7JdeA5/XUHA+2DxQP+xsM=

Data: 3506
Decompressor: 203
ieWD7CCM2IDEEI7YjsAz/7kAAYrZM8CrisOq/sPi9rYJxkb0Abn9BehtAIl2
/uhTAOhkAIl28Dv3cy3oRgCLRv6JBYt28Il2/oM8AHQEizTr94pEAohFAoPH
AznPddL+xgPJg8ED68mLdv6JNYM8AHQEizTr94pEAohFAol+/on+aFgBgzwA
dAdWizTo9f9etAaKVALNIcMz9ojz/k70dRu0BrL/zSF0IDz+cgi0BrL/zSEE
/sZG9AiIRvLQZvLR1v7Ldddr9gPDzSA=

Total: 3864
Use this Base64 decoder and save the binary files as 'compress.com' and 'decompress.com' and then do:
compress < source > compressed_file
decompress < compressed_file > copy_of_source

in a DOS shell (tested with WinXP). There's no error checking so compressing big files will create incorrect results. A few small additions and it could cope with any sized file. Also, it can't decompress to binary as it can't output a 0xff value (the compressed data escapes the 0xff value as 0xfe 0xff with 0xfe escaped as 0xfe 0xfe). Using command line filenames would overcome the binary output problem, but would be a bigger executable.

What kind of compression algorithms does the program use?

@Sir_Lagsalot: It uses a variable bit width LZW (the one used in GIF files).

Bash Poem (566+117) + 4687 = 5370
For fun I have disguised a compressor as a poem:
for I in my chamber nodded, nearly napping, suddenly heard rapping, tapping upon my door    \
"'T is some visiter" \ I\  muttered, o\'er lamplight "nothing more" \
just this sainted maiden whom the angels name Lenore    \
And "Prophet!" said me "thing of evil" -- "prophet still, if bird or devil!"    \
Leave no token of that lie thy soul hath spoken and sitting take thy ore from This floor    \
But you velvet bird from some shore above   \
here this with sad raven before his word still spoke nothing    \
"                                          " Quoth the Raven Never more;                    do C=$[C+1];E=`perl -e "print chr($C+128)"`;echo "s/$I/$E/g">>c;echo "s/$E/$I/g">>d;done;LANG=C sed -f $1;rm c d

This is a unified compressor: run with the option "c" it will compress, and with "d" it will decompress. It has two parts: a 566 byte "readers digest" version of the poem and (2) a 117 byte suffix where all the "real" bash is done.
With some care (e.g. starting the poem with "for I in") bash will interpret the "lossy" version of poem as an array. It replaces each element of the array with a non-ASCII character (we assume the input is ASCII so there are no collisions).  One minor advantage of this solution: since we make use of the fact that we can assume the input is ASCII, the output of this compression will never be longer than its input, regardless of what the input and/or lossy part is.
The rule that this comes closest to violating is the rule about providing a decent compression ratio on other texts. However, It shaves 1386 bytes off the GPL V2 text, well over it's own size, which seems to match the OPs definition of decent. Thus it seems to provide so-called decent compression on general texts. This is because pretty much any English text will have "the" "that" etc. Clearly it will work better if you replace the "lossy" part with text resembling the original you want to losslessly compress.
Splitting pictures and audio into lossy and non-lossy parts is a known technique. This doesn't work as well for text: 4687 bytes isn't that great even if we exclude the 566 bytes from the lossy version and we can't really automatically generate a lossy version of text the same we can for audio. On the plus side this means every time you compress something with this compressor, you can have the fun of creating a lossy version by hand. So this seems like a reasonable "for fun" solution.

C++, 4134 bytes (code = 1357, compressed = 2777)
This does a Burrows-Wheeler transform + a Move-To-Front like Keith Randall's, but then compresses the resulting byte sequence using an adaptive Range Coder. Unfortunately, the improved compression from the range coder isn't enough to offset C++'s verbosity. I could golf this code some more, namely use a different input/output method, but it wouldn't be enough to beat the other submissions with the current algorithm.
The code is Windows specific, and only ascii text is supported.
To compress: "C text_file compressed_file"
To decompress: "D compressed_file uncompressed_file"
Pretty much any command line error or file error will crash the program, and it takes the better part of a minute to encode or decode the poem.
#include <windows.h>
#include <algorithm>
typedef DWORD I;typedef BYTE u;
#define W while
#define A(x)for(a=0;a<x;a++)
#define P(x)*o++=x;
I q,T=1<<31,B=T>>8,a,l,f[257],b,G=127,p=G,N=255;I Y(u*i,u*j){return
memcmp(i,j,l)<0;}I E(u*i,u*o){b=0;I L=0,h=0,R=T;u*c=o,*e=i+l;W(i<e){I
r=R/p,s=0;A(*i)s+=f[a];s*=r;L+=s;R=*i<N?r*f[*i++]++:R-s;p++;W(R<=B){if((L>>23)<N){for(;h;h--)P(N)P(L>>23)}else{if(L&T){o[-1]++;for(;h;h--)P(0)P(L>>23)}else
h++;}R<<=8;L<<=8;L&=T-1;}}P(L>>23)P(L>>15)P(L>>7)return
o-c;}void D(u*i,u*o){I R=128,L=*i>>1;u*e=o+l;W(o<e){W(R<=B){L<<=8;L|=((*i<<7)|(i++[1]>>1))&N;R<<=8;}I
h=R/p,m=L/h,x=0,v=0;W(v<=m)v+=f[x++];P(--x);L-=h*(v-f[x]);R=h*f[x]++;p++;}}void
main(I Z,char**v){u d[1<<16];I c=*v[1]<68,s;HANDLE F=CreateFileA(v[2],T,0,0,3,0,0),o=CreateFileA(v[3],T/2,0,0,2,0,0);ReadFile(F,d,GetFileSize(F,0),&l,0);l=c?l:*(I*)d;A(G)f[a]=1;u M[256];A(G)M[a]=a+1;u*g=new u[l*3],*h=g+l;if(c){memcpy(d+l,d,l);u**R=new
u*[l];A(l)R[a]=d+a;std::sort(R,R+l,Y);A(l){b=R[a][l-1];I
i=strchr((char*)M,b)-(char*)M;memmove(M+1,M,i);*M=g[a]=b;h[a]=i;}s=E(h,d+l+8);}else{D(d+8,g);A(l){I
k=g[a];g[a]=M[k];memmove(M+1,M,k);*M=g[a];}}u**j=new u*[l];A(l)j[a]=new
u[l*2],memset(j[a],0,l*2),j[a]+=l;A(l){for(b=0;b<l;)*--j[b]=g[b++];std::sort(j,j+l,Y);}if(c){A(l){if(!memcmp(j[a],d,l)){I*t=(I*)(d+l);*t=l;t[1]=a;g=d+l,l=s+8;}}}else
g=j[*(I*)(d+4)];WriteFile(o,g,l,&q,0);}

JavaScript, 393 (code) + 3521 (test) = 3914 (total)
This program iteratively substitutes unused byte values for 2- to 4- character chunks of the input. Each substitution is scored based on the original chunk's frequency and length, and the best substitution is chosen each time around. I would add a final Huffman coding stage if I could figure out how to do it in a relatively small number of characters. Decompression is essentially a series of find-and-replace operations.
Usage
C() provides compression; U() provides decompression. As JavaScript's strings are based on 16-bit Unicode code units, only the least significant 8 bits of each code unit are used in the compressed data format; this is compatible with Firefox's btoa() and atob() functions for Base64 encoding. (usage example)
This program may only work in Firefox because of a non-standard "g" option to .replace().
Code
Golfed code:
S=String.fromCharCode;function C(c){h=[];for(f=0;129>f;++f){g='';i=0;for(e=2;5>e;++e){d={};for(a=0;a<=c.length-e;a+=e)b="K"+c.substr(a,e),d[b]=d[b]?d[b]+1:1;for(b in d)a=d[b],a=a*e-(1+e+a),a>i&&(g=b.slice(1),i=a)}if(!g)break;h[f]=g;c=c.replace(g,S(127+f),"g")}return h.join("\1")+"\1"+c}function U(a){c=a.split("\1");a=c.pop();for(b=c.length,d=127+b;b--;)a=a.replace(S(--d),c[b],"g");return a}

Before golfing:
function compress(str) {

    var hash, offset, match, iteration, expansions, bestMatch, bestScore, times, length, score;

    expansions = [];

    for (iteration = 0; iteration < 129; ++iteration) {

        bestMatch = null;
        bestScore = 0;

        for (length = 2; length < 5; ++length) {

            hash = {};

            for (offset = 0; offset <= str.length - length; offset += length) {
                match = 'K' + str.substr(offset, length);
                hash[match] = hash[match] ? hash[match] + 1 : 1;
            }

            for (match in hash) {
                times = hash[match];
                score = times * length - (1 + length + times);
                if (score > bestScore) {
                    bestMatch = match.slice(1);
                    bestScore = score;
                }
            }

        }

        if (!bestMatch) {
            break;
        }

        expansions[iteration] = bestMatch;
        str = str.replace(bestMatch, String.fromCharCode(127 + iteration), 'g');

    }

    return expansions.join('\u0001') + '\u0001' + str;
}

function uncompress(str) {
    var i, j, expansions;

    expansions = str.split('\u0001');
    str = expansions.pop();

    for (j = expansions.length, i = 127 + j; j--;) {
        str = str.replace(String.fromCharCode(--i), expansions[j], 'g');
    }

    return str;
}

Why do I get C(text).length=7301? (FF 60.0.2)

To anyone from the future: Javascript moved on a bit. The 'g' flag in replace() has been deprecated. You should use a RegExp object like newData.replace(new RegExp(${token}, 'g'), replacements.pop()). I still couldn't reproduce the original 3521 size for the compressed file, but now I have 4660 instead of over 9000. http://jsfiddle.net/e9134zv8/

PHP, (347 + 6166 + 176) = 6689
So I went with a simplistic dictionary + substitution approach.
If a word appears multiple times and it's shorter to (encode the word + save the substitution entry) then it makes the replacement.  If the "word" happens to be a number, it does it anyways to prevent accidental substitutions during decompression.  The "dictionary" of substitutions is joined by null bytes, followed by two null bytes, followed by the body the substitution works on.
Possible improvements:

Windows doesn't like piping more than 4kb of data around, so find a better way than using files.
The ability to match long strings of whitespace and count them as "words" without adding too much code.
Coming up with something better substitutions instead of using numbers.

Usage: the compressor looks for a file called "i" and writes the compressed data to "o".  The decompressor looks for "o" and writes the uncompressed data to "d".  This is my shoddy workaround to Windows not liking to pipe boats of data around.

compress.php (347)
<?$d=file_get_contents('i');$z=chr(0);preg_match_all('|\b(\w+)\b|',$d,$m);$n=0;foreach($m[0]as$w){$l=strlen($w);$q[$w]=isset($q[$w])?$q[$w]+$l:$l;}arsort($q);foreach($q as$w=>$s){$l=strlen($w);$c=$s/$l;if($c*strlen($n)+$l<$s||is_int($w)){$d=preg_replace('|\b'.preg_quote($w).'\b|',$n++,$d);$f[]=$w;}}file_put_contents('o',implode($z,$f).$z.$z.$d);

Expanded version with comments and explanation.

Output sample without dictionary.  Kinda funny to look at.
Normal size: 6166.
Ah, distinctly I remember it 45 in 0 bleak December,
25 each separate dying ember wrought its ghost 39 0 37.
Eagerly I wished 0 88:--vainly I had sought to borrow
From 9 books surcease of 43--43 for 0 lost 8--
For 0 rare 1 67 40 54 0 26 38 8--
                                          Nameless 63 for evermore.

25 0 silken sad uncertain rustling of each purple curtain
Thrilled me--filled me 19 fantastic terrors never felt 17;
So 4 now, to 13 0 beating of 9 64, I stood repeating
"'T is 57 31 36 49 at 9 2 5
Some late 31 36 49 at 9 2 5;--
                                          58 it is, 1 10 16."

decompress.php (176)
<?$z=chr(0);$d=file_get_contents('o');list($w,$d)=explode($z.$z,$d);$w=explode($z,$w);$n=0;foreach($w as$r){$d=preg_replace('|\b'.$n++.'\b|',$r,$d);};file_put_contents('d',$d);

Expanded version with explanation.

Any suggestions for improvement welcome.
Edit: Added the "unrolled" versions of the code and added tons of comments.  Should be easy to follow.

Gah! Same language and method as I was using! Dammit. Though I hadn't got as far as skipping single words.

what happens when there are numbers within the text? it would end up replacing the original numbers with an out-of-place word. Though I took a similar approach (regex splits, finding common words to substitute and producing a replacement dictionary and gluing it on with nulls), I used unicode characters instead of numbers (starting from chr(128), since anything after that is nonprintable in standard ascii)

@Blazer: Actually, there's code in place (namely ||is_int($w)) to handle numbers by always adding them to the dictionary, but it seems to be buggy: after compressing and decompressing the whole Gutenberg E-text, the output starts with The 4 3 EBook 2 The Raven, by Edgar Allan Poe. :-(  I suspect the problem is that something is getting replaced twice; you might want consider using strtr() instead to avoid that issue.

@Ilmari if you have a number-heavy document, adding those numbers to the dictionary could result in the compression being larger than it was  originally. to store several 1-2 character long items is not effective. like if you were to replace the word 'a' in the document

@Blazer - For all compression algorithms there's certain inputs that will result in a larger output.  It's inherent in lossless compression, just like the inability to reliably compress entropic data.

@IlmariKaronen - I'll look into it.  I specifically included word boundary markers for the matching/replacing, so it shouldn't be caused by overlapping "symbols".  If anything, the actual numbers should have made it into the dictionary and been back-substituted correctly.

@GigaWatt: I think the problem is that you're doing the substitution on multiple passes.  So, for example, you first replace of with 2 and then, because it's also in the dictionary, 2 with, say, 747. The decompressor sees 747 and decodes it back to 2 (but not to of, since that dictionary entry has been processed already).

GolfScript, 3647 (compressed size 3408 + code size 239)
128,{[.;]''+}%:d;8:k;{2k?={1k+:k;}*}:|;{2base}:b;{.[0]*@b+0@->}:$;.0=
{'':&,:i;1/{.d&@+?.0<{;d,i@d&@:&.0=:i;[+]+:d;k$\|}{:i;&\+:&;}if}%[0]k*+[]*8/{b}%"\0"\+}
{1>{8$}/][]*:^;{^k<b^k>:^;}:r~{.}{d,|d=:&r..d,<{d=}{;&}if[1<&\+]d\+:d;}while;}if

The algorithm used is LZW compression with variable-width codes. The first line is shared code, the second is the compression code and the third is the decompression code.
It handles files with ASCII characters in the range 1-127, and it recognizes compressed files automatically (they start with a 0 byte), so there are no parameters required to decompress.
Example run:
$ md5sum raven.txt
286206abbb7eca7b1ab69ea4b81da227  raven.txt
$ ruby golfscript.rb compress.gs < raven.txt > raven.lzw
$ ls -l raven.lzw
-rw-r--r-- 1 ahammar ahammar 3408 2012-01-27 22:27 raven.lzw
$ ruby golfscript.rb compress.gs < raven.lzw | md5sum
286206abbb7eca7b1ab69ea4b81da227  -

Note: I started on this long before the requirement to handle 100kb was added, so I haven't tested it on input of that size. However, it takes about 30 seconds to compress the test input and 5 seconds to decompress it, using about 20MB of memory at its peak.

Compressing a 76 kB file seems to take about 19 minutes, while decompressing it takes 10.  That is kind of slow, but then again, it does pass the original rules, so... I dunno.  Seems kind of unfair not to allow it under the circumstances.  I guess I could invoke an implicit "grandfather clause" for you or something.

Haskell, 3973
Late to the party, and not going to win, but I had fun writing it so I might as well post it.
It's a straightforward variable-width implementation of LZW, with a dictionary explicitely limited to printable ASCII, tab and linefeed.  Run with no arguments, it compresses standard input to file C.  Run with any argument (but "--decompress" would be a reasonable bet), it decompresses file C to standard output.
import List
import System
import Data.Binary
q=head
main=getArgs>>=m
m[]=getContents>>=encodeFile"C".s 97 128 1 0.e 97h
m _=decodeFile"C">>=putStr.d tail""96h.u 97 128
h=zip[0..].map(:[])$"\t\n"++[' '..'~']
e _ _[]=[]
e n s y=c:e(n+1)((n,take(1+l)y):s)(drop(l)y)where{Just(c,p)=find((`isPrefixOf`y).snd)s;l=length p}
d _ _ _ _[]=""
d f p n s(x:y)=t++d id t(n+1)(f$(n,p++[q t]):s)y where t=maybe(p++[q p])id$lookup x s
s _ _ _ a[]=a::Integer
s n w o a y|n>w=s n(2*w)o a y|0<1=s(n+1)w(o*w)(a+o*q y)(tail y)
u _ _ 0=[]
u n w x|n>w=u n(2*w)x|0<1=(x`mod`w::Integer):u(n+1)w(x`div`w)

code size: 578
compressed sample size: 3395


text:
Random sampling without replacement
Create a function that will output a set of distinct random numbers drawn from a range. The order of the elements in the set is unimportant (they can even be sorted), but it must be possible for the contents of the set to be different each time the function is called.
The function will receive 3 parameters in whatever order you want:

Count of numbers in output set
Lower limit (inclusive)
Upper limit (inclusive)

Assume all numbers are integers in the range 0 (inclusive) to 231 (exclusive). The output can be passed back any way you want (write to console, as an array, etc.)
Judging
Criteria includes the 3 R's

Run-time - tested on a quad-core Windows 7 machine with whatever compiler is freely or easily available (provide a link if necessary)
Robustness - does the function handle corner cases or will it fall into an infinite loop or produce invalid results - an exception or error on invalid input is valid
Randomness - it should produce random results that are not easily predictable with a random distribution. Using the built in random number generator is fine. But there should be no obvious biases or obvious predictable patterns. Needs to be better than that random number generator used by the Accounting Department in Dilbert

If it is robust and random then it comes down to run-time. Failing to be robust or random greatly hurts its standings.

Is the output supposed to pass something like the DIEHARD or TestU01 tests, or how will you judge its randomness?  Oh, and should the code run in 32 or 64 bit mode?  (That will make a big difference for optimization.)

TestU01 is probably a bit harsh, I guess. Does criterion 3 imply a uniform distribution? Also, why the non-repeating requirement? That's not particularly random, then.

@Joey, sure it is. It's random sampling without replacement. As long as no-one claims that the different positions in the list are independent random variables there's no problem.

Ah, indeed. But I'm not sure whether there are well-established libraries and tools for measuring randomness of sampling :-)

@IlmariKaronen: RE: Randomness: I've seen implementations before that were woefully unrandom. Either they had a heavy bias, or lacked the ability to produce different results on consecutive runs. So we are not talking cryptographic level randomness, but more random than the Accounting Department's random number generator in Dilbert.

If the request is to pick 5 distinct values in the range of (0..3) - shall we sanitize against such unfulfillable requests?

And since it is a performance hack, the question is important, what type of test is performed. For example, if you have to pick 10,000 elements of 10,001, it would be fast to shuffle the 10,001 and pick the first 10,000. But if you just have to pick 1,000 of 100,000 you can put randomly chosen elements into a set, until it is filled with 1,000 elements (which is my solution so far), but this will be slow, if you have most of the elements of a very big collection.

Python
import random

def sample(n, lower, upper):
    result = []
    pool = {}
    for _ in xrange(n):
        i = random.randint(lower, upper)
        x = pool.get(i, i)
        pool[i] = pool.get(lower, lower)
        lower += 1
        result.append(x)
    return result

I probably just re-invented some well-known algorithm, but the idea is to (conceptually) perform a partial Fisher-Yates shuffle of the range lower..upper to get the length n prefix of a uniformly shuffled range.
Of course, storing the whole range would be rather expensive, so I only store the locations where the elements have been swapped.
This way, the algorithm should perform well both in the case where you're sampling numbers from a tight range (e.g. 1000 numbers in the range 1..1000), as well as the case where you're sampling numbers from a large range.
I'm not sure about the quality of randomness from the built-in generator in Python, but it's relatively simple to swap in any generator that can generate integers uniformly from some range.

Python uses Mersenne Twister, so it's relatively decent.

Ruby >= 1.8.7
def pick(num, min, max)
  (min..max).to_a.sample(num)
end

p pick(5, 10, 20) #=>[12, 18, 13, 11, 10]

python 2.7
import random
print(lambda x,y,z:random.sample(xrange(y,z),x))(input(),input(),input())

not sure what your standing is on using builtin random methods, but here you go anyways. nice and short
edit: just noticed that range() doesn't like to make big lists. results in a memory error. will see if there is any other way to do this...
edit2: range was the wrong function, xrange works. The maximum integer is actually 2**31-1 for python
test:
python sample.py
10
0
2**31-1
[786475923, 2087214992, 951609341, 1894308203, 173531663, 211170399, 426989602, 1909298419, 1424337410, 2090382873]

C
Returns an array containing x unique random ints between min and max. (caller must free)
#include <stdlib.h>
#include <stdint.h>
#define MAX_ALLOC ((uint32_t)0x40000000)  //max allocated bytes, fix per platform
#define MAX_SAMPLES (MAX_ALLOC/sizeof(uint32_t))

int* randsamp(uint32_t x, uint32_t min, uint32_t max)
{
   uint32_t r,i=x,*a;
   if (!x||x>MAX_SAMPLES||x>(max-min+1)) return NULL;
   a=malloc(x*sizeof(uint32_t));
   while (i--) {
      r= (max-min+1-i);
      a[i]=min+=(r ? rand()%r : 0);
      min++;
   }
   while (x>1) {
      r=a[i=rand()%x--];
      a[i]=a[x];
      a[x]=r;
   }
   return a;
}

Works by generating x sequential random integers in the range, then shuffling them.
Add a seed(time) somewhere in caller if you don't want the same results every run.

R
s <- function(n, lower, upper) sample(lower:upper,n); s(10,0,2^31-2)

The question is not correct. Do you need uniform sampling or not? In the case uniform sampling is needed I have the following code in R, which has average complexity O(s log s), where s is the sample size.
# The Tree growing algorithm for uniform sampling without replacement
# by Pavel Ruzankin
quicksample = function (n,size)
# n - the number of items to choose from
# size - the sample size
{
  s=as.integer(size)
  if (s>n) {
    stop("Sample size is greater than the number of items to choose from")
  }
  # upv=integer(s) #level up edge is pointing to
  leftv=integer(s) #left edge is poiting to; must be filled with zeros
  rightv=integer(s) #right edge is pointig to; must be filled with zeros
  samp=integer(s) #the sample
  ordn=integer(s) #relative ordinal number

  ordn[1L]=1L #initial value for the root vertex
  samp[1L]=sample(n,1L)
  if (s > 1L) for (j in 2L:s) {
    curn=sample(n-j+1L,1L) #current number sampled
    curordn=0L #currend ordinal number
    v=1L #current vertice
    from=1L #how have come here: 0 - by left edge, 1 - by right edge
    repeat {
      curordn=curordn+ordn[v]
      if (curn+curordn>samp[v]) { #going down by the right edge
        if (from == 0L) {
          ordn[v]=ordn[v]-1L
        }
        if (rightv[v]!=0L) {
          v=rightv[v]
          from=1L
        } else { #creating a new vertex
          samp[j]=curn+curordn
          ordn[j]=1L
          # upv[j]=v
          rightv[v]=j
          break
        }
      } else { #going down by the left edge
        if (from==1L) {
          ordn[v]=ordn[v]+1L
        }
        if (leftv[v]!=0L) {
          v=leftv[v]
          from=0L
        } else { #creating a new vertex
          samp[j]=curn+curordn-1L
          ordn[j]=-1L
          # upv[j]=v
          leftv[v]=j
          break
        }
      }
    }
  }
  return(samp)
}

Of course, one may rewrite it in C for better performance. The complexity of this algorithm is discussed in:
Rouzankin, P. S.; Voytishek, A. V. On the cost of algorithms for random selection. Monte Carlo Methods Appl. 5 (1999), no. 1, 39-54.
http://dx.doi.org/10.1515/mcma.1999.5.1.39
You may look through this paper for another algorithm with the same average complexity.
But if you do not need uniform sampling, only requiring that all sampled numbers be different, then the situation changes dramatically. It is not hard to write an algorithm that has average complexity O(s).
See also for uniform sampling: P. Gupta, G. P. Bhattacharjee. (1984) An efficient algorithm for random sampling without replacement. International Journal of Computer Mathematics 16:4, pages 201-209. DOI: 10.1080/00207168408803438
Teuhola, J. and Nevalainen, O. 1982. Two efficient algorithms for random sampling without replacement. /IJCM/, 11(2): 127–140. DOI: 10.1080/00207168208803304
In the last paper the authors use hash tables and claim that their algorithms have O(s) complexity. There is one more fast hash table algorithm, which will soon be implemented in pqR (pretty quick R):
https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html

APL, 18 22 bytes
{⍵[0]+(1↑⍺)?⍵[1]-⍵[0]}

Declares an anonymous function that takes two arguments ⍺ and ⍵. ⍺ is the number of random numbers you want, ⍵ is a vector containing the lower and upper bounds, in that order.
a?b picks a random numbers between 0-b without replacement. By taking ⍵[1]-⍵[0] we get the range size. Then we pick ⍺ numbers (see below) from that range and add the lower bound. In C, this would be
lower + rand() * (upper - lower)

⍺ times without replacement. Parentheses not needed because APL operates right-to-left.
Assuming I've understood the conditions correctly, this fails the 'robustness' criteria because the function will fail if given improper arguments (e.g. passing a vector instead of a scalar as ⍺).
In the event that ⍺ is a vector rather than a scalar, 1↑⍺ takes the first element of ⍺. For a scalar, this is the scalar itself. For a vector, it's the first element. This should make the function meet the 'robustness' criteria.
Example:
Input: 100 {⍵[0]+⍺?⍵[1]-⍵[0]} 0 100
Output: 34 10 85 2 46 56 32 8 36 79 77 24 90 70 99 61 0 21 86 50 83 5 23 27 26 98 88 66 58 54 76 20 91 72 71 65 63 15 33 11 96 60 43 55 30 48 73 75 31 13 19 3 45 44 95 57 97 37 68 78 89 14 51 47 74 9 67 18 12 92 6 49 41 4 80 29 82 16 94 52 59 28 17 87 25 84 35 22 38 1 93 81 42 40 69 53 7 39 64 62

This is not a code golf but a fastest cose, therefore the goal is producing the fastest code to perform the task rather than the shortest. Anyway, you don't really need to pick the items from the arguments like that, and you can determine their order, so {⍵+⍺?⎕-⍵} should suffice, where the prompt is for the upper bound and right arg is lower bound

Scala
object RandSet {
  val random = util.Random

  def rand (count: Int, lower: Int, upper: Int, sofar: Set[Int] = Set.empty): Set[Int] =
    if (count == sofar.size) sofar else
    rand (count, lower, upper, sofar + (random.nextInt (upper-lower) + lower))
}

object RandSetRunner {

  def main (args: Array [String]) : Unit = {
    if (args.length == 4)
      (0 until args (0).toInt).foreach { unused =>
      println (RandSet.rand (args (1).toInt, args (2).toInt, args (3).toInt).mkString (" "))
    }
    else Console.err.println ("usage: scala RandSetRunner OUTERCOUNT COUNT MIN MAX")
  }
}

compile and run:
scalac RandSetRunner.scala
scala RandSetRunner 200 15 0 100

The second line will run 200 tests with 15 values from 0 to 100, because Scala produces fast bytecode but needs some startup time. So 200 starts with 15 values from 0 to 100 would consume more time.
Sample on a 2 Ghz Single Core:
time scala RandSetRunner 100000 10 0 1000000 > /dev/null

real    0m2.728s
user    0m2.416s
sys     0m0.168s

Logic:
Using the build-in random and recursively picking numbers in the range (max-min), adding min and checking, if the size of the set is the expected size.
Critique:

It will be fast for small samples of big ranges, but if the task is to pick nearly all elements of a sample (999 numbers out of 1000) it will repeatedly pick numbers, already in the set.
From the question, I'm unsure, whether I have to sanitize against unfulfillable requests like Take 10 distinct numbers from 4 to 8. This will now lead to an endless loop, but can easily be avoided with a prior check which I will append if requested.

Scheme
Not sure why you need 3 parameters passed nor why i need to assume any range...
(import srfi-1) ;; for iota
(import srfi-27) ;; randomness
(import srfi-43) ;; for vector-swap!

(define rand (random-source-make-integers
               default-random-source))

;; n: length, i: lower limit
(define (random-range n i)
  (let ([v (list->vector (iota n i))])
    (let f ([n n])
      (let* ([i (rand n)] [n (- n 1)])
        (if (zero? n) v
            (begin (vector-swap! v n i) (f n)))))))

R
random <- function(count, from, to) {
  rand.range <- to - from

  vec <- c()

  for (i in 1:count) {
    t <- sample(rand.range, 1) + from
    while(i %in% vec) {
      t <- sample(rand.range, 1) + from
    }
    vec <- c(vec, t)
  }

  return(vec)
}

C++
This code is best when drawing many samples from the range.
#include <exception>
#include <stdexcept>
#include <cstdlib>

template<typename OutputIterator>
 void sample(OutputIterator out, int n, int min, int max)
{
  if (n < 0)
    throw std::runtime_error("negative sample size");
  if (max < min)
    throw std::runtime_error("invalid range");
  if (n > max-min+1)
    throw std::runtime_error("sample size larger than range");

  while (n>0)
  {
    double r = std::rand()/(RAND_MAX+1.0);
    if (r*(max-min+1) < n)
    {
      *out++ = min;
      --n;
    }
    ++min;
  }
}

This can easily get stuck in an infinite loop unless max-min is much larger than n.  Also, the output sequence is monotonically increasing, so you're getting very low quality randomness but still paying the cost of calling rand() multiple times per result.  A random shuffle of the array would probably be worth the extra run-time.

Q (19 characters)
f:{(neg x)?y+til z}

Then use f[x;y;z] as [count of numbers in output set;starting point;size of range]
e.g. f[5;10;10] will output 5 distinct random numbers between 10 and 19 inclusive.
q)\ts do[100000;f[100;1;10000]]
2418 131456j

Results above show performance at 100,000 iterations of picking 100 random numbers between 1 & 10,000.

R, 31 or 40 bytes (depending on the meaning of the word “range”)
If the input has 3 numbers, a[1], a[2], a[3], and by “range” you mean “an integer sequence from a[2] to a[3]”, then you have this:
a=scan();sample(a[2]:a[3],a[1])

If you have an array n from which you are about to resample, but under the restriction of the lower and upper limits, like “resample values of the given array n from the range a[1]...a[2]”, then use this:
a=scan();sample(n[n>=a[2]&n<=a[3]],a[1])

I am quite surprised why the previous result was not golfed considering the built-in sample with replacement facilities! We create a vector that satisfies the range condition and re-sample it.

Robustness: the corner cases (sequences of the same length as the range to sample from) are handled by default.
Run-time: extremely fast because it is built in.
Randomness: the seed is automatically changed every time the RNG is invoked.

at least on my machine, 0:(2^31) causes an Error: cannot allocate a vector of size 16.0 Gb

@Giuseppe Recently, I have been working with big-memory problems, and the solution to that is actually... running it on a better machine. The restrictions in the formulation of the task pertain to the processor, not to memory, so is it... rule abuse?
Ah, I am an ass. I thought it was a code golf challenge, but actually it is... fastest-code. I lose I guess?

Javascript (using external library) (64 bytes / 104 bytes??)
(a,b,n)=>_.Range(0,n).Select(x=>Math.random()*(b-a)+a).ToArray()

Link to lib: https://github.com/mvegh1/Enumerable/
Code explanation: Lambda expression accepts  min,max,count as args. Create a collection of size n, and map each element to a random number fitting the min/max criteria. Convert to native JS array and return it. I ran this also on an input of size 5,000,000, and after applying a distinct transform still showed 5,000,000 elements. If it is agreed upon that this isn't safe enough of a guarantee for distinctness I will update the answer
I included some statistics in the image below...

EDIT: The below image shows code / performance that guarantees every element will be distinct. It's much much slower (6.65 seconds for 50,000 elements) vs the original code above for same args (0.012 seconds)

K (oK), 14 bytes
Solution:
{y+(-x)?1+z-y}

Try it online!
Example:
> {y+(-x)?1+z-y}. 10 10 20      / note: there are two ways to provide input, dot or
13 20 16 17 19 10 14 12 11 18
> {y+(-x)?1+z-y}[10;10;20]      / explicitly with [x;y;z]
12 11 13 19 15 17 18 20 14 10

Explanation:
Takes 3 implicit inputs per spec:

x, count of numbers in output set,
y, lower limit (inclusive)
z, upper limit (inclusive)

{y+(-x)?1+z-y} / the solution
{            } / lambda function with x, y and z as implicit inputs
          z-y  / subtract lower limit from upper limit
        1+     / add 1
   (-x)?       / take x many distinct items from 0..(1+z=y)
 y+            / add lower limit

Notes:
Also a polyglot in q/kdb+ with an extra set of brackets: {y+((-)x)?1+z-y} (16 bytes).

Axiom + its library
f(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b or n>99999999 =>r
    d:=1+b-a
    for i in 1..n repeat
          r:=concat(r,a+random(d)$INT)
    r

The above f() function return as error the empty list, in the case f(n,a,b) with a>b. In other cases of invalid input, it not run with one error message in Axiom window, because argument will be not of the right type. Examples
(6) -> f(1,1,5)
   (6)  [2]
                                                       Type: List Integer
(7) -> f(1,1,1)
   (7)  [1]
                                                       Type: List Integer
(10) -> f(10,1,1)
   (10)  [1,1,1,1,1,1,1,1,1,1]
                                                       Type: List Integer
(11) -> f(10,-20,-1)
   (11)  [- 10,- 4,- 18,- 5,- 5,- 11,- 15,- 1,- 20,- 1]
                                                       Type: List Integer
(12) -> f(10,-20,-1)
   (12)  [- 4,- 5,- 3,- 4,- 18,- 1,- 2,- 14,- 19,- 8]
                                                       Type: List Integer
(13) -> f(10,-20,-1)
   (13)  [- 18,- 12,- 12,- 19,- 19,- 15,- 5,- 17,- 19,- 4]
                                                       Type: List Integer
(14) -> f(10,-20,-1)
   (14)  [- 8,- 11,- 20,- 10,- 4,- 8,- 11,- 3,- 10,- 16]
                                                       Type: List Integer
(15) -> f(10,9,-1)
   (15)  []
                                                       Type: List Integer
(16) -> f(10,0,100)
   (16)  [72,83,41,35,27,0,33,18,60,38]
                                                       Type: List Integer


text:
Sudoku board generator
A program that randomly generates a Sudoku game board with varying degrees of difficulty (however you decide to measure difficulty). Sudoku requires that there is only one solution, so your program should too. Input and output can be any form or method of your choosing.
Judging
Fastest code. Tested on a quad-code Windows 7 machine with freely or easily available compiler. Provide link if necessary.

Actually, it's not really sudoku if there is more than one possible solution.  Many solving strategies rely on the fact that there cannot be multiple solutions.

@StevenRumbalski: So should a single solution be required?

Yes, otherwise an empty grid would be a valid puzzle.  See http://www.technologyreview.com/blog/arxiv/27469/.

@StevenRumbalski: That is what I thought. Updated listing.

I don't think the number of blank cells is strongly (if at all) correlated with difficulty.

@PeterTaylor: I've made difficulty measurement at the discretion of the implementor.

If it helps, 17 is the minimum number of filled positions required to have a unique solution.

@JimMcKeeth, that makes things worse, because evaluating difficulty well is more expensive than building the board.

@PeterTaylor: If there is a mechanism to allow for variable difficulty then that is satisfactory. As you said, evaluating the difficulty is expensive.

I think number of filled in position is the standard difficulty measure in magazines that publish Sudoku (e.g. below 25 they'll call it hard). Of course, it doesn't mean it's a good measure.

why is this already accepted? :(

@ajax333221: No-one else submitted anything and that seemed like as good of a solution as any. When new submissions come in then I am happy to evaluate them and accept a different one.

Scheme
Why should I be constrained on the platform used? Especially on such a developer-unfriendly platform as Windows! Anyways... doesn't matter since this code compiles on all Scheme implementations that provide the standard libraries srfi-1, srfi-27 and srfi-43 (that means almost all of them), on virtually (pun intended) every platform. The only non-portable-across-all-implementatons construct I use is "import", but I might as well have used "use" or "require" among others. This minor incompatibility between implementations will be fixed this year, don't worry.
Because of the holy wars pertaining to the Lisp family of languages on the matters of minimalism, the last standard in final status (R6RS) was rejected by most implementors, prefering instead to stick to R5RS until the steering comitee broke up. They came up with the idea to split the language in two, the first being a minimalistic core (assigned to working group 1). The second will be a superset of the first which will better suit daily usage. Both will form R7RS, which will be released this year. This will solve many incompatibilities between implementations.
;; Sudoku generator (v0.2)

;; list ops          randomness     vector ops
(import srfi-1) (import srfi-27) (import srfi-43)

(define rand (random-source-make-integers
                 default-random-source))

(define (shuffle! vec)
  (let swap! ([n (vector-length vec)])
    (let* ([i (rand n)] [n (- n 1)])
      (when (> n 1) (vector-swap! vec n i) (swap! n)))))

(define (make-row)
  (let ([row (vector-unfold (lambda (i) (+ i 1)) 9)])
    (shuffle! row) row))

(define (make-rows)
  (let f ([i 8] [r (make-row)])
    (cons r
      (if (zero? i) (list)
          (f (- i 1) (vector-copy r 1 10 (vector-ref r 0)))))))

(define (split-in ls n)
  (let ([n (quotient (length ls) n)])
    (let f ([ls ls])
      (if (null? ls) ls (cons (take ls n) (f (drop ls n)))))))

(define (make-grid)
  (let ([g (list->vector
              (map list->vector
              (zip (split-in (make-rows) 3))))])
    (shuffle! g) (vector-for-each shuffle! g)
    (vector-concatenate (vector->list g))))

Difficulty: none
I felt the code was too complicated so I rewrote it from scratch. For clue pruning, I am currently working on encoding the board in CNF notation. Since I have access to the original grid, testing for uniqueness is easier. Pruning is done by priority (we prefer to prune cells who maximize the number of possibilities in its surroundings).
So far, this only generates a valid complete grid using only a vector of numbers from 1 to 9 that swaps each index with a random index. This random row is used to derive the other rows by successive rotation. This works because there are only 8 other possible rows, given one sudoku row.
Thus, so far we have ensured there are no row or column conflicts possible. As a matter of fact, the sudoku is based on latin squares which are roman grids of size n*n (a square) which must have unique numbers on every row and column in the range 1 to n. A sudoku is a latin square of size 9*9, with an added constraint: regions.
The next step is to split the list of rows in 3, which now looks like this, given an initial row of (1 2 3 4 5 6 7 8 9):
;; this is a latin square
(((1 2 3 4 5 6 7 8 9)
  (2 3 4 5 6 7 8 9 1)
  (3 4 5 6 7 8 9 1 2))
 ((4 5 6 7 8 9 1 2 3)
  (5 6 7 8 9 1 2 3 4)
  (6 7 8 9 1 2 3 4 5))
 ((7 8 9 1 2 3 4 5 6)
  (8 9 1 2 3 4 5 6 7)
  (9 1 2 3 4 5 6 7 8)))

Given a grid like that, I can "zip" the lists (perform matrix transposition) so that it now looks like this:
;; this is now a sudoku
(((1 2 3 4 5 6 7 8 9)
  (4 5 6 7 8 9 1 2 3)
  (7 8 9 1 2 3 4 5 6))
 ((2 3 4 5 6 7 8 9 1)
  (5 6 7 8 9 1 2 3 4)
  (8 9 1 2 3 4 5 6 7))
 ((3 4 5 6 7 8 9 1 2)
  (6 7 8 9 1 2 3 4 5)
  (9 1 2 3 4 5 6 7 8)))

Magic! No row, column or region conflicts! What needs to be done next is to shuffle the three lists of rows, and the three rows within them. To do that, we convert all lists to vectors, then reuse the same shuffle procedure used with the first row. The last step is to collapse everything back to a grid of 9 rows.
I will post updates later. I am currently more advanced than this, but the rest is still in development (I promise you the cleverness and simplicity of my algorithms will surprise you). This was not done in one day, but with great amounts of research for optimal algorithms.

Did anyone ever win a code golf challenge (or a performance challenge) with Scheme? Or are you on your way to be the first?

Well, Scheme's focus is on algorithmic performance. While probably being the most minimalist non-toy language. It is a do-it-yourself which requires you to design in a top-down fashion. While having fonctions like call-with-current-continuation and so many parentheses will scare away most, these concepts allow you to travel back and forth in time, have fine-grained control over fonctions, their scoping etc. It's impossible not to choose optimal algorithms in Scheme because you clearly see the nesting (recursion) involved. Why not Scheme?

The thing is, while Perl optimization works by shaving off characters, Scheme optimization works by shaving off functions. I should win more often but people keep wanting less characters instead of just less processing...

You don't normally optimize Perl code by removing characters. However, the definition of a code golf is that the shortest entry wins. Note that this problem is not a code golf (and correctly not tagged as one) because the fastest code wins. Of course the optimization required for code golf problems is to remove characters because that's the winning criterion. You won't write code golf code for production, though, while you may well write speed-optimized production code.