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