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>
01has 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. \$\endgroup\$01has property X:(1) = (0) + (1). If you want to exclude that then you should say that the two sets of columns must be disjoint. \$\endgroup\$2^mcolumn 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 tom * 2^(m/2)... \$\endgroup\$