text:
Graphical Representation of Koch Snowflake
Generate a Koch Snowflake
A Koch snowflake is a triangle that for each n, another equilateral point is added in the middle of each side: http://en.wikipedia.org/wiki/Koch_snowflake#Properties
We already had a kolmogrov-complexity Koch Snowflake challenge for n=4.  The new challenge is to draw a Koch snowflake with any n between 1 and 10.
Rules

The snowflakes may not be hardcoded in the program or in files - they must be generated by your program.
Your program must support all sized n between 1 and 10.
The number of sides must be input by the user through std-in.
You must print a graphical representation of the snowflake to the screen.

Sample Koch Snowflakes with n equaling 1, 2, 3, and 4 (green lines for clarity only, do not reproduce them):

In the event of a tie-breaker, the program with the highest number of upvotes wins (pop-contest).

I'm not making sense of this: "You must use a function to calculate where to place the pixel. If your program does not have a built-in function for this purpose, you may deduct the cost of implementing one from your score." What pixel?

@xnor It was originally meant to calculate how to draw the snowflake on a per-pixel/character basis (the challenge was originally an ASCII-art challenge too).  Most people will probably just use lines, so I will remove that.

Can one draw the whole snowflake filled in?

Of course.  This comment needs to be longer.

Beyond n=7, you can't see the newly added triangles in the snowflake on a computer screen. Is any "best effort" here OK? Is there a minimum resolution for pixel-based solutions?

As long as they would be there if it was displayed large enough, you are alright.

Mathematica 72
Region@Line@AnglePath[Nest[Join@@({#,1,4,1}&/@#)&,{4,4,4},Input[]-1]π/3]

n=3

Thanks for alephalpha.

Nice job.  Golf it by two characters, and you get the win!

@Hosch250 Updated, Thank you.

You can use AnglePath in Mathematica 10.1.

@chyaong Graphics@Line@AnglePath[Nest[Join@@({-1,2,-1,#}&/@#)&,{2,2,2},Input[]-1]Pi/3]

@alephalpha Nice work.

Can you provide an ungolfed translation of your code too?

@alephalpha 73 chars: ListLinePlot@AnglePath[Nest[Join@@({#,1,4,1}&/@#)&,{4,4,4},Input[]-1]π/3]

MATLAB, 119 115
In an unusual turn of events, I found that this program actually worked better as I golfed it. First, it became much faster due to vectorization. Now, it displays a helpful prompt ~n:~ reminding the user of which quantity to enter!
Newlines are not part of the program.
x=exp(i*pi/3);
o='~n:~';
P=x.^o;
for l=2:input(o);
P=[kron(P(1:end-1),~~o)+kron(diff(P)/3,[0 1 1+1/x 2]) 1];
end;
plot(P)

n = 9:

o is an arbitrary string which is equal to [0 2 4 0] modulo 6. eiπ/3 raised to these powers gives the vertices of an equilateral triangle in the complex plane. The first kron is used to make a copy of the list of points with each one duplicated 4 times. ~~o is the convenient way to get a vector of 4 ones. Secondly diff(P) finds the vector between each pair of consecutive points. Multiples of this vector (0, 1/3, (1 + e-iπ/3)/3, and 2/3) are added to each of the old points.

Uhm, could you explain somewhat more how this code works? I thought I knew some Matlab but this is ... insanity?? =)

@flawr I added a few notes, does that help any?

Thank you very much! I'm gonna keep that string-abuse trick in mind=)

LOGO: 95
to w:c ifelse:c=1[fd 2 lt 60][w:c-1 w:c-1 lt 180 w:c-1 w:c-1]end
to k:c repeat 3[w:c rt 180]end

Defines function k with a single level parameter.
Edit
In the this online editor http://www.calormen.com/jslogo/ you can add k readword to use prompt for input, but for some reason this command does not support the standard abbreviation rw.
The 102 characters solution below works in USBLogo with standard input as specified in the question. However the code needed slight changes as UCBLogo has some weird parser. It requires to and end to be in separate lines and space before : is required but on the other hand : are optional.
to w c
ifelse c=1[fd 2 lt 60][w c-1 w c-1 lt 180 w c-1 w c-1]
end
to k c
repeat 3[w c rt 180]
end
k rw

How do you run LOGO?

@BetaDecay I used this: http://logo.twentygototen.org but this was the first I found: http://www.calormen.com/jslogo/
You can also install USBLogo

T-SQL: 686 (excluding formatting)
For SQL Server 2012+.
Even though this will never be a contender, I had to see if I could get it done in T-SQL.
Gone for the approach of starting with the three initial edges, then recursing through each edge and replacing them with 4 edges for each level. Finally unioning it all up into a single geometry for the level specified for @i
DECLARE @i INT=8,@ FLOAT=0,@l FLOAT=9;
WITH R AS(
    SELECT sX,sY,eX,eY,@l l,B,1i
    FROM(VALUES(@,@,@l,@,0),(@l,@,@l/2,SQRT(@l*@l-(@l/2)*(@l/2)),-120),(@l/2,SQRT(@l*@l-(@l/2)*(@l/2)),@,@,-240))a(sX,sY,eX,eY,B)
    UNION ALL
    SELECT a.sX,a.sY,a.eX,a.eY,l/3,a.B,i+1
    FROM R
        CROSS APPLY(VALUES(sX,sY,sX+(eX-sX)/3,sY+(eY-sY)/3,sX+((eX-sX)/3)*2,sY+((eY-sY)/3)*2))x(x1,y1,x2,y2,x3,y3)
        CROSS APPLY(VALUES(x2+((l/3)*SIN(RADIANS(B-210.))),y2+((l/3)*COS(RADIANS(B-210.)))))n(x4,y4)
        CROSS APPLY(VALUES(x1,y1,x2,y2,B),
            (x3,y3,eX,eY,B),
            (x2,y2,x4,y4,B+60),
            (x4,y4,x3,y3,B-60)
        )a(sX,sY,eX,eY,B)
WHERE @i>i)
SELECT Geometry::UnionAggregate(Geometry::Parse(CONCAT('LINESTRING(',sX,' ',sY,',',eX,' ',eY,')')))
FROM R
WHERE i=@i

I had no idea such wizardry could be achieved with T-SQL!

Mathematica - 177
r[x_, y_] := Sequence[x, RotationTransform[π/3, x]@y, y]
Graphics@Polygon@Nest[
 ReplaceList[#, {___, x_, y_, ___}  Sequence[x,r[2 x/3 + y/3, 2 y/3 + x/3], y]
  ] &, {{0, 0}, {.5, √3/2}, {1, 0}, {0, 0}}, Input[]]

Bonus clip of varying the angle of middle piece

BBC BASIC, 179
REV 1
INPUTn
z=FNt(500,470,0,0,3^n/9)END
DEFFNt(x,y,i,j,a)
LINEx-36*a,y-21*a,x+36*a,y-a*21PLOT85,x,y+a*42IFa FORj=-1TO1FORi=-1TO1z=FNt(x+24*a*i,y+j*14*a*(i*i*3-2),i,j,-j*a/3)NEXTNEXT
=0

As before, but in black and white, in ungolfed (but streamlined) and golfed versions. Not a winner, despite the fact that doing it ths way avoids the need for a special treament for n=1.
  INPUTn
        REM call function and throw return value away to z
  z=FNt(500,470,0,0,3^n/9)
  END

        REM x,y=centre of triangle. a=scale.
        REM loop variables i,j are only passed in order to make them local, not global.
  DEFFNt(x,y,i,j,a)

        REM first draw a line at the bottom of the triangle. PLOT85 then draws a filled triangle,
        REM using the specified point (top of the triangle) and the last two points visited (those used to draw the line.)
  LINEx-36*a,y-21*a,x+36*a,y-21*a
  PLOT85,x,y+42*a

        REM if the absolute magnitude of a is sufficient to be truthy, recurse to the next level.
        REM j determines if the triangle will be upright, inverted or (if j=0) infinitely small.
        REM i loops through the three triangles of each orientation, from left to right.
  IFa FORj=-1TO1 FORi=-1TO1:z=FNt(x+24*a*i,y+j*14*a*(i*i*3-2),i,j,-j*a/3):NEXT:NEXT

        REM return 0
  =0

REV 0
According to the OP's answer to @xnor, filled in snowflakes are OK. This answer was inspired by xnor's comment. The colours are just for fun and to show the way it is constructed. Take a triangle (magenta in this case) and overplot with 6 triangles 1/3 of the base.
  INPUTn
  z=FNt(500,470,n,1,0,0)
  END

  DEFFNt(x,y,n,o,i,a)
  a=3^n/22
  GCOLn
  MOVEx-36*a,y-o*21*a
  MOVEx+36*a,y-o*21*a
  PLOT85,x,y+o*42*a
  IFn>1FORi=-1TO1:z=FNt(x+24*a*i,y+14*a*(i*i*3-2),n-1,-1,i,a):z=FNt(x+24*a*i,y-14*a*(i*i*3-2),n-1,1,i,a)NEXT
  =0

I like how it looks like 7 of them merged together.

@hosch250 Indeed, I seem to have "invented" a new fractal whose silhouette happens to be a Koch snowflake, and if you delete the magenta part you are left with 6 smaller Koch snowflakes. The golfed version will be just a plain black silhouette, but I will leave this image up, too.

Do you write it BBC Basic or BBC BASIC? I go for the latter but I don't know if it's correct...

@BetaDecay BASIC is a backronym for Beginners' All-purpose Standard/Symbolic Instruction Code. The "Standard" bit is debatable as there are so many variants. http://en.wikipedia.org/wiki/BASIC. Most variants of BASIC prefer the capitalised version, but according to the Wikipedia page, Visual Basic prefers lowercase. I think BBC BASIC as shipped was uppercase. I'm using the version at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html. It's uppercase in the website and IDE, So I'd say the uppercase version is more correct. But I don't think it matters much.

Ahh okay, I'll carry on with the uppercase version

Python 3 - 139
Uses the turtle graphics library.
from turtle import*
b=int(input())
a=eval(("FR"*3)+".replace('F','FLFRFLF')"*~-b)
for j in a:fd(9/b*("G">j));rt(60*(2-3*("Q">j))*("K"<j))])

Cool. I like your string-based approach of finding the shape with no more than two lines of code! But can't you check for "G">j, "Q"<j and use fd(9/b) to save 3 bytes? Furthermore you can avoid the if statements multiplying, e.g., ("G">j) with the argument 9/b and put them all in one line behind for. Oh! Then you can even combine rt and lt using 120*(...)-60*(...)

This appears to render the Koch snowflake input+1.  An input of 1 should just be a triangle like the picture above shows.

@Falko Thanks for all that help!

@hosch250 Edited

Now it doesn't draw anything, and an input of 1 creates a division by 0 error.

instead of (b-1) you can do *-~b

60*[0,-1,2][("L"==j)+2*("R"==j)] could also replace your ternary in the last line.

60*(2-3*("Q">j))*("K"<j) is even shorter. Also the -~ is backwards, should be ~- (my bad ;p )

Maybe a=eval('"FRFRF"'+'.replace("F","FLFRFLF")'*~-b)

Python 3, 117 bytes
from turtle import*
ht();n=int(input())-1
for c in eval("'101'.join("*n+"'0'*4"+")"*n):rt(60+180*(c<'1'));fd(99/3**n)

Method:

The solution uses Python's turtle graphics.
n is input - 1
Starting from the string 0000 we join its every character with 101 n times iteratively with the eval trick (thanks to @xnor for that).
For every character in the final string we turn 60 degrees right or 120 degrees left based on the character value (1 or 0) and then move forward a length (99/3^n) which guarantees a similar size for all n's.
The last 0 in the string will be useless but it just redraws the same line the first 0 draws.

Example output for input = 3:

R: 240 175
Because I trying to get my head around R, here's another version.  There's likely to be lot better ways to do this and I'm happy to receive pointers.  What I've done seems very convoluted.
n=readline();d=c(0,-120,-240);c=1;while(c<n){c=c+1;e=c();for(i in 1:length(d)){e=c(e,d[i],d[i]+60,d[i]-60,d[i])};d=e};f=pi/180;plot(cumsum(sin(d*f)),cumsum(cos(d*f)),type="l")

Wise fwom youw gwave...
I knew I'd want to try implementing this in Befunge-98 using TURT, but I couldn't figure out how to go about it and I sat on it for several months. Now, only recently, I figured out a way to do it without using self-modification! And so...
Befunge-98 with the TURT fingerprint, 103
;v;"TRUT"4(02-&:0\:0\1P>:3+:4`!*;
>j$;space makes me cry;^
^>1-:01-\:0\:01-\:0
0>I@
^>6a*L
^>ca*R
^>fF

Let's get some implementation details out of the way first:

I tested this using CCBI 2.1, whose implementation of TURT (the turtle graphics fingerprint) makes I "print" the image to a SVG file. If you run this in CCBI without the command-argument --turt-line=PATH, it will come out as a file named CCBI_TURT.svg by default. This is the closest I could come to "print a graphical representation of the snowflake to the screen" with available Funge interpreters I could find. Maybe someday there will be a better interpreter out there that has a graphical display for the turtle, but for now...
There has to be a newline at the end for CCBI to run it without hanging (this is included with the character count). I know, right?

Basically, this works by using the stack as a sort of makeshift L-system and expanding it on the fly. On each pass, if the top number on the stack is:

-2, then it prints and stops;
-1, the turtle turns counterclockwise 60 degrees;
0, it turns clockwise 120 degrees;
1, it moves forward (by 15 pixels here, but you can change it by modifying the f on the last line);
some number n that's 2 or greater, then it is expanded on the stack to n-1, -1, n-1, 0, n-1, -1, n-1.

For n = 10, this process takes a very long time (a couple of minutes on my system), and the resulting SVG is ~10MB in size and invisible when viewed in the browser because you can't adjust the size of the brush using TURT. IrfanView seems to work decently if you have the right plugins. I'm not super familiar with SVG, so I don't know what the preferred method is for viewing those files (especially when they're really big).
Hey, at least it works - which, considering it's Befunge, is something to be thankful for on its own.

APL(Dyalog Extended), 57 bytes SBCS
'A=↑1 +=⌽¯60 -=⌽60'⌂turtle'A' 'A-A++A-A'⌂lsys⍣⎕⊢'A++A++A'

APL has builtins for generation of fractal L-systems and drawing them using turtle graphics.
Requires Dyalog for Windows.

Python 2, 127 bytes
from turtle import *
def L(l,d=input()-1):
 for x in[1,-2,1,0]:[L(l,d-1),rt(60*x)] if d>0 else fd(l)
for i in'lol':lt(120);L(9)

Grats for having the 50,000th post on here.

authors: Семен Акинфиев


text:
Find highest scoring matrix without property X
This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge.
A cyclic matrix is fully specified by its first row r. The remaining rows are each cyclic permutations of the row r with offset equal to the row index. We will allow cyclic matrices which are not square so that they are simply missing some of their last rows. We do however always assume that the number of rows is no more than the number of columns. For example, consider the following 3 by 5 cyclic matrix.
10111
11011
11101

We say a matrix has property X if it contains two non-empty sets of columns with non-identical indices which have the same (vector) sum. The vector sum of two columns is simply an element-wise summation of the two columns.  That is the sum of two columns containing x elements each is another column containing x elements.
The matrix above trivially has property X as the first and last columns are the same. The identity matrix never has property X.
If we just remove the last column of the matrix above then we get an example which does not have property X and would give a score of 4/3.
1011
1101
1110

The task
The task is to write code to find the highest scoring cyclic matrix whose entries are all 0 or 1 and which does not have property X.
Score
Your score will be the number columns divided by the number of rows in your best scoring matrix.
Tie Breaker
If two answers have the same score, the one submitted first wins.
In the (very) unlikely event that someone finds a method to get unlimited scores, the first valid proof of such a solution will be accepted.  In the even more unlikely event that you can find a proof of optimality of a finite matrix I will of course award the win too.
Hint
Getting a score of 12/8 is not too hard.
Languages and libraries
You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.
Leading entries

36/19 by Peter Taylor (Java)
32/17 by Suboptimus Prime (C#)
21/12 by justhalf (Python 2)

Ah, property X is on columns, not rows.

As written, the 1 by 2 matrix 01  has property X because the set of the first column has the same vector sum as the empty set. Perhaps you meant nonempty sets of columns? I think it's cleaner not to change it though.

@xnor Good point. I have edited the question as you suggested.

Wow, do you actually know whether there is a solution with score higher than 2?

The easiest reading of the rules is still that 01 has property X: (1) = (0) + (1). If you want to exclude that then you should say that the two sets of columns must be disjoint.

@PeterTaylor That was just a mistake by me. I have deleted the offending line in the question. Thank you for spotting this.

@Lembik: Btw, why do you write 12/8 instead of 4/3?

@justhalf 12/8 > 4/3 :)  I am saying that you can find an 8 by 12 matrix without property X.

Oops, haha, miscalculated. Sorry for the confusion!

pretty sure its immposible to get a higher score then 2

I believe we can get infinite score.

Hm you might be right i was trying to get a general solution with linear algebra with linear independance but the rules dont apply actualy which i just noticed. I am very sure tho you can get a solution which will show if its infinite or a finite with a specific number

Oops, mistake in assumption. My method doesn't generate infinite result, but at least it finds something better than 12/8.

Wait... can the matrix contain numbers different than 0 and 1?

No it can not.   .

I tried to prove a finite upper bound by pigeonhole, but am a log factor off. The idea is that a wide enough matrix has more column-subsets of a given size then possible sums of that many column vectors, so there must be a repeated sum.

@xnor I don't believe there is a finite upper bound, but I don't know how to prove that either.  Which is why I hope the contest will prove fun :)

I can at least show that obtaining a score of x requires a matrix whose size is asymptotically exponential in x, so matrices achieving large scores would have to be enormous.

@xnor That is very interesting and I would love to see it. Of course at this point a score of 3 would be very impressive. Does your method say how large a matrix would be needed for that?

Unfortunately, it only gives trivial bounds for scores like 3. For a score of 5, it gives a minimum of 4x20, and for a score of 10, it gives 62x620.

This question will give much insight on this problem (on how hard it is to check property X, which is NP-hard, unfortunately) http://mathoverflow.net/questions/157634/number-of-vectors-so-that-no-two-subset-sums-are-equal

@justhalf This is interesting but not directly relevant.  The problem they consider does not include the restriction that the matrix is cyclic which might make it a lot easier, who knows. In particular, we don't know if the problem of telling if a cyclic matrix has property X is NP-hard or not. My guess is that it is not.

Yes, it doesn't deal with the cyclic nature. Let's see whether anyone can find a polynomial time algorithm to check property X on cyclic matrices.

Currently we are just brute-forcing all the 2^m column combinations to check property X. If we could somehow devise a "meet in the middle" scheme (see the "subset sum" problem) this could probably reduce that to m * 2^(m/2)...

16/9 20/11 22/12 28/15 30/16 32/17 34/18 36/19 (Java)
This uses a number of ideas to reduce the search space and cost. View the revision history for more details on earlier versions of the code.

It's clear that wlog we can consider only circulant matrices in which the first row is a Lyndon word: if the word is non-prime then it must have property X, and otherwise we can rotate without affecting the score or property X.
Based on heuristics from the observed short winners, I'm now iterating through the Lyndon words starting at the ones with 50% density (i.e. the same number of 0 and 1) and working out; I use the algorithm described in A Gray code for fixed-density necklaces and Lyndon words in constant amortized time, Sawada and Williams, Theoretical Computer Science 502 (2013): 46-54.
An empirical observation is that the values occur in pairs: each optimum Lyndon word that I've found scores the same as its reversal. So I get about a factor of two speedup by only considering one half of each such pair.
My original code worked with BigInteger to give an exact test. I get a significant speed improvement, at the risk of false negatives, by operating modulo a large prime and keeping everything in primitives. The prime I've chosen is the largest one smaller than 257, as that allows multiplying by the base of my notional vector representation without overflowing.
I've stolen Suboptimus Prime's heuristic that it's possible to get quick rejections by considering subsets in increasing order of size. I've now merged that idea with the ternary subset meet-in-the-middle approach to test for colliding subsets. (Credit to KennyTM for suggesting trying to adapt the approach from the integer subset problem; I think that xnor and I saw the way to do it pretty much simultaneously). Rather than looking for two subsets which can include each column 0 or 1 times and have the same sum, we look for one subset which can include each column -1, 0, or 1 times and sum to zero. This significantly reduces the memory requirements.
There's an extra factor of two saving in memory requirements by observing that since each element in {-1,0,1}^m has its negation also in {-1,0,1}^m it's only necessary to store one of the two.
I also improve memory requirements and performance by using a custom hashmap implementation. To test 36/19 requires storing 3^18 sums, and 3^18 longs is almost 3GB without any overhead - I gave it 6GB of heap because 4GB wasn't enough; to go any further (i.e. test 38/20) within 8GB of RAM would require further optimisation to store ints rather than longs. With 20 bits required to say which subset produces the sum that would leave 12 bits plus the implicit bits from the bucket; I fear that there would be too many false collisions to get any hits.
Since the weight of the evidence suggests that we should look at 2n/(n+1), I'm speeding things up by just testing that.
There's some unnecessary but reassuring statistical output.

import java.util.*;

// Aiming to find a solution for (2n, n+1).
public class PPCG41021_QRTernary_FixedDensity {
    private static final int N = 36;
    private static int density;
    private static long start;
    private static long nextProgressReport;

    public static void main(String[] args) {
        start = System.nanoTime();
        nextProgressReport = start + 5 * 60 * 1000000000L;

        // 0, -1, 1, -2, 2, ...
        for (int i = 0; i < N - 1; i++) {
            int off = i >> 1;
            if ((i & 1) == 1) off = ~off;
            density = (N >> 1) + off;

            // Iterate over Lyndon words of length N and given density.
            for (int j = 0; j < N; j++) a[j] = j < N - density ? '0' : '1';
            c = 1;
            Bs[1] = N - density;
            Bt[1] = density;
            gen(N - density, density, 1);
            System.out.println("----");
        }

        System.out.println("Finished in " + (System.nanoTime() - start)/1000000 + " ms");
    }

    private static int c;
    private static int[] Bs = new int[N + 1], Bt = new int[N + 1];
    private static char[] a = new char[N];
    private static void gen(int s, int t, int r) {
        if (s > 0 && t > 0) {
            int j = oracle(s, t, r);
            for (int i = t - 1; i >= j; i--) {
                updateBlock(s, t, i);
                char tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                gen(s-1, t-i, testSuffix(r) ? c-1 : r);
                tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                restoreBlock(s, t, i);
            }
        }
        visit();
    }

    private static int oracle(int s, int t, int r) {
        int j = pseudoOracle(s, t, r);
        updateBlock(s, t, j);
        int p = testNecklace(testSuffix(r) ? c - 1 : r);
        restoreBlock(s, t, j);
        return p == N ? j : j + 1;
    }

    private static int pseudoOracle(int s, int t, int r) {
        if (s == 1) return t;
        if (c == 1) return s == 2 ? N / 2 : 1;
        if (s - 1 > Bs[r] + 1) return 0;
        if (s - 1 == Bs[r] + 1) return cmpPair(s-1, t, Bs[c-1]+1, Bt[c-1]) <= 0 ? 0 : 1;
        if (s - 1 == Bs[r]) {
            if (s == 2) return Math.max(t - Bt[r], (t+1) >> 1);
            return Math.max(t - Bt[r], (cmpPair(s-1, t, Bs[c-1] + 1, Bt[c-1]) <= 0) ? 0 : 1);
        }
        if (s == Bs[r]) return t;
        throw new UnsupportedOperationException("Hit the case not covered by the paper or its accompanying code");
    }

    private static int testNecklace(int r) {
        if (density == 0 || density == N) return 1;
        int p = 0;
        for (int i = 0; i < c; i++) {
            if (r - i <= 0) r += c;
            if (cmpBlocks(c-i, r-i) < 0) return 0;
            if (cmpBlocks(c-i, r-1) > 0) return N;
            if (r < c) p += Bs[r-i] + Bt[r-i];
        }
        return p;
    }

    private static int cmpPair(int a1, int a2, int b1, int b2) {
        if (a1 < b1) return -1;
        if (a1 > b1) return 1;
        if (a2 < b2) return -1;
        if (a2 > b2) return 1;
        return 0;
    }

    private static int cmpBlocks(int i, int j) {
        return cmpPair(Bs[i], Bt[i], Bs[j], Bt[j]);
    }

    private static boolean testSuffix(int r) {
        for (int i = 0; i < r; i++) {
            if (c - 1 - i == r) return true;
            if (cmpBlocks(c-1-i, r-i) < 0) return false;
            if (cmpBlocks(c-1-i, r-1) > 0) return true;
        }
        return false;
    }

    private static void updateBlock(int s, int t, int i) {
        if (i == 0 && c > 1) {
            Bs[c-1]++;
            Bs[c] = s - 1;
        }
        else {
            Bs[c] = 1;
            Bt[c] = i;
            Bs[c+1] = s-1;
            Bt[c+1] = t-i;
            c++;
        }
    }

    private static void restoreBlock(int s, int t, int i) {
        if (i == 0 && (c > 0 || (Bs[1] != 1 || Bt[1] != 0))) {
            Bs[c-1]--;
            Bs[c] = s;
        }
        else {
            Bs[c-1] = s;
            Bt[c-1] = t;
            c--;
        }
    }

    private static long[] stats = new long[N/2+1];
    private static long visited = 0;
    private static void visit() {
        String word = new String(a);

        visited++;
        if (precedesReversal(word) && testTernary(word)) System.out.println(word + " after " + (System.nanoTime() - start)/1000000 + " ms");
        if (System.nanoTime() > nextProgressReport) {
            System.out.println("Progress: visited " + visited + "; stats " + Arrays.toString(stats) + " after " + (System.nanoTime() - start)/1000000 + " ms");
             nextProgressReport += 5 * 60 * 1000000000L;
        }
    }

    private static boolean precedesReversal(String w) {
        int n = w.length();
        StringBuilder rev = new StringBuilder(w);
        rev.reverse();
        rev.append(rev, 0, n);
        for (int i = 0; i < n; i++) {
            if (rev.substring(i, i + n).compareTo(w) < 0) return false;
        }
        return true;
    }

    private static boolean testTernary(String word) {
        int n = word.length();
        String rep = word + word;

        int base = 1;
        for (char ch : word.toCharArray()) base += ch & 1;

        // Operating base b for b up to 32 implies that we can multiply by b modulo p<2^57 without overflowing a long.
        // We're storing 3^(n/2) ~= 2^(0.8*n) sums, so while n < 35.6 we don't get *too* bad a probability of false reject.
        // (In fact the birthday paradox assumes independence, and our values aren't independent, so we're better off than that).
        long p = (1L << 57) - 13;
        long[] basis = new long[n];
        basis[0] = 1;
        for (int i = 1; i < basis.length; i++) basis[i] = (basis[i-1] * base) % p;

        int rows = n / 2 + 1;
        long[] colVals = new long[n];
        for (int col = 0; col < n; col++) {
            for (int row = 0; row < rows; row++) {
                colVals[col] = (colVals[col] + basis[row] * (rep.charAt(row + col) & 1)) % p;
            }
        }

        MapInt57Int27 map = new MapInt57Int27();
        // Special-case the initial insertion.
        int[] oldLens = new int[map.entries.length];
        int[] oldSupercounts = new int[1 << 10];
        {
            // count = 1
            for (int k = 0; k < n/2; k++) {
                int val = 1 << (25 - k);
                if (!map.put(colVals[k], val)) { stats[1]++; return false; }
                if (!map.put(colVals[k + n/2], val + (1 << 26))) { stats[1]++; return false; }
            }
        }
        final long keyMask = (1L << 37) - 1;
        for (int count = 2; count <= n/2; count++) {
            int[] lens = map.counts.clone();
            int[] supercounts = map.supercounts.clone();
            for (int sup = 0; sup < 1 << 10; sup++) {
                int unaccountedFor = supercounts[sup] - oldSupercounts[sup];
                for (int supi = 0; supi < 1 << 10 && unaccountedFor > 0; supi++) {
                    int i = (sup << 10) + supi;
                    int stop = lens[i];
                    unaccountedFor -= stop - oldLens[i];
                    for (int j = oldLens[i]; j < stop; j++) {
                        long existingKV = map.entries[i][j];
                        long existingKey = ((existingKV & keyMask) << 20) + i;
                        int existingVal = (int)(existingKV >>> 37);

                        // For each possible prepend...
                        int half = (existingVal >> 26) * n/2;
                        // We have 27 bits of key, of which the top marks the half, so 26 bits. That means there are 6 bits at the top which we need to not count.
                        int k = Integer.numberOfLeadingZeros(existingVal << 6) - 1;
                        while (k >= 0) {
                            int newVal = existingVal | (1 << (25 - k));
                            long pos = (existingKey + colVals[k + half]) % p;
                            if (pos << 1 > p) pos = p - pos;
                            if (pos == 0 || !map.put(pos, newVal)) { stats[count]++; return false; }
                            long neg = (p - existingKey + colVals[k + half]) % p;
                            if (neg << 1 > p) neg = p - neg;
                            if (neg == 0 || !map.put(neg, newVal)) { stats[count]++; return false; }
                            k--;
                        }
                    }
                }
            }
            oldLens = lens;
            oldSupercounts = supercounts;
        }

        stats[n/2]++;
        return true;
    }

    static class MapInt57Int27 {
        private long[][] entries;
        private int[] counts;
        private int[] supercounts;

        public MapInt57Int27() {
            entries = new long[1 << 20][];
            counts = new int[1 << 20];
            supercounts = new int[1 << 10];
        }

        public boolean put(long key, int val) {
            int bucket = (int)(key & (entries.length - 1));
            long insert = (key >>> 20) | (((long)val) << 37);
            final long mask = (1L << 37) - 1;

            long[] chain = entries[bucket];
            if (chain == null) {
                chain = new long[16];
                entries[bucket] = chain;
                chain[0] = insert;
                counts[bucket]++;
                supercounts[bucket >> 10]++;
                return true;
            }

            int stop = counts[bucket];
            for (int i = 0; i < stop; i++) {
                if ((chain[i] & mask) == (insert & mask)) {
                    return false;
                }
            }

            if (stop == chain.length) {
                long[] newChain = new long[chain.length < 512 ? chain.length << 1 : chain.length + 512];
                System.arraycopy(chain, 0, newChain, 0, chain.length);
                entries[bucket] = newChain;
                chain = newChain;
            }
            chain[stop] = insert;
            counts[bucket]++;
            supercounts[bucket >> 10]++;
            return true;
        }
    }
}

The first one found is
000001001010110001000101001111111111

and that's the only hit in 15 hours.
Smaller winners:
4/3:    0111                       (plus 8 different 8/6)
9/6:    001001011                  (and 5 others)
11/7:   00010100111                (and 3 others)
13/8:   0001001101011              (and 5 others)
15/9:   000010110110111            (and 21 others)
16/9:   0000101110111011           (and 1 other)
20/11:  00000101111011110111       (and others)
22/12:  0000001100110011101011     (and others)
24/13:  000000101011101011101011   (and others)
26/14:  00000001101110010011010111 (and others)
28/15:  0000000010000111100111010111 (and others)
30/16:  000000001011001110011010101111 (and probably others)
32/17:  00001100010010100100101011111111 (and others)
34/18:  0000101000100101000110010111111111 (and others)

This is a good improvement. It seems using Lyndon words means you only need to check roughly 2^n/n binary strings for the first row, instead of 2^n.

As you are using each digit of BigInteger as a matrix cell, won't there be wrong answer when n > 10?

@KennyTM, note that the second parameter is the radix. There is a small bug: I should be using n rather than rows, although it's fail-safe in the sense that it would discard valid solutions rather than accept invalid ones. It also doesn't affect the results.

Can you explain more about the "non-prime iff no property X" that you seem to imply in your sentences?

@justhalf, I don't think that's implied and I certainly don't intend to imply it. A prime word can have property X or not: the point is that rotating it doesn't change whether or not it has property X, so we can consider the Lyndon word in the rotational set as a representative element.

I see, so the purpose of that sentence is only to claim that the only first rows that we need to brute force are all those Lyndon words.

I think we're practically limited to this score, since the property X checking is very time consuming, unless we found another equivalent condition which can be evaluated faster. That's why I was so eager to see that "non-prime" implies property X =D

@justhalf, I reckon that I can check up to MAX_N=24 in 12 hours on a fast computer using one thread, but that seems to be about as far as I can go because of memory constraints.

It isn't at all obvious to me why "we can consider only circulant matrices in which the first row is a Lyndon word". I certainly believe you, but would you indulge me in explaining why property X implies Lyndon wordity? I'd appreciate it. :)

@COTO, that's not the implication. There are three types of words: non-prime words, Lyndon words, and rotations of Lyndon words. The only one for which there's an implication is that non-prime implies that every column has an identical twin (or maybe even more identical siblings) and hence has property X.

OK, thanks. I meant to say "the absence of property X implies Lyndon wordity" since you've stated the contrapositive: that the absence of Lyndon wordity implies property X.

@COTO, I haven't stated that, and it's not true. It would imply that every matrix has property X.

"[W]e can consider only circulant matrices in which the first row is a Lyndon word". Ergo if the first row is not a Lyndon word, we cannot consider the resulting circulant matrix. Ergo the resulting circulant matrix must have property X, otherwise we would have to consider it. What am I getting confused?

@COTO, "otherwise we can rotate". I'm partitioning the matrices into equivalence classes and only testing one representative from each equivalence class.

Ah, OK. I read something different out of your sentence structure, but I get it now.

Wah, 28/15, a good result! I'm curious to see the detailed results for each n. Is there a pattern that can be observed in what kind of Lyndon words satisfy the requirement? If we can find any, then we might be able to find a constructive proof.

@PeterTaylor I've been trying to understand your revolvingDoorDifference function and I can say that that's some high level sorcery :) Is that your own implementation or did you find it somewhere?

@SuboptimusPrime, I found it at http://people.math.sfu.ca/~kya17/teaching/math343/16-343.pdf and fixed a bug. Interestingly the algorithm I'm now using to iterate through Lyndon words is one of a class of related algorithms which also does k-of-n subsets, so I might be able to refactor and share some code.

@PeterTaylor Can I borrow your revolving door implementation? It's seems better than the algorithm I'm currently using.

@SuboptimusPrime, go for it. We're already both stealing from each other, no reason to stop now ;)

@PeterTaylor Cool, thanks. Calculating the sum of columns on each iteration was the second biggest bottleneck for my program. That still leaves the biggest bottleneck which is the hashset performance, even though my hashset is almost twice as fast as the default one.

Python 2 - 21/12
In the process of proving that a 2-(3/n) always exists for any n
Inspired by this question, I used De Bruijn Sequence to brute force the possible matrices. And after bruteforcing for n=6,7,8,9,10, I found a pattern that the highest solution is always in the shape of (n, 2n-3).
So I created another method to bruteforce just that shape of matrix, and use multiprocessing to speed things up, since this task is highly distributable. In 16-core ubuntu, it can find solution for n=12 in around 4 minutes:

Trying (0, 254)
Trying (254, 509)
Trying (509, 764)
Trying (764, 1018)
Trying (1018, 1273)
Trying (1273, 1528)
Trying (1528, 1782)
Trying (1782, 2037)
Trying (2037, 2292)
Trying (2292, 2546)
Trying (2546, 2801)
Trying (2801, 3056)
Trying (3056, 3310)
Trying (3820, 4075)
Trying (3565, 3820)
Trying (3310, 3565)
(1625, 1646)
[[0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0]
 [0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0]
 [0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0]
 [1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0]
 [0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1]
 [0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0]
 [1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0]
 [0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1]
 [1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0]
 [1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1]
 [1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1]
 [1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1]]
(12, 21)
Score: 1.7500

real    4m9.121s
user    42m47.472s
sys 0m5.780s

The bulk of computation goes to checking property X, which requires checking all subsets (there are 2^(2n-3) subsets)
Note that I rotate the first row to the left, not to the right as in the question. But these are equivalent since you can just reverse the whole matrix. =)
The code:
import math
import numpy as np
from itertools import combinations
from multiprocessing import Process, Queue, cpu_count

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    alphabet = list(range(k))
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

def generate_cyclic_matrix(seq, n):
    result = []
    for i in range(n):
        result.append(seq[i:]+seq[:i])
    return np.array(result)

def generate_cyclic_matrix_without_property_x(n=3, n_jobs=-1):
    seq = de_bruijn(2,n)
    seq = seq + seq[:n/2]
    max_idx = len(seq)
    max_score = 1
    max_matrix = np.array([[]])
    max_ij = (0,0)
    workers = []
    queue = Queue()
    if n_jobs < 0:
        n_jobs += cpu_count()+1
    for i in range(n_jobs):
        worker = Process(target=worker_function, args=(seq,i*(2**n-2*n+3)/n_jobs, (i+1)*(2**n-2*n+3)/n_jobs, n, queue))
        workers.append(worker)
        worker.start()
    (result, max_ij) = queue.get()
    for worker in workers:
        worker.terminate()
    return (result, max_ij)

def worker_function(seq,min_idx,max_idx,n,queue):
    print 'Trying (%d, %d)' % (min_idx, max_idx)
    for i in range(min_idx, max_idx):
        j = i+2*n-3
        result = generate_cyclic_matrix(seq[i:j], n)
        if has_property_x(result):
            continue
        else:
            queue.put( (result, (i,j)) )
            return

def has_property_x(mat):
    vecs = zip(*mat)
    vector_sums = set()
    for i in range(1, len(vecs)+1):
        for combination in combinations(vecs, i):
            vector_sum = tuple(sum(combination, np.array([0]*len(mat))))
            if vector_sum in vector_sums:
                return True
            else:
                vector_sums.add(vector_sum)
    return False

def main():
    import sys
    n = int(sys.argv[1])
    if len(sys.argv) > 2:
        n_jobs = int(sys.argv[2])
    else:
        n_jobs = -1
    (matrix, ij) = generate_cyclic_matrix_without_property_x(n, n_jobs)
    print ij
    print matrix
    print matrix.shape
    print 'Score: %.4f' % (float(matrix.shape[1])/matrix.shape[0])

if __name__ == '__main__':
    main()

Old answer, for reference
The optimal solution so far (n=10):

(855, 872)
[[1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0]
 [1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1]
 [0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1]
 [1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0]
 [0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1]
 [1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0]
 [0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1]
 [0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0]
 [1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0]
 [1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1]]
(10, 17)
Score: 1.7000

For n=7:

(86, 97)
[[0 1 1 1 0 1 0 0 1 1 1]
 [1 1 1 0 1 0 0 1 1 1 0]
 [1 1 0 1 0 0 1 1 1 0 1]
 [1 0 1 0 0 1 1 1 0 1 1]
 [0 1 0 0 1 1 1 0 1 1 1]
 [1 0 0 1 1 1 0 1 1 1 0]
 [0 0 1 1 1 0 1 1 1 0 1]]
(7, 11)
Score: 1.5714

A solution with the shape as described by OP (n=8):

(227, 239)
[[0 1 0 1 1 1 1 1 0 1 1 0]
 [1 0 1 1 1 1 1 0 1 1 0 0]
 [0 1 1 1 1 1 0 1 1 0 0 1]
 [1 1 1 1 1 0 1 1 0 0 1 0]
 [1 1 1 1 0 1 1 0 0 1 0 1]
 [1 1 1 0 1 1 0 0 1 0 1 1]
 [1 1 0 1 1 0 0 1 0 1 1 1]
 [1 0 1 1 0 0 1 0 1 1 1 1]]
(8, 12)
Score: 1.5000

But a better one (n=8):

(95, 108)
[[0 1 1 0 0 1 0 0 0 1 1 0 1]
 [1 1 0 0 1 0 0 0 1 1 0 1 0]
 [1 0 0 1 0 0 0 1 1 0 1 0 1]
 [0 0 1 0 0 0 1 1 0 1 0 1 1]
 [0 1 0 0 0 1 1 0 1 0 1 1 0]
 [1 0 0 0 1 1 0 1 0 1 1 0 0]
 [0 0 0 1 1 0 1 0 1 1 0 0 1]
 [0 0 1 1 0 1 0 1 1 0 0 1 0]]
(8, 13)
Score: 1.6250

It also found another optimal solution at n=9:

(103, 118)
[[0 1 0 1 1 1 0 0 0 0 1 1 0 0 1]
 [1 0 1 1 1 0 0 0 0 1 1 0 0 1 0]
 [0 1 1 1 0 0 0 0 1 1 0 0 1 0 1]
 [1 1 1 0 0 0 0 1 1 0 0 1 0 1 0]
 [1 1 0 0 0 0 1 1 0 0 1 0 1 0 1]
 [1 0 0 0 0 1 1 0 0 1 0 1 0 1 1]
 [0 0 0 0 1 1 0 0 1 0 1 0 1 1 1]
 [0 0 0 1 1 0 0 1 0 1 0 1 1 1 0]
 [0 0 1 1 0 0 1 0 1 0 1 1 1 0 0]]
(9, 15)
Score: 1.6667

The code is as follows. It's just brute force, but at least it can find something better than OP's claim =)
import numpy as np
from itertools import combinations

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    alphabet = list(range(k))
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

def generate_cyclic_matrix(seq, n):
    result = []
    for i in range(n):
        result.append(seq[i:]+seq[:i])
    return np.array(result)

def generate_cyclic_matrix_without_property_x(n=3):
    seq = de_bruijn(2,n)
    max_score = 0
    max_matrix = []
    max_ij = (0,0)
    for i in range(2**n+1):
        for j in range(i+n, 2**n+1):
            score = float(j-i)/n
            if score <= max_score:
                continue
            result = generate_cyclic_matrix(seq[i:j], n)
            if has_property_x(result):
                continue
            else:
                if score > max_score:
                    max_score = score
                    max_matrix = result
                    max_ij = (i,j)
    return (max_matrix, max_ij)

def has_property_x(mat):
    vecs = zip(*mat)
    vector_sums = set()
    for i in range(1, len(vecs)):
        for combination in combinations(vecs, i):
            vector_sum = tuple(sum(combination, np.array([0]*len(mat))))
            if vector_sum in vector_sums:
                return True
            else:
                vector_sums.add(vector_sum)
    return False

def main():
    import sys
    n = int(sys.argv[1])
    (matrix, ij) = generate_cyclic_matrix_without_property_x(n)
    print ij
    print matrix
    print matrix.shape
    print 'Score: %.4f' % (float(matrix.shape[1])/matrix.shape[0])

if __name__ == '__main__':
    main()

A great start :)

@Lembik Now I can beat almost (limited by computational time) anyone claiming any score below 2. =)

In that case, can you beat 19/10 ?

@Lembik I don't think I can. It requires n >= 31, which implies I'd need to check up to 2^(2n-3) = 2^59 combinations of 31-dimensional vector. Won't finish in our lifetime =D

I'm not sure where de Bruijn sequences fit into things - can't you just brute-force by counting? But your brute force doesn't actually seem to be complete, because I think I've got a better result than the one you found.

Can you prove that you can always obtain a matrix of n*(2n-3)

At least the formula doesn't work for n=5: The best ratio is 6/5 or 7/6.

@xnor: No, I haven't been able to prove it, unfortunately. This is just a conjecture after seeing a pattern, and the code is just to brute-force it.

@PeterTaylor: I used de Bruijn sequence because I initially thought that the vectors of all possible combinations don't have property X (which is why I thought the answer is infinite). But after I found that that's not the case, I still continued using de Bruijn sequence. You seem to have found the truly optimal solution, though. Congrats! =). And btw using this sequence I only need to brute-force 2^n instead of 2^(2n-3), although like you said, it's not complete.

@KennyTM: Yes, the formula only works for n>=6. For n<=5, we have: 1/1, 2/2, 4/3, 5/4, 6/5.

Since the score is smaller for low n (6/5 instead of 7/5), and given the Java answer is correct it is higher for big n (20/11 instead of 19/11, 22/12 instead of 21/12), I believe the matrix width is superlinear in n, and the score may be able to exceed 2.

@KennyTM: I can't really follow your reasoning. What do you mean by "higher for big n"? My answer also gets higher for bigger n, just that its limit is 2.

@justhalf I mean the Java program shows for higher n, the pattern becomes 2n-2. Perhaps it becomes 2n-1, 2n, ... 2n+x for even higher n, which breaks the limit "2".

I see. Let's see whether that's true. =). Btw @xnor, I found another answer that seems to suggest there will always be solution for 2n-3: http://math.stackexchange.com/a/672555/92861

Oops, yeah, that's true, sorry for that. I edited my answer.

24/13 26/14 28/15 30/16 32/17 (C#)
Edit:
Deleted outdated info from my answer. I'm using mostly the same algorithm as Peter Taylor (Edit: looks like he is using a better algorithm now), although I've added some of my own optimizations:

I've implemented "meet in the middle" strategy of searching for
column sets with the same vector sum (suggested by this KennyTM's
comment). This strategy improved memory usage a lot, but it's
rather slow, so I've added the HasPropertyXFast function, that
quickly checks if there are small set with equal sums before using
"meet in the middle" approach.
While iterating through column sets in the HasPropertyXFast
function, I start from checking column sets with 1 column, then with
2, 3 and so on. The function returns as soon as the first collision
of column sums is found. In practice it means that I usually have to
check just a few hundreds or thousands of column sets rather than
millions.
I'm using long variables to store and compare entire columns and
their vector sums. This approach is at least an order of magnitude
faster than comparing columns as arrays.
I've added my own implementation of hashset, optimized for long
data type and for my usage patterns.
I'm reusing the same 3 hashsets for the entire lifetime of the
application to reduce the number of memory allocations and improve
performance.
Multithreading support.

Program output:
00000000000111011101010010011111
10000000000011101110101001001111
11000000000001110111010100100111
11100000000000111011101010010011
11110000000000011101110101001001
11111000000000001110111010100100
01111100000000000111011101010010
00111110000000000011101110101001
10011111000000000001110111010100
01001111100000000000111011101010
00100111110000000000011101110101
10010011111000000000001110111010
01001001111100000000000111011101
10100100111110000000000011101110
01010010011111000000000001110111
10101001001111100000000000111011
11010100100111110000000000011101
Score: 32/17 = 1,88235294117647
Time elapsed: 02:11:05.9791250

Code:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    const int MaxWidth = 32;
    const int MaxHeight = 17;

    static object _lyndonWordLock = new object();

    static void Main(string[] args)
    {
        Stopwatch sw = Stopwatch.StartNew();
        double maxScore = 0;
        const int minHeight = 17; // 1
        for (int height = minHeight; height <= MaxHeight; height++)
        {
            Console.WriteLine("Row count = " + height);
            Console.WriteLine("Time elapsed: " + sw.Elapsed + "\r\n");

            int minWidth = Math.Max(height, (int)(height * maxScore) + 1);
            for (int width = minWidth; width <= MaxWidth; width++)
            {
#if MULTITHREADING
                int[,] matrix = FindMatrixParallel(width, height);
#else
                int[,] matrix = FindMatrix(width, height);
#endif
                if (matrix != null)
                {
                    PrintMatrix(matrix);
                    Console.WriteLine("Time elapsed: " + sw.Elapsed + "\r\n");
                    maxScore = (double)width / height;
                }
                else
                    break;
            }
        }
    }

#if MULTITHREADING
    static int[,] FindMatrixParallel(int width, int height)
    {
        _lyndonWord = 0;
        _stopSearch = false;

        int threadCount = Environment.ProcessorCount;
        Task<int[,]>[] tasks = new Task<int[,]>[threadCount];
        for (int i = 0; i < threadCount; i++)
            tasks[i] = Task<int[,]>.Run(() => FindMatrix(width, height));

        int index = Task.WaitAny(tasks);
        if (tasks[index].Result != null)
            _stopSearch = true;

        Task.WaitAll(tasks);
        foreach (Task<int[,]> task in tasks)
            if (task.Result != null)
                return task.Result;

        return null;
    }

    static volatile bool _stopSearch;
#endif

    static int[,] FindMatrix(int width, int height)
    {
#if MULTITHREADING
        _columnSums = new LongSet();
        _left = new LongSet();
        _right = new LongSet();
#endif

        foreach (long rowTemplate in GetLyndonWords(width))
        {
            int[,] matrix = new int[width, height];
            for (int x = 0; x < width; x++)
            {
                int cellValue = (int)(rowTemplate >> (width - 1 - x)) % 2;
                for (int y = 0; y < height; y++)
                    matrix[(x + y) % width, y] = cellValue;
            }

            if (!HasPropertyX(matrix))
                return matrix;

#if MULTITHREADING
            if (_stopSearch)
                return null;
#endif
        }

        return null;
    }

#if MULTITHREADING
    static long _lyndonWord;
#endif

    static IEnumerable<long> GetLyndonWords(int length)
    {
        long lyndonWord = 0;
        long max = (1L << (length - 1)) - 1;
        while (lyndonWord <= max)
        {
            if ((lyndonWord % 2 != 0) && PrecedesReversal(lyndonWord, length))
                yield return lyndonWord;

#if MULTITHREADING
            lock (_lyndonWordLock)
            {
                if (_lyndonWord <= max)
                    _lyndonWord = NextLyndonWord(_lyndonWord, length);
                else
                    yield break;

                lyndonWord = _lyndonWord;
            }
#else
            lyndonWord = NextLyndonWord(lyndonWord, length);
#endif
        }
    }

    static readonly int[] _lookup =
    {
        32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17,
        0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18
    };

    static int NumberOfTrailingZeros(uint i)
    {
        return _lookup[(i & -i) % 37];
    }

    static long NextLyndonWord(long w, int length)
    {
        if (w == 0)
            return 1;

        int currentLength = length - NumberOfTrailingZeros((uint)w);
        while (currentLength < length)
        {
            w += w >> currentLength;
            currentLength *= 2;
        }

        w++;

        return w;
    }

    private static bool PrecedesReversal(long lyndonWord, int length)
    {
        int shift = length - 1;

        long reverse = 0;
        for (int i = 0; i < length; i++)
        {
            long bit = (lyndonWord >> i) % 2;
            reverse |= bit << (shift - i);
        }

        for (int i = 0; i < length; i++)
        {
            if (reverse < lyndonWord)
                return false;

            long bit = reverse % 2;
            reverse /= 2;
            reverse += bit << shift;
        }

        return true;
    }

#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _left = new LongSet();
#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _right = new LongSet();

    static bool HasPropertyX(int[,] matrix)
    {
        long[] matrixColumns = GetMatrixColumns(matrix);
        if (matrixColumns.Length == 1)
            return false;

        return HasPropertyXFast(matrixColumns) || MeetInTheMiddle(matrixColumns);
    }

    static bool MeetInTheMiddle(long[] matrixColumns)
    {
        long[] leftColumns = matrixColumns.Take(matrixColumns.Length / 2).ToArray();
        long[] rightColumns = matrixColumns.Skip(matrixColumns.Length / 2).ToArray();

        if (PrepareHashSet(leftColumns, _left) || PrepareHashSet(rightColumns, _right))
            return true;

        foreach (long columnSum in _left.GetValues())
            if (_right.Contains(columnSum))
                return true;

        return false;
    }

    static bool PrepareHashSet(long[] columns, LongSet sums)
    {
        int setSize = (int)System.Numerics.BigInteger.Pow(3, columns.Length);
        sums.Reset(setSize, setSize);
        foreach (long column in columns)
        {
            foreach (long sum in sums.GetValues())
                if (!sums.Add(sum + column) || !sums.Add(sum - column))
                    return true;

            if (!sums.Add(column) || !sums.Add(-column))
                return true;
        }

        return false;
    }

#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _columnSums = new LongSet();

    static bool HasPropertyXFast(long[] matrixColumns)
    {
        int width = matrixColumns.Length;

        int maxColumnCount = width / 3;
        _columnSums.Reset(width, SumOfBinomialCoefficients(width, maxColumnCount));

        int resetBit, setBit;
        for (int k = 1; k <= maxColumnCount; k++)
        {
            uint columnMask = (1u << k) - 1;
            long sum = 0;
            for (int i = 0; i < k; i++)
                sum += matrixColumns[i];

            while (true)
            {
                if (!_columnSums.Add(sum))
                    return true;
                if (!NextColumnMask(columnMask, k, width, out resetBit, out setBit))
                    break;
                columnMask ^= (1u << resetBit) ^ (1u << setBit);
                sum = sum - matrixColumns[resetBit] + matrixColumns[setBit];
            }
        }

        return false;
    }

    // stolen from Peter Taylor
    static bool NextColumnMask(uint mask, int k, int n, out int resetBit, out int setBit)
    {
        int gap = NumberOfTrailingZeros(~mask);
        int next = 1 + NumberOfTrailingZeros(mask & (mask + 1));

        if (((k - gap) & 1) == 0)
        {
            if (gap == 0)
            {
                resetBit = next - 1;
                setBit = next - 2;
            }
            else if (gap == 1)
            {
                resetBit = 0;
                setBit = 1;
            }
            else
            {
                resetBit = gap - 2;
                setBit = gap;
            }
        }
        else
        {
            if (next == n)
            {
                resetBit = 0;
                setBit = 0;
                return false;
            }

            if ((mask & (1 << next)) == 0)
            {
                if (gap == 0)
                {
                    resetBit = next - 1;
                    setBit = next;
                }
                else
                {
                    resetBit = gap - 1;
                    setBit = next;
                }
            }
            else
            {
                resetBit = next;
                setBit = gap;
            }
        }

        return true;
    }

    static long[] GetMatrixColumns(int[,] matrix)
    {
        int width = matrix.GetLength(0);
        int height = matrix.GetLength(1);

        long[] result = new long[width];
        for (int x = 0; x < width; x++)
        {
            long column = 0;
            for (int y = 0; y < height; y++)
            {
                column *= 13;
                if (matrix[x, y] == 1)
                    column++;
            }

            result[x] = column;
        }

        return result;
    }

    static int SumOfBinomialCoefficients(int n, int k)
    {
        int result = 0;
        for (int i = 0; i <= k; i++)
            result += BinomialCoefficient(n, i);
        return result;
    }

    static int BinomialCoefficient(int n, int k)
    {
        long result = 1;
        for (int i = n - k + 1; i <= n; i++)
            result *= i;
        for (int i = 2; i <= k; i++)
            result /= i;
        return (int)result;
    }

    static void PrintMatrix(int[,] matrix)
    {
        int width = matrix.GetLength(0);
        int height = matrix.GetLength(1);

        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
                Console.Write(matrix[x, y]);
            Console.WriteLine();
        }

        Console.WriteLine("Score: {0}/{1} = {2}", width, height, (double)width / height);
    }
}

class LongSet
{
    private static readonly int[] primes =
    {
        17, 37, 67, 89, 113, 149, 191, 239, 307, 389, 487, 613, 769, 967, 1213, 1523, 1907,
        2389, 2999, 3761, 4703, 5879, 7349, 9187, 11489, 14369, 17971, 22469, 28087, 35111,
        43889, 54869, 68597, 85751, 107197, 133999, 167521, 209431, 261791, 327247, 409063,
        511333, 639167, 798961, 998717, 1248407, 1560511, 1950643, 2438309, 3047909,
        809891, 4762367, 5952959, 7441219, 9301529, 11626913, 14533661, 18167089, 22708867,
        28386089, 35482627, 44353297, 55441637, 69302071, 86627603, 108284507, 135355669,
        169194593, 211493263, 264366593, 330458263, 413072843, 516341057, 645426329,
        806782913, 1008478649, 1260598321
    };

    private int[] _buckets;
    private int[] _nextItemIndexes;
    private long[] _items;
    private int _count;
    private int _minCapacity;
    private int _maxCapacity;
    private int _currentCapacity;

    public LongSet()
    {
        Initialize(0, 0);
    }

    private int GetPrime(int capacity)
    {
        foreach (int prime in primes)
            if (prime >= capacity)
                return prime;

        return int.MaxValue;
    }

    public void Reset(int minCapacity, int maxCapacity)
    {
        if (maxCapacity > _maxCapacity)
            Initialize(minCapacity, maxCapacity);
        else
            ClearBuckets();
    }

    private void Initialize(int minCapacity, int maxCapacity)
    {
        _minCapacity = GetPrime(minCapacity);
        _maxCapacity = GetPrime(maxCapacity);
        _currentCapacity = _minCapacity;

        _buckets = new int[_maxCapacity];
        _nextItemIndexes = new int[_maxCapacity];
        _items = new long[_maxCapacity];
        _count = 0;
    }

    private void ClearBuckets()
    {
        Array.Clear(_buckets, 0, _currentCapacity);
        _count = 0;
        _currentCapacity = _minCapacity;
    }

    public bool Add(long value)
    {
        int bucket = (int)((ulong)value % (ulong)_currentCapacity);
        for (int i = _buckets[bucket] - 1; i >= 0; i = _nextItemIndexes[i])
            if (_items[i] == value)
                return false;

        if (_count == _currentCapacity)
        {
            Grow();
            bucket = (int)((ulong)value % (ulong)_currentCapacity);
        }

        int index = _count;
        _items[index] = value;
        _nextItemIndexes[index] = _buckets[bucket] - 1;
        _buckets[bucket] = index + 1;
        _count++;

        return true;
    }

    private void Grow()
    {
        Array.Clear(_buckets, 0, _currentCapacity);

        const int growthFactor = 8;
        int newCapacity = GetPrime(_currentCapacity * growthFactor);
        if (newCapacity > _maxCapacity)
            newCapacity = _maxCapacity;
        _currentCapacity = newCapacity;

        for (int i = 0; i < _count; i++)
        {
            int bucket = (int)((ulong)_items[i] % (ulong)newCapacity);
            _nextItemIndexes[i] = _buckets[bucket] - 1;
            _buckets[bucket] = i + 1;
        }
    }

    public bool Contains(long value)
    {
        int bucket = (int)((ulong)value % (ulong)_buckets.Length);
        for (int i = _buckets[bucket] - 1; i >= 0; i = _nextItemIndexes[i])
            if (_items[i] == value)
                return true;

        return false;
    }

    public IReadOnlyList<long> GetValues()
    {
        return new ArraySegment<long>(_items, 0, _count);
    }
}

Configuration file:
<?xml version="1.0" encoding="utf-8" ?>
<configuration>
  <runtime>
    <gcAllowVeryLargeObjects enabled="true" />
  </runtime>
</configuration>

In some regards you seem to have pessimised rather than optimised. The only thing which really looks like an optimisation is allowing bits to clash by using ulong and letting the shift wrap instead of using BigInteger.

@PeterTaylor The most important optimisation is in HasPropertyX function. The function returns as soon as the first collision of column sums is found (unlike your scoreLyndonWord function). I've also sorted the column masks in such a way that we first check the column sets that are more likely to collide. These two optimisations improved the performance by an order of magnitude.

Although performance changes are often surprising, in principle the early abort shouldn't give more than a factor of 2, and GetSumOfColumns adds an extra loop which I would expect to cost more than that factor of 2. The mask sorting sounds interesting: maybe you could edit the answer to talk a bit about it? (And at some point I will experiment with an alternative way to do the early abort: the reason I can't do it is that HashSet doesn't support concurrent iteration and modification, but I have ideas to avoid the need for an iterator).

@PeterTaylor Added some explanation to the answer, hopefully it clears things up a bit.

@SuboptimusPrime: Hmm, yeah, the summing based on columns is basically what I do in my answer as well. But you used faster language (C# > Python in speed) and faster algorithm (Peter's > mine). I saw in another thread that you can use Gray Code as the mask to do incremental sum, so you only need to add/remove one vector each iteration. Perhaps you want to implement that? EDIT: ah, but your limit is the memory, so I guess 26 columns is the maximum for your algorithm so far?

@justhalf, I've done Grey code, but it doesn't seem to make enough of a difference. Well, overall with some other optimisations I have a 7.5-fold improvement for MAX_N=22, but I think the biggest improvement comes from finding a better way to not use BigInteger.

@justhalf Using Gray code means that you have to iterate through column sets in a different order. Even though each iteration is faster, you end up doing way more iterations before you find two column sets with the same vector sum. I've tried it and it was about 20 times slower than my current algorithm.

@justhalf Btw, the maximum for my algorithm is actually 27 columns, but there are no 27x14 matrices without property X, so I can't improve my score without optimizing the memory usage of my program.

@justhalf, using a Gray-esque approach for iterating over the subsets of a fixed size is actually worthwhile. It allowed me to find a 26/14 in under 9 minutes and 34 of them in two hours, at which point I aborted. Currently testing to see whether I can get 28/15 in a reasonable time.

30/16 is great!  Seems we are creeping to 2.. but can we actually get to it? Do you think 16 is optimal for 30, 15 is optimal for 28 etc.?

@Lembik I'm pretty sure that 15 rows is optimal for 28 columns although there could be a 29/15 matrix without property X. I intentionally skipped 29/15 and went straight for 30/16 since 29/15 was taking too long.

@SuboptimusPrime It be great to find any ratio that contradicts the hypothesis that increasing the number or columns by 2 always increases the number of rows by 1.  If the limit of the score really is 2 I feel that a) would be very surprising and b) ought to have a proof.  How long does each matrix take to test in the 30/16 case?

@Lembik I did't really check how long it takes to test a single matrix but it's probably just a tiny fraction of a second. But it took over 3 hours to find a 30/16 matrix that doesn't have property X since the number of matrices grows exponentially as number of columns increases.

If each test is quick and the memory problems are ok, it might be worth trying a few thousand random 40/20 matrices where the first row has roughly equal numbers of 1s and 0s.

@Lembik I suspect that there is like a billion of 40/20 matrices that do have property X for each one that doesn't, so the probability of finding one is not too high. This is just a guess, but I can't check it anyway since the current version of my program can not work with 40/20 matrices.

@Lembik, my code takes about 20 seconds to check a 28/15. I'm searching for 29/15, currently at 35 hours with no success. I'm also searching for 30/16, with some additional heuristics to try to speed it up, but no hits yet in just under 6 hours.

Are you able to explore 31/16 and/or 32/16 exhaustively?

@Lembik Probably not. I've tried to search 31/16 matrices for 10 hours and didn't find anything. Exhaustive search would probably take much longer because even 29/15 didn't finish in 10 hours.

@Lembik, I explored 29/15 exhaustively in 75.5 hours. 31/16 would take about 3 times as long - so more than a week. Both of us have made some optimisations since I started running that test of 29/15, so maybe it would be down to a week now. There's nothing stopping you from compiling my code or SuboptimusPrime's code and running it yourself if you have a computer which you can leave on for that long.

source: Stack Exchange

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

sort: votes


text:
Avoiding Rivers
Background
In typography, rivers are visual gaps in a block of text, which occur due to coincidental alignment of spaces. These are particularly annoying since your brain seems to pick them up more easily in peripheral vision, which constantly distracts your eyes.
As an example, take the following block of text, lines broken such that the line width does not exceed 82 characters:
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui
officia deserunt mollit anim id est laborum. Lorem ipsum dolor sit amet,
consectetur adipisicing elit, sed do eismod tempor incididunt ut labore et dolore
maga aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris
nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in
voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint
occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id
est laborum.

There is a river spanning six lines in the bottom right part, which I've highlighted in the following block:
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui
officia deserunt mollit anim id est laborum. Lorem█ipsum dolor sit amet,
consectetur adipisicing elit, sed do eismod tempor█incididunt ut labore et dolore
maga aliqua. Ut enim ad minim veniam, quis nostrud█exercitation ullamco laboris
nisi ut aliquip ex ea commodo consequat. Duis aute█irure dolor in reprehenderit in
voluptate velit esse cillum dolore eu fugiat nulla█pariatur. Excepteur sint
occaecat cupidatat non proident, sunt in culpa qui█officia deserunt mollit anim id
est laborum.

We can mitigate this by choosing a slightly different column width. E.g. if we layout the same text using lines no longer than 78 characters, there is no river longer than two lines:
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis
nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore
eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt
in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor
sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut
labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis
aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in
culpa qui officia deserunt mollit anim id est laborum.

Note that for the purpose of this question we're only considering monospaced fonts, such that rivers are simply vertical columns of spaces. The length of a river is the number of lines it spans.
Aside: If you're interesting in river detection in proportional fonts, there are some interesting posts around the network.
The Challenge
You're given a string of printable ASCII characters (code point 0x20 to 0x7E) - i.e. a single line. Print this text, with a line width between 70 and 90 characters (inclusive), such that the maximum length of any river in the text is minimised. If there are multiple text widths with the same (minimal) maximum river length, choose the narrower width. The above example with 78 characters is the correct output for that text.
To break lines, you should replace space characters (0x20) with line breaks, such that the resulting lines have as many characters as possible, but not more than the chosen text width. Note that the resulting line break itself is not part of that count. As an example, in the last block above, Lorem[...]tempor contains 78 characters, which is also the text's width.
You may assume that the input will not contain consecutive spaces, and won't have leading or trailing spaces. You may also assume that no word (consecutive substring of non-spaces) will contain more than 70 characters.
You may write a program or function, taking input via STDIN, command-line argument or function argument and printing the result to STDOUT.
This is code golf, so the shortest answer (in bytes) wins.

I think in your 78 and 82 column wrap examples, the last and second-to-last lines are incorrect. In the 82 example, the last break should be between id and est, and in the 78 example it should be between in and culpa. Or am I doing something wrong?

@Optimizer The tie break is the text length, not the river length.

I guess it doesn't count as an official river, but in the example 78 characters max length, there seems to be a pretty long diagonal river in the top-ish left-ish area

Do we consider cases like this as continues rivers ?

Great challenge! Hm, next one could be about having (not purely vertical ) rivers shaping subliminal letters ;)

@Optimizer I don't think any of the five existing solutions considers that, and I've defined rivers as a vertical column of space characters, so no.

I doubt that they are specially treating it as not a river ... I am not, but I have a fix for that

@Optimizer I'll leave it up to you (and any other participant). It was an oversight in the spec.

That DSP.SE post has some awesome answers!

Can I have trailing white spaces on each lines in the output ?

@Optimizer Sorry, no, I think the spec for breaking lines is pretty precise about replacing those spaces with line breaks.

Can we output a list of lines? And I'm guessing not, but can we take input as a list of words (i.e. pre-split on spaces)?

CJam, 116 106 99 84 77 72 bytes
l:X;93,72>{:D;OOXS/{S+_2$+,D<{+}{@@);a+\}?}/a+}%{z'K*S/:!0a/1fb$W=}$0=N*

Takes the single line input and prints the correct output to STDOUT.
UPDATE : Improved a lot and removed redundant loops by doing all calculations in the sorting loop itself. Also fixed a bug in river length calculation.
Explanation soon (after I golf it even further)
Try it here

@Optimizer You could use input from ARGV though, then you can do ea~ instead of X each time. Saves two bytes.

Ruby 162 160 158 152 160 157 (demo)
i=gets+' '
(69..s=r=89).map{|c|w=i.scan(/(.{1,#{c}}\S) /).flatten
m=(0..c).map{|i|w.map{|l|l[i]}+[?x]}.join.scan(/ +/).map(&:size).max
m<s&&(s=m;r=w)}
puts r

The un-golfed version:
input = gets+' '

result = ''

(69..smallest_max=89).each{|w|
  #split text into words of at most w characters
  wrap = (input+' ').scan(/(.{1,#{w}}\S) /).flatten

  #transpose lines and find biggest "river"
  max_crt_river = (0..99).map{|i| wrap.map{|l|l[i]} }.flatten.join.scan(/ +/).max_by(&:size).size

  if max_crt_river < smallest_max
    smallest_max = max_crt_river
    result = wrap.join ?\n
  end
}
puts result

@MartinBüttner %r{...} allows me to use string interpolation. I just tried 21.times, but it has some more implications down the road, and I haven't managed to reach a shorter solution.

@MartinBüttner You are right, it does work! I've edited my answer. Thanks!

This doesn't work with http://pastebin.com/vN2iAzNd

@Joshpbarron Very well spotted! I fixed it now.

Bash+coreutils, 236 157 bytes
Edited with a different approach - quite a bit shorter than before:
a=(`for i in {71..91};{
for((b=1;b++<i;));{
fold -s$i<<<$@|cut -b$b|uniq -c|sort -nr|grep -m1 "[0-9]  "
}|sort -nr|sed q
}|nl -v71|sort -nk2`)
fold -s$a<<<$@

Reads the input string from the command line.
With 3 nested sorts, I shudder to think what the big-O time complexity is for this, but it does complete the example in under 10 seconds on my machine.

APL (105)
{∊{1↓∊⍵,3⊃⎕TC}¨⊃G/⍨V=⌊/V←{⌈/≢¨⊂⍨¨↓⍉2≠⌿+\↑≢¨¨⍵}¨G←(K⊂⍨' '=K←' ',⍵)∘{×⍴⍺:(⊂z/⍺),⍵∇⍨⍺/⍨~z←⍵>+\≢¨⍺⋄⍺}¨70+⍳21}

Explanation:

(K⊂⍨' '=K←' ',⍵): Add a space in front of ⍵, then split ⍵ on the spaces. Each word retains the space it begins with.
∘{...}¨70+⍳21: with that value, for each number in the range [71, 91]: (Because of the way the words are split, each 'line' ends up with an extra space on the beginning, which will be removed later. The range is shifted by one to compensate for the extra space.)

×⍴⍺:: if there are still words left,

z←⍵>+\≢¨⍺: get the length for each word, and calculate a running total of the length, per word. Mark with a 1 all the words that can be taken to fill up the next line, and store this in z.
(⊂z/⍺),⍵∇⍨⍺⍨~z: take those words, and then process what's left of the list.

⋄⍺: if not, return ⍺ (which is now empty).

G←: store the list of lists of lines in G (one for each possible line length).
V←{...}¨G: for each possibility, calculate the length of the longest river and store it in V:

+\↑≢¨¨⍵: get the length of each word (again), and make a matrix out of the lengths. Calculate the running total for each line on the rows of the matrix. (Thus, the extra space at the beginning of each line is ignored.)
2≠⌿: for each column of the matrix, see if the current length of the line at that point does not match the line after it. If so, there is not a river there.
⊂⍨¨↓⍉: split each column of the matrix by itself (on the 1s). This gives a list of lists, where for each river there will be a list [1, 0, 0, ...], depending on the length of the river. If there is no river, the list will be [1].
⌈/≢¨: get the length of each river, and get the maximum value of that.

⊃G/⍨V=⌊/V: from G, select the first item for which the length of the longest river is equal to the minimum for all items.
{1↓∊⍵,3⊃⎕TC}¨: for each line, join all of the words together, remove the fist item (the extra space from the beginning), and add a newline to the end.
∊: join all the lines together.

That's 200 bytes, not 105.

@user11153 I haven't specified UTF-8 as the encoding. The APL character set fits into a single codepage (and that codepage exists), i.e. there is an existing encoding by which each of those characters fits into a byte, and hence 105 is perfectly fine.

Good to know! :)

Python 3, 329 bytes
import re,itertools as s
def b(t,n):
 l=0;o=""
 for i in t.split():
  if l+len(i)>n:o=o[:-1]+'\n';l=0
  l+=len(i)+1;o+=i+' '
 return o
t=input();o={}
for n in range(90,69,-1):o[max([len(max(re.findall('\s+',x),default='')) for x in ["".join(i) for i in s.zip_longest(*b(t,n).split('\n'),fillvalue='')]])]=n
print(b(t,o[min(o)]))

Ungolfed version:
# Iterates over words until length > n, then replaces ' ' with '\n'
def b(t,n):
    l = 0
    o = ""
    for i in t.split():
        if l + len(i) > n:
            o = o[:-1] + '\n'
            l = 0
        l += len(i) + 1
        o += i + ' '
    return o

t = input()
o = {}
# range from 90 to 70, to add to dict in right order
for n in range(90,69,-1):
    # break text at length n and split text into lines
    temp = b(t,n).split('\n')
    # convert columns into rows
    temp = itertools.zip_longest(*temp, fillvalue='')
    # convert the char tuples to strings
    temp = ["".join(i) for i in temp]
    # findall runs of spaces, get longest run and get length
    temp = [len(max(re.findall('\s+',x),default='')) for x in temp]
    # add max river length as dict key, with line length as value
    o[max(temp)] = n

print(b(t,o[min(o)]))

Python, 314 bytes
Many thanks to SP3000, grc, and FryAmTheEggman:
b=range;x=len
def p(i):
 l=[];z=''
 for n in t:
  if x(z)+x(n)<=i:z+=n+' '
  else:l+=[z];z=n+' '
 return l+[z]*(z!=l[x(l)-1])
t=input().split();q=[]
for i in b(70,91):l=p(i);q+=[max(sum(x(l[k+1])>j<x(l[k])and l[k][j]is' '==l[k+1][j]for k in b(x(l)-1))for j in b(i))]
print(*p(q.index(min(q))+70),sep='\n')

More like Pi-thon

JavaScript (ES6) 194 202
Iterative solution, maybe shorter if made recursive
F=s=>{
  for(m=1e6,b=' ',n=70;n<91;n++)
    l=b+'x'.repeat(n),x=r=q='',
    (s+l).split(b).map(w=>
      (t=l,l+=b+w)[n]&&(
        l=w,r=r?[...t].map((c,p)=>x<(v=c>b?0:-~r[p])?x=v:v,q+=t+'\n'):[]
      )
    ),x<m&&(o=q,m=x);
  alert(o)
}

Explained
F=s=> {
  m = 1e9; // global max river length, start at high value
  for(n=70; n < 91; n++) // loop on line length
  {
    l=' '+'x'.repeat(n), // a too long first word, to force a split and start
    x=0, // current max river length
    q='', // current line splitted text
    r=0, // current river length for each column (start 0 to mark first loop)
    (s+l) // add a too long word to force a last split. Last and first row will not be managed
    .split(' ').map(w=> // repeat for each word
      (
        t=l, // current partial row in t (first one will be dropped)
        (l += ' '+w)[n] // add word to partial row and check if too long
        &&
        (
          l = w, // start a new partial row with current word
          r=r? // update array r if not at first loop
          (
            q+=t+'\n', // current row + newline added to complete text
            [...t].map((c,p)=>( // for each char c at position p in row t
              v = c != ' '
                ? 0 // if c is not space, reset river length at 0
                : -~r[p], // if c is space, increment river length
              x<v ? x=v : v // if current > max, update max
            ))
          ):[]
        )
      )
    )
    x < m && ( // if current max less than global max, save current text and current max
      o = q,
      m = x
    )
  }
  console.log(o,m)
}

Test in FireFox/FireBug console.
F('Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.')

Output
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis
nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore
eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt
in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor
sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut
labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis
aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in
culpa qui officia deserunt mollit anim id est laborum.

Jelly, 37 bytes
Z=⁶ŒgẎ§Ṁ
KƤẈ>Tị⁸ðƬœ-ƝK€
ḲçⱮ70r90¤ÑÞḢY

Try it online!
How it works
Z=⁶ŒgẎ§Ṁ - Link 1: Calculating max river length
         - Takes a list of lines on the left
Z        - Transpose
 =⁶      - Map spaces to 1 and everything else to 0
   Œg    - Over each row, group adjacent equal values
     Ẏ   - Tighten, removing the rows
      §  - Sum each
           The groups of adjacent elements are either runs of 0 or 1
           The sums map runs of 0s to 0, and runs of 1 to their lengths
       Ṁ - Yield the maximum

KƤẈ>Tị⁸ðƬœ-ƝK€ - Link 2: Breaks a string into a line width limited paragraph
               - Takes a list of words W on the left and a width N on the right
       ð       - Group into a dyad f(W, N):
 Ƥ             -   Over each prefix of W:
K              -     Join it by spaces
  Ẉ            -   Length of each
   >           -   Greater than N?
    T          -   Indices of truthy elements
     ị⁸        -   Index into W
                 This removes elements from W up the width N
        Ƭ      - Repeatedly apply f(W, N) until a fixed point
           Ɲ   - Over each overlapping pair [a, b]:
         œ-    -   Remove each element of b from a
            K€ - Join by spaces

ḲçⱮ70r90¤ÑÞḢY - Main link. Takes a string S on the left
Ḳ             - Split S into words, W
        ¤     - Create a nilad:
   70         -   70
      90      -   90
     r        -   Inclusive range; [70, 71, ..., 89, 90]
  Ɱ           - Over each element i in the range:
 ç            -   Call Link 2 with W on the left and i on the right
          Þ   - Sort by:
         Ñ    -   Max river length (Link 1)
           Ḣ  - First element (the narrowest width, and shortest river)
            Y - Join by newlines

authors: نورا الجماعي

all_licenses: 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:
WinAli - Virtual CPU for understanding assembly language
WinAli is a model assembler for Windows. It emulates a real CPU and is meant to help students learning and understanding the Assembly language.
German Wikipedia article: http://de.wikipedia.org/wiki/WinAli (there is no english article at the moment)
In case you want to test your produced output: Link to Google Drive (the program itself is in German but is easy to use even if you don't understand German)
Some information about WinAli (data and syntax)
Data types:
The only data type in WinAli is a 2 byte long "Integer" which is in fact a Smallint or short. So you don't have to take care of correct types. This is also rounded when dividing.
Variables and constants:
Variables are defined like this after the commands:
name DS F

name is obviously the name of the variable
DS is the keyword for a new variable
F defines the length of the variable in bits; this is zero-based and hexadecimal so F = 16 bits

Constants are very similar:
name DC value

name is simply the name of the constant
DC is the keyword for a new constant
value is the value assigned to that constant e.g. two DC '2'
You don't need to specify constants at the end of the code. You can also write them inline with the LDA (load) operation e.g. LDA 0,'2'. This loads "2" into register 0 (the accumulator).

Syntax:
The code is aligned into 4 columns which are separated by a space or tab:
label command params comment

label is used for the b label command (goto label) and is often skipped.
command one of the commands listed below.
params one or two parameters with at least one register and if needed another register, variable, stack or address; these parameters are separated by a comma (,).
comments (optional) a comment prefixed with ; or * until the end of the line.

Small code reference:
There are more commands but for this challenge you only need those:

INI A Stores the next user input into variable A
OUTI A Outputs the value the variable A is holding. You can't use a register here for some reason.
LDA 0,A Loads the value of A into register 0
STA 0,A Stores the value of register 0 into the variable A
ADD 0,A Adds the value of A to the value of register 0
SUB 0,A Multiplies the value of A with the value of register 0
DIV 0,A Divides the value of A by the value of register 0
EOJ Defines the end of the job i.e. executable code. Variable and constant declarations begin after this mark.

Not explicitly needed for this challenge:

program START 0 Sets the first address to be executed to 0 i.e. the next line (program is just the name of the program but is needed for the compiler)
END program Ends the program i.e. stop executing, even if other operations would follow

Your challenge!
Write a program or script that takes a mathematical expression with constant numbers and variables and outputs the WinAli code that takes all variables as input and outputs the result of that expression.

You don't need to output the START and END commands
Even though there are 16 registers defined in WinAli we only use register 0, which is the accumulator for all calculations
You can't use two variables as parameters of a command. You have to save all your results into the accumulator (register 0)
The input is always on the form of either x:=(a+b)/c or simply (a+b)/c, you decide
You only need to take care of + - * / (ADD, SUB, MUL, DIV), so no complex calculations like roots, squares or even sinus
Tip: Try to first extract simple expressions with only 2 arguments e.g. a:=a+b then x:=a/c
Tip: Your program is allowed to use additional (auxiliary) variables if you can't overwrite variables that are not used later in your code. Define them as h1 DS F.
Tip: Empty lines are useless. Try to avoid them. (You really don't need them)

Example:

Mathematical expression:
 x := (a+b)*c

Expected output (empty lines are for easier reading):
    INI a
    INI b
    INI c

    LDA 0,a
    ADD 0,b
    MUL 0,c
    STA 0,a

    OUTI a
    EOJ
a   DS F
b   DS F
c   DS F

Scoring:
Your score is defined by the length of your code + the length of the output of the following expressions:
x:=a+b+c*c/d

x:=(a+b)/c-d

x:=a-b*c-d/e

x:=2*a-b*c+d

-10% if your code can handle unary minus in expressions.

In case of a tie, the answer that produces the shortest working WinAli code wins.
The solutions may not be hardcoded in any way. I will validate each answer with additional expressions to make sure your answer is correct.

What exactly is a mathematical expression? For example are negative constants allowed? Unary minus? Variable names longer than one letter?

Do the input directives (INI x) need to follow any specific order?

@nutki a mathematical expression is meant like a simple x=a+b so no solving of complex equations, negative constants are allowed, variable names can be more than one letter (ab is not a*b), INI x can be put where ever you like there is no specific order needed as it stores the next input into the give variable but it would be nice if they follow the order a-z instead of being random

@nutki by unary minus you mean things like MUL 0,-a? this is not possible because there are no negative addresses (a is just a pointer to a value), but you can subtract the value from 0 to get the negative representation (SUB 0,a) and then work with this negative value; you may even be able to store this in the original variable.

I meant unary minus in the input expression so for example x:=-a*b or x:=a/-(b+c). Since the input order is not specified I guess we have to use the same variables names in the WinAli code, is that the case? With those restrictions are there identifiers that are never on the input? For example can h1 be an input variable name?

@nutki for the simplicity of this challenge you don't need to take care of unary minus (in your first example you only have to add a 0 in front of that - though), input variable names are supposed to be one character only so h1 is no input variable. To make the resulting WinAli code easier to understand, variable names should persist so the input of a is the same in both the expression and the code (a in x:=a*b is the same as in INI a). If your program can handle unary minus than I allow -10% to your score.

Since output size counts to the score is it OK to remove the initial tabs?

@nutki because the tabs are necessary for the code to work it counts towards the score. The first tabs separate the jump markers from the command.

One more question: are negative constants allowed? I assumed so and spend significant characters on supporting likes of -5*a, a+-10 etc. But I don't see any indication in the description.

@nutki sure, all values between -32768 and 32767 (16bit) can be stored in a constant. Not supporting those should invalidate an answer.

Perl 5: 948, 355 code + 593 output
After some golfing. Previous shorter version did not properly parse (a+b)-4*c.
%m=split'\b','-SUB+ADD/DIV*MUL<LDA>STA';$i='(\w+|(?<!\w|\))-\d+)';
$_=<>;@x{@y=/([a-z]\w*)/gi}=@y;print"\tINI $_
"for@x=keys%x;
$f=$_,$x.="<$&>".($g=(grep$f!~$_,a..zz)[0]),$x{$g}=s/@/$g/
while s|\($i\)|$1|g,s|$i[*/]$i|@|||s|$i[+-]$i|@|;$_="$x
\tOUTI $_\tEOJ
";s/>$i<\1//g;s!(^|\b)[-+/*<>]!\n\t$m{$&} 0,!g;
s!-?\d+$!'$&'!mg;print;print"$_\tDS F
"for keys%x

Example use:
$perl winali.pl <<<"2*a-b*c+d"
    INI b
    INI a
    INI d
    INI c

    LDA 0,'2'
    MUL 0,a
    STA 0,a
    LDA 0,b
    MUL 0,c
    STA 0,b
    LDA 0,a
    SUB 0,b
    ADD 0,d
    STA 0,b
    OUTI b
    EOJ
b   DS F
a   DS F
d   DS F
c   DS F

Verified. Would be nice if the input is sorted alphabetically. Just one tip: empty lines are ignored so they may reduce your output length a little bit

Some optimizations you could do: remove the trailing new line

With the above optimizations your output will be 585 bytes long (8 bytes less)

Trailing newline can be removed at no code cost, but to remove an empty line after INI would probably cost more than 4 characters of code.

oh, then just remove the trailing newline, it's not needed and will save you 4 bytes :)