Matrix property X revisited (or the Joy of X) This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge.

A T matrix is fully specified by its first row r and first column c. Each remaining element of the matrix is just a copy of the element that is diagonally up and left. That is M[i,j] = M[i-1,j-1]. We will allow T matrices which are not square. 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 T 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 one or more columns is simply an element-wise summation of their columns.  That is the sum of two or more columns containing x elements each is another column containing x elements. The sum of one column is trivially the column itself.

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 T matrix with binary entries  and which does not have property X. For clarity, a matrix with binary entries has the property that each one of its entries is either 0 or 1.

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

All the answers at Find highest scoring matrix without property X are valid here but they are not optimal. There are T matrices without property X which are not cyclic.

For example, there is a 7 by 12 T matrix without property X but no such cyclic matrix.

21/11 would beat all the current answers from this and the previous challenge.

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.

Bonus The first answer with a score greater than 2 gets an immediate 200 point bounty award.  Ton Hospel has now achieved this!



Current leader board


C++. Score 31/15 by Ton Hospel
Java. Score 36/19 by Peter Taylor
Haskell. Score 14/8 by alexander-brett
C++, Score 23/12 25/13 27/14 28/14 31/15

Finally a result with ratio > 2:

rows=15,cols=31
1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 


I completely explored 1 to 14 rows. 15 would take too long to completely explore. The results are:

1/1   = 1
2/2   = 1
4/3   = 1.333
5/4   = 1.25
7/5   = 1.4
9/6   = 1.5
12/7  = 1.714
14/8  = 1.75
16/9  = 1.778
18/10 = 1.8
20/11 = 1.818
23/12 = 1.917
25/13 = 1.923
28/14 = 2


The code given below is an older version of the program. The newest version is at https://github.com/thospel/personal-propertyX.

/*
  Compile using something like:
    g++ -Wall -O3 -march=native -fstrict-aliasing -std=c++11 -g propertyX.cpp -lpthread -o propertyX
*/
#include &lt;cstdint&gt;
#include &lt;climits&gt;
#include &lt;ctgmath&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;array&gt;
#include &lt;chrono&gt;
#include &lt;mutex&gt;
#include &lt;atomic&gt;
#include &lt;thread&gt;

using namespace std;

const int ELEMENTS = 2;

using uint    = unsigned int;
using Element = uint64_t;
using Column  = array&lt;Element, ELEMENTS&gt;;
using Set     = vector&lt;Column&gt;;
using Sum     = uint8_t;
using Index   = uint32_t;
using sec = chrono::seconds;

int const PERIOD = 5*60;
int const MAX_ROWS = 54;
int const COL_FACTOR = (MAX_ROWS+1) | 1;                // 55
int const ROW_ZERO   = COL_FACTOR/2;                    // 27
int const ROWS_PER_ELEMENT = CHAR_BIT * sizeof(Element) / log2(COL_FACTOR); //11
Element constexpr ELEMENT_FILL(Element v = ROW_ZERO, int n = ROWS_PER_ELEMENT) {
    return n ? ELEMENT_FILL(v, n-1) * COL_FACTOR + v : 0;
}
Element constexpr POWN(Element v, int n) {
    return n ? POWN(v, n-1)*v : 1;
}
Element const ELEMENT_TOP = POWN(COL_FACTOR, ROWS_PER_ELEMENT -1);
int const MAX_COLS = ROWS_PER_ELEMENT * ELEMENTS;       // 22

atomic&lt;Index&gt; col_next;
atomic&lt;uint&gt;  period;
chrono::steady_clock::time_point start;
mutex period_mutex;

uint ratio_row;
uint ratio_col;
mutex ratio_mutex;

auto const nr_threads = thread::hardware_concurrency();
// auto const nr_threads = 1;

struct State {
    State(uint cols);
    void process(Index i);
    void extend(uint row);
    void print(uint rows);
    Index nr_columns() const { return static_cast&lt;Index&gt;(1) &lt;&lt; cols_; }

    Column last_;
    Element top_;
    int top_offset_;
    uint ratio_row_ = 0;
    uint ratio_col_ = 1;
    uint cols_;
    array&lt;Sum, MAX_ROWS + MAX_COLS -1&gt; side;
    vector&lt;Set&gt; sets;
};

ostream&amp; operator&lt;&lt;(ostream&amp; os, Column const&amp; column) {
    for (int i=0; i&lt;ELEMENTS; ++i) {
        auto v = column[i];
        for (int j=0; j&lt;ROWS_PER_ELEMENT; ++j) {
            auto bit = v / ELEMENT_TOP;
            cout &lt;&lt; " " &lt;&lt; bit;
            v -= bit * ELEMENT_TOP;
            v *= COL_FACTOR;
        }
    }
    return os;
}

State::State(uint cols) : cols_{cols} {
    sets.resize(MAX_ROWS+2);
    for (int i=0; i&lt;2; ++i) {
        sets[i].resize(2);
        for (int j=0; j &lt; ELEMENTS; ++j) {
            sets[i][0][j] =  ELEMENT_FILL();
            sets[i][1][j] =  static_cast&lt;Element&gt;(-1) - ELEMENT_FILL(1);
        }
    }
    top_ = POWN(COL_FACTOR, (cols_-1) % ROWS_PER_ELEMENT);
    top_offset_ = ELEMENTS - 1 - (cols_-1) / ROWS_PER_ELEMENT;
}

void State::print(uint rows) {
    for (auto c=0U; c&lt;cols_;c++) {
        for (auto r=0U; r&lt;rows;r++) {
            cout &lt;&lt; static_cast&lt;int&gt;(side[cols_-c+r-1]) &lt;&lt; " ";
        }
        cout &lt;&lt; "\n";
    }
    cout &lt;&lt; "----------" &lt;&lt; endl;
}

void check(uint cols, uint t) {
    State state(cols);

    Index nr_columns = state.nr_columns();
    while (1) {
        Index col = col_next++;
        if (col &gt;= nr_columns) break;
        state.process(col);

        auto now = chrono::steady_clock::now();
        auto elapsed = chrono::duration_cast&lt;sec&gt;(now-start).count();
        if (elapsed &gt;= period) {
            lock_guard&lt;mutex&gt; lock{period_mutex};
            if (elapsed &gt;= period) {
                cout &lt;&lt; "col=" &lt;&lt; col &lt;&lt; "/" &lt;&lt; nr_columns &lt;&lt; " (" &lt;&lt; 100.*col/nr_columns &lt;&lt; "% " &lt;&lt; elapsed &lt;&lt; " s)" &lt;&lt; endl;
                period = (elapsed/PERIOD+1)*PERIOD;
            }
        }
    }
}

void State::process(Index col) {
    last_.fill(0);
    for (uint i=0; i&lt;cols_; ++i) {
        Element bit = col &gt;&gt; i &amp; 1;
        side[i] = bit;
        Element carry = 0;
        for (int j=0; j&lt;ELEMENTS; ++j) {
            auto c = last_[j] % COL_FACTOR;
            last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
            if (j == top_offset_ &amp;&amp; bit) last_[j] += top_;
            carry = c;
        }
    }
    // cout &lt;&lt; "col=" &lt;&lt; col &lt;&lt; ", value=" &lt;&lt; last_ &lt;&lt; "\n";
    extend(0);
}

void State::extend(uint row) {
    // cout &lt;&lt; "Extend row " &lt;&lt; row &lt;&lt; " " &lt;&lt; static_cast&lt;int&gt;(side[cols_+row-1]) &lt;&lt; "\n";
    if (row &gt;= MAX_ROWS) throw(range_error("row out of range"));

    // Execute subset sum. The new column is added to set {from} giving {to}
    // {sum} is the other set.
    auto const&amp; set_from = sets[row];
    auto const&amp; set_sum  = sets[row + 1];
    auto      &amp; set_to   = sets[row + 2];
    if (set_to.size() == 0) {
        auto size = 3 * set_from.size() - 2;
        set_to.resize(size);
        for (int j=0; j&lt;ELEMENTS; ++j)
            set_to[size-1][j] = static_cast&lt;Element&gt;(-1) - ELEMENT_FILL(1);
    }

    // Merge sort {set_from - last_} , {set_from} and {set_from + last_}
    auto ptr_sum    = &amp;set_sum[1][0];
    auto ptr_low    = &amp;set_from[0][0];
    auto ptr_middle = &amp;set_from[0][0];
    auto ptr_high   = &amp;set_from[0][0];
    Column col_low, col_high;
    for (int j=0; j&lt;ELEMENTS; ++j) {
        col_low   [j] = *ptr_low++  - last_[j];
        col_high  [j] = *ptr_high++ + last_[j];
    }

    auto ptr_end = &amp;set_to[set_to.size()-1][0];
    auto ptr_to  = &amp;set_to[0][0];
    while (ptr_to &lt; ptr_end) {
        for (int j=0; j&lt;ELEMENTS; ++j) {
            if (col_low[j] &lt; ptr_middle[j]) goto LOW;
            if (col_low[j] &gt; ptr_middle[j]) goto MIDDLE;
        }
        // low == middle
        // cout &lt;&lt; "low == middle\n";
        return;

      LOW:
        // cout &lt;&lt; "LOW\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            if (col_low[j] &lt; col_high[j]) goto LOW0;
            if (col_low[j] &gt; col_high[j]) goto HIGH0;
        }
        // low == high
        // cout &lt;&lt; "low == high\n";
        return;

      MIDDLE:
        // cout &lt;&lt; "MIDDLE\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            if (ptr_middle[j] &lt; col_high[j]) goto MIDDLE0;
            if (ptr_middle[j] &gt; col_high[j]) goto HIGH0;
        }
        // middle == high
        // cout &lt;&lt; "middle == high\n";
        return;

      LOW0:
        // cout &lt;&lt; "LOW0\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            *ptr_to++  = col_low[j];
            col_low[j] = *ptr_low++ - last_[j];
        }
        goto SUM;

      MIDDLE0:
        // cout &lt;&lt; "MIDDLE0\n";
        for (int j=0; j&lt;ELEMENTS; ++j)
            *ptr_to++ = *ptr_middle++;
        goto SUM;

      HIGH0:
        // cout &lt;&lt; "HIGH0\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            *ptr_to++ = col_high[j];
            col_high[j] = *ptr_high++ + last_[j];
        }
        goto SUM;
      SUM:
        for (int j=-ELEMENTS; j&lt;0; ++j) {
            if (ptr_to[j] &gt; ptr_sum[j]) {
                ptr_sum += ELEMENTS;
                goto SUM;
            }
            if (ptr_to[j] &lt; ptr_sum[j]) goto DONE;
        }
        // sum == to
        for (int j=-ELEMENTS; j&lt;0; ++j)
            if (ptr_to[j] != ELEMENT_FILL()) {
                // sum == to and to != 0
                // cout &lt;&lt; "sum == to\n";
                // cout &lt;&lt; set_sum[(ptr_sum - &amp;set_sum[0][0])/ELEMENTS-1] &lt;&lt; "\n";
                return;
            }
      DONE:;
    }
    // cout &lt;&lt; "Wee\n";
    auto row1 = row+1;
    if (0)
        for (uint i=0; i&lt;row1+2; ++i) {
            cout &lt;&lt; "Set " &lt;&lt; i &lt;&lt; "\n";
            auto&amp; set = sets[i];
            for (auto&amp; column: set)
                cout &lt;&lt; column &lt;&lt; "\n";
        }

    if (row1 * ratio_col_ &gt; ratio_row_ * cols_) {
        ratio_row_ = row1;
        ratio_col_ = cols_;
        lock_guard&lt;mutex&gt; lock{ratio_mutex};

        if (ratio_row_ * ratio_col &gt; ratio_row * ratio_col_) {

            auto now = chrono::steady_clock::now();
            auto elapsed = chrono::duration_cast&lt;sec&gt;(now-start).count();
            cout &lt;&lt; "cols=" &lt;&lt; cols_ &lt;&lt; ",rows=" &lt;&lt; row1 &lt;&lt; " (" &lt;&lt; elapsed &lt;&lt; " s)\n";
            print(row1);
            ratio_row = ratio_row_;
            ratio_col = ratio_col_;
        }
    }

    auto last = last_;

    Element carry = 0;
    for (int j=0; j&lt;ELEMENTS; ++j) {
        auto c = last_[j] % COL_FACTOR;
        last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
        carry = c;
    }

    side[cols_+row] = 0;
    extend(row1);

    last_[top_offset_] += top_;
    side[cols_+row] = 1;
    extend(row1);

    last_ = last;
}

void my_main(int argc, char** argv) {
    if (!col_next.is_lock_free()) cout &lt;&lt; "col_next is not lock free\n";
    if (!period.  is_lock_free()) cout &lt;&lt; "period is not lock free\n";

    int min_col = 2;
    int max_col = MAX_COLS;
    if (argc &gt; 1) {
        min_col = atoi(argv[1]);
        if (min_col &lt; 2)
            throw(range_error("Column must be &gt;= 2"));
        if (min_col &gt; MAX_COLS)
            throw(range_error("Column must be &lt;= " + to_string(MAX_COLS)));
    }
    if (argc &gt; 2) {
        max_col = atoi(argv[2]);
        if (max_col &lt; min_col)
            throw(range_error("Column must be &gt;= " + to_string(min_col)));
        if (max_col &gt; MAX_COLS)
            throw(range_error("Column must be &lt;= " + to_string(MAX_COLS)));
    }

    for (int cols = min_col; cols &lt;= max_col; ++cols) {
        cout &lt;&lt; "Trying " &lt;&lt; cols &lt;&lt; " columns" &lt;&lt; endl;
        ratio_row = 0;
        ratio_col = 1;
        col_next = 0;
        period = PERIOD;
        start = chrono::steady_clock::now();
        vector&lt;thread&gt; threads;
        for (auto t = 1U; t &lt; nr_threads; t++)
            threads.emplace_back(check, cols, t);
        check(cols, 0);
        for (auto&amp; thread: threads)
            thread.join();
    }
}

int main(int argc, char** argv) {
    try {
        my_main(argc, argv);
    } catch(exception&amp; e) {
        cerr &lt;&lt; "Error: " &lt;&lt; e.what() &lt;&lt; endl;
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}