Return to Question

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

• 34/18 by Peter Taylor (Java)
• 32/17 by Suboptimus Prime (C#)
• 21/12 by justhalf (Python 2)

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)

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

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

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

• 34/18 by Peter Taylor (Java)
• 32/17 by Suboptimus Prime (C#)
• 21/12 by justhalf (Python 2)