text:
We'll be counting stars
Your objective is to take multiline ASCII like
|  v  |
* * * *
 * * *

and have an array that includes everything that isn't a star changed to a star (except for [any-width] spaces) and the number of stars it included and the number of stars it now includes.  So the output of my example would be:
['*  *  *
* * * *
 * * *',7,10]

or
["*  *  *\n* * * *\n * * *", 7, 10]

depending on what your code language does.
This is a code-golf challenge, so the shortest bytes wins!

Can you clarify the input and output formats, please? Which form the code should have (program, function)?

@HeikoOberdiek Oh, yes.  It can be both, whichever's shorter for you.

@TheWobbuffet What about input/output formats? Can it just be a function that takes an argument and return an array, for example? Or does it have to print out the answer (and what would be the required format for that)?

GolfScript, 30 characters
.{.'
 '?)\42if}%.{@'*'/,(}2*]`

Takes the input from stdin. Example (test online):
> |  v  |
> * * * *
>  * * *

["*  *  *\n* * * *\n * * *\n" 7 10]

Python - 58 66 characters
Sooo... my first Code Golf attempt...
Code:
import re;p=re.sub(r'\S','*',i);print[p,i.count('*'),p.count('*')]

Output:
['*  *  *\n* * * *\n * * *', 7, 10]

Variables:

i - input string
p - pattern
o - output -  removed

Dependencies:
Python re module
Full code:
import re
i = '|  v  |\n* * * *\n * * *'
p = re.sub(r'\S','*', i)
print [p, i.count('*'), p.count('*')]

Edits:

Added import re to solution
Replaced o= with print
r'[/\S/g]' was changed to r'\S' (thanks @14mRh4X0r)

Hey, welcome to PPCG! This is mostly a good answer, so please don't take the rest of this post personally: There are a few things wrong with it. You've listed the re module as a dependency, but it's still necessary to include it in the answer and score. Your program also doesn't output the result like it's supposed to (however, since you don't actually use the o variable for anything, you can just s/o=/print/ and only lose three). Other than that, this looks good!

Actually, there's one tiny other thing. Your i variable contains | v | * * * * * * * instead of the actual test input (which includes newlines). That being said, your program still works if you include the newlines, so your program doesn't have to be changed at all, just the post. :)

Hi @undergroundmonorail - thanks for the feedback :) I'll update my post now

No problem. Also, I haven't tested this at all, but 14mRh4X0r from chat says that r'[/\S/g]' could be replaced with r'\S' to save a few characters.

@undergroundmonorail and he's right :) thanks

You don't need the r in r'\S'

JavaScript (ECMASCript 6) - 51 Characters
i=j=0,[A.replace(/\S/g,x=>(j++,i+=x=='*','*')),i,j]

Assumes the variable A contains the multiline ASCII input. To take it from the user then replace the A with prompt() (+7 characters) or as a function (again +7 characters):
f=A=>(i=j=0,[A.replace(/\S/g,y=>(j++,i+=y=='*','*')),i,j])

Output is to the console.
Test:
A='|  v  |\n* * * *\n * * *'
i=j=0,[A.replace(/\S/g,x=>(j++,i+=x=='*','*')),i,j]

Outputs:
["*  *  *
* * * *
 * * *", 7, 10]

Ruby 2.0, 53 characters
p [r=gets($n).gsub(/\S/,?*),$_.count(?*),r.count(?*)]

Not sure on the exact input/output formats required.  This takes input on STDIN and formats the output like so:
Input:
|  v  |
* * * *
 * * *

Output:
["*  *  *\n* * * *\n * * *", 7, 10]

Rebol, 84
c: s: 0 parse t[any["*"(++ s)|" "|"^/"| m: skip(change m"*" ++ c)]]reduce[t s s + c]

Set t to the text like so....
t: {|  v  |
* * * *
 * * *}

and this would return...
["*  *  *^/* * * *^/ * * *" 7 10]

Ungolfed version with some notes:
c: s: 0    ;; "s" is star count before change, "c" is count of chars changed to stars

; so using single-char ANY rule to parse each character in "t"

parse t [
    any [                              ;; so "t" is made up of ANY...
        "*"     (++ s) |               ;; "*" (if so then increment s)
        " "            |               ;; or a space
        "^/"           |               ;; or a newline
        m: skip (change m "*"  ++ c)   ;; or anything else (skip)
                                       ;;   (and so change to "*" & increment c)
    ]
]

reduce [t s s + c]      ;; return array with amended text (t) and counts

Groovy : 96 92 chars
s=System.in.text
t=s.replaceAll(/[^\*\s]/,/\*/)
println "['$t',${s.count"*"},${t.count"*"}]"

Uses Groovy 2.2.1
Reads from STDIN. IMHO, not especially clever, but fairly easy to read (given its brevity)

PHP ≥ 5.5, 84 69 63 bytes
$a=[preg_replace('/\S/','*',$s,-1,$n),substr_count($s,'*'),$n];

Not a lot to say about this. As there is no specification for how to handle input/output, I'm assuming variable storage. Expects the input in variable $s and stores the array in variable $a. Too bad those function names are s o long.

Stax, 12 bytes
ç≈°▼╔╔²AGΓM4

Run and debug it
Explanation
.\S'*YRQx2Dy#P
.\S              push regex \S
   '*            push '*'
     Y           store star in Y
      R          perform regex replacement on the input
       Q         peek and print with newline
        x        push input again
         2D      execute the following twice:
           y     push '*'
            #    number of stars
             P   pop and print with newline

05AB1E, 17 bytes
…
     м©S'*:I'*¢®g)

Assumes the mentioned "[any-width] spaces" only include spaces, tabs, and newlines (with codepoints 32, 9, and 10 respectively).
Try it online.
Explanation:
…\n\t м       # Remove all newlines, tabs, and spaces of the (implicit) input-string
       ©      # Store this string in variable `®` (without popping)
        S     # Convert it to a list of characters
         '*: '# Replace each non-whitespace character in the (implicit) input with a "*"
I             # Push the input again
 '*¢         '# Pop and count the amount of "*" in this string
®             # Push the non-whitespace string from variable `®`
 g            # Pop and push its length
            ) # Wrap everything on the stack into a list
              # (after which it is output implicitly as result)

Perl, 52 bytes
$_=join'',<>;printf'["%s",%s,%s]',$_,tr/*//,s/\S/*/g

Takes input from standard input, prints to standard output.
Assuming the output format like you described in your question, could be made quite a bit shorter if a different output format would be allowed.

Javascript - 50 characters
i.replace(/\S/g,'*').replace(/\n/g,':').split(':')

Test
Input
var i = 'Lately I been, I been losing sleep\nDreaming about the things that we could be\nBut baby, I been, I been prayin\' hard';
i.replace(/\S/g,'*').replace(/\n/g,':').split(':')

Output
["****** * ***** * **** ****** *****", "******** ***** *** ****** **** ** ***** **", "*** ***** * ***** * **** ******* ****"]

This doesn't really meet the specification. Look here for an example.

Java, 199 bytes
Golfed:
class C{public static void main(String[]a){String i=a[0],o=i.replaceAll("\\S","*");System.out.println("["+o+","+g(i)+","+g(o)+"]");}static int g(String x){return x.replaceAll("[^\\*]","").length();}}

Un-golfed:
public class CountingStars {

    public static void main(String[] args) {
        String input = args[0];
        //replace all non-white-space char with *
        String output = input.replaceAll("\\S", "*");
        System.out.println("[" + output + "," + getStars(input) + "," + getStars(output) +"]");
    }

    static int getStars(String x) {
        //replace all non-* characters with empty-string and return length
        return x.replaceAll("[^\\*]", "").length();
    }
}

Run online.

In JavaScript/CoffeeScript - 66 Characters
Like the PHP Example, the length is due to the length of the function names
[x.replace(/\S/g,"*"),x.split("*").length-1,x.match(/\S/g).length]

Example Usage (CoffeeScript):
((x="|  v  |\n* * * *\n * * *")->[x.replace(/\S/g,'*'),x.split('*').length-1,x.match(/\S/g).length])()

3-char shorter : [x.replace(r=/\S/g,s='*'),x.split(s).length-1,x.match(r).length]

C# - 116
Shortest way i can think of that returns an array..
object[]R(string a){var o=Regex.Replace(a,"\\S", "*");return new object[]{o,a.Count(x=>x=='*'),o.Count(x=>x=='*')};}

AWK, (too long)
awk '{y+=gsub(/[^* ]/, "*"); x+=NF}NR>1{z=z "\n" $0} NR==1{z=z $0} END{print "[\x27"z (x-y) "," x "\x27]"}'

I'm no awk master so I'm sure it can be improved. The takeaway is I had fun writing it! The struggle came with how to preserve the newlines from the input but not put the , 7,10] on a new line. That bit of logic (NR>1{z=z "\n" $0} NR==1{z=z $0}) cost me a lot of characters. I'd be interested to see any other awk approaches on that front.
I didn't provide the file at the end of the script, but obviously the usage would be awk '{<code>}' ascii.txt, where ascii.txt contains the mult-line "input".
Output
 ['* * *
 * * * *
 * * *',7,10]

Zsh -F, 44 bytes
T(){tr -dc *|wc -c}
T<f
tr<f -c '
 ' *>g
T<g

Try it online!
Input from a file f, output to stdout and a file g
Ungolfed and commented:
T () {        # define a function T
  tr -dc *  \ # keep only the asterisks in the input
    | wc -c   # count characters
}
T < f         # apply T to the file f
tr        \   # replace
  -c      \   # everything except
  '\n '   \   # spaces or newlines
  *       \   # with asterisks
  < f     \   # input from the file f
  > g         # output to the file g
T < g         # apply T to the file g

-F prevents the * from being interpreted specially

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

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


text:
Animate a Rotating Lissajous Figure
Entries for this challenge will display an animated rotating Lissajous figure.  The appearance of 3d rotation occurs as the x parameter is successively phase-shifted in each frame.
Input:
The a and b parameters (as per the wikipedia article) will be specified at the command line, or read from stdin.
Output:
This is ascii-art, so output will be displayed in a terminal emulator window or equivalent.  Output size may be hardcoded, but the Lissajous figure must be at least big enough to fill a 80x24 window.
The animation frame rate will be approximately 50fps.  Sleeping for 20ms between each frame is fine, as long as the time to calculate each frame is small compared with the fixed sleep time.  If your choice of language cannot calculate quick enough on your chosen platform, then you'll have to calculate the time to sleep dynamically.
Each frame will not be displayed until all calculation for that frame is complete.  There is no need to clear the screen between each frame.
The figure will make a full 2*Pi rotation approximately every 4 seconds.
For each frame, a full closed curve must be generated.  At least 1000 points must be calculated along the curve.  Line-drawing in between points is not necessary.
Points of the curve will be plotted as # characters.  The rest of the display area will be blank/whitespace.
This is code-golf, so the shortest answer in bytes (deemed acceptable by me) will be the accepted winner one week after this posting.

Ungolfed reference answer.

Are we allowed to draw it using a graphics-oriented language?

@TheDoctor I was torn on that, but decided to restrict to [tag:ascii-art].  Perhaps we can do a [tag:graphical-output] follow-up if this ends up popular.

As with many rotating figures, these figures rotate different ways depending on how you look at them. For example, your answer seems to be rocking back and forth to me. But when I try hard, I can see regular rotation.

Perl - 177

while($d+=.1){print"\e[H\e[2J";$a=0;while(($a+=.01)<4*atan2 1,0){$x=$==40+40*cos$d+$a*$ARGV[0];$y=$==13+13*sin$d+$a*$ARGV[1];print"\e[$y;$x"."H#";}print$/;select($v,$v,$v,.03);}

The coefficients are passed via arguments. The above gif is produced from perl % 2 3

@DigitalTrauma I have my very own tool for recording screen in X11

C (reference answer - not golfed)
Output with ./lissajous 2 3:

/*
 * lissajous.c
 *
 * Compile with:
 *   cc lissajous.c -lm -o lissajous
 *
 * Usage:
 *   ./lissajous a b
 *
 * a and b are the parameters as described in:
 * http://en.wikipedia.org/wiki/Lissajous_curve
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <unistd.h>

int main (int argc, char **argv) {
    char buffer[25][80];
    double t, p;
    int x, y;
    int a, b;

    if (argc != 3) return 1;

    a = atoi(argv[1]);
    b = atoi(argv[2]);

    for (;;) {
        for (p = 0; p < 2 * M_PI; p += M_PI / 100) {
            memset(buffer, ' ', sizeof(buffer));
            /* Set 1st char of final line to nul.  Then we can printf
             * the whole 2d array as if it were one long 1d buffer.
             * Line wraps at 80 chars are assumed */
            buffer[24][0] = 0;
            for (t = 0; t < 2 * M_PI; t += M_PI / 500) {
                x = 39.5 * (1 + sin(a * t + p));
                y = 11.5 * (1 + sin(b * t));
                buffer[y][x] = '#';
            }
            printf("%s\n", &buffer[0][0]);
            usleep(20000);
        }
    }
    return (0);
}

C, 257 bytes
Ok, well I couldn't resist golfing it a bit myself.  I think there's a lot more golfing to be done on this though:
#include<math.h>
main(int a,char**v){char x,y,b,d[25][80];double t,p,q=2*M_PI;a=atoi(v[1]);b=atoi(v[2]);for(p=0;memset(d,32,2000);p+=q/100){p=p<q?p:0;d[24][0]=0;for(t=0;t<q;y=11.5*sin(b*t)+12,d[y][x]=35,t+=q/1e3)x=39.5*sin(a*t+p)+40;puts(d);usleep(20000);}}

funny how the reference answer is getting upvotes...

@TheDoctor I know, right.  Thats why I ended up adding a  golfed version, as it didn't feel right to get upvotes for an ungolfed answer.

If you're usleeping for 20000ms, why not just sleep for 20s ?

@ace usleep(20000)== 20000 micro seconds, not 20000 milli seconds

Oops, sorry, my bad. What about usleep(2e4);?

@ace Nice idea, but for reasons beyond me, I need to #include <unistd.h> to get this form of integer literal to work with gcc.

Hmm... I guess it may be related to the fact that 2e4 is actually a float in C, not an int. But I think it will still work in your t+=q/1000 part (t+=q/1e3)

@ace Sure - that works for 1 char ;-).  Thanks.

Python 3 - 280
Don't have one of those fancy animated gifs for ya, sorry. Windows console is slow at printing :P
Not sure this meets the 50fps requirement though I'm not sure it's really possible with Python. You can adjust the 1000 on the second line for the amount of points to calculate (the list is output width, output height, points to find, progression per frame (pi*2/n) and starting point). Or you can remove them and specify in the input as well.
import math as m
a,b,w,h,p,r,t=list(map(int,input().split()))+[79,24,1000,100,0]
while 1:v,z=w/2,h/2;d=[[int(m.sin(a*k+t)*v+v),int(m.sin(b*k)*z+z)]for k in[m.pi*2/p*l for l in range(p)]];print('\n'.join(''.join([' ','#'][[i,j]in d]for i in range(w))for j in range(h)));t+=m.pi*2/r

MORE IMPORTANT EDIT: Input via stdin, space-separated, newline terminated. Will wait for your input.
EDIT: Screenshot. Changed height to 40 for this one.

Hmm, it just hangs for me with python 3.2.3 (and 2.7.3) on Ubuntu.  I guess I need to dig up a windows VM from somewhere.  Or learn python.

@DigitalTrauma Hm. I'm running 3.3.2. Strange that it doesn't work though, don't see any platform-specific procedures in my code.

Save as lissajous.py, then run python3 lissajous.py 2 3 should be sufficient, right?

@DigitalTrauma Oh, oh, sorry. It takes input from stdin, not the args (failed to specify that...oops). Space-separated.

Aha - I guess I should have seen input() and guessed that.  Works fine now for me with 3.2.3.  +1

@DigitalTrauma I imported time without using it. XD Is the timing okay or should I add a delay?

Its a bit slower than the c reference on my VM, but I'm ok with it.

BTW under Linus (bash) you can start it all in one command thus: python3 lissajous.py <<< "2 3"

@DigitalTrauma I'll remove the import then ;D also, thanks for the +1 (phone glitch there)

C# - 360 352 (cross platform - 332 for Windows only)

Edited after micro-golfing and rounding bug fix + suggestion by Ypnypn
Not exactly a contender at that length - and it's pretty much a verbatim copy of the reference - but oh well. :)
namespace System{class P{static int Main(string[]m){double p=Math.PI*2,a=int.Parse(m[0]),b=int.Parse(m[1]),q,t;for(;;)for(q=0;q<p;q+=p/200){var s=new string(' ',1920).ToCharArray();for(t=0;t<p;t+=p/1000)s[(int)(39.5*Math.Sin(a*t+q)+40)+(int)(11.5*Math.Sin(b*t)+12)*80]='#';Console.SetCursorPosition(0,0);Console.Write(s);Threading.Thread.Sleep(20);}}}}

Memory hog, creating a new array for every refresh - originally (re)used a StringBuilder, but sacrificed it for shortness. But at least the refresh takes less than 1 ms on my old Core2.
After removing some - now length-hurtful - old golfing, thereby reducing it by 8 characters, I tried to get it back to the "poetic" 360 by reverting to double rather than int parsing, and returning to 80*24 instead of 1920. That's still only 359, though - and no other single character addition that I can think of really adds any value to the code. So we'll just stick with 352. :-)
Unrolled (lost the pre-golf code):
namespace System
{
    class P
    {
        static int Main(string[] m)
        {
            double p = Math.PI * 2,
                   a = int.Parse(m[0]),
                   b = int.Parse(m[1]),
                   q, t;

            for (;;)
            {
                for (q = 0; q < p; q += p/200)
                {
                    var s = new string(' ', 1920).ToCharArray();
                    // Alternative - Windows console only:
                    // var s = new char[1920];

                    for (t = 0; t < p; t += p/1000)
                    {
                        s[
                            (int) (39.5*Math.Sin(a * t + q) + 40)
                          + (int) (11.5*Math.Sin(b * t) + 12) * 80
                        ] = '#';
                    }
                    Console.SetCursorPosition(0, 0);
                    Console.Write(s);
                    Threading.Thread.Sleep(20);
                }
            }
        }
    }
}

The Windows console actually accepts outputting a lot of null chars resulting in output that's (graphically) identical to using an actual space character - which allows a few characters less to initialize the character array.

Windows console actually accepts outputting a lot of null chars.  Ah perhaps that explains why it doesn't so well with mono on Ubuntu.  I don't have windows/.net handy right now, so I'll take your word for it that it works.

Just added a screenshot - should make it cross platform, but considering the non-contender status it has already - and the rather "poetic" number of characters, maybe it should just be left as is. :-)

No need for all answers to be cross-platform IMO.  If answers are platform-specific, its good to mention the platform, though C# is so well-known that its already obvious.

Does using C = Console really save any characters?

@Ypnypn - not after invading the System namespace, nope. Didn't change it, or look for it, because the self-stated goal was to get to the same 360 characters while still using "proper" char array initialization. Thanks. :-)

Python 2.7 - 214
I think I'm going to have another look at this. I have a feeling this can be brought down even further, but it will be hard to hit the Perl byte count. The math seems to be my biggest limitation here.
Warning: may crash whatever terminal you are using. I tested this on the Windows command prompt with lissajous.py 2 3. Because of the quick writing to the command prompt, expect the frames to jump a little bit. This can be mostly resolved (at the cost of speed) by using a greater s in the range(s) and t=2*pi*i.
I don't use \r or \b here purposely because I'm running it on Windows and it would cost extra characters.
from math import*;import sys;a,b=sys.argv[1:];p=s=1920
while p:
 c = [" "]*s
 for i in range(s):
    t=2*pi*i/s;c[int(round((39.5*(1+sin(eval(a)*t+p))))+round(11.5*(1+sin(eval(b)*t)))*80)]="#"
 print ''.join(c)
 p+=.1

+1 Works on Ubuntu, though the output is a bit jumpy

@DigitalTrauma Yeah the jumpiness is caused by this being a cross platform solution (ie. to work on Windows command prompt).

source: Stack Exchange

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

sort: votes


text:
How high can you go? (A coding+algorithms challenge)
Now that everyone has developed their (often amazing) low level coding expertise for How slow is Python really? (Or how fast is your language?) and How Slow Is Python Really (Part II)? it is time for a challenge which will also stretch your ability to improve an algorithm.
The following code computes a list of length 9. Position i in the list counts the number of times at least i consecutive zeros were found when computing the inner products between F and S. To do this exactly, it iterates over all possible lists F of length n and lists S of length n+m-1.
#!/usr/bin/python
import itertools
import operator

n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
    for F in itertools.product([-1,1], repeat = n):
        i = 0
        while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
            leadingzerocounts[i] +=1
            i+=1
print leadingzerocounts

The output is

[4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064]

If you increase n to 10,12,14,16,18,20 using this code it very rapidly becomes far too slow.
Rules

The challenge is to give the correct output for as large an n as possible. Only even values of n are relevant.
If there is a tie, the win goes to the fastest code on my machine for the largest n.
I reserve the right not to test code that takes more than 10 minutes.
You may change the algorithm in any way you like as long as it gives the correct output. In fact you will have to change the algorithm to make any decent progress toward winning.
The winner will be awarded one week from when the question was set.
The bounty will be awarded when it is due which is a little after when the winner will be awarded.

My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.
Status.

C. n = 12 in 49 seconds by @Fors
Java. n = 16 in 3:07 by @PeterTaylor
C++. n = 16 in 2:21 by @ilmale
Rpython. n = 22 in 3:11 by @primo
Java. n = 22 in 6:56 by @PeterTaylor
Nimrod. n = 24 in 9:28 seconds by @ReimerBehrends

The winner was Reimer  Behrends with an entry in Nimrod!
As a check, the output for n = 22 should be [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680].

The competition is now over but... I will offer 200 points for every submission that increases  n by 2 (within 10 minutes on my computer) until I run out of points. This offer is open forever.

"I reserve the right not to test code that takes more than a few minutes." > You should specify an exact time on your machine, otherwise this question will lack an objective winning criterion.

I love these "increase my speed" challenges. If you are building a commercial product with these, you are going to have one hell of a fast product, and you are also an evil genius.

@Rusher I 100% promise I am not going to make 1 cent from any of this. I just like series of questions of increasing difficulty! It somehow reminds me of Bruce Lee movies :)

@Rusher Technically, unless you have permission from the poster, you cannot use these codes commercially, as they are licensed under CC-By-SA. But if your product is closed-source, it's not like anyone would know...

Perhaps a more informative title would draw attention to this?

@TheDoctor Good point but do you have any suggestions? I am not good at titles.

How about "Optimize this algorithm for larger inputs"? I'm not really sure what it does.

@TheDoctor Thank you. Is there any part of the code I can explain?

As a sanity check for claims that are large enough to be hard to check with another implementation, the first item should be 2^(2n) n! / ((n/2)!^2)

If we keep doing this sort of challenge, I think we should at least attempt to solve a different problem to keep it interesting (not a variation on the same problem with extra specifications).

@grovesNL Yes this is the last challenge on this theme. However I would argue it's great to have a few of increasing difficulty so people can use the hard work they have put into previous challenges.

What is the purpose of m? Is the list S just 2n long, and leadingzerocounts just n+1 length?

@qwr  Yes that is right.

@Lembik So are we calculating dot products? Because the lists are of unequal length

@qwr S is longer than F which is why the dot products are of the form F, S[i:i+n]. That is, F with a window of S of length n.

@ace Technically and practically, CC-BY-SA does allow commercial use. It just requires attribution and sharing of source code. CC-BY-NC-SA (NC=non-commercial) would exclude money making.

8-core means you have 8 physical cores? Or is it 4-core with hyperthreading = 8 virtual cores? Or is it 8-core with hyperthreading for 16 virtual cores?

@Claudiu It's this CPU http://techreport.com/review/23750/amd-fx-8350-processor-reviewed .

@Claudiu his CPU has 8 physical cores, but the fetch/decode and FPU units are shared between cores. So when the bottleneck is on one of those areas, it behaves more like an quadcore. Abuse integer logic and avoid large code sizes and it's more like an 8-core.

@Lembik Each additional bounty you grant will need to be at least twice the previous one (up until 500, of course).

@primo :) I would run out of points too quickly.

@Lembik No, I mean, it's not a suggestion. Click the start a bounty button again. I will require you to give at least 200 rep, because you previously granted one for 100.

Nimrod (N=22)
import math, locks

const
  N = 20
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, int]
  ComputeThread = TThread[int]

var
  leadingZeros: ZeroCounter
  lock: TLock
  innerProductTable: array[0..FMax, int8]

proc initInnerProductTable =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)

initInnerProductTable()

proc zeroInnerProduct(i: int): bool =
  innerProductTable[i] == 0

proc search2(lz: var ZeroCounter, s, f, i: int) =
  if zeroInnerProduct(s xor f) and i < M:
    lz[i] += 1 shl (M - i - 1)
    search2(lz, (s shr 1) + 0, f, i+1)
    search2(lz, (s shr 1) + SStep, f, i+1)

when defined(gcc):
  const
    unrollDepth = 1
else:
  const
    unrollDepth = 4

template search(lz: var ZeroCounter, s, f, i: int) =
  when i < unrollDepth:
    if zeroInnerProduct(s xor f) and i < M:
      lz[i] += 1 shl (M - i - 1)
      search(lz, (s shr 1) + 0, f, i+1)
      search(lz, (s shr 1) + SStep, f, i+1)
  else:
    search2(lz, s, f, i)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for f in countup(base, FMax div 2, numThreads):
    for s in 0..FMax:
      search(lz, s, f, 0)
  acquire(lock)
  for i in 0..M-1:
    leadingZeros[i] += lz[i]*2
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

Compile with
nimrod cc --threads:on -d:release count.nim

(Nimrod can be downloaded here.)
This runs in the allotted time for n=20 (and for n=18 when only using a single thread, taking about 2 minutes in the latter case).
The algorithm uses a recursive search, pruning the search tree whenever a non-zero inner product is encountered. We also cut the search space in half by observing that for any pair of vectors (F, -F) we only need to consider one because the other produces the exact same sets of inner products (by negating S also).
The implementation uses Nimrod's metaprogramming facilities to unroll/inline the first few levels of the recursive search. This saves a little time when using gcc 4.8 and 4.9 as the backend of Nimrod and a fair amount for clang.
The search space could be further pruned by observing that we only need to consider values of S that differ in an even number of the first N positions from our choice of F. However, the complexity or memory needs of that do not scale for large values of N, given that the loop body is completely skipped in those cases.
Tabulating where the inner product is zero appears to be faster than using any bit counting functionality in the loop. Apparently accessing the table has pretty good locality.
It looks as though the problem should be amenable to dynamic programming, considering how the recursive search works, but there is no apparent way to do that with a reasonable amount of memory.
Example outputs:
N=16:
@[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]

N=18:
@[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

N=20:
@[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

For purposes of comparing the algorithm with other implementations, N=16 takes about 7.9 seconds on my machine when using a single thread and 2.3 seconds when using four cores.
N=22 takes about 15 minutes on a 64-core machine with gcc 4.4.6 as Nimrod's backend and overflows 64-bit integers in leadingZeros[0] (possibly not unsigned ones, haven't looked at it).

Update: I've found room for a couple more improvements. First, for a given value of F, we can enumerate the first 16 entries of the corresponding S vectors precisely, because they must differ in exactly N/2 places. So we precompute a list of bit vectors of size N that have N/2 bits set and use these to derive the initial part of S from F.
Second, we can improve upon the recursive search by observing that we always know the value of F[N] (as the MSB is zero in the bit representation). This allows us to predict precisely which branch we recurse into from the inner product. While that would actually allow us to turn the entire search into a recursive loop, that actually happens to screw up branch prediction quite a bit, so we keep the top levels in its original form. We still save some time, primarily by reducing the amount of branching we are doing.
For some cleanup, the code is now using unsigned integers and fix them at 64-bit (just in case someone wants to run this on a 32-bit architecture).
Overall speedup is between a factor of x3 and x4. N = 22 still needs more than eight cores to run in under 10 minutes, but on a 64-core machine it's now down to about four minutes (with numThreads bumped up accordingly). I don't think there's much more room for improvement without a different algorithm, though.
N=22:
@[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

Updated again, making use of further possible reductions in search space. Runs in about 9:49 minutes for N=22 on my quadcore machine.
Final update (I think). Better equivalence classes for choices of F, cutting runtime for N=22 down to 3:19 minutes 57 seconds (edit: I had accidentally run that with only one thread) on my machine.
This change makes use of the fact that a pair of vectors produces the same leading zeros if one can be transformed into the other by rotating it. Unfortunately, a fairly critical low-level optimization requires that the top bit of F in the bit representation is always the same, and while using this equivalence slashed the search space quite a bit and reduced runtime by about one quarter over using a different state space reduction on F, the overhead from eliminating the low-level optimization more than offset it. However, it turns out that this problem can be eliminated by also considering the fact that F that are inverses of one another are also equivalent. While this added to the complexity of the calculation of the equivalence classes a bit, it also allowed me to retain the aforementioned low-level optimization, leading to a speedup of about x3.
One more update to support 128-bit integers for the accumulated data. To compile with 128 bit integers, you'll need longint.nim from here and to compile with -d:use128bit. N=24 still takes more than 10 minutes, but I've included the result below for those interested.
N=24:
@[761152247121980686336, 122682715414070296576, 19793870419291799552, 3193295704340561920, 515628872377565184, 83289931274780672, 13484616786640896, 2191103969198080, 359662314586112, 60521536552960, 10893677035520, 2293940617216, 631498735616, 230983794688, 102068682752, 48748969984, 23993655296, 11932487680, 5955725312, 2975736832, 1487591936, 743737600, 371864192, 185931328, 92965664]

import math, locks, unsigned

when defined(use128bit):
  import longint
else:
  type int128 = uint64 # Fallback on unsupported architectures
  template toInt128(x: expr): expr = uint64(x)

const
  N = 22
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, uint64]
  ZeroCounterLong = array[0..M-1, int128]
  ComputeThread = TThread[int]
  Pair = tuple[value, weight: int32]

var
  leadingZeros: ZeroCounterLong
  lock: TLock
  innerProductTable: array[0..FMax, int8]
  zeroInnerProductList = newSeq[int32]()
  equiv: array[0..FMax, int32]
  fTable = newSeq[Pair]()

proc initInnerProductTables =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)
    if innerProductTable[i] == 0:
      if (i and 1) == 0:
        add(zeroInnerProductList, int32(i))

initInnerProductTables()

proc ror1(x: int): int {.inline.} =
  ((x shr 1) or (x shl (N-1))) and FMax

proc initEquivClasses =
  add(fTable, (0'i32, 1'i32))
  for i in 1..FMax:
    var r = i
    var found = false
    block loop:
      for j in 0..N-1:
        for m in [0, FMax]:
          if equiv[r xor m] != 0:
            fTable[equiv[r xor m]-1].weight += 1
            found = true
            break loop
        r = ror1(r)
    if not found:
      equiv[i] = int32(len(fTable)+1)
      add(fTable, (int32(i), 1'i32))

initEquivClasses()

when defined(gcc):
  const unrollDepth = 4
else:
  const unrollDepth = 4

proc search2(lz: var ZeroCounter, s0, f, w: int) =
  var s = s0
  for i in unrollDepth..M-1:
    lz[i] = lz[i] + uint64(w)
    s = s shr 1
    case innerProductTable[s xor f]
    of 0:
      # s = s + 0
    of -1:
      s = s + SStep
    else:
      return

template search(lz: var ZeroCounter, s, f, w, i: int) =
  when i < unrollDepth:
    lz[i] = lz[i] + uint64(w)
    if i < M-1:
      let s2 = s shr 1
      case innerProductTable[s2 xor f]
      of 0:
        search(lz, s2 + 0, f, w, i+1)
      of -1:
        search(lz, s2 + SStep, f, w, i+1)
      else:
        discard
  else:
    search2(lz, s, f, w)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for fi in countup(base, len(fTable)-1, numThreads):
    let (fp, w) = fTable[fi]
    let f = if (fp and (FSize div 2)) == 0: fp else: fp xor FMax
    for sp in zeroInnerProductList:
      let s = f xor sp
      search(lz, s, f, w, 0)
  acquire(lock)
  for i in 0..M-1:
    let t = lz[i].toInt128 shl (M-i).toInt128
    leadingZeros[i] = leadingZeros[i] + t
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

The result with N=22 is 12410090985684467712 which takes 63.42 bits and thus fits into an unsigned 64-bit.

You have definitely raised the bar very impressively.

Good to see somebody using Nimrod. :)

@Stefan Maybe your coding wizardry could get this method below 10 minutes for N=22?

I tried N= 22 which did terminate after a few hours. However it gives me [-6036653088025083904, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680] which seems to be an overflow error.  I know no nimrod but is it possible to use unsigned ints to solve this?

@PeterTaylor I am on a 64 bit system which might help. Are you really on a 32 bit system?

@PeterTaylor I just checked and I think ReimerBehrends' answers for n = 18 are right.

@Lembik, yes, I found another place where I was using 32-bit integers not expecting them to overflow.

N=22 is only 29 minutes on my machine with this new code.

It turns out that I can cut the search space by a factor of 4 with very little coding effort and get a 4x speedup in the process. It's a bit tricky to prove that it's still correct, though. Basically, both the numbers of F and S vectors you have to consider can be cut in half. That's easy to show for S, but the F case is non-trivial (though the results are obviously correct).

@ReimerBehrends The same symmetries I exploit. If you've found a vector pair S, F with S[0]=1, S[1]=1, and F[0]=1, you've actually found 3 more (S[0]=-1, S[1]=1, F[0]=-1), (S[0]=1, S[1]=-1, F[0]=-1), (S[0]=-1, S[1]=-1, F[0]=1), and the inverses of all of these for a total of 8. Because each of these has a -1 in at least one of these three positions, the search space can be limited so that these are never encountered, and instead counting each vector pair found as 8.

n = 22 in 6:48!

I assume you mean numThreads = 16 ?

It seems to take 27 seconds?!  Do I need to change anything apart from N to try N = 24 in terms of avoiding overflows?

Yeah, I had accidentally run it with only 1 thread to see how fast it was, so it's actually a bit faster than the 3:19 minutes I had noted. For N>=24, I have to rewrite the code a bit to avoid overflow when accumulating the result. I'll look at that.

@Lembik, now you see why I tried to avoid explaining my method in much detail. :P

@PeterTaylor: Huh?

Your new equivalence classes are the same as mine.

You have raised the bar to N = 24.  Well done! (See new timings in question.)

@PeterTaylor: I'll take your word for it, but I didn't look at your answer and I didn't have to. Tip: Once you print out the F's as bit sequences, grouping together those values that generate the same sets of leading zeros (for small N, i.e. <= 10), there is a rather obvious pattern.

The smiley was to indicate that I wasn't being entirely serious.

Java (n=22?)
I think most of the answers which do better than n=16 use a similar approach to this, although they differ in the symmetries they exploit and the way they divide the task between threads.
The vectors defined in the question can be replaced with bit strings, and the inner product with XORing the overlapping window and checking that there are exactly n/2 bits set (and hence n/2 bits cleared). There are n! / ((n/2)!) (central binomial coefficient) strings of n bits with n/2 bits set (which I call balanced strings), so for any given F there are that many windows of S which give a zero inner product. Moreover, the action of sliding S along one and checking whether we can still find an incoming bit which gives a zero inner product corresponds to looking for an edge in a graph whose nodes are the windows and whose edges link a node u to a node v whose first n-1 bits are the last n-1 bits of u.
For example, with n=6 and F=001001 we get this graph:

and for F=001011 we get this graph:

Then we need to count for each i from 0 to n how many paths of length i there are, summing over the graphs for every F. I think most of us are using depth-first search.
Note that the graphs are sparse: it's easy to prove that each node has in-degree of at most 1 and out-degree of at most one. That also means that the only structures possible are simple chains and simple loops. This simplifies the DFS a bit.
I exploit a couple of symmetries: the balanced strings are closed under bit inverse (the ~ operation in many languages from the ALGOL family), and under bit rotation, so we can group together values of F which are related by these operations and only do the DFS once.
public class CodeGolf26459v8D implements Runnable {
    private static final int NUM_THREADS = 8;

    public static void main(String[] args) {
        v8D(22);
    }

    private static void v8D(int n) {
        int[] bk = new int[1 << n];
        int off = 0;
        for (int i = 0; i < bk.length; i++) {
            bk[i] = Integer.bitCount(i) == n/2 ? off++ : -1;
        }

        int[] fwd = new int[off];
        for (int i = 0; i < bk.length; i++) {
            if (bk[i] >= 0) fwd[bk[i]] = i;
        }

        CodeGolf26459v8D[] runners = new CodeGolf26459v8D[NUM_THREADS];
        Thread[] threads = new Thread[runners.length];
        for (int i = 0; i < runners.length; i++) {
            runners[i] = new CodeGolf26459v8D(n, i, runners.length, bk, fwd);
            threads[i] = new Thread(runners[i]);
            threads[i].start();
        }

        try {
            for (int i = 0; i < threads.length; i++) threads[i].join();
        }
        catch (InterruptedException ie) {
            throw new RuntimeException("This shouldn't be reachable", ie);
        }

        long surviving = ((long)fwd.length) << (n - 1);
        for (int i = 0; i <= n; i++) {
            for (CodeGolf26459v8D runner : runners) surviving -= runner.survival[i];
            System.out.print(i == 0 ? "[" : ", ");
            java.math.BigInteger result = new java.math.BigInteger(Long.toString(surviving));
            System.out.print(result.shiftLeft(n + 1 - i));
        }
        System.out.println("]");
    }

    public final int n;
    protected final int id;
    protected final int numRunners;
    private final int[] bk;
    private final int[] fwd;

    public long[] survival;

    public CodeGolf26459v8D(int n, int id, int numRunners, int[] bk, int[] fwd) {
        this.n = n;
        this.id = id;
        this.numRunners = numRunners;

        this.bk = bk;
        this.fwd = fwd;
    }

    private int dfs2(int[] graphShape, int flip, int i) {
        if (graphShape[i] != 0) return graphShape[i];

        int succ = flip ^ (fwd[i] << 1);
        if (succ >= bk.length) succ ^= bk.length + 1;

        int j = bk[succ];
        if (j == -1) return graphShape[i] = 1;

        graphShape[i] = n + 1; // To detect cycles
        return graphShape[i] = dfs2(graphShape, flip, j) + 1;
    }

    @Override
    public void run() {
        int n = this.n;
        int[] bk = this.bk;
        int[] fwd = this.fwd;

        // NB The initial count is approx 2^(2n - 1.33 - 0.5 lg n)
        // For n=18 we overflow 32-bit
        // 64-bit is good up to n=32.
        long[] survival = new long[n + 1];
        boolean[] visited = new boolean[1 << (n - 1)];
        int th = 0;
        for (int f = 0; f < visited.length; f++) {
            if (visited[f]) continue;

            int m = 1, g = f;
            while (true) {
                visited[g] = true;
                int ng = g << 1;
                if ((ng >> (n - 1)) != 0) ng ^= (1 << n) - 1;
                if (ng == f) break;
                m++;
                g = ng;
            }

            if (th++ % numRunners != id) continue;

            int[] graphShape = new int[fwd.length];
            int flip = (f << 1) ^ f;
            for (int i = 0; i < graphShape.length; i++) {
                int life = dfs2(graphShape, flip, i);
                if (life <= n) survival[life] += m;
            }
        }

        this.survival = survival;
    }
}

On my 2.5GHz Core 2 I get
# n=18
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

real    0m3.131s
user    0m10.133s
sys     0m0.380s

# n=20
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

real    1m8.706s
user    4m20.980s
sys     0m0.564s

# n=22
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

real    20m10.654s
user    76m53.880s
sys     0m6.852s

Since Lembik's computer has 8 cores and executed my earlier single-threaded program twice as fast as mine, I'm optimistic that it will execute n=22 in less than 8 minutes.

7:17! Very nice. Would you mind explaining your method a little more?

C
It is basically just a slightly optimised implementation of the algorithm in the question. It can manage n=12 within the time limit.
#include <stdio.h>
#include <inttypes.h>

#define n 12
#define m (n + 1)

int main() {
    int i;
    uint64_t S, F, o[m] = {0};
    for (S = 0; S < (1LLU << (n + m - 1)); S += 2)
        for (F = 0; F < (1 << (n - 1)); F++)
            for (i = 0; i < m; i++)
                if (__builtin_popcount(((S >> i) & ((1 << n) - 1)) ^ F) == n >> 1)
                    o[i] += 4;
                else
                    break;
    for (i = 0; i < m; i++)
        printf("%" PRIu64 " ", o[i]);
    return 0;
}

Test run for n=12, including compilation:
$ clang -O3 -march=native -fstrict-aliasing -ftree-vectorize -Wall fast.c
$ time ./a.out
15502147584 3497066496 792854528 179535872 41181184 9826304 2603008 883712 381952 177920 85504 42560 21280
real    0m53.266s
user    0m53.042s
sys     0m0.068s
$

Comment: I just turned my brain on and used some simple combinatorics to calculate that the first value will always be n! / ((n / 2)!)^2 * 2^(n + m - 1). It seems to me that there must be a completely algebraic solution to this problem.

I get lots of warnings when I compile this. Try gcc -Wall -Wextra Fors.c -o Fors

There were a couple of unused variables forgotten from an earlier iteration, but I removed them so at least a couple of warnings should have disappeared.
I don't have GCC available at the moment (only Clang), and Clang doesn't give me any warnings at the moment (after removing the unused variables). And as Clang usually is more strict when it comes to warnings I must say I'm a bit surprised that you got any warnings at all.

It complains about Fors.c:13:17: warning: suggest parentheses around ‘-’ in operand of ‘&’ [-Wparentheses] (twice) and also warning: format ‘%llu’ expects argument of type ‘long long unsigned int’, but argument 2 has type ‘uint64_t’ [-Wformat=]  . In fact clang complains about the printf statement too  for me,

With the latest changes GCC shouldn't throw any warning messages.

It still complains about Fors.c:13:49: warning: suggest parentheses around arithmetic in operand of ‘^’ [-Wparentheses]
But in worse news... it takes longer than 10 minutes on my machine.

I guess GCC doesn't trust that the programmer knows the order of precedence in C.
What flags did you compile it with? I compiled it with -O3, which should be enough. With no optimisation flags at all I understand that it would take more than ten minutes.

gcc -Wall -Wextra -O3 Fors.c -o Fors . It also takes more than 10 minutes when compiled with clang -O3 Fors.c  -o Forsclang

There's an easy speed-up by 4 exploiting symmetry.

You may try gcc -O3 -march=native -fwhole-program -fstrict-aliasing -ftree-vectorize -Wall Fors.c -o Fors, but I don't know whether it will work.

I just reran it and it took just over 5 minutes and 50 seconds. My LLVM version is 5.1, the OS is OS X and the CPU is a 2.5 GHz Intel Core i5 processor. I see no reason to why it runs so much slower on your machine, except potentially an older compiler.
I think I see the speed-up Peter Taylor.

Thanks. It is much faster with your gcc command line it turns out than using clang -O3 on my system.  I was using  3.4-1ubuntu3 (tags/RELEASE_34/final) (based on LLVM 3.4) before.

Java, n=16
For any given value of F there are \binom{n}{n/2} vectors which have a zero inner product with it. So we can build a graph whose vertices are those matching vectors and whose edges correspond to the shifting of S, and then we just need to count paths of length up to n in the graph.
I haven't tried microoptimising this by replacing conditionals with bitwise operations, but each double-increment of n increases running time about 16-fold, so that's not going to make enough of a difference unless I'm pretty close to the threshold. On my machine, I'm not.
public class CodeGolf26459 {

    public static void main(String[] args) {
        v3(16);
    }

    // Order of 2^(2n-1) * n ops
    private static void v3(int n) {
        long[] counts = new long[n+1];
        int mask = (1 << n) - 1;
        for (int f = 0; f < (1 << (n-1)); f++) {
            // Find adjacencies
            long[] subcounts = new long[1 << n];
            for (int g = 0; g < (1 << n); g++) {
                subcounts[g] = Integer.bitCount(f ^ g) == n/2 ? 2 : -1;
            }

            for (int round = 0; round <= n; round++) {
                long count = 0;
                // Extend one bit.
                long[] next = new long[1 << n];
                for (int i = 0; i < (1 << n); i++) {
                    long s = subcounts[i];
                    if (s == -1) next[i] = -1;
                    else {
                        count += s;
                        int j = (i << 1) & mask;
                        if (subcounts[j] >= 0) next[j] += s;
                        if (subcounts[j + 1] >= 0) next[j + 1] += s;
                    }
                }
                counts[round] += count << (n - round);
                subcounts = next;
            }
        }

        System.out.print("[");
        for (long count : counts) System.out.print(count+", ");
        System.out.println("]");
    }
}

On my 2.5GHz Core 2 I get
$ javac CodeGolf26459.java && time java -server CodeGolf26459
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600, ]

real    6m2.663s
user    6m4.631s
sys     0m1.580s

Piggybacking since I don't want to implement my own solution right now. Each vertex has at most one successor, so you don't really need the array. To iterate efficiently over combinations of f and starting vertices, iterate over all f_xor_g with exactly n/2 set bits. For each of these, iterate over all f and take g = f ^ f_xor_g.

@David, I know, and my version 7 does n=18 in one minute on my Atom netbook, but I can't post it until I get back from holiday.

RPython, N=22 ~3:23
Multi-threaded, using a stackless recursive descent. The program accepts two command line arguments: N, and the number of worker threads.
from time import sleep

from rpython.rlib.rthread import start_new_thread, allocate_lock
from rpython.rlib.rarithmetic import r_int64, build_int, widen
from rpython.rlib.rbigint import rbigint

r_int8 = build_int('r_char', True, 8)

class ThreadEnv:
  __slots__ = ['n', 'counts', 'num_threads',
               'v_range', 'v_num', 'running', 'lock']

  def __init__(self):
    self.n = 0
    self.counts = [rbigint.fromint(0)]
    self.num_threads = 0
    self.v_range = [0]
    self.v_num = 0
    self.running = 0
    self.lock = None

env = ThreadEnv()

bt_bits = 12
bt_mask = (1<<bt_bits)-1
# computed compile time
bit_table = [r_int8(0)]
for i in xrange(1,1<<bt_bits):
  bit_table += [((i&1)<<1) + bit_table[i>>1]]

def main(argv):
  argc = len(argv)
  if argc < 2 or argc > 3:
    print 'Usage: %s N [NUM_THREADS=2]'%argv[0]
    return 1

  if argc == 3:
    env.num_threads = int(argv[2])
  else:
    env.num_threads = 2

  env.n = int(argv[1])
  env.counts = [rbigint.fromint(0)]*env.n
  env.lock = allocate_lock()

  v_range = []
  v_max = 1<<(env.n-1)
  v_num = 0
  v = (1<<(env.n>>1))-1
  while v < v_max:
    v_num += 1
    v_range += [v]
    if v&1:
      # special case odd v
      s = (v+1)&-v
      v ^= s|(s>>1)
    else:
      s = v&-v
      r = v+s
      # s is at least 2, skip two iterations
      i = 3
      s >>= 2
      while s:
        i += 1
        s >>= 1
      v = r|((v^r)>>i)
  env.v_range = v_range
  env.v_num = v_num

  for i in xrange(env.num_threads-1):
    start_new_thread(run,())

  # use the main process as a worker
  run()

  # wait for any laggers
  while env.running:
    sleep(0.05)

  result = []
  for i in range(env.n):
    result += [env.counts[i].lshift(env.n-i+3).str()]
  result += [env.counts[env.n-1].lshift(3).str()]
  print result
  return 0

def run():
  with env.lock:
    v_start = env.running
    env.running += 1

  n = env.n
  counts = [r_int64(0)]*n
  mask = (1<<n)-1
  v_range = env.v_range
  v_num = env.v_num
  z_count = 1<<(n-2)

  for i in xrange(v_start, v_num, env.num_threads):
    v = v_range[i]
    counts[0] += z_count
    counts[1] += v_num
    r = v^(v<<1)
    for w in v_range:
      # unroll counts[2] for speed
      # ideally, we could loop over x directly,
      # rather than over all v, only to throw the majority away
      # there's a 2x-3x speed improvement to be had here...
      x = w^r
      if widen(bit_table[x>>bt_bits]) + widen(bit_table[x&bt_mask]) == n:
        counts[2] += 1
        x, y = v, x
        o, k = 2, 3
        while k < n:
          # x = F ^ S
          # y = F ^ (S<<1)
          o = k
          z = (((x^y)<<1)^y)&mask
          # z is now F ^ (S<<2), possibly xor 1
          # what S and F actually are is of no consequence

          # the compiler hint `widen` let's the translator know
          # to store the result as a native int, rather than a signed char
          bt_high = widen(bit_table[z>>bt_bits])
          if bt_high + widen(bit_table[z&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z
            k += 1
          elif bt_high + widen(bit_table[(z^1)&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z^1
            k += 1
          else: k = n

  with env.lock:
    for i in xrange(n):
      env.counts[i] = env.counts[i].add(rbigint.fromrarith_int(counts[i]))
    env.running -= 1

def target(*args):
  return main, None

To Compile
Make a local clone of the PyPy repository using mercurial, git, or whatever you prefer. Type the following incantation (assuming the above script is named convolution-high.py):
$ pypy %PYPY_REPO%/rpython/bin/rpython --thread convolution-high.py

where %PYPY_REPO% represents an environment variable pointing to the repository you just cloned. Compilation takes about one minute.

Sample Timings
N=16, 4 threads:
$ timeit convolution-high-c 16 4
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]
Elapsed Time:     0:00:00.109
Process Time:     0:00:00.390

N=18, 4 threads:
$ timeit convolution-high-c 18 4
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]
Elapsed Time:     0:00:01.250
Process Time:     0:00:04.937

N=20, 4 threads:
$ timeit convolution-high-c 20 4
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]
Elapsed Time:     0:00:15.531
Process Time:     0:01:01.328

N=22, 4 threads:
$ timeit convolution-high-c 22 4
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]
Elapsed Time:     0:03:23.156
Process Time:     0:13:25.437

9:26. Welcome to the 22 crew :)

I am not sure why but your new version is no faster for me. Still about 9:30 when I do time ./primo-c 22 8 .

@Lembik that would make sense if division were about as fast on average as 3 right shifts (3=Sum{(n+1)/(2^n)},n=1..infty). For certian architectures, I suppose that might be the case, but on mine division is noticably slower. Thanks for taking the time to test it :)

Python 3.3, N = 20, 3.5min
Disclaimer: my intention is NOT to post this as my own answer, since the algorithm I'm using is only a shameless port from primo's RPython solution. My purpose here is only to show what you can do in Python if you combine the magic of Numpy and Numba modules.
Numba explained in short:

Numba is an just-in-time specializing compiler which compiles annotated Python and NumPy code to LLVM (through decorators). http://numba.pydata.org/

Update 1: I noticed after tossing the numbers around that we can simply skip some of the numbers completely. So now maxf becomes (1 << n) // 2 and maxs becomes maxf2**. This will speed up the process quite a bit. n = 16 now takes only ~48s (down from 4,5min). I also have another idea which I'm going to try and see if I can make it go a little faster.
Update 2: Changed algorithm (primo's solution). While my port does not yet support multithreading it is pretty trivial to add. It is even possible to release CPython GIL using Numba and ctypes. This solution, however, runs very fast on single core too!
import numpy as np
import numba as nb

bt_bits = 11
bt_mask = (1 << bt_bits) - 1
bit_table = np.zeros(1 << bt_bits, np.int32)

for i in range(0, 1 << bt_bits):
    bit_table[i] = ((i & 1) << 1) + bit_table[i >> 1]

@nb.njit("void(int32, int32, int32, int32, int64[:], int64[:])")
def run(n, m, start, re, counts, result):
    mask = (1 << n) - 1

    v_max = (1 << n) // 2
    rr = v_max // 2

    v = (1 << (n >> 1)) - 1
    while v < v_max:
        s = start

        while s < rr:
            f = v ^ s
            counts[0] += 8
            t = s << 1
            o, j = 0, 1

            while o < j and j < m:
                o = j
                w = (t ^ f) & mask
                bt_high = bit_table[w >> bt_bits]

                if bt_high + bit_table[w & bt_mask] == n:
                    counts[j] += 8
                    t <<= 1
                    j += 1
                elif bt_high + bit_table[(w ^ 1) & bt_mask] == n:
                    counts[j] += 8
                    t = (t | 1) << 1
                    j += 1
                    s += re

            s = v & -v
            r = v + s
            o = v ^ r
            o = (o >> 2) // s
            v = r | o

    for e in range(m):
        result[e] += counts[e] << (n - e)

And finally:
if __name__ == "__main__":
    n = 20
    m = n + 1

    result = np.zeros(m, np.int64)
    counts = np.zeros(m, np.int64)

    s1 = time.time() * 1000
    run(n, m, 0, 1, counts, result)
    s2 = time.time() * 1000

    print(result)
    print("{0}ms".format(s2 - s1))

This runs on my machine in 212688ms or ~3.5min.

Thanks. Now how about n = 18 ? :)

It has been almost 20min since I started the program using n = 18. I think it is safe to say that Python can't solve this even with Numba on time using this particular algorithm.

I am optimistic that a better algorithm exists.

I tried pip install numba but it says it can't find llvmpy. I tried sudo pip install llvmpy but it says it can't find versioneer. I tried sudo pip install versioneer but it says I already have it.

Although I haven't got numba to work yet (I think I will have to install anaconda in the end) I am impressed by this. The question is, can you get it to solve N=22 using a similar method to the nimrod one?

Behrends' solutions is very clever! I could try to port it to Python and use Numba to see how fast it would run. Surprisingly Numba version runs much faster than the equivalent Lisp and C# versions on my machine. I'm currently working on an another type of a solution for this problem. It ALMOST works, but not quite yet =P

@AnnaJokela I think the translation may not be correct. s += re should be shifted two indentations to the left, and the block s = v & -v ... v = r | o should be shifted one indentation to the left. A few other notes, counts[j] += 1 is compiler optimized as counts[j]++, which is why I add 1 instead of 8, and shift an extra 3 at the end. When cycling through all values with the same bit count, odd v can be special cased: find the first 0 bit, flip that bit and the one preceeding it.

@AnnaJokela I've modified your code a bit to satisfy my own curiosity: http://codepad.org/Y2rOQF77 Timings for n=14: CPython+Numpy+Numba - 78ms; PyPy - 375ms; CPython - 10.531s; CPython+Numpy - 36.203s. I'm impressed. Numba is 5x faster than PyPy (which was already 28x faster than CPython). And it's very nearly as fast as compiled RPython when single-threaded (for n=18: 15.453s vs. 14.687s).

Looks like Reimer Behrends' latest method is the one to copy!

It sure looks like it. I have to admit that the solution I was working on wasn't even half as good as his. I must tip a hat for him and his brains!

C++ N=16
I'm testing on a EEEPC with an atom.. my time don't make a lot of sense. :D
The atom solve n=14 in 34 seconds. And n=16 in 20 minutes. I want to test n = 16 on OP pc. I'm optimistic.
The ideas is that every time we find a solution for a given F we have found 2^i solution because we can change the lower part of S leading to the same result.
#include <stdio.h>
#include <cinttypes>
#include <cstring>

int main()
{
   const int n = 16;
   const int m = n + 1;
   const uint64_t maxS = 1ULL << (2*n);
   const uint64_t maxF = 1ULL << n;
   const uint64_t mask = (1ULL << n)-1;
   uint64_t out[m]={0};
   uint64_t temp[m] = {0};
   for( uint64_t F = 0; F < maxF; ++F )
   {
      for( uint64_t S = 0; S < maxS; ++S )
      {
         int numSolution = 1;
         for( int i = n; i >= 0; --i )
         {
            const uint64_t window = S >> i;
            if( __builtin_popcount( mask & (window ^ F) ) == (n / 2) )
            {
               temp[i] += 1;
            } else {
               numSolution = 1 << i;
               S += numSolution - 1;
               break;
            }
         }
         for( int i = n; i >= 0; --i )
         {
            out[i] += temp[i]*numSolution;
            temp[i] = 0;
         }
      }
   }
   for( int i = n; i >= 0; --i )
   {
      uint64_t x = out[i];
      printf( "%lu ", x );
   }
   return 0;
}

to compile:
gcc 26459.cpp -std=c++11 -O3 -march=native -fstrict-aliasing -ftree-vectorize -Wall -pedantic -o 26459

This is great. I have some half-baked ideas in fact for how to solve it for larger n. Would you like to hear them or could that spoil the competition?

JAVASCRIPT n:12
In my computer it took 231.242 seconds. In the Demo I'm using webworkers to prevent freezing the browser. This sure can be further improved with parallel workers. I know JS don't stand a chance in this challenge but I did it for fun!
Click to run the online Demo
var n = 8;
var m = n + 1;
var o = [];
var popCount = function(bits) {
  var SK5  = 0x55555555,
      SK3  = 0x33333333,
      SKF0 = 0x0f0f0f0f,
      SKFF = 0xff00ff;

  bits -= (bits >> 1) & SK5;
  bits  = (bits & SK3) + ((bits >> 2) & SK3);
  bits  = (bits & SKF0) + ((bits >> 4) & SKF0);
  bits += bits >> 8;

  return (bits + (bits >> 15)) & 63;
};
for(var S = 0; S < (1 << n + m - 1); S += 2){
  for(var F = 0; F < (1 << n - 1); F += 1){
    for (var i = 0; i < m; i++){
      var c = popCount(((S >> i) & ((1 << n) - 1)) ^ F);
      if(c == n >> 1){
        if(!o[i]) o[i] = 0;
        o[i] += 4;
      } else break;
    }
  }
}
return o;

What about one of those new(ish) fast javascript engines?  Could those be used?

You mean something like dart?

Actually I am wrong. You might as well just try both firefox and chromium.  Unless you want to write it in asm.js of course :)

challenge accepted ... gonna do it!

Tried this and took my computer 5.4 seconds to do n=22
[235388928,86292480,19031048,5020640,1657928,783920,545408,481256,463832,460256,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744]
http://i.imgur.com/FIJa2Ch.png

omg ...what machine are you using? I want one!

@Spedwards That's the wrong answer for n = 22. See the question for the correct output.

Rust
Port of @ilmale's C++ answer in Rust.
Try it online!
src/main.rs
fn main() {
    const N: u64 = 8;
    const M: usize = (N + 1) as usize;
    const MAX_S: u64 = 1 << (2 * N);
    const MAX_F: u64 = 1 << N;
    const MASK: u64 = (1 << N) - 1;

    let mut out = [0; M];
    let mut temp = [0; M];

    for f in 0..MAX_F {
        let mut s = 0;
        while s < MAX_S {
            let mut num_solution = 1;
            for i in (0..=N).rev() {
                let window = s >> i;
                if (MASK & (window ^ f)).count_ones() == (N / 2) as u32 {
                    temp[i as usize] += 1;
                } else {
                    num_solution = 1 << i;
                    s += num_solution - 1;
                    break;
                }
            }
            for i in (0..=N).rev() {
                out[i as usize] += temp[i as usize] * num_solution;
                temp[i as usize] = 0;
            }
            s += 1;
        }
    }

    for i in (0..=N).rev() {
        let x = out[i as usize];
        print!("{} ", x);
    }
}

Build and running
# win10 environment

$ set Copt-level=3
$ set Clto=fat
$ set Ctarget-cpu=native
$ cargo build --release
$ cargo run --release

How high do you get with this?

Fortran: n=12
I just made a quick'n'dirty version in Fortran, no optimizations except OpenMP. It should squeeze in at just below 10 minutes for n=12 on the OPs machine, it takes 10:39 on my machine which is sligthly slower.
64-bit integers have a negative performance impact indeed; guess I would have to rethink the whole algorithm for this to be much faster. Don't know if I'm going to bother, I think I'll rather spend some time thinking up a good challenge that's more to my own tastes. If anyone else wants to take this and run with it, go ahead :)
program golf
use iso_fortran_env
implicit none
integer, parameter ::  n=12
integer :: F(n), S(2*n)
integer(int64) :: leadingzerocounts(n+1)
integer :: k
integer(int64) :: i,j,bindec,enc

leadingzerocounts=0

!$OMP parallel do private(i,enc,j,bindec,S,F,k) reduction(+:leadingzerocounts) schedule(dynamic)
do i=0,2**(2*n)-1
  enc=i
  ! Short loop to convert i into the array S with -1s and 1s
  do j=2*n,1,-1
    bindec=2**(j-1)
    if (enc-bindec .ge. 0) then
      S(j)=1
      enc=enc-bindec
    else
      S(j)=-1
    endif
  end do
  do j=0,2**(n)-1
    ! Convert j into the array F with -1s and 1s
    enc=j
    do k=n,1,-1
      bindec=2**(k-1)
      if (enc-bindec .ge. 0) then
        F(k)=1
        enc=enc-bindec
      else
        F(k)=-1
      endif
    end do
    ! Compute dot product
    do k=1,n+1
      if (dot_product(F,S(k:k+n-1)) /= 0) exit
      leadingzerocounts(k)=leadingzerocounts(k)+1
    end do
  end do
end do
!$OMP end parallel do

print *, leadingzerocounts

end

Lua: n = 16
Disclaimer: my intention is NOT to post this as my own answer, since the algorithm I'm using is shamelessly stolen from Anna Jokela's clever answer. which was shamelessly stolen from ilmale's clever answer.
Besides, it's not even valid - it has inaccuracies caused by floating point numbers (it would be better if Lua would support 64-bit integers). However, I'm still uploading it, just to show how fast this solution is. It's a dynamic programming language, and yet I can calculate n = 16 in reasonable time (1 minute on 800MHz CPU).
Run with LuaJIT, standard interpreter is too slow.
local bit = require "bit"
local band = bit.band
local bor = bit.bor
local bxor = bit.bxor
local lshift = bit.lshift
local rshift = bit.rshift

-- http://stackoverflow.com/a/11283689/736054
local function pop_count(w)
    local b1 = 1431655765
    local b2 = 858993459
    local b3 = 252645135
    local b7 = 63

    w = band(rshift(w, 1), b1) + band(w, b1)
    w = band(rshift(w, 2), b2) + band(w, b2)
    w = band(w + rshift(w, 4), b3)
    return band(rshift(w, 24) + rshift(w, 16) + rshift(w, 8) + w, b7)
end

local function gen_array(n, value)
    value = value or 0
    array = {}
    for i = 1, n do
        array[i] = value
    end
    return array
end

local n = 16
local u = math.floor(n / 2)
local m = n + 1
local maxf = math.floor(lshift(1, n) / 2)
local maxs = maxf ^ 2
local mask = lshift(1, n) - 1

local out = gen_array(m, 0)
local temp = gen_array(m, 0)

for f = 0, maxf do
    local s = 0
    while s <= maxs do
        local num_solution = 1

        for i = n, 0, -1 do
            if pop_count(band(mask, bxor(rshift(s, i), f))) == u then
                temp[i + 1] = temp[i + 1] + 8
            else
                num_solution = lshift(1, i)
                s = s + num_solution - 1
                break
            end
        end

        for i = 1, m do
            out[i] = out[i] + temp[i] * num_solution
            temp[i] = 0
        end

        s = s + 1
    end
end

for i = m, 1, -1 do
    print(out[i])
end

Thank you. I think recent lua versions use long long int which should be 64 bit on a 64 bit system. See "lua_integer" at http://www.lua.org/work/doc/manual.html .

@Lembik: Interesting. Either way, it's standard Lua (which already supports long long instead of double with a compilation setting), not LuaJIT.

I think I was just wrong in any case wrt luajit. One would need 5.3 which doesn't exist. The best advice lua people could give was "try 5.3-workx".

authors: Артём Матеуш


text:
Monopoly Compression
Given a string representing the current state of a game of Monopoly at the beginning of a player's turn, compress all the necessary data into the smallest output. Answers will be judged by output size and source size.
Note: There are many regional variations, but all references in this post to property names, etc, are based on this board.

Input:
Input will be given as a single ; separated string. This string is given to the program in whatever way is customary in your chosen language, whether that's stdin, arguments, etc.
The unformatted input looks like this:
numPlayers                     (1 to 8)
whose turn                     (0 to numPlayers-1)
for each player:
    bankrupt?                  (true/false)
    money                      (0 to 2^16-1)
    get-out-of-jail-free cards (0 to 2)
    position                   (0 to 39)
    jail turns                 (-1 to 2)
for 28 properties:
    owner                      (-1 to numPlayers-1)
    mortgaged?                 (true/false)
    improvement level          (0 to 5)
for 16 chance cards in deck:
    card index                 (-1 to 15)
for 16 community chest cards in deck:
    card index                 (-1 to 15)

An example formatted input is this:
3;1;false;1546;0;14;-1;false;7692;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

Taken bit by bit:
3;1;

There are 3 players, and it is player 1's turn (zero-indexed, so the second player)
Players
false;1546;0;14;-1;
false;7692;1;10;1;
true;

The first player:

is not bankrupt
has $1546 cash on hand
owns 0 get-out-of-jail-free cards
is on position 14 (Virginia Ave)
is not in jail

The second player is in jail, and has been for one turn. I'm not sure why, since he has a GOoJF card, but he's there.
The third player is bankrupt, and more information is neither required nor given.
Properties
1;false;1;
1;false;0;
0;true;0;
-1;false;0;
-1;false;0;
-1;false;0;
...

Properties are listed in order around the board, starting from Mediterranean and ending at Boardwalk. Properties that cannot be owned are not included in this list, so there will be a total of 28. Improvement level 0 means unimproved. Level 1 is one house, up to level 5 for a hotel. A -1 for owner means it is not owned by any player.
According to standard rules, a property that is mortgaged must be owned and must not be improved. A property that is improved must be owned and must not be mortgaged.
In addition, for a property to be improved, a player must own the entire color block. For the purposes of this game, we do not care if properties are being improved "evenly".
Note that these positions are not the same as the player positions given above. For instance, a player on the 5 position would be on Reading Railroad, which is the third property in the list (since Go, Community Chest, and Income Tax cannot be owned). Player positions run from 0(Go) clockwise to 39(Boardwalk).
Cards
0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;
3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

Each of the Chance and Community Chest decks have 16 total cards. The numbers are presented as they appear in the currently shuffled deck. For this example, the first card pulled off the Chance deck will be card 0, followed by card 1 (whoever shuffled that deck sucks). The first card pulled from Community chest is card 3, then 12.
Don't worry about what each card means (the card text), except for card 0. That is the Get Out of Jail Free card for that deck. If a player owns it, it will be at the end of the list, represented as -1.

Output:
You must output (to console, stdout, or file) a representation of the game state. This must include all information required to represent the game. For example, you could omit (or abbreviate) unowned properties, since they can neither be improved or mortgaged. The input cannot omit them because it is an unindexed list.
Compression should be done in a way that you can compute worst-case output size. This may disqualify certain compression algorithms (unless you can prove the worst case, and give an example of worst-case input).
Unless your source code is unreasonably verbose, give an explanation of how the game is represented. Answers consisting of nothing but a golfed program and compressed output are discouraged. For example, if you are omitting certain values, explain how it is possible to derive them from the output.

Scoring/Rules:
Scoring is based both on worst-case compression size in bits, and source code size in bytes:
score = (outputBits * 2) + encoderSourceBytes

A complete answer must include:

Output example
Encoder source
Decoder source (not counted against score)

All encoders must be complete programs, and standard loopholes are forbidden. Using built-in or external compression libraries is also forbidden.
The winner is the answer with the lowest score, as defined above.

Hm, why not require a decoder as well as a proof that the encoding actually works (and is revertible)? Also what about including stuff like built-in gzip compression? That would make it really hard to figure out the worst-case compression size.

@m.buettner Edited. I added a bit about compression libraries, and a bit about proof of worst-case. I don't really want to enforce a decoder. Posters can include them if they wish to prove their solution, but it won't be counted against the score.

Oh yeah, I wasn't suggesting to add them to the score. You could still require an (ungolfed) decoder as proof. That makes it easier to test whether submissions can handle special cases.

@m.buettner You make an excellent point. Decoders it is.

The second player is in jail, and has been for one turn. I'm not sure why, since he has a GOoJF card, but he's there. Being in jail is good lategame because you're not paying rent. :)

@undergroundmonorail Oh, I know, but only two properties are owned in this input. If this is late game, these are horrible players. In addition, one is bankrupt, so he must have been hit hard by the dice ;)

@Geobits Heh, I didn't bother going through the rest of the input. Fair enough. :P

Err, three are owned. I had one owned by a bankrupt player and one improved without matching properties. Fixed to make input legal.

Does the output have match the input exactly or could changes be made that do not actually affect the state of the game? (e.g. moving bankrupt players to the end of the list wouldn't really matter since their not part of turns any longer)

@m.buettner No, it doesn't have to exactly match. However, I'd hesitate to swap players unless you can show which player was originally in what position. You should be able to match it up to a player list (0->Alice,1->Bob,2->Charlie).

@Geobits that does make sense.

(An answer was recently edited, which brought this question to my attention, and I decided to give it a try although its an old question.)
Swift 1.2 - 1016 Points (2*81 + 854)
The output is at worst 81 bytes, and changes with the amount of players.
Either of the two methods work. The Playground version is slightly longer.
Compress Playground
(Assumes Input.txt is in the Playground Documents Directory)
// Compressor e(inputFileName, outputFileName)
import Cocoa;typealias S=String;typealias U=UInt8;func e(a:S,b:S){var d=NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask, true)as![S],g=d[0],r=S(contentsOfFile:"\(g)/\(a)",encoding:4,error:nil)!.componentsSeparatedByString(";"),z=[U](count:4,repeatedValue:0),c=[U](),p:()->Int={r.removeAtIndex(0).toInt()!},f:()->Bool={r.removeAtIndex(0)=="true" ?true:false},j=U(p());c+=[(j<<4)|(U(p()))];for _ in 0..<j{if f(){c+=[255]}else{let(t,g,v)=(UInt16(p()),U(p()),U(p()));c+=[(U(p()))|(g<<2),v,U(t>>8),U(t&255)]}};for _ in 0..<28{c+=[(U(bitPattern:Int8(p()))<<4)|((f() ?1:0)<<3)|(U(p()))]};for h in 0..<16{let y=h>7 ?1:0,x=Int8(p()),w=Int8(p());c+=[(U(bitPattern:x)<<4)|(U(bitPattern:w)&15)];z[y]=z[y]<<1;if x == -1{z[y]|=1};z[y+1]=z[y+1]<<1;if w == -1{z[y+1]|=1}};NSData(bytes:c+z,length:c.count+4).writeToFile("\(g)/\(b)",atomically:true)}

// Decompressor d(inputFileName, outputFileName)
func d(a:S,b:S){var d = NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask,true)as![String],e=d[0],i=NSData(contentsOfFile:"\(e)/\(a)")!,n=[UInt8](count:i.length,repeatedValue:0),o="";i.getBytes(&n,length:i.length);let k=n.removeAtIndex(0),j=k>>4;o+="\(j);\(k&15);";for _ in 0..<j{let h=n.removeAtIndex(0);if h>>7 == 1{o+="true;";continue};let p=n.removeAtIndex(0),b=n.removeAtIndex(0),c=n.removeAtIndex(0);o+="false;\(UInt16(b)<<8|UInt16(c));\(h>>2);\(p);\(h&0b11);"};for _ in 0..<28{let p=Int8(bitPattern:n.removeAtIndex(0)),mortgage=((p>>3)&1)==1 ?"true":"false";o+="\(p>>4);\(mortgage);\(p&7);"};var m=[U](count:4,repeatedValue:0);for i in reverse(0..<4){m[i]=n.removeLast()};for h in 0..<16{var i=h>7 ?1:0,z=n.removeAtIndex(0),x=Int8(z>>4),y=Int8(z&15),isUnowned1=m[i]&128;m[i]=m[i]<<1;let isUnowned2=m[i+1]&128;m[i+1]=m[i+1]<<1;if isUnowned1 != 0 {x=(-1)};if isUnowned2 != 0 {y=(-1)};o+="\(x);\(y);"};o.writeToFile("\(e)/\(b)",atomically:true,encoding:4,error:nil)}

// Test function to compare the files
func t(a:S,b:S)->Bool{let d=NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask,true)as![String],c=d[0],i=S(contentsOfFile:"\(c)/\(a)",encoding:4,error:nil)!,j=S(contentsOfFile:"\(c)/\(b)",encoding:4,error:nil)!;return i==j}
// Usage
e("Input.txt", "Output.bin")  // Encode
d("Output.bin", "Output.txt") // Decode
t("Input.txt", "Output.txt")  // Test -> Should output 'true'

Compress.swift - run in Terminal using swift Compress.swift
(Assumes Input.txt is on the Desktop)
// Compressor - 854 Bytes
import Cocoa;typealias S=String;typealias U=UInt8;func e(a:S,b:S){var d=NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask, true)as![S],g=d[0],r=S(contentsOfFile:"\(g)/\(a)",encoding:4,error:nil)!.componentsSeparatedByString(";"),z=[U](count:4,repeatedValue:0),c=[U](),p:()->Int={r.removeAtIndex(0).toInt()!},f:()->Bool={r.removeAtIndex(0)=="true" ?true:false},j=U(p());c+=[(j<<4)|(U(p()))];for _ in 0..<j{if f(){c+=[255]}else{let(t,g,v)=(UInt16(p()),U(p()),U(p()));c+=[(U(p()))|(g<<2),v,U(t>>8),U(t&255)]}};for _ in 0..<28{c+=[(U(bitPattern:Int8(p()))<<4)|((f() ?1:0)<<3)|(U(p()))]};for h in 0..<16{let y=h>7 ?1:0,x=Int8(p()),w=Int8(p());c+=[(U(bitPattern:x)<<4)|(U(bitPattern:w)&15)];z[y]=z[y]<<1;if x == -1{z[y]|=1};z[y+1]=z[y+1]<<1;if w == -1{z[y+1]|=1}};NSData(bytes:c+z,length:c.count+4).writeToFile("\(g)/\(b)",atomically:true)}
// Decompressor
func d(a:S,b:S){var d = NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask,true)as![String],e=d[0],i=NSData(contentsOfFile:"\(e)/\(a)")!,n=[UInt8](count:i.length,repeatedValue:0),o="";i.getBytes(&n,length:i.length);let k=n.removeAtIndex(0),j=k>>4;o+="\(j);\(k&15);";for _ in 0..<j{let h=n.removeAtIndex(0);if h>>7 == 1{o+="true;";continue};let p=n.removeAtIndex(0),b=n.removeAtIndex(0),c=n.removeAtIndex(0);o+="false;\(UInt16(b)<<8|UInt16(c));\(h>>2);\(p);\(h&0b11);"};for _ in 0..<28{let p=Int8(bitPattern:n.removeAtIndex(0)),mortgage=((p>>3)&1)==1 ?"true":"false";o+="\(p>>4);\(mortgage);\(p&7);"};var m=[U](count:4,repeatedValue:0);for i in reverse(0..<4){m[i]=n.removeLast()};for h in 0..<16{var i=h>7 ?1:0,z=n.removeAtIndex(0),x=Int8(z>>4),y=Int8(z&15),isUnowned1=m[i]&128;m[i]=m[i]<<1;let isUnowned2=m[i+1]&128;m[i+1]=m[i+1]<<1;if isUnowned1 != 0 {x=(-1)};if isUnowned2 != 0 {y=(-1)};o+="\(x);\(y);"};o.writeToFile("\(e)/\(b)",atomically:true,encoding:4,error:nil)}
func t(a:S,b:S)->Bool{let d=NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask,true)as![String],c=d[0],i=S(contentsOfFile:"\(c)/\(a)",encoding:4,error:nil)!,j=S(contentsOfFile:"\(c)/\(b)",encoding:4,error:nil)!;return i==j}
e("Input.txt", "Output.bin")
d("Output.bin", "Output.txt")
println(t("Input.txt", "Output.txt"))

Sample Input/Output
3;1;false;1534;0;14;0;false;34;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;6;9;4;-1;4;8;4;2;9;5;11;10;14;7;

.
31 00 0E 05 FE 05 0A 00 22 FF 11 10 08 F0 F0 F0
F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0
F0 F0 F0 F0 F0 F0 01 23 45 67 89 AB CD EF 3C 69
4F 48 42 95 BA E7 00 00 20 00

Pure C (3592 points)
The output is 182 bytes. The size is O(1), so this is the worst case.
This uses sscanf extensively to read the files, and simply dumps the structs to disk.
I had to slightly modify the input, as your example didn't include 28 properties.
For variables, I named them from the first letter of what it is, or if that would conflict, the second (or subsequent) letter. For example, Game, pLayer, pRoperty, etc.
compress.c (680 bytes):
#import <stdio.h>
#import <stdint.h>
#define T(X) for(int i=0;i<(X);i++)
typedef uint8_t U;typedef struct{U p;U t;U a[16];U e[16];}G;typedef struct{U b;uint16_t m;U c;U p;U t;}L;typedef struct{int8_t o;U m;U i;}R;G g;L l[8];R r[28];main(){FILE *f=fopen("input.txt","r");fscanf(f,"%d;%d;",&g.p,&g.t);T(g.p){l[i].b=(fgetc(f)=='t');while(fgetc(f)!=';');if(!l[i].b){fscanf(f,"%d;%d;%d;%d;",&l[i].m,&l[i].c,&l[i].p,&l[i].t);}}T(28){fscanf(f,"%d;",&r[i].o);r[i].m=(fgetc(f)=='t');while(fgetc(f)!=';');fscanf(f,"%d;",&r[i].i);}T(16){fscanf(f,"%d;",&g.a[i]);}T(16){fscanf(f,"%d;",&g.e[i]);}f=fopen("c.dat","w");fwrite(&g,sizeof(G),1,f);fwrite(&l,sizeof(L),8,f);fwrite(&r,sizeof(R),28,f);}

compress.c (pre-golfed)
#include "m.h"

#define NEXT_FIELD b=strchr(b,';')+1;

G g;
L l[8];
R r[28];

char a[1024];
char *b = a;

main() {
    FILE *i = fopen("input.txt", "r");
    fgets(a, 1024, i);
    fclose(i);

    sscanf(b, "%d;%d;", &g.p, &g.t);
    NEXT_FIELD NEXT_FIELD

    TIMES(g.p) {
        l[i].b = (*b == 't'); NEXT_FIELD
        if(!l[i].b) {
            sscanf(b, "%d;%d;%d;%d;", &l[i].m, &l[i].c, &l[i].p, &l[i].t);
            NEXT_FIELD NEXT_FIELD NEXT_FIELD NEXT_FIELD
        }
    }

    TIMES(28) {
        sscanf(b, "%d;", &r[i].o); NEXT_FIELD
        r[i].m = (*b == 't'); NEXT_FIELD
        sscanf(b, "%d;", &r[i].i); NEXT_FIELD
    }

    TIMES(16) {
        sscanf(b, "%d", &g.a[i]);
        NEXT_FIELD
    }

    TIMES(16) {
        sscanf(b, "%d", &g.e[i]);
        NEXT_FIELD
    }

    FILE *c = fopen("c.dat", "w");
    fwrite(&g, sizeof(G), 1, c);
    fwrite(&l, sizeof(L), 8, c);
    fwrite(&r, sizeof(R), 28, c);
    fclose(c);
}

decompress.c:
#import <stdio.h>
#import <stdint.h>

#define T(X) for(int i = 0; i < (X); i++)
typedef uint8_t U;

typedef struct {
    U p;
    U t;
    U a[16];
    U e[16];
} G;
typedef struct {
    U b;
    uint16_t m;
    U c;
    U p;
    U t;
} L;
typedef struct {
    int8_t o;
    U m;
    U i;
} R;

G g;
L l[8];
R r[28];

main() {
    FILE *c = fopen("c.dat", "r");
    fread(&g, sizeof(G), 1, c);
    fread(&l, sizeof(L), 8, c);
    fread(&r, sizeof(R), 28, c);
    fclose(c);

    FILE *d = fopen("output.txt", "w");

    fprintf(d, "%d;%d;", g.p, g.t);
    T(g.p) {
        fprintf(d, "%s;", l[i].b ? "true" : "false");
        if(!l[i].b){
            fprintf(d, "%d;%d;%d;%d;", l[i].m, l[i].c, l[i].p, l[i].t);
        }
    }
    T(28) {
        fprintf(d, "%d;%s;%d;", r[i].o, r[i].m ? "true" : "false", r[i].i);
    }
    T(16) { fprintf(d, "%d;", g.a[i] != 255 ? g.a[i] : -1); }
    T(16) { fprintf(d, "%d;", g.e[i] != 255 ? g.e[i] : -1); }

    fclose(d);
}

Input / output:
3;1;false;1546;0;14;0;false;7692;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

Compressed (182 bytes):
0301 0001 0203 0405 0607 0809 0a0b 0c0d
0e0f 030c 0704 0502 0d0b 0f06 0809 0a01
0eff 0000 0a06 000e 0000 0000 0c1e 010a
0100 0100 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0100 0101 0000 0001 00ff 0000 ff00
00ff 0000 ff00 00ff 0000 ff00 00ff 0000
ff00 00ff 0000 ff00 00ff 0000 ff00 00ff
0000 ff00 00ff 0000 ff00 00ff 0000 ff00
00ff 0000 ff00 00ff 0000 ff00 00ff 0000
ff00 00ff 0000

Run it!
$ make compress decompress && ./compress && ./decompress && md5 input.txt output.txt
MD5 (input.txt) = fa655a5a17d67b188424ab0dcfdfb825
MD5 (output.txt) = fa655a5a17d67b188424ab0dcfdfb825

Thanks, I rolled the header in to save a bit, and fixed my score to count bytes.

Looks like you could save some bytes with run-length encoding after. Not sure how feasible that is but if you do it via an escape byte it should also do well with non-repeating data. Heh.