text:
Crossword numbering
Produce a program to correctly number a crossword grid.
Input
The input will be the name of a file representing the crossword
grid. The input filename may be passed as an argument, on the
standard input, or by other conventional means other than
hardcoding.
Grid file format: A text file. The first line consists of two white-space
separated integer constants M and N. Following that line are M
lines each consisting of N characters (plus a new line) selected
from [#A-Z ]. These characters are interpreted such that '#'
indicates a blocked square, ' ' a open square in the puzzle
with no known contents and any letter an open square whose
containing that letter.
Output
The output will be a numbering file, and may be sent to the
standard output, to a file whose name is derived from the
input filename, to a user specified file, or to some other
conventional destination.
Numbering file format A text file. Lines starting with '#' are ignored and
may be used for comments. All other lines contain a tab separated
triplet i, m, n where i represents a number to be printed
on the grid, and m and n represent the row and column of the
square where it should be printed. The number of both rows and
columns starts at 1.
Numbering scheme
A correctly numbered grid has the following properties:

Numbering begins at 1.
No column or span of open squares is unnumbered. (You may assume
that no single character answer will exist in the problem.)
Numbers will be encountered in counting order by scanning from
top row to the bottom taking each row from left to right. (So,
every horizontal span is numbered at its leftmost square, and
every column is numbered at its topmost square.)

Test input and expected output
Input:
5   5
#  ##
#
  #
    #
##  #

Output (neglecting comment lines):
1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3

Aside
This is the first of what will hopefully be several crossword
related challenges. I plan to use a consistent set of
file-formats throughout and to build up a respectable suite of
crossword related utilities in the process. For instance a
subsequent puzzle will call for printing a ASCII version of the
crossword based on the input and output of this puzzle.

Single-character spans are not numbered, right?

@Kieth: I prefer the rule where there are no such spans, but I haven't specified it here because validating the grid is planned as another problem. I suppose which you use is a matter of taste.

will input file be in txt?

@www0z0k: Yes. The unix geek in me always defaults to text.

line breaks are '\n'?

@www0z0k: Line breaks are whatever is native on your platform. That's ASCII decimal 20 on mine and represented as '\n' in c on all platforms. The assumption is that the input file was produced on the same system that will process it, so this issue should be transparent. A general note about code-golf: if you're working in a strange language or on a strange platform simple make a note of anything that might surprise the reader. People will make allowance for that in judging your submission.

Ruby - 210 139 characters
o=0
(n=(/#/=~d=$<.read.gsub("
",S='#'))+1).upto(d.size-1){|i|d[i]!=S&&(i<n*2||d[i-1]==S||d[i-n]==S)&&print("%d\t%d\t%d
"%[o+=1,i/n,i%n+1])}

Tested with ruby 1.9.

I follow most of that. Not sure what s.shift.split.map does, but that must be forming the array from the input.

BTW-- How should I invoke it at a unix command line. I tried giving it a shebang appropriate to my system, but it complains ./temp.ruby:4: wrong argument type Symbol (expected Proc) (TypeError).

s.shift takes the first line, split returns ["m", "n"], map returns [m, n]. I'm running it with ruby1.9 like this: ruby1.9 test.rb.

Python, 194 177 176 172 characters
f=open(raw_input())
V,H=map(int,next(f).split())
p=W=H+2
h='#'
t=W*h+h
n=1
for c in h.join(f):
 t=t[1:]+c;p+=1
 if'# 'in(t[-2:],t[::W]):print"%d\t%d\t%d"%(n,p/W,p%W);n+=1

You should be able to use h.join(f) I think

and next(f) instead of f.readline() if you are >=2.6 else f.next()

My python was never very good, but it looks like you're using extra '#'s to handle the edge cases, no? However, I'm getting some odd output on the test data, including extra numbers.

@dmckee, yes I'm using extra #s to mark the edge.  Can you post a test case where you think it fails?

@Kieth: For the test case above I'm getting 12 output lines (and the first 10 don't match). Using python2.6 or 2.7 on my Mac. Running it with echo test_input_file_name | python golf.py, is that wrong?

I ran it the same way, and got the results in your question.  Make sure you don't have any extra or missing spaces in your input file.

@Kieth: You were, of course, right. Despite great care taken to insure the absence of extra spaces before pasting into the question a couple had made there way into the file before I test your solution. My apologies.

'# 'in(t[-2:],t[::W])

PHP - 175 characters
<?for($i=$n=strpos($d=strtr(`cat $argv[1]`,"\n",$_="#"),$_)+$o=1;isset($d[$i]);++$i)$d[$i]!=$_&($i<$n*2|$d[$i-1]==$_|$d[$i-$n]==$_)&&printf("%d\t%d\t%d\n",$o++,$i/$n,$i%$n+1);

I wondered when someone was going to do it in a 1d array.

C++ 270 264 260 256 253 char
#include<string>
#include<iostream>
#define X cin.getline(&l[1],C+2)
using namespace std;int main(){int r=0,c,R,C,a=0;cin>>R>>C;string l(C+2,35),o(l);X;for(;++r<=R;o=l)for(X,c=0;++c<=C;)if(l[c]!=35&&(l[c-1]==35||o[c]==35))printf("%d %d %d\n",++a,r,c);}

To use:
g++ cross.cpp -o cross
cat puzzle |  cross

Nicely formatted:
#include<string>
#include<iostream>
// using this #define saved 1 char
#define X cin.getline(&l[1],C+2)

using namespace std;

int main()
{
    int r=0,c,R,C,a=0;
    cin>>R>>C;
    string l(C+2,35),o(l);
    X;

    for(;++r<=R;o=l)
        for(X,c=0;++c<=C;)
            if(l[c]!=35&&(l[c-1]==35||o[c]==35))
                printf("%d %d %d\n",++a,r,c);
}

I tried reading the whole crossword in one go and using a single loop.
But the cost of compensating for the '\n character outweighed any gains:
#include <iostream>
#include <string>
#define M cin.getline(&l[C+1],R*C
using namespace std;

int main()
{
    int R,C,a=0,x=0;
    cin>>R>>C;
    string l(++R*++C,35);
    M);M,0);

    for(;++x<R*C;)
        if ((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))
            printf("%d %d %d\n",++a,x/C,x%C);
}

Compressed: 260 chars
#include<iostream>
#include<string>
#define M cin.getline(&l[C+1],R*C
using namespace std;int main(){int R,C,a=0,x=0;cin>>R>>C;string l(++R*++C,35);M);M,0);for(;++x<R*C;)if((l[x]+=l[x]==10?25:0)!=35&&(l[x-1]==35||l[x-C]==35))printf("%d %d %d\n",++a,x/C,x%C);}

Took me a few tries to invoke it right. Slick.

C, 184 189 chars
char*f,g[999],*r=g;i,j,n;main(w){
for(fscanf(f=fopen(gets(g),"r"),"%*d%d%*[\n]",&w);fgets(r,99,f);++j)
for(i=0;i++<w;++r)
*r==35||j&&i>1&&r[-w]-35&&r[-1]-35||printf("%d\t%d\t%d\n",++n,j+1,i);}

Not much to say here; the logic is pretty basic. The program takes the filename on standard input at runtime. (It's so annoying that the program has to work with a filename, and can't just read the file contents directly from standard input. But the one who pays the piper calls the tune!)
The weird fscanf() pattern is my attempt to scan the full first line, including the newline but not including leading whitespace on the following line. There's a reason why nobody uses scanf().

I think you reverse the rows and columns number. If I understand correctly, the first number is the number of rows, but you treat it as the number of columns.

From what I can tell, the output of my program matches the example given in the description, and the output from the reference implementation. Can you give me a specific example of what you're referring to?

Any example where the rows and columns numbers are not equal.

Okay, but let's get specific please. When given the example grid provided in description, my program outputs (1,2) for the number 1. Are you saying that my program ought to output (2,1)?

I'm talking about input, not output. When the first line is 5 5, you take the first 5 as the width, when you should have taken the second (which doesn't matter, of course, in this example).

See, this is why I asked for a specific example: I can't read.

Citing the question: Following that line are M lines each consisting of N characters'

Heh. No need to rub it in! I've already admitted my error and fixed the program (at a cost of 5 chars, no less).

Reference implementation:
c99 ungolfed and rather more than 2000 characters including various debugging frobs still in there.
#include <stdio.h>
#include <string.h>

void printgrid(int m, int n, char grid[m][n]){
  fprintf(stderr,"===\n");
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
      switch (grid[i][j]) {
      case '\t': fputc('t',stderr); break;
      case '\0': fputc('0',stderr); break;
      case '\n': fputc('n',stderr); break;
      default: fputc(grid[i][j],stderr); break;
      }
    }
    fputc('\n',stderr);
  }
  fprintf(stderr,"===\n");
}

void readgrid(FILE *f, int m, int n, char grid[m][n]){
  int i = 0;
  int j = 0;
  int c = 0;
  while ( (c = fgetc(f)) != EOF) {
    if (c == '\n') {
      if (j != n) fprintf(stderr,"Short input line (%d)\n",i);
      i++;
      j=0;
    } else {
      grid[i][j++] = c;
    }
  }
}

int main(int argc, char** argv){
  const char *infname;
  FILE *inf=NULL;
  FILE *outf=stdout;

  /* deal with the command line */
  switch (argc) {
  case 3: /* two or more arguments. Take the second to be the output
         filename */
    if (!(outf = fopen(argv[2],"w"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[2]);
      return 2;
    }
    /* FALLTHROUGH */
  case 2: /* exactly one argument */
    infname = argv[1];
    if (!(inf = fopen(infname,"r"))) {
      fprintf(stderr,"%s: Couldn't open file '%s'. Exiting.",
          argv[0],argv[1]);
      return 1;
    };
    break;
  default:
    printf("%s: Number a crossword grid.\n\t%s <grid file> [<output file>]\n",
       argv[0],argv[0]);
    return 0;
  }

  /* Read the grid size from the first line */
  int m=0,n=0;
  char lbuf[81];
  fgets(lbuf,81,inf);
  sscanf(lbuf,"%d %d",&m,&n);

  /* Intialize the grid */
  char grid[m][n];
  for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
      grid[i][j]='#';
    }
  }

/*    printgrid(m,n,grid); */
  readgrid(inf,m,n,grid);
/*    printgrid(m,n,grid);  */

  /* loop through the grid  produce numbering output */
  fprintf(outf,"# Numbering for '%s'\n",infname);
  int num=1;
  for (int i=0; i<m; ++i){
    for (int j=0; j<n; ++j){
/*       fprintf(stderr,"\t\t\t (%d,%d): '%c' ['%c','%c']\n",i,j, */
/*        grid[i][j],grid[i-1][j],grid[i][j-1]); */
      if ( grid[i][j] != '#' &&
       ( (i == 0) || (j == 0) ||
         (grid[i-1][j] == '#') ||
         (grid[i][j-1] == '#') )
         ){
    fprintf(outf,"%d\t%d\t%d\n",num++,i+1,j+1);
      }
    }
  }
  fclose(outf);
  return 0;
}

PerlTeX: 1143 chars (but I haven't golfed it yet)
\documentclass{article}

\usepackage{perltex}
\usepackage{tikz}

\perlnewcommand{\readfile}[1]{
  open my $fh, '<', shift;
  ($rm,$cm) = split /\s+/, scalar <$fh>;
  @m = map { chomp; [ map { /\s/ ? 1 : 0 } split // ] } <$fh>;
  return "";
}

\perldo{
  $n=1;
  sub num {
    my ($r,$c) = @_;
    if ($r == 0) {
      return $n++;
    }
    if ($c == 0) {
      return $n++;
    }
    unless ($m[$r][$c-1] and $m[$r-1][$c]) {
      return $n++;
    }
    return;
  }
}

\perlnewcommand{\makegrid}[0]{
  my $scale = 1;
  my $return;
  my ($x,$y) = (0,$r*$scale);
  my ($ri,$ci) = (0,0);
  for my $r (@m) {
    for my $open (@$r) {
      my $f = $open ? '' : '[fill]';
      my $xx = $x + $scale;
      my $yy = $y + $scale;
      $return .= "\\draw $f ($x,$y) rectangle ($xx,$yy);\n";

      my $num = $open ? num($ri,$ci) : 0;
      if ( $num ) {
        $return .= "\\node [below right] at ($x, $yy) {$num};";
      }

      $x += $scale;
      $ci++;
    }
    $ci = 0;
    $x = 0;
    $ri++;
    $y -= $scale;
  }
  return $return;
}

\begin{document}
\readfile{grid.txt}

\begin{tikzpicture}
  \makegrid
\end{tikzpicture}

\end{document}

It needs a file called grid.txt with the spec, then compile with
perltex --nosafe --latex=pdflatex grid.tex

Scala 252:
object c extends App{val z=readLine.split("[ ]+")map(_.toInt-1)
val b=(0 to z(0)).map{r=>readLine}
var c=0
(0 to z(0)).map{y=>(0 to z(1)).map{x=>if(b(y)(x)==' '&&((x==0||b(y)(x-1)==35)||(y==0||b(y-1)(x)==35))){c+=1
println(c+"\t"+(y+1)+"\t"+(x+1))}}
}}

compilation and invocation:
scalac cg-318-crossword.scala && cat cg-318-crossword | scala c

SHELL SCRIPT
#!/bin/sh
crossWordFile=$1

totLines=`head -1 $crossWordFile | cut -d" " -f1`
totChars=`head -1 $crossWordFile | awk -F' ' '{printf $2}'`

NEXT_NUM=1
for ((ROW=2; ROW<=(${totLines}+1); ROW++))
do
   LINE=`sed -n ${ROW}p $crossWordFile`
   for ((COUNT=0; COUNT<${totChars}; COUNT++))
   do
      lineNumber=`expr $ROW - 1`
      columnNumber=`expr $COUNT + 1`
      TOKEN=${LINE:$COUNT:1}
      if [ "${TOKEN}" != "#" ]; then
      if [ ${lineNumber} -eq 1 ] || [ ${columnNumber} -eq 1 ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
      elif [ "${TOKEN}" != "#" ] ; then
          upGrid=`sed -n ${lineNumber}p $crossWordFile | cut -c"${columnNumber}"`
          leftGrid=`sed -n ${ROW}p $crossWordFile | cut -c${COUNT}`
          if [ "${leftGrid}" = "#" ] || [ "${upGrid}" = "#" ]; then
          printf "${NEXT_NUM}\t${lineNumber}\t${columnNumber}\n"
          NEXT_NUM=`expr $NEXT_NUM + 1`
          fi
      fi
      fi
   done
done

sample I/O:
./numberCrossWord.sh crosswordGrid.txt
1       1       2
2       1       3
3       2       2
4       2       4
5       2       5
6       3       1
7       3       4
8       4       1
9       4       3
10      5       3

I might have not understood the requirements fully, as I just tried to understand from provided I/O, please forgive if the solution is just a workaround for given particular case :)

My /bin/sh complains about line 11. Could you say what shell you are using (including version number)?

Line 8 seems to be similar to line 11.. isn't?
$bash --version GNU bash, version 3.1.17(1)-release (x86_64-suse-linux)

try modifying #!bin/sh    to    #/!/bin/bash  , It should work now!

ANSI C 694 chars
This is a C version that looks for horizontal or vertical runs of two spaces that are either butted up against the edge, or against a '#' character.
Input file is taken from stdin and must be:
<rows count> <cols count><newline>
<cols characters><newline> x rows
...

Any tips for compacting this will be gratefully received.
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define H '#'

char *p,*g;
int m=0,d=0,r=0,c=0,R=0,C=0;
void n() {
    while(!isdigit(d=getchar()));
    m=d-'0';
    while(isdigit(d=getchar()))
        m=m*10+d-'0';
}

int t() {
    return (((c<1||*(p-1)==H)&&c<C-1&&*p!=H&&p[1]!=H)||
            ((r<1||*(p-C-1)==H)&&r<R-1&&*p!=H&&p[C+1]!=H));
}

int main (int argc, const char * argv[])
{
    n();R=m;m=0;n();C=m;
    p=g=malloc(R*C+R+1);
    while((d=getchar())!=EOF) {
        *p++=d;
    }
    int *a,*b;
    b=a=malloc(sizeof(int)*R*C+R+1);
    p=g;m=0;
    while(*p) {
        if(t()) {
            *a++=++m;
            *a++=r+1;
            *a++=c+1;
        }
        if(++c/C) r++,p++;
        c-=c/C*c;
        p++;
    }
    while(*b) {
        printf("%d\t%d\t%d\n",*b,b[1],b[2]);
        b+=3;
    }
}

Output for the Example Provided
1   1   2
2   1   3
3   2   2
4   2   4
5   2   5
6   3   1
7   3   4
8   4   1
9   4   3
10  5   3

This code correctly handles #_# vertical and horizontal single space gaps, which although they may not occur as a single unconnected space, appear to be allowed, e.g. as the last letter of a, say, horizontal word.

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:
Binary search ("bisect") tool
Implement the binary search algorithm as used to identify the source code revision that breaks a computer software program. Your tool should take two arguments specifying the earliest and latest numbered revision to search (both positive integers), and you have two options for making comparisons:

Execute the shell command ./test N, where N is the revision number. If the test passes (i.e. the revision is good), it will return exit code 0.
Call the function test(N), which will return true if the test passes, false otherwise.

Standard output must be the number of the first bad revision, and try to make your tool's source code as short as possible. Enjoy!

Just some clarification, do you want a script or just a function?

@Nemo157: A complete script. I include the test(N) function option primarily for fairness to those programming languages with no standard way to execute shell commands, such as JavaScript.

Ruby - 92 82 62 60 characters
Iterative is way shorter, but nowhere near as cool as tail recursive.
l,h=$*.map &:to_i
test(m=(l+h)/2)?l=m+1:h=m-1 while l<=h
p l

The old tail recursive method for reference
b=proc{|l,h|h<l ?l:(m=(l+h)/2;test(m)?l=m+1:h=m-1;redo)}
puts b[*$*.map(&:to_i)]

Testing script
Uses a little magic to inject the test function and runs a file consisting of purely the above code.
low = Random.rand(100)
mid = low + Random.rand(1e25)
high = mid + Random.rand(1e50)

File.open('./bisect-test-method.rb','w') do |file|
  file << "def test(value)
             value < #{mid}
           end
          "
end

puts "Using input:"
puts "  low=#{low}"
puts "  high=#{high}"
puts "  first_bad=#{mid}"
puts "Output: #{`ruby -r ./bisect-test-method golf-bisect.rb #{low} #{high}`}"

Output:
Using input:
  low=4
  high=75343785543465286986587973836706907796015092187720
  first_bad=5013102893257647460384884
Output: 5013102893257647460384884

Python, 64 chars
This one is recursive, so will overflow the stack for really large input
01234567890123456789012345678901234567890123456789012345678901234567890
|         |         |         |         |         |         |         |
 B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

test run
def test(n):
    print "testing ", n
    return n<66

L,H=10,1000

B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

print B(L,H)

outputs
testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  62
testing  66
testing  64
testing  65
66

Should print 66, not 65 (return H, not L).

@Keith, ok changed that

Python - 77 chars
Abusing the python bisect module. L is the low value, H is the high value
class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

here is a test run
def test(n):
    print "testing ", n
    return n>66
L,H=10,1000

class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

outputs
testing  505
testing  257
testing  133
testing  71
testing  40
testing  56
testing  64
testing  68
testing  66
testing  67

Explanation:
Here is how bisect is defined. Basically it expects a list and decides whether to bisect up or down based on the value it finds by looking at a[mid]. This calls __getitem__ on a, which instead of being a list, is a class that I have defined myself.
def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

bisect=bisect_right

Python - 70 chars
def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L

test run
def test(n):
    print "testing ", n
    return n<66
L,H=10,1000

def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L

print B(L,H)

outputs
testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  63
testing  67
testing  65
testing  66
65

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


text:
Binary tree encoding
Let's suppose you have a complete binary tree (i.e. each internal node has exactly two non empty descendants). Each node contains a nonzero integer. You are given the task of encoding and decoding the tree into/from a list of integers.
The tree is stored internally something like:
struct node {
  int data;
  struct node *left, *right;
};

And you have to implement two functions:
int *encode(struct node *root);
struct node *decode(int *array);

It is up to you how you encode and decode.
Points for:

minimum encoding length
complexity (ideally linear in number of nodes)
originality

No points for source code length and you are not restricted to C.
Tree example:
     5
    / \
   3   2
      / \
     2   1
    / \
   9   9

Input and output requirements wouldn't hurt.

@Yasir: The encoding algorithm is your job so I cannot provide any input and output. int * is a black box for user.

Are there on any restrictions on the range of integers? More specifically if we use a language with arbitrarily large integers are we allowed to make use of that? And is the size of the encoded data measured in number of integers or number of bytes?

Do the encode and decode functions need to be side-effect free (other than memory allocation)? Or may they for example store data in global variables?

Yet another question: Do you measure average encoding length or worst case encoding length?

@sepp2k. 1) Arbitrary large integers are ok. However the only allowed sentinel is 0. You can encode lengths if you want. 2) Ideally it is side-effect free, but not necessary. 3) Average encoding length.

@Alex: Sorry to nag, but are we counting number of bytes or number of integers? I'm asking because I'm thinking of a solution where encode always returns a list of two integers, but the second one may be very large.

@sepp2k. Number of bytes. Any sequence of bytes can be interpreted as an integer.

Assuming the data integers themselves are actual 32-bit integers, there is a simple encoding that uses only 32*n bits.

Crap...I finished implementing a solution before I realized you wanted a binary tree and not a binary search tree. Much less structure in a binary tree...

Ok, posted an actual solution!

In your example, isn't '3' an internal node? Because it doesn't have exactly two non empty descendants. Ah - a leaf isn't an internal node? I guess I didn't get the question. Is a == encode (decode (a)) everything I have to reach with my tree?

~ 1.03 N
It seems all the answers so far take least 2*N * 32-bits to store. (Except the solutions in languages which allows integer values longer than 32 bits, like the Haskell and Ruby solutions - but those are still going to take extra bytes to encode whenever the data is greater than  16K.)
Here is a solution which only takes N+ceiling(N/32)+1 ints of storage. This approaches 1.03125 N for large N, and is under 1.1 N for all N greater than 20.
The idea is to store an extra bit for each node where 1 is "hasChildren".  These bits are packed into N/32 words up front.
int* encodeHelper(Node* n, int* code, int* pos, int* flag)
{
   int hasKids = (n->left!=0);
   code[*flag/32]|=hasKids<<(*flag&31);
   *flag+=1;
   if (hasKids) bencodeHelper(n->left, code, pos, flag);
   code[*pos]=n->data;
   *pos+=1;
   if (hasKids) bencodeHelper(n->right, code, pos, flag);
   return code;
}

int* encode(Node* h, int* sizeOut)
{
   int nnodes=countNodes(h);
   int nflags = (int)ceil(nnodes/32.0);
   int pos=nflags+1;
   int flag=32;
   int* out;
   *sizeOut = 1+nnodes+nflags;
   out = calloc(*sizeOut, sizeof(int));
   if (!h) return out;
   out[0]=nflags+1; //store start of data
   return encodeHelper(h,out,&pos,&flag);
}

Node* decodeHelper(int* code, int* pos, int* flag)
{
   Node*n = calloc(1, sizeof(Node));
   int hasKids = code[*flag/32]>>(*flag&31)&1;
   *flag+=1;
   if (hasKids) n->left = bdecodeHelper(code, pos, flag);
   n->data = code[*pos];
   *pos+=1;
   if (hasKids) n->right = bdecodeHelper(code, pos, flag);
   return n;
}

Node* decode(int* code)
{
   int flag=32;
   int pos=code[0];
   if (!pos) return NULL;
   return decodeHelper(code, &pos, &flag);
}

(compelete implementation here)

This Haskell program encodes a tree of n nodes in n Integers. The trick is that it encodes the node's data doubled, and then uses the lower-order bit to indicate if this is a leaf node, or an interior node.
Technically, the Parser monad here is over-kill, since there is only one parser created, decoder and I could have put the parser chaining logic directly there. But this way the decoder is very clear, and the Parser despite it's small size, is a reasonable simple parsing framework.
import Control.Monad (ap)

data Tree = Leaf Integer | Node Integer Tree Tree
  deriving (Eq, Show)

encode :: Tree -> [Integer]
encode (Leaf n)     = [n*2]
encode (Node n t u) = (n*2+1) : encode t ++ encode u

decode :: [Integer] -> Maybe Tree
decode = fullyParse decoder
  where
    decoder :: Parser Integer Tree
    decoder = do
      i <- next
      let n = i `div` 2
      if even i
        then return (Leaf n)
        else return (Node n) `ap` decoder `ap` decoder

-- A simple Parsing Monad
data Parser a b = P { runParser :: [a] -> Maybe (b, [a]) }

instance Monad (Parser a) where
  return a = P ( \ts -> Just (a, ts) )
  p >>= q  = P ( \ts -> runParser p ts >>= (\(v,ts') -> runParser (q v) ts') )
  fail _   = P ( const Nothing )

next :: Parser a a
next = P n
 where n (t:ts) = Just (t,ts)
       n _      = Nothing

fullyParse :: Parser a b -> [a] -> Maybe b
fullyParse p ts = runParser p ts >>= consumedResult
  where
    consumedResult (v,[]) = Just v
    consumedResult _      = Nothing

-- Example
main :: IO ()
main = do
    putStrLn $ "example:  " ++ show ex
    putStrLn $ "encoding: " ++ show encEx
    putStrLn $ "decoding: " ++ show decEx
    putStrLn $ "worked?   " ++ show worked
  where
    ex = Node 5
          (Leaf 3)
          (Node 2
            (Node 2
              (Leaf 9)
              (Leaf 9)
            )
            (Leaf 1)
          )
    encEx = encode ex
    decEx = decode encEx
    worked = maybe False (ex ==) decEx

Running this gets you:
> runhaskell TreeEncoding.hs
example:  Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1))
encoding: [11,6,5,5,18,18,2]
decoding: Just (Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1)))
worked?   True

In C
#include <stdlib.h>
#include <stdio.h>

struct Node;
typedef struct Node Node;

struct Node
{
    int   data;
    Node* left;
    Node* right;
};
/* Private Functions */
static int*  encodeNode(Node* tree, int* store);
static Node* decodeNode(int** store);

/* Public Functions */
Node*   newNode(int data,Node* left,Node* right);
void    deleteTree(Node* tree);
int     countNodesTree(Node* tree);
int*    encode(Node *tree);
Node*   decode(int* store);
void    printTree(Node* tree);

Node* newNode(int data,Node* left,Node* right)
{
    Node* result    = (Node*)malloc(sizeof(Node));
    result->data    = data;
    result->left    = left;
    result->right   = right;

    return result;
}

void deleteTree(Node* tree)
{
    if (tree == NULL)
    {   return;
    }

    deleteTree(tree->left);
    deleteTree(tree->right);
    free(tree);
}

int countNodesTree(Node* tree)
{
    if (tree == NULL)
    {   return 0;
    }

    return    countNodesTree(tree->left)
            + countNodesTree(tree->right)
            + 1;
}

void printTree(Node* tree)
{
    if (tree == NULL)
    {
        fprintf(stdout, "- ");
    }
    else
    {
        fprintf(stdout, "%d ", tree->data);
        printTree(tree->left);
        printTree(tree->right);
    }
};

The encode:
int* encode(Node *tree)
{
    int     nodeCount   = countNodesTree(tree);
    int*    result      = (int*)malloc(sizeof(int) * (nodeCount * 2 + 1));

    // Put the node count in the first element.
    // This makes it easy to also serialize this object for transport
    // i.e. you can put it in a file or a stream (socket) and easily recover it.
    result[0]           = nodeCount;
    encodeNode(tree, result + 1);
    return result;
}

int* encodeNode(Node* tree, int* store)
{
    if (tree != NULL)
    {
        store[0]    = tree->data;
        /*
         * Slight overkill. for this question.
         * But works and makes future enhancement easy
         */
        store[1]    = (tree->left  == NULL ? 0 : 1)
                    + (tree->right == NULL ? 0 : 2);
        store += 2;

        store       = encodeNode(tree->left,  store);
        store       = encodeNode(tree->right, store);
    }
    return store;
}

The decode:
Node* decode(int* store)
{
    if (store == NULL)
    { fprintf(stderr, "Bad Input terminating: encode() always return non NULL\n");
      exit(1);
    }

    if (store[0] == 0)
    {
        return NULL;
    }

    store++;
    return decodeNode(&store);
}

Node* decodeNode(int** store)
{
    int     value   = (*store)[0];
    int     flag    = (*store)[1];
    (*store) += 2;

    Node*   left    = flag & 1 ? decodeNode(store) : NULL;
    Node*   right   = flag & 2 ? decodeNode(store) : NULL;

    return newNode(value, left, right);
}

Main:
int main()
{
    Node*   t = newNode(5,
                        newNode(3, NULL, NULL),
                        newNode(2,
                                newNode(2,
                                        newNode(9, NULL, NULL),
                                        newNode(9, NULL, NULL)
                                       ),
                                newNode(1, NULL, NULL)
                               )
                       );

    printTree(t);
    fprintf(stdout,"\n");

    int*    e   = encode(t);
    Node*   d   = decode(e);
    printTree(d);
    fprintf(stdout,"\n");

    free(e);
    deleteTree(d);
    deleteTree(t);
}

Note. Each node is encoded as two integers (plus one int for the count of nodes).
So the supplied tree encodes like this:
 7, 5, 3, 3, 0, 2, 3, 2, 3, 9, 0, 9, 0 1, 0
 ^  ^
 ^  ^ Node 1
 ^
 Count

In Ruby, with the same encoding than @MtnViewMark :
class Node
        def initialize(data, left = nil, right = nil)
                @data, @left, @right = data, left, right
        end

        def encode
                "%d %s %s" % [@data<<1|1, @left.encode, @right.encode]
        end

        class << self
                def decode(str)
                        _decode(str.split.map &:to_i)
                end

                private

                def _decode(a)
                        n = a.shift
                        if n & 1 == 1
                                Node.new(n>>1, _decode(a), _decode(a))
                        else
                                Leaf.new(n>>1)
                        end
                end
        end
end

class Leaf < Node
        def encode
                (@data<<1).to_s
        end
end

tree=Node.decode("11 6 5 5 18 18 2")
print tree.encode

The cost is one integer per node (data << 1 | has_childs) :
11 6 5 5 18 18 2

Wow - that looks lean and elegant. However, it doesn't take an Array of int, does it?

Given a binary tree with n nodes, this encodes it in a list of 2n + 1 integers. Both the encoding and decoding algorithms have O(n) complexity.
I use the 0 integer as a sentinel marker when encoding, indicating when I unfold the recursion. Then when I'm decoding, I put the tree nodes I'm creating on a stack (of sorts) and use the 0s in the list to keep track of where to add the next node. I haven't tried, but I'm pretty sure the decoding would break if the tree was not complete.
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

// Prototypes
struct BTnode;
struct BTnode * bt_add_left(struct BTnode * node, int data);
struct BTnode * bt_add_right(struct BTnode * node, int data);
int             bt_depth(struct BTnode * tree);
int             bt_encode_preorder(int * list, struct BTnode * tree, int index);
struct BTnode * bt_node_create(int data);
int             bt_node_delete(struct BTnode * node);
void            bt_print_preorder(struct BTnode * tree);
int *           encode(struct BTnode * tree);
struct BTnode * decode(int * list);

// Binary tree node
struct BTnode
{
  int data;
  struct BTnode *left, *right;
};

// Add node to this node's left
struct BTnode * bt_add_left(struct BTnode * node, int data)
{
  struct BTnode * newnode = bt_node_create(data);
  node->left = newnode;
  return newnode;
}

// Add node to this node's right
struct BTnode * bt_add_right(struct BTnode * node, int data)
{
  struct BTnode * newnode = bt_node_create(data);
  node->right = newnode;
  return newnode;
}

// Determine depth of the tree
int bt_depth(struct BTnode * tree)
{
  int depth;
  int leftdepth = 0;
  int  rightdepth = 0;
  if( tree == NULL ) return 0;

  if( tree->left != NULL )
    leftdepth = bt_depth(tree->left);
  if( tree->right != NULL )
    rightdepth = bt_depth(tree->right);

  depth = leftdepth;
  if(rightdepth > leftdepth)
    depth = rightdepth;

  return depth + 1;
}

// Recursively add node values to integer list, using 0 as an unfolding sentinel
int bt_encode_preorder(int * list, struct BTnode * tree, int index)
{
  list[ index++ ] = tree->data;

  // This assumes the tree is complete (i.e., if the current node does not have
  // a left child, then it does not have a right child either)
  if( tree->left != NULL )
  {
    index = bt_encode_preorder(list, tree->left, index);
    index = bt_encode_preorder(list, tree->right, index);
  }

  // Add sentinel
  list[ index++ ] = 0;
  return index;
}

// Allocate memory for a node
struct BTnode * bt_node_create(int data)
{
  struct BTnode * newnode = (struct BTnode *) malloc(sizeof(struct BTnode));
  newnode->left = NULL;
  newnode->right = NULL;
  newnode->data = data;
  return newnode;
}

// Free node memory
int bt_node_delete(struct BTnode * node)
{
  int data;
  if(node == NULL)
    return 0;
  data = node->data;

  if(node->left != NULL)
    bt_node_delete(node->left);
  if(node->right != NULL)
    bt_node_delete(node->right);

  free(node);
  return data;
}

// Print all values from the tree in pre-order
void bt_print_preorder(struct BTnode * tree)
{
  printf("%d ", tree->data);
  if(tree->left != NULL)
    bt_print_preorder(tree->left);
  if(tree->right != NULL)
    bt_print_preorder(tree->right);
}

// Decode binary tree structure from a list of integers
struct BTnode * decode(int * list)
{
  struct BTnode * tree;
  struct BTnode * nodestack[ list[0] ];
  int i,j;

  // Handle trivial case
  if( list == NULL ) return NULL;

  tree = bt_node_create( list[1] );
  nodestack[ 1 ] = tree;

  j = 1;
  for(i = 2; i < list[0]; i++)
  {
    if( list[i] == 0 )
    {
      //printf("popping\n");
      j--;
    }
    else
    {
      if( nodestack[j]->left == NULL )
      {
        //printf("Adding %d to left of %d\n", list[i], nodestack[j]->data);
        nodestack[ j+1 ] = bt_add_left(nodestack[j], list[i]);
        j++;
      }
      else
      {
        //printf("Adding %d to right of %d\n", list[i], nodestack[j]->data);
        nodestack[ j+1 ] = bt_add_right(nodestack[j], list[i]);
        j++;
      }
    }
  }

  return tree;
}

// Encode binary tree structure as a list of integers
int * encode(struct BTnode * tree)
{
  int maxnodes, depth, length;
  int * list;
  int j;

  // Handle trivial case
  if(tree == NULL) return NULL;

  // Calculate maximum number of nodes in the tree from the tree depth
  maxnodes = 1;
  depth = bt_depth(tree);
  for(j = 0; j < depth; j++)
  {
    maxnodes += pow(2, j);
  }

  // Allocate memory for the list; we need two ints for each value plus the
  // first value in the list to indicate length
  list = (int *) malloc( ((maxnodes * 2)+1) * sizeof(int));
  length = bt_encode_preorder(list, tree, 1);
  list[ 0 ] = length;
  return list;
}

int main()
{
  struct BTnode * tree;
  struct BTnode * newtree;
  int * list;
  int i;

  /* Provided example

        5
       / \
      3   2
         / \
        2   1
       / \
      9   9
  */
  tree = bt_node_create(5);
  bt_add_left(tree, 3);
  struct BTnode * temp = bt_add_right(tree, 2);
  bt_add_right(temp, 1);
  temp = bt_add_left(temp, 2);
  bt_add_left(temp, 9);
  bt_add_right(temp, 9);
  printf("T (traversed in pre-order):  ");
  bt_print_preorder(tree);
  printf("\n");

  list = encode(tree);
  printf("T (encoded as integer list): ");
  for(i = 1; i < list[0]; i++)
    printf("%d ", list[i]);
  printf("\n");

  newtree = decode(list);
  printf("T' (decoded from int list):  ");
  bt_print_preorder(newtree);
  printf("\n\n");

  // Free memory
  bt_node_delete(tree);
  bt_node_delete(newtree);
  free(list);
  return 0;
}

Saved this as encode.c then compiled and executed. This program uses the example tree you provided, and I've tested it on a few others successfully.
$ gcc -Wall -lm -o encode encode.c
$ ./encode
T (traversed in pre-order):  5 3 2 2 9 9 1
T (encoded as integer list): 5 3 0 2 2 9 0 9 0 0 1 0 0 0
T' (decoded from int list):  5 3 2 2 9 9 1

It is pretty much what I had in mind :).

won't this fail decoding if the data contains a 0?

@AShelly He explicitly said that 0 would not be included in the tree. If it were, then yes this would fail.

My code encodes the tree in a preorder traversal, each leaf in two ints (its data followed by 0) and each internal node in one int (its data followed by its left child, then its right).  For a complete binary tree (as you define it) with n nodes, n must be odd, and there are (n+1)/2 leaves and (n-1)/2 internal nodes, so that's 3n/2+1/2 integers for the encoding.
warning: untested, just typed it in.
struct node {
  int data;
  struct node *left, *right;
};

void encodeInternal(struct node *root, vector<int> *buf) {
  buf->push_back(root->data);
  if (root->left) {
    encodeInternal(root->left, buf);
    encodeInternal(root->right, buf);
  } else {
    buf->push_back(0);
  }
}
int *encode(struct node *root) {
  vector<int> buf;
  encodeInternal(root, &buf);
  return &buf[0];
}

struct decodeResult {
  int encoded_size;
  struct node *n;
}
struct decodeResult decodeInternal(int *array) {
  struct node *n = (struct node*)malloc(sizeof(struct node));
  n->data = array[0];
  if (array[1] == 0) {
    n->left = n->right = NULL;
    return (decodeResult){2, n};
  } else {
    decodeResult L = decodeInternal(array + 1);
    decodeResult R = decodeInternal(array + 1 + L.encoded_size);
    n->left = L.n;
    n->right = R.n;
    return (decodeResult){1 + L.encoded_size + R.encoded_size, n};
  }
}
struct node *decode(int *array) {
  return decodeInternal(array).n;
}

Scala:
trait Node {
  def encode (): Array[Int]
}

case object Node {
  def decode (a: Array[Int]): InnerNode = {
    if (a.length == 1) InnerNode (a(0)) else {
      val r = InnerNode (a(1))
      val l = decode (a.tail.tail)
      InnerNode (a(0), l, r)
    }
  }
}

case object Leaf extends Node {
  def encode (): Array[Int] = Array.empty
}

case class InnerNode (val data: Int, var l: Node=Leaf, var r: Node=Leaf) extends Node {
  def encode (): Array[Int] = Array (data) ++ r.encode () ++ l.encode ()
}

object BinTreeTest extends App {
  println (Node.decode (Array (1, 2, 3, 4, 5)).encode.mkString (", "))
}

This is an approach which uses deprecated syntax, but compiles without error in Scala 2.9.1 . It generates a Tree and decodes every encoded Tree to the same Array as used for encoding. Maybe I get somehow rid of the deprecated warnings today.

Wow - that was a simple one. First idea worked immediately.

Here's my try.  It stores the tree in an array of size 2**depth+1.  It
uses a[0] to hold the size, and a[size] to hold the index of the
first "empty node" it encounters in a depth-first traversal.  (An
empty node is the place where a child would be stored if the parent
had one).  Each empty node holds the index of the next empty node that
will be encountered.
This scheme avoids reserving bits to mark the presense children, so
each node can use the full integer range.  It also allows unbalanced
trees - a parent can have only one child.
output:
empty tree:  [0]
head node only:  [2,5,0]
example tree: [16,5,3,2,5,14,2,1,0,0, 0,0,9,9,15,0,4];

The Encoder:
//utility
 int findDepth(Node* n) {
    int l = 0 ,r = 0;
    if (n) {
       l = 1 + findDepth(n->left);
       r = 1 + findDepth(n->right);
    }
    return ( l > r ) ? l : r;
 }

//Encode Function
 int* encodeTree(Node* head) {
    int* out;
    int depth = findDepth(head);
    int size = depth>0;
    while (depth--) size*=2;
    out = calloc(size+1,sizeof(int));
    out[0]=size;
    encodeNode(head, out,1, out+size);
    return out;
 }

 void encodeNode(Node* n, int* a, int idx, int* pEmpty) {
    if (n) {
       a[idx]=n->data;
       encodeNode(n->left,a,idx*2,pEmpty);
       encodeNode(n->right,a,idx*2+1,pEmpty);
    }
    else if (idx<a[0]) {
       *pEmpty = idx;
       pEmpty = a+idx;
    }
 }

The Decoder:
 //Decode Function
 Node* decodeArray(int* a) {
    return (a[0]) ?  decodeNode(a,1,a+a[0]) : NULL;
 }

 Node* decodeNode(int* a, int idx, int* pEmpty) {
    Node* n = NULL;
    if (idx== *pEmpty)
       *pEmpty=a[idx];
    else {
       n = calloc(1,sizeof(Node));
       n->data = a[idx];
       if (idx*2<a[0]) {
          n->left = decodeNode(a, idx*2, pEmpty);
          n->right = decodeNode(a, idx*2+1, pEmpty);
       }
    }
    return n;
 }

(thanks @daniel sobral for fixing the formatting)

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


text:
Calculate ISBN-13 check digit
Write a function which, given the first 12 digits of an ISBN-13 code, will calculate the entire ISBN via calculating and appending an appropriate check digit.
Your function's input is a string containing the first 12 digits of the ISBN. Its output is a string containing all 13 digits.
Formal specification
Write a function which, when given a string s consisting entirely of exactly 12 decimal digits (and no other characters), returns a string t with the following properties:

t consists of exactly 13 decimal digits (and no other characters);
s is a prefix of t;
the sum of all digits in odd positions in t (i.e. the first, third, fifth, etc.), plus three times the sum of all digits in even positions in t (i.e. the second, fourth, sixth, etc), is a multiple of 10.

Example / test case
Input
978030640615
Output
9780306406157
Victory condition
As a code-golf challenge, the shortest answer wins.

Are input and output supposed to contain dashes or only the digits?

Updated the description, the input and output are only the digits

Is outputting the full ISBN-13 acceptable as well?

Note that questions should really be self contained, so it would be helpful to include a description of the algorithm here.

For me above post is poor of example test... There would be at last 10 isbn and one of that has to return 0 as last digit...

Golfscript - 25 chars
{...+(;2%+{+}*3-~10%`+}:f

Whole program version is only 19 chars
...+(;2%+{+}*3-~10%

Check back here for analysis later. Meanwhile check out my old uninspired answer
Golfscript - 32 chars
Similar to the luhn number calculation
{.{2+}%.(;2%{.+}%+{+}*~)10%`+}:f

Analysis for 978030640615
{...}:f this is how you define the function in golfscript
.       store an extra copy of the input string
        '978030640615' '978030640615'
{2+}%   add 2 to each ascii digit, so '0'=>50, I can get away with this instead
        of {15&}% because we are doing mod 10 math on it later
        '978030640615' [59 57 58 50 53 50 56 54 50 56 51 55]
.       duplicate that list
        '978030640615' [59 57 58 50 53 50 56 54 50 56 51 55] [59 57 58 50 53 50 56 54 50 56 51 55]
(;      trim the first element off
        '978030640615' [59 57 58 50 53 50 56 54 50 56 51 55] [57 58 50 53 50 56 54 50 56 51 55]
2%      select every second element
        '978030640615' [59 57 58 50 53 50 56 54 50 56 51 55] [57 50 50 54 56 55]
{.+}%   double each element by adding to itself
        '978030640615' [59 57 58 50 53 50 56 54 50 56 51 55] [114 100 100 108 112 110]
+       join the two lists together
        '978030640615' [59 57 58 50 53 50 56 54 50 56 51 55 114 100 100 108 112 110]
{+}*    add up the items in the list
        '978030640615' 1293
~       bitwise not
        '978030640615' -1294
)       add one
        '978030640615' -1293
10%     mod 10
        '978030640615' 7
`       convert to str
        '978030640615' '7'
+       join the strings
        '9780306406157'

After running the code through an interpreter, I think you can save some characters (in your 32 character Luhn-based solution) by getting rid of the first { and the last three characters; }:f.  I wonder if the same thing can be done for the first solution...

@MikeDtrick, those characters are how GS defines a function. The 19 char version does what you suggest, but the question asked for a "function"

You don't need the :f (yeah, I know functions were commonly named back then).

Python - 44 chars
f=lambda s:s+`-sum(map(int,s+s[1::2]*2))%10`

Python - 53 chars
def f(s):d=map(int,s);return s+`-sum(d+d[1::2]*2)%10`

I think f('9780306406159') outputs '97803064061598' instead of '9780306406157'

@Eelvex, the input string should always be 12 digits

Ah, somehow '9' sneaked in. Sorry...

I would like to leave a useless note that f=lambda s:s+\sum(map(int,s*7+s[::2]*2))%10`` also has 44 chars

Haskell - 54 characters
i s=s++show(sum[-read[c]*m|c<-s|m<-cycle[1,3]]`mod`10)

This requires support for parallel list comprehensions, which is supported by GHC (with the -XParallelListComp flag) and Hugs (with the -98 flag).

Do you not need to include that flag in the count? Besides that, you can replace [1,3] by [9,7] and remove the - which saves you a byte :)

APL (27 characters)
F←{⍵,⍕10|10-(12⍴1 3)+.×⍎¨⍵}

I'm using Dyalog APL as my interpreter. Here's a quick explanation, mostly from right to left (within the function definition, F←{ ... }):

⍎¨⍵: Execute/evaluate (⍎) each (¨) character given in the right argument (⍵).
(12⍴1 3): Reshape (⍴) the vector 1 3 into a 12-element vector (repeating to fill the gaps).
+.×: Take the dot product (+.×) of its left argument ((12⍴1 3)) and its right argument (⍎¨⍵).
10-: Subtract from 10.
10|: Find the remainder after division by 10.
⍕: Format the number (i.e., give a character representation).
⍵,: Append (,) our calculated digit to the right argument.

PHP - 86 85 82 chars
function c($i){for($a=$s=0;$a<12;)$s+=$i[$a]*($a++%2?3:1);return$i.(10-$s%10)%10;}

Re-format and explanation:
function c($i){                     // function c, $i is the input

    for($a=$s=0;$a<12;)             // for loop x12 - both $a and $s equal 0
                                    // notice there is no incrementation and
                                    // no curly braces as there is just one
                                    // command to loop through

        $s+=$i[$a]*($a++%2?3:1);    // $s (sum) is being incremented by
                                    // $ath character of $i (auto-casted to
                                    // int) multiplied by 3 or 1, depending
                                    // wheter $a is even or not (%2 results
                                    // either 1 or 0, but 0 == FALSE)
                                    // $a is incremented here, using the
                                    // post-incrementation - which means that
                                    // it is incremented, but AFTER the value
                                    // is returned

    return$i.(10-$s%10)%10;         // returns $i with the check digit
                                    // attached - first it is %'d by 10,
                                    // then the result is subtracted from
                                    // 10 and finally %'d by 10 again (which
                                    // effectively just replaces 10 with 0)
                                    // % has higher priority than -, so there
                                    // are no parentheses around $s%10
}

Exactly the approach I took in my C# answer. Seems PHP is ~9 characters more efficient!

72 bytes with some tweaks

Windows PowerShell, 57
filter i{$_+(990-($_-replace'(.)(.)','+$1+3*$2'|iex))%10}

Haskell, 78 71 66 characters
i s=s++(show$mod(2-sum(zipWith(*)(cycle[1,3])(map fromEnum s)))10)

Ruby - 73 65 chars
f=->s{s+((2-(s+s.gsub(/.(.)/,'\1')*2).bytes.inject(:+))%10).to_s}

"\\1" -> '\1'?

@Nemo, thanks, my ruby is a bit rusty

Use Ruby 1.9 syntax f=->s{...}. Save 6 chars. Also write s<<(...).to_sinstead of adding 48 and use Fixnum#chr.

Python - 91, 89
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
|         |         |         |         |         |         |         |         |         |
 def c(i):return i+`(10-(sum(int(x)*3for x in i[1::2])+sum(int(x)for x in i[::2]))%10)%10`

Spaces are optional between the first argument and for (and in and the third) in a list comprehension so long as it can be split up by the parser (not using a variable name).  -2 chars there.

C# (94 characters)
string I(string i){int s=0,j=0;for(;j<12;)s+=(i[j]-48)*(j++%2<1?1:3);return i+((10-s%10)%10);}

With linebreaks/whitespace for readability:
string I(string i)
{
    int s = 0, j = 0;
    for (; j < 12; )
        s += (i[j] - 48) * (j++ % 2 < 1 ? 1 : 3);
    return i + ((10 - s % 10) % 10);
}

Tested on several ISBNs from books on my shelf, so I know it's working!

J - 55 45 38
f=:3 :'y,":10|10-10|+/(12$1 3)*"."0 y'

eg
f '978030640615'
9780306406157

old way:
f=:,":@(10(10&|@-)(10&|@+/@((12$1 3)*(i.12)&(".@{))))

(i.12)(".@{)y can be replaced with "."0 y

C# – 89 77 characters
string I(string s){return s+(9992-s.Sum(x=>x-0)-2*s.Where((x,i)=>i%2>0).Sum(x=>x-0))%10;}

Formatted for readability:
string I(string s)
{
    return s +
            (9992
            - s.Sum(x => x - 0)
            - 2 * s.Where((x, i) => i%2 > 0).Sum(x => x - 0)
            ) % 10;
}

We do not multiply by one or three, we just add everything, plus we add all even-placed characters one more time, multiplied by two.
9992 is large enough so that the sum of all ASCII characters is less than that (so that we may mod by 10 and be sure the result is positive, no need to mod by 10 twice), and is not divisible by zero because we add up all those extra 2*12*48 (twelve ASCII digits, weighed by 1 and 3) == 1152, which allows us to spare one extra character (instead of twice subtracting 48, we subtract 0 just to convert from char to int, but instead of 990, we need to write 9992).
But then again, even though much less beautiful ;-), this old-school solution gets us to 80 characters (but this is almost C-compatible):
string T(string i){int s=2,j=0;for(;j<12;)s+=i[j]*(9-j++%2*2);return i+s%10;}

Perl 6, 29 28 bytes
{$_~:1[.comb «*»(9,7)]%10}

Try it online!

So base 1 can be used as a substitute for sum? Interesting!

@JoKing It's actually a very old trick in the world of APL and J :)

Wrong result for 978186197371 it seems to be 8 not 9...

Excuse me I think I had pasted the wrong number

Ruby - 80 characters
def f s;s+(10-s.bytes.zip([1,3]*6).map{|j,k|(j-48)*k}.inject(:+)%10).to_s[0];end

Perl, 53 chars
sub i{($_)=@_;s/(.)(.)/$s+=$1+$2*3/ger;$_.(10-$s)%10}

This doesn't work as it modifies $_ in the replacement and then uses that altered value as part of the return.

@Xcali: fixed now.

dc, 44 chars
[d0r[I~3*rI~rsn++lndZ0<x]dsxx+I%Ir-I%rI*+]sI

Invoke as lIx, e.g:
dc -e'[d0r[I~3*rI~rsn++lndZ0<x]dsxx+I%Ir-I%rI*+]sI' -e '978030640615lIxp'

Q, 36 chars
{x,-3!10-mod[;10]sum(12#1 3)*"I"$'x}

D - 97 characters
auto f(string s){int n;foreach(i,c;s)n+=((i&1)*2+1)*(c-48);return s~cast(char)((10-n%10)%10+48);}

Formatted more legibly:
auto f(string s)
{
    int n;

    foreach(i, c; s)
        n += ((i & 1) * 2 + 1) * (c - 48);

    return s ~ cast(char)((10 - n % 10) % 10 + 48);
}

The verbosity of D's cast operator definitely makes it harder to write obsessively short code though.

Java - 161 Characters :(
int b[]=new int[a.length];
int d=0,n=0,j=1;
for(char c:a.toCharArray())b[d++]=Integer.valueOf(c+"");
for(int i:b)n+=(j++%2==0)?(i*3):(i*1);
return a+(10-(n%10));

This answer does not satisfy the first requirement, since it is not a function.

APL (Dyalog Unicode), 18 bytesSBCS
Anonymous tacit prefix function taking string as argument. Using Bubbler's approach.
⊢,∘⍕10|⍎¨+.×9 7⍴⍨≢

Try it online!
≢ length of argument (12)
9 7⍴⍨ cyclically reshape [9,7] to that length
+.× dot product of the following with that:
⍎¨ `evaluate each character
10| mod-10 of that
,∘⍕ prepend the following the the stringification of that:
⊢ the unmodified argument

05AB1E, 11 bytes
SιO`3*+θTα«

Try it online or verify a few more test cases.
Explanation:
S            # Convert the (implicit) input to a list of digits
             #  i.e. 978030640615 → [9,7,8,0,3,0,6,4,0,6,1,5]
 ι           # Uninterleave it
             #  → [[9,8,3,6,0,1],[7,0,0,4,6,5]]
  O          # Sum each inner list
             #  → [27,22]
   `         # Push them both separated to the stack
    3*       # Multiply the top one by 3
             #  → 66
      +      # Sum them together
             #  → 93
       θ     # Only leave the last digit
             #  → 3
        Tα   # Take the absolute difference of this digit with 10
             #  → 7
          «  # And append this digit to the (implicit) input
             #  → 9780306406157
             # (after which it is output implicitly as result)

Vyxal, 8 bytes
⁽Tẇ∑N₀%J

Try it Online!
Port of Jelly
Explained
⁽Tẇ∑N₀%J
⁽Tẇ       # Triple every second digit
   ∑N     # -sum of that
     ₀%   # modulo by 10
       J  # append that result to the original input

Scala 84
def b(i:String)=i+(10-((i.sliding(2,2).map(_.toInt).map(k=>k/10+k%10*3).sum)%10)%10)

Testing:
val isbn="978030640615"
b(isbn)

Result:
"9780306406157"

C, 80 79 characters
The function modifies the string in place, but returns the original string pointer to satisfy the problem requirements.
s;char*f(char*p){for(s=2;*p;s+=7**p++)s+=9**p++;*p++=48+s%10;*p=0;return p-13;}

Some explanation: Instead of subtracting 48 (the ASCII value of the digit 0) from each input character, the accumulator s is initialized so that it is modulo 10 equal to 48+3*48+48+3*48...+48+3*48 = 24*48 = 1152.  The step 10-sum can be avoided by accumulating s by subtraction instead of addition.  However, the module operator % in C would not give a usable result if s was negative, so instead of using s-= the multipliers 3 and 1 are replaced by -3=7 modulo 10 and -1=9 modulo 10, respectively.
Test harness:
#include <stdio.h>
#define N 12
int main()
{
     char b[N+2];
     fgets(b, N+1, stdin);
     puts(f(b));
     return 0;
}

Q (44 chars)
f:{x,string 10-mod[;10]0+/sum@'2 cut"I"$/:x}

This is actually incorrect I think

Groovy 75, 66 chars
i={int i;it+(10-it.inject(0){t,c->t+(i++&1?:3)*(c as int)}%10)%10}

use:
String z = "978030640615"
println i(z)

-> 9780306406157

APL (25)
{⍵,⍕10-10|+/(⍎¨⍵)×12⍴1,3}

The algo has to end with 10| because else it could return 10 in place of 0

Python 2, 78 76 bytes
lambda n:n+`10-(sum(int(a)+3*int(b)for a,b in zip(n[::2],n[1::2]))%10or 10)`

Try it online!
Takes a string as an argument.
Explanation:
Using python slice notation, converts a string into a list of character pairs. ("978030640615" -> [("9","7"), ("8", "0"), ("3", "0"), ("6", "4"), ("0", "6"), ("1", "5")] )
For that list of pairs, converts each item into an integer and returns a+3b.
Sums all the results.
Gets the sum modulo 10, OR 10 if the remainder is 0. (This prevents the final digit from being 10 instead of 0.)
Removes the remainder from 10 to get the check digit.
Converts the calculated check digit to a string via deprecated backtick expression.
Returns the original number plus the calculated check digit.
Edit:
Saved 2 byes by removing spaces (thanks Jo King!).

You can remove the spaces before for and or

Result to me that 978186197371 has last digit 8 and not 9... I get that number from the only link I print in my Apl solution

Excuse me I think I have pasted the wrong number...

Stax, 11 10 bytes
╣Γ♠☼ù≤m╒X₧

Run and debug it
This is a complete program instead of a function, as stax does not implement functions.
Unpacked, ungolfed, and commented, it looks like this.
q   print input without popping and without newline
E   explode into array of decimal digits
97E [9,7] (this will become the repetition counts)
:B  repeat elements; repetition counts wrap around to cover all input digits
|+  get sum of array with repeated digts
A%  modulus 10
P   print

Run this one

Powershell, 55 53 52 bytes
Inspired by Joey's answer. I'm impressed with her regex.
"$args"+($args-replace'(.)(.)','+40-$1-3*$2'|iex)%10

Powershell, 55 bytes, whithout regex
param($s)$s[1,3,5,7,9,11*2+0..11]|%{$r+=58-$_};$s+$r%10

Explanation:

the index range = (the even positions 1,3,5,7,9,11 repeated 2 times + all positions  0..11)
$r+=58-$_ makes a sum of supplements up to 10+[char]'0'
$s+$r%10 outputs the result

Test script:
$f = {

param($s)$s[1,3,5,7,9,11*2+0..11]|%{$r+=58-$_};$s+$r%10

}

@(
    ,("978030640615" , "9780306406157")

) | % {
    $s,$expected = $_
    $result = &$f $s
    "$($result-eq$expected)"
    $s
    $result
}

Output:
True
978030640615
9780306406157

APL(NARS), chars 38, bytes 76
{⍵,10∣10-10∣+/w,2×w[v/⍨∼2∣v←⍳≢w←⍎¨⍕⍵]}

I had some other test for see better and get definition from Wikipedia, and examples in the page:
https://isbn-information.com/check-digit-for-the-13-digit-isbn.html  test:
  h←{⍵,10∣10-10∣+/w,2×w[v/⍨∼2∣v←⍳≢w←⍎¨⍕⍵]}
  h 978186197271
978186197271 2
  h 978168197271
978168197271 8
  h 978186197371
978186197371 9
  h 978186197375
978186197375 7

the formula i use would be in one not APL language if w is the argument =>
f(w)==w,(10-(sum(digit(w),2*digitsEVENINDICES(w))mod 10))mod 10

comment:
{⍵,10∣10-10∣+/w,2×w[v/⍨∼2∣v←⍳≢w←⍎¨⍕⍵]}
                   v/⍨∼2∣v←⍳≢w←⍎¨⍕⍵] call w the array of digits of ⍵, return even index
               2×w[                  consider all the digit even of w and multipy for 2
             w,                      put above that array, the array w
           +/                        sum all
      10-10∣                          10 - (above sum)mod 10
    10∣                               above mod 10
 {⍵,                                 add as digit to the number of argument, and return all that

dc, 25 bytes
dn[A~9z^8+*rd0<M+]dsMxA%p

Try it online!
I know there's already a dc answer here, but 25<44 so I guess I feel 19 bytes of okay about it.
This uses the fact that 8+9^z is equivalent to either -3 or -1 mod 10 depending on whether z is even or odd. So I use A~ to break the number into digits on the stack, but as I build the stack I multiply each digit by 8+9^z where z is the current stack size. Then I add them all as the function stack unrolls, and print the last digit.

JavaScript, 57 bytes
f=s=>s+(10-s.split``.reduce((a,b,i)=>a+b*(3-i%2*2),0)%10)

You can invoke it like this:
f("978030640615")

Effectively, it goes through each (digit, index) pair (b, i), and works out i % 2 (is i odd?), multiplies it by 2, and subtracts it from 3. Take a look at this:
For odd numbers:

(i % 2) is 1
((i % 2) * 2) is 2
3 - ((i % 2) * 2) is 1

For even numbers:

(i % 2) is 0
((i % 2) * 2) is 0
3 - ((i % 2) * 2) is 3

And so we have now generated the correct multipliers. From there it is simple, just add the current accumulator value, initialised at 0, to the current character multiplied by this generated multiplier. JavaScript automatically casts string to numbers when you do this multiplication.
Calculating the last digit is done by taking the last digit (by computing the value modulo 10), and subtracting this from 10.

Fail 000000000000

K (ngn/k), 19 bytes
{x,$10!2+/x*12#9 7}

Try it online!
Uses the 9 7 instead of 1 3 trick from @Bubbler's J answer, as well as 2+/x... to convert ASCII digits to usable numbers (e.g. "0" is 48, so adding two makes it 50 which allows it to work given the mod by 10 later).

12#9 7 build a 12-length list of 9 7 repeated (i.e. 9 7 9 7 9 7 9 7 9 7 9 7)
x* multiply the underlying ASCII character values by this pattern
2+/ seed a sum with 2 to properly offset the input digits
10! mod by 10
$ convert result to a string
x, append it to the input and return

Pyt, 20 bytes
ĐąĐŁř⁺1∧2*⁺·1ᴇ%1ᴇ-~ǰ

Try it online!
Đ                          implicit input; Đuplicate
 ą                         convert to ąrray of digits
  ĐŁ                       Đuplicate and get Łength
    ř⁺1∧                   řangify [1,2,...,n], increment, and AND with 1
        2*⁺                double and increment (yielding [1,3,1,3,...])
           ·               dot product
            1ᴇ%            modulo 10
               1ᴇ-~        10 - previous result
                   ǰ       ǰoin stack with no delimiters; implicit print

MATLAB - 82 chars
function c(i)
[i num2str(mod(10-mod(sum(str2num(i(:)).*repmat([1;3],6,1)),10),10))]

R, 147 characters
f=function(v){s=as.numeric(strsplit(v,"")[[1]]);t=0;for(i in 1:12)if(i%%2==0)t=t+s[i]*3 else t=t+s[i];paste(v,(10-(t%%10))%%10,collapse="",sep="")}

Usage:
f("978030640615")
[1] "9780306406157"

J, 25
,[:":10|0(-+/)"."0*1 3$~#

   f =: ,[:":10|0(-+/)"."0*1 3$~#
   f '978030640615'
9780306406157

Javascript: 73 71 chars
function _(b){for(i=s=0;12>i;)s+=((i*2&2)+1)*b[i++];return b+(10-s%10)}

Usage:
_('978030640615') //"9780306406157"

Why not define _ as an arrow function too? That saves quite a few characters :)

Clojure 264 -> 241 characters:
(defn s [a b] (let [c (count a)] (if (= 0 c) b (s (rest a) (+ b (* (if (= 0 (m c 2)) 1 3) (first a)))))))
(defn m [a b] (let [f (mod a b)] (if (= f 10) 0 f)))
(defn c [a] (str a (m (- 10 (m (s (map #(read-string %) (map str a)) 0) 10)) 10)))

Usage
(c "978030640615")

Non minified:
(defn sum [collection total]
  (let [len (count collection)]
    (if (= 0 len)
         total
         (sum (rest collection)
           (+ total
            (* (if (= 0 (mod len 2)) 1 3)
             (first collection)))))))

(defn mods [a b]
  (let [f (mod a b)]
    (if (= f 10)
      0
      f)))

(defn create [isbn]
  (str isbn
       (mods (- 10 (mods (sum (map #(read-string %) (map str isbn)) 0) 10)) 10)))

Usage:
(create "978030640615")

New to Clojure so I have to believe that can be knocked down.

Tcl, 79
proc f c {lmap a\ b [split $c {}] {incr d [expr $a+3*$b]};list $c[expr -$d%10]}

Husk, 16 bytes
S:(→sΣz¤*or;¢"97

Try it online!
Explanation
Instead of subtracting the sum from 10 I use negated coefficients, the rest is pretty self-explanatory:
S:(              )  -- apply the following function and append result to itself:
   →s               -- mod 10 / last digit
     Σ              -- sum
      z      ¢"97   -- zip input with ['9','7','9','7'...] under:
       ¤ (r;)       --   convert both chars to number, then
        *           --   multiply

Tcl, 87 bytes
proc C s {lmap c [split $s ""] {incr t [expr [incr i]%2?$c:3*$c]}
list $s[expr -$t%10]}

Try it online!

Tcl, 64 bytes
proc C s {list $s[expr ([regsub -all (.)(.) $s {-\1-3*\2}])%10]}

Try it online!

J, 21 bytes
,10":@|1#."."+*9 7$~#

Try it online!
How it works
,10":@|1#."."+*9 7$~#
                    #  Take length of input
               9 7$~   Repeat 9 7 that many times
          "."+*        Multiply (elementwise) to the digits
       1#.             Sum
 10   |                Modulo 10
   ":@                 Format to string
,                      Append to the end of the input string

The negative of a + 3b + c + 3d + ... modulo 10 is equal to 9a + 7b + 9c + 7d + ... modulo 10.

MBASIC, 106 bytes
1 INPUT T$:FOR I=1 TO 12 STEP 2:O=O+VAL(MID$(T$,I,1)):E=E+3*VAL(MID$(T$,I+1,1)):NEXT:PRINT 10-(O+E) MOD 10

It ain't pretty, but it works.
? 978030640615
7

><>, 24 bytes
0{:9)68**-:nl2%2*7+*+a%!

Try it online!
Explanation
0                      !  # initiates sum (final digit) as 0
 {                        # get the next digit
  :9)68**-                # convert from char to int for any iteration except the last
          :n              # print the digit
            l2%2*7+*      # multiply the digit by either 9 or 7 alternately
                    +     # add to sum
                     a%   # mod sum by 10

Kotlin, 120 108 83 77 69 bytes
{s->s+(10-(s.map{it.toInt()-48}.chunked(2).sumBy{it[0]+3*it[1]})%10)}

Try it online!

Thanks to @ovs for removing 8 bytes!!

I don't think you need .absoluteValue as all digits are non-negative, So this works for 69 bytes.

you're right! thanks! I removed it after, to get it to 77 bytes, but your edit was much better

Perl 5, 48 bytes
sub f{"@_"=~s/(.)(.)/$t-=$1+3*$2/ger;"@_".$t%10}

Try it online!
Doing this as a full program would be shorter:
Perl 5 -p, 31 bytes
s/(.)(.)/$\-=$1+3*$2/ger;$\%=10

Try it online!

Jelly, 10 bytes
ȮD×Ðe3SN%⁵

Try it online!
How it works
ȮD×Ðe3SN%⁵ - Main link. Takes n on the left
Ȯ          - Print n
 D         - Convert to digits
   Ðe      - To even indices:
  ×  3     -   Triple
      S    - Take the sum
       N   - Negate
        %⁵ - Mod 10
             Implicitly print this digit

Go, 118 bytes
func f(n int)int{o,e:=0,0
for i,x:=1,n;i<13;i++{if i%2==0{o+=x%10}else{e+=x%10}
x/=10}
return n*10+(10-(o+3*e)%10)%10}

Attempt This Online!

Japt, 14 bytes
I/O as a string.
+¬xÈ*YgDìÃìÌnA

Try it
+¬xÈ*YgDìÃìÌnA     :Implicit input of string U
+                  :Append
 ¬                 :  Split U
  x                :  Reduce by addition
   È               :  After passing each element at index Y through the following function
    *              :    Multiply by
     Yg            :      Index Y into
       D           :        13
        ì          :        To digit array
         Ã         :  End reduction
          ì        :  To digit array
           Ì       :  Last element
            n      :  Subtract from
             A     :   Ten

Thunno, \$ 17 \log_{256}(96) \approx \$ 13.99 bytes
DZLdZl.SAu3*+n10%

Attempt This Online!
Port of Kevin Cruijssen's 05AB1E answer.
Explanation
DZLdZl.SAu3*+n10%  # Implicit input
DZL                # Print the input without a trailing newline
   dZl             # Convert it to a list of digits and uninterleave
      .SAu         # Sum each list and dump onto the stack
          3*+      # Multiply the top one by 3 and add together
             n10%  # Negate and mod by 10
                   # This is output implicitly, concatenated onto the input,
                   # which was output without a newline at the start

Thunno 2, 10 bytes
zʂẸ3×+ṄT%a

Attempt This Online!
Explanation
zʂẸ3×+ṄT%a  # Implicit input   ->  978030640615
z           # Uninterleave     ->  [[9,8,3,6,0,1],[7,0,0,4,6,5]]
 ʂ          # Sum each         ->  [27,22]
  Ẹ         # Dump onto stack  ->  27, 22
   3×       # Triple           ->  27, 66
     +      # Add              ->  93
      Ṅ     # Negate           ->  -93
       T%   # Mod 10           ->  7
         a  # Append to input  ->  9780306406157
            # Implicit output

Python
>>>r=input()
>>>a=0
>>>for x in r[::2]:
    a+=int(x)
>>>for x in r[1::2]:
    a+=int(x)*3
>>>a=(10-(a%10))%10
print(r+str(a))

I've added the language name to your answer; I was going to add a character count too but it looks like you've cut and paste from the REPL. Could you change this so it's a function as requested in the question and add a character count?

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


text:
->The Tragedy of Macbeth<-
The Setup

Here you can find the full text of The Tragedy of Macbeth.  If you view the source, and save it as text, you will notice it comes out to 206,244 total characters (including the whitespace at the end of the html).
The Challenge

Write a program which compresses the text linked above into the smallest possible text file which can then reproduce the original text exactly (including the whitespace).
The Rules

Your program cannot have any prior knowledge of the text it is compressing.  The goal however is still to compress this specific text, so don't worry if it sucks at other text as long as it does the best job possible on Macbeth.
The program must take either "compress" or "decompress" as the first parameter and the text file as the second command line parameter.  The compressed output has to be a text file, and it has to be UTF16.  The compressed output when decompressed must match exactly the original file in a character for character comparison.
The program needs to finish in a reasonable amount of time.  If it takes longer than a few seconds, please list the average running time with your submission.
The Scoring

The only score is the number of characters in the compressed output.  The score only counts if the decompress matches the original in a character for character comparison.

There's no limit on the size of the source code?

re: The compressed output has to be a text file, and it has to be UTF16., why? also, does that mean that the output must only contain valid UTF16 codepoints?

@Dogbert: No limit on the size of the source code.

0x0000~0xFFFF are valid UTF-16 right?

@Hasturkun: it's an arbitrary encoding selection to take away a variable from the equation.  Yes it can only contain valid UTF16 code points.

"Your program cannot have any prior knowledge of the text it is compressing. The goal however is still to compress this specific text, so don't worry if it sucks at other text as long as it does the best job possible on Macbeth." -- then there is some knowledge of the text implicitly hidden in the program.

Is the input text supposed to include the surrounding HTML?

@S.Mark: Not quite: Sixty-six code points are not used to encode characters. Noncharacters consist of U+FDD0..U+FDEF and any code point ending in the value FFFE or FFFF—that is, U+FFFE, U+FFFF, U+1FFFE, U+1FFFF, ... U+10FFFE, U+10FFFF. (The Unicode Standard, version 5.2)

Nick: I guess you mean either Unicode code points or UTF-16 code units.

Alright, so the UTF requirement was just arbitrary.  Any suggestions for a readable text format worthy that would eliminate as much confusion as possible?

Is that question really appropriate? A good solution is likely to have a large precomputed dictionary, that won't fit comfortably here.

@NickLarsen, why on Earth would you want the compressed file to be "readable text"? It's not going to make sense anyway.

@Peter: My guess would be that the intention is something like Twitter image encoding challenge. But that's just a guess.

The point is to make it more of a challenge than having people 7zip the text on highest compression settings and actually spend a little time thinking about it.

@NickLarsen, seems to me a good way of going about that would be to just forbid built-in and external compression functions. At least that way people have to golf an implementation of a standard algorithm.

@Peter: the thing is, currently this isn't a golfing problem.  Winner is the shortest compressed output.  Which is likely to make use of the largest code.

I'm also surprised how many try or assume golfing here.

It makes sense to count the length of the program plus the length of the output - then it becomes something approximating a competition to find the best bound on the Kolmogorov complexity.

Pseudo-code, compresses Macbeth to 0 bytes
Counter-example (yeah, almost joke) submission intended to point out the flaws with the question.  (the C# was a bit long both in source size and resulting output)
if argument is "compress"
  compare entire input file to the Tragedy of Macbeth
  if equal, then output empty file
  else if input is non-empty,
    then RLE-encode input stream on chr(127) only and output that
  else [if input is empty]
    then RLE-encode a string of zero times chr(127)
else if argument is "decompress"
  if input is empty
  then output the Tragedy of Macbeth
  else RLE-decode input file on chr(127) only and output back

With this approach, Macbeth is brought down to as short a file as possible. Other text input is usually passed untouched, at worst gains a byte per chr(127) which tend not to occur in actual text.

Zero bytes?! shaking fist Grr, +1.

It can suck at other files, so why bother RLE-encoding?I'd just pass non-Macbeth though unchanged.

@Romain what if the input file is empty?

@JB good point :)

Python, compresses to 40,304 bytes.
Similar to Mark's answer, but uses bzip2 instead of zlib (usually better for plain text.)
import bz2 as z,sys;print getattr(z,sys.argv[2])(open(sys.argv[1]).read())

Call like so:
python macbeth.py macbeth.txt compress > macbeth-compressed.txt
python macbeth.py macbeth.txt uncompress > macbeth-uncompressed.txt

Results:
thomas@jupiter:~$ python macbeth.py macbeth.txt compress | wc -c
40304

Post the results in text format?

@NickLarsen How do I do that? It's 44KB of binary data.

The point is to encode the text into other text.

 as z costs 5 strokes, but you only save 2 since you only use z once

@gnibbler: Since it isn't a code-golf, the discussion is off topic.

C#, 1 byte compressed
I've hardly ever used C#'s file manipulation capabilities, so I'll try not to screw this up too badly:
class Program
{
    //args[0]: "compress" = compress mode, anything else = extract mode
    //args[1]: filename of source
    //args[2]: filename of target
    static void Main(string[] args)
    {
        byte[] info;

        using (FileStream fs = File.Open(args[1], FileMode.Open))
        {
            //read the source file
            info = new byte[fs.Length];
            fs.Read(info, 0, (int)fs.Length);
        }

        byte[] macbeth;

        using (WebClient client = new WebClient())
        {
            //get the real MacBeth
            macbeth = client.DownloadData(@"http://shakespeare.mit.edu/macbeth/full.html");
        }

        if (args[0] == "compress")
        {
            //is this also MacBeth?
            if (Encoding.Default.GetString(macbeth).Equals(Encoding.Default.GetString(info), StringComparison.Ordinal))
            {
                //yep, write a dot
                using (FileStream fsOut = File.Create(args[2]))
                {
                    byte[] infoOut = new UTF8Encoding(true).GetBytes(".");
                    fsOut.Write(infoOut, 0, infoOut.Length);
                }
            }
            else
            {
                //nope, better just copy it
                File.Copy(args[1], args[2];
            }
        }
        else
        {
            //is it a dot?
            if (info.Length == 1 && info[0] == Convert.ToByte("."))
            {
                //yep, write MacBeth
                using (FileStream fsOut = File.Create(args[2]))
                {
                    fsOut.Write(macbeth, 0, macbeth.Length);
                }
            }
            else
            {
                //nope! just copy the file
                File.Copy(args[1], args[2]);
            }
        }
    }
}

Compresses MacBeth all the way down to a single byte. While admittedly cheesy, this is technically within the rules (I checked). If it's good enough for Jon Skeet, it's good enough for me.
Holy smoke, talk about a tiny file size, huh? And it's lossless! I'm going to make a million dollars.

Won't work on non-Macbeth documents, will it? I mean, it should still produce output, even if poorly compressed.

@Romain I don't think so. It may be an overly-literal reading, but the task is to compress MacBeth, specifically, without any requirements for other input.  Technically, I could use a completely empty input and claim I've compressed MacBeth to 0 bytes, but that would be silly.

@Romain - Now that I think about it, though, you make a good point. Fixed now.


text:
Binary representation of a number is palindrome or not?
Write a full program  to find whether the binary representation of a number is palindrome or not?
Sample Input
5

Sample Output
YES

Print YES if binary representation is palindrome and NO otherwise.

What should be the output when it's not a palindrome?

@dogbert It should be 'NO' without the quotes.

How do you know it's a palindrome? Because the values from the first nonzero to the end of the "string" are palindromic? This smells really bad to me, as a challenge.

Much as I <3 gnibbler's answer, it's not actually the shortest solution, and any question tagged [code-golf] should pick the shortest solution as the winner.

Input is given how?

@Joey Standard Input

We should be able to write as a function

Golfscript -- 22 chars
~2base.-1%="YES""NO"if

Python - 46 chars
n=bin(input())[2:]
print'YNEOS'[n!=n[::-1]::2]

Wow. What does [n!=n[::-1]::2] do?

@Dogbert, n[::-1] is a slice. The start and end indexs are empty, so it means the whole string. The stepsize is -1, so when you see [::-1] it is a short way to reverse a string/list etc. So n!=n[::-1] is True (ie 1) when n is not a palindrome. Therefore when n is a palindrome, you get 'YNEOS'[0::2] - start at 0 and take every 2nd character. When n is not a palindrome you get 'YNEOS'[1::2] - start at 1 and take every second character :)

I think people are voting for the slice trick :), rightly so. :P +1

Vyxal, 85 bitsv1, 10.625 bytes
-6 bits thanks to @lyxal
-3 bits thanks to @the-thonnu
bḂ≠`∨ȯno`½iN

Try it Online!
b            # binary of input
 Ḃ≠          # is not equal to its reverse (essentially: is not a palindrome?)
   `∨ȯno`    # compressed string `yesno`
         ½   # split into two strings of equal length
          i  # index that inequality (0/1) into that
           N # case swapped to uppercase

Try it Online! for 11.375 bytes

Or Try it Online! for 11.125 bytes

10.625 bytes

C 84 81 74 Characters
r;main(v,x){for(scanf("%d",&v),x=v;v;v/=2)r=r*2|v&1;puts(r-x?"NO":"YES");}

It does not use any function like string reverse.

Couldn't you save a few characters changing r<<=1 into r*=2, v>>=1 into v/=2 and {} into ;?

@paxdiablo Indeed. Changed. Thanks a lot.

r*=2,r|=v&1 -> r=r*2|v&1 (-2)

and moving that term to the body of the loop saves another byte.

Ruby, 41 39
$><<%w(YES NO)[(n="%b"%$*)<=>n.reverse]

Thanks to Michael Kohl's "%b"%gets trick.

Very nice, I like this a lot! +1 for using the spaceship in a creative way :-)

Javascript - 79 77 chars
alert((a=(prompt()*1).toString(2))-a.split("").reverse().join("")?"NO":"YES")

More information
prompt()*1 :  Quick trick to convert string to number.
.toString(2) : That's how you convert to binary in javascript.
a.split("").reverse().join("") : There is no native support to reverse string, so you have to convert string to array and array to string.
("[part1]" - "[part 2]")?"YES":"NO" : - is a replacement for != to save 1 char.

Excellent explanation.

PHP - 41
<?=strrev($n=decbin(`cat`))==$n?@YES:@NO;

Test:
php 713.php <<< 5
YES
php 713.php <<< 6
NO

If you're going to use shell calls to get the input, might as well use m4 instead of cat to save one.  There's also pg and dd (which writes some bytes to stderr).

Have You tried that on Windows? ;)

Perl, 45 characters
$_=sprintf'%b',shift;
print reverse==$_?YES:NO

Ruby, 43 characters
puts((n="%b"%gets)==n.reverse ? "YES":"NO")

Save 2: puts (n="%b"%gets)==n.reverse ? :YES: :NO

Windows PowerShell, 67
('NO','YES')[($a=[Convert]::ToString("$input",2))-eq-join$a[64..0]]

05AB1E, 17 12 bytes
‘NO…Ü‘#EbÂQè

-5 bytes thanks to Adnan.
Try it online!

Hey nice! I tried to golf it a bit and came to 12 bytes ‘NO…Ü‘#EbÂQè :).

Great! I still don't know how to use/make compressed strings. Also, I didn't know the function bin() existed

There is actually a detailed example here, if you are interested :).

JavaScript, 75 bytes 69 bytes
alert((a=[...(+prompt()).toString(2)]).some(x=>x-a.pop())?"NO":"YES")

Try it online!
A different approach from HoLyVieR's solution
Explanation
+prompt() :  Converts string to number
[...s] : converts a string s to an array of chars
.some((x) => x - a.pop()) : checks whether there is one element in the array that does not equal the last element of the array
Edit
69 chars, thanks to the suggestions by Shaggy

69 bytes, or 55 bytes as a function.

67 bytes, or 53  bytes as a function.

@Shaggy, thanks for the first one, I'll add it, as for the second one, I think it makes more sense to be suggested in HoLyVieR's answer

Arturo, 47 bytes
print(=reverse<=as.binary do arg\0)?->'YES->'NO

Python (51)
n=bin(input())[2:]
print'YES'if n==n[::-1]else'NO'

You can ['NO','YES'][n==n[::-1]]

Perl (73)
No string reverse:
print f(split//,sprintf'%b',shift);
sub f{@_<=1?YES:shift!=pop()?NO:f(@_)}

Perl (127)
This one constructs all palindromes up to 2^32.
sub f{
    my($x,$l)=@_;
    $l+=2,f(($x<<$_)+1+(1<<$l-1),$l)?return 1:0 for 1..15-$l/2;
    $x-$ARGV[0]?0:1
}
print f(0,1)+f(0,0)+f(1,1)?YES:NO

Bash, 55 chars
C=`dc<<<$1\ 2op`;[ $C = `rev<<<$C` ]&&echo YES||echo NO

Well, technically that's bash and dc and rev :-)

Haskell (79)
0?k=n;n?k=div n 2?(n`mod`2+k*2);f x|x==x?0="YES"|True="No";main=interact$f.read

Don't forget: In Haskell, this will work with really big numbers.

Ahm, that's actually 79 characters. ;-)

J - 33 characters
13 : ';(]-:|.)#:y{''YES'';''NO'''

J: 24
((-:|.)#:x){2 3$'NO YES'

eg:
   ((-:|.)#:5){2 3$'NO YES'
YES
   ((-:|.)#:12){2 3$'NO YES'
NO
   ((-:|.)#:125){2 3$'NO YES'
NO
   ((-:|.)#:63){2 3$'NO YES'
YES

C (77 bytes)
r,t;main(n){for(t=n=atoi(gets(&n));n;r*=2,r|=n%2,n/=2);puts(r-t?"NO":"YES");}

TEST

Pyth, 18 bytes
%2>"YNEOS"!qJ.BQ_J

Also 18 bytes:
@,"NO""YES"qJ.BQ_J

PHP, not competing
I wanted to do it without using strings at all.
iterative solution, 78 bytes
for($x=log($n=$argv[1],2);$i<$x&($n>>$i^$n>>$x-$i^1);$i++);echo$i<$x/2?NO:YES;

recursive solution, 113 bytes
function p($n,$x=0){return$n<2?$n:is_pal(($n&(1<<$x=log($n,2)/2)-1)^$n>>$x+!is_int($x));}echo p($argv[1])?YES:NO;

If n is a binary palindrome, the upper half xor the lower half is also a binary palindrome and vice versa.

a port of the excellent C answer from fR0DDY, 58 bytes
for($x=2*$v=$argv[1];$x/=2;$r=$r*2|$x&1);echo$r-$v?NO:YES;

a binary reverse. Columbus´ egg.

Retina, 80 78 bytes
Byte count assumes ISO 8859-1 encoding.
.+
$*
+`(1+)\1
${1}0
01
1
^((.)*?).??((?<-2>.)*$)
$1¶$3
O$^`.(?=.*¶)

^(.*)¶\1

Try it online
Convert to unary. Convert that to binary. Cut the number in half and remove a middle digit if there is one. Reverse the first half. Match if both halves are equal.

Jelly, 12 bytes (non-competing)
BṚ⁼Bị“YES“NO

Try it online!
Explanation:
BṚ⁼Bị“YES“NO Main link. Arguments: z.
B            Binary representation of z.
 Ṛ           Reversed.
   B         Binary representation of z.
  ⁼          Check if x is equal to y.
     “YES“NO [['Y', 'E', 'S'], ['N', 'O']]
    ị        xth element of y (1-indexed).

Before printing, Python's str function is mapped through a list, and then the elements are concatenated, so you see YES or NO.

APL (Dyalog Unicode), 23 bytes (SBCS)
'NO' 'YES'⊃⍨≡∘⌽⍨2⊥⍣¯1⊢⎕

-3 bytes from Bubbler, after fitting the question requirements.
Instead of performing an if-else like below, this program uses APL's representation of true as 1 and false as 0 to select from an array, where 'NO' is in the 0th index and 'YES' is in the first index.
Try it online!
APL (Dyalog Unicode), 26 bytes (SBCS)
{(⌽≡⊢)2(⊥⍣¯1)⍵:'YES'⋄'NO'}

Explanation
{(⌽≡⊢)2(⊥⍣¯1)⍵:'YES'⋄'NO'}
{                        } function wrapper
             ⍵             take the right argument
      2(⊥⍣¯1)              convert to base 2, and split into -1 groups(gets all digits)
 (⌽≡⊢)                     reverse equals right expression?
              :'YES'⋄'NO'} if the above is true, display 'YES', otherwise 'NO'

Try it online!

@petStorm Right, somehow I didn't notice that either. Adding ⎕ at the end solves the problem.

You can write a full program with test cases on TIO like this. Some golfing gives 24 bytes (which is the same length as tacit).

Oh, sorry about that. I'll fix it soon. Thanks for the help!

23 bytes with (⌽≡⊢) → ≡∘⌽⍨ (because ≡∘⌽⍨x → x≡∘⌽x → x≡⌽x)

A second commutation. Got it.

This really should have gotten a 100-rep bounty, not 200, so I'll skip one of your 100-rep bounties.

No worries. I figured as much.

Wolfram Language (Mathematica), 46 bytes
If[PalindromeQ@IntegerDigits[#,2],"YES","NO"]&

Try it online!

Arn, 16 bytes
±î«Áýãf©¯tvf–É‰2

Try it!
Explained
Unpacked: "YES"^(=\|:;b)||"NO. Man that yes/no required output really killed my byte count
    "YES"         String
  ^               Repeated
    (             Begin expression
        \         Fold with...
      =           ...equality
          |:      Bifurcate
              _   Variable initialized to STDIN; implied
            ;b    Binary representation
    )             End expression
||                Boolean OR
  "NO             String, ending quote implied

This works because empty strings are falsey.

Pyth, 16 bytes
?q_K.BQK"YES""NO

Try it online!
?q_K.BQK"YES""NO
   K.BQ          // Assign binary input to K
?q_K   K         // Evaluate whether K and reversed K are equal
        "YES""NO // Ternary output.

Nibbles, 11.5 11 bytes (22 nibbles)
Edit: -1 nibble thanks to xigoi
?==;``@$\@"YES" "NO"

    ``@                 # get binary representation of
       $                # input
   ;                    # and save it;
 ==                     # is this equal to
        \               # reverse of
         @              # itself?
?                       # if so:
           "YES"        #   output "YES"
                        # otherwise:
                 "NO"   #   output "NO"

Why not use ==?

Japt, 13 bytes
¢è¬?`y`u:"NO

Try it

Thunno 2, 12 bytes
ḃḲQ"YESNO"½i

Attempt This Online!
Unfortunately, the Thunno 2 dictionary only holds words which are 4 letters or more, so neither YES nor NO can be compressed.
Explanation
ḃḲQ"YESNO"½i  # Implicit input
ḃ             # Convert to binary
 ḲQ           # Not equal to its reverse?
              # (i.e. 0 if palindrome, 1 otherwise)
   "YESNO"    # String "YESNO"
          ½   # Halve to get ["YES", "NO"]
           i  # Index into the list
              # Implicit output

Haxe, 164 bytes
Works only with system platforms (php, neko, cpp, etc.). Takes input through command line arguments.
class T{static function main(){var r:Dynamic=Std.parseInt(Sys.args()[0]);var s=r.toString(2);trace(s==[for(i in-s.length+1...1)s.charAt(-i)].join('')?"YES":"NO");}}

Matlab, 71 bytes
function paly(n)
v=de2bi(n);
if v==v(numel(v):-1:1)
'YES'
else
'NO'
end

Welcome to PPCG!

05AB1E, 13 bytes
bÂQi'…Üë'€¸}u

Try it online!
bÂQi'…Üë'€¸}u  # full program
   i           # if...
 Â             # implicit input...
b              # in binary...
  Q            # is equal to...
 Â             # implicit input...
b              # in binary...
 Â             # reversed...
    '…Ü        # then push "yes"
       ë       # else...
        '€¸    # push "no"
           }   # exit if statement
            u  # convert to uppercase
               # implicit output

Python, 84 Bytes
f=lambda x:['NO','YES'][int(bin(x)[2:]==(bin(x)[2:])[-1::-1])]
print(f(int(input())))

Try online on TIO
If just a pure function was allowed:
Try pure function online (60 Bytes)

This seems valid. You don't need the [-1:: in [-1::-1]. Just [2:][::-1] is enough

55 bytes by removing a lot of unnecessary stuff, or 51 bytes for a function

Uiua SBCS, 22 bytes
&p⊡≍⇌.⋯⋕&sc{"NO""YES"}

Try it!


text:
Calculate the number of trailing zeros in n!
Write a function which takes n as a parameter, and returns the number of trailing zeros in n!.
Input Constraints
0 <= n <= 10^100
Output Constraints
Should be return the result in less than 10 seconds.
Test Input
1
213
45678
1234567
78943533
4567894123
121233112233112231233112323123

Test Output
0
51
11416
308638
19735878
1141973522
30308278058278057808278080759

Shortest code by character count wins.

I'm not sure if we should have this here, as it's basically the same as https://www.spoj.pl/SHORTEN/problems/FACTZERO

@Nabb, I had no idea that this question was on SPOJ. I've put a significantly larger limit on the input here though.

@Dogbert: The limit is larger but the algorithms here are going to be exactly the same as over at SPOJ.

for shortest code, you should use the code-golf tag

It's on Euler as well :) (i think)

@Nabb, Aaah, your top on the leaderboard.

Should we tag it "euler project" and "spoiler"?

Python, 36 Chars
Ripped from my earlier answer
f=lambda n:n//5+(n//5>0and f(n//5)or 0) #Py3k #39 Chars
f=lambda n:n/5+(n/5>0and f(n/5)or 0) #Before 3.0 #36 Chars

But you still need the input and output right?

@Debanjan, the question states, write a function....

@sOle:My bad!I missed that.

Python 50 47 Characters
n=input()
x=5
s=0
while n/x:s+=n/x;x*=5
print s

Ruby, 52 43
n=gets.to_i;a=0;i=1
a+=n/i*=5while i<n
p a

You could use (a+=n/i;i*=5)while i<n to save a char.

And ofcourse, p a as a is a number.

Haskell, 63 bytes
f i=length$filter(\x->x`mod`5/=0)[1..i];main=interact$show.f.read

J, 26
! `f=:3 :'+/<.y%5^(1+i.144x)'`

eg
   f 121233112233112231233112323123x
     30308278058278057808278080759
   f 4567894123
     1141973522
   f 0
     0
   f 10^100x
     2499999999999999...99999999999999999982

in less than a second for all input examples