C++ (heuristic): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086
This is slightly behind Peter Taylor's result, being 1 to 3 lower for n=7
, 9
and 10
. The advantage is that it's much faster, so I can run it for higher values of n
. And it can be understood without any fancy math. ;)
The current code is dimensioned to run up to n=15
. Run times increase roughly by a factor of 4 for each increase in n
. For example, it was 0.008 second for n=7
, 0.07 seconds for n=9
, 1.34 seconds for n=11
, 27 seconds for n=13
, and 9 minutes for n=15
.
There are two key observations I used:
- Instead of operating on the values themselves, the heuristic operates on counting arrays. To do this, a list of all unique counting arrays is generated first.
- Using counting arrays with small values is more beneficial, since they eliminate less of the solution space. This is based on each count
c
excluding the range of c / 2
to 2 * c
from other values. For smaller values of c
, this range is smaller, which means that fewer values are excluded by using it.
Generate Unique Counting Arrays
I went brute force on this one, iterating through all values, generating the count array for each of them, and uniquifying the resulting list. This could certainly be done more efficiently, but it is good enough for the kinds of values we're operating with.
This is extremely quick for the small values. For the larger values, the overhead does become substantial. For example, for n=15
, it uses about 75% of the whole runtime. This would definitely be an area to look at when trying to go much higher than n=15
. Even just the memory usage for building a list of the counting arrays for all values would start to become problematic.
The number of unique counting arrays is about 6% of the number of values for n=15
. This relative count becomes smaller as n
becomes larger.
Greedy Selection of Counting Array Values
The main part of the algorithm selects counting array values from the generated list using a simple greedy approach.
Based on the theory that using counting arrays with small counts is beneficial, the counting arrays are sorted by the sum of their counts.
They are then checked in order, and a value is selected if it is compatible with all previously used values. So this involves one single linear pass through the unique counting arrays, where each candidate is compared to the values that were previously selected.
I have some ideas on how the heuristic could potentially be improved. But this seemed like a reasonable starting point, and the results looked quite good.
Code
This is not highly optimized. I had a more elaborate data structure at some point, but it would have needed more work to generalize it beyond n=8
, and the difference in performance did not seem very substantial.
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
typedef uint32_t Value;
class Counter {
public:
static void setN(int n);
Counter();
Counter(Value val);
bool operator==(const Counter& rhs) const;
bool operator<(const Counter& rhs) const;
bool collides(const Counter& other) const;
private:
static const int FIELD_BITS = 4;
static const uint64_t FIELD_MASK = 0x0f;
static int m_n;
static Value m_valMask;
uint64_t fieldSum() const;
uint64_t m_fields;
};
void Counter::setN(int n) {
m_n = n;
m_valMask = (static_cast<Value>(1) << n) - 1;
}
Counter::Counter()
: m_fields(0) {
}
Counter::Counter(Value val) {
m_fields = 0;
for (int k = 0; k < m_n; ++k) {
m_fields <<= FIELD_BITS;
m_fields |= __builtin_popcount(val & m_valMask);
val >>= 1;
}
}
bool Counter::operator==(const Counter& rhs) const {
return m_fields == rhs.m_fields;
}
bool Counter::operator<(const Counter& rhs) const {
uint64_t lhsSum = fieldSum();
uint64_t rhsSum = rhs.fieldSum();
if (lhsSum < rhsSum) {
return true;
}
if (lhsSum > rhsSum) {
return false;
}
return m_fields < rhs.m_fields;
}
bool Counter::collides(const Counter& other) const {
uint64_t fields1 = m_fields;
uint64_t fields2 = other.m_fields;
for (int k = 0; k < m_n; ++k) {
uint64_t c1 = fields1 & FIELD_MASK;
uint64_t c2 = fields2 & FIELD_MASK;
if (c1 > 2 * c2 || c2 > 2 * c1) {
return false;
}
fields1 >>= FIELD_BITS;
fields2 >>= FIELD_BITS;
}
return true;
}
int Counter::m_n = 0;
Value Counter::m_valMask = 0;
uint64_t Counter::fieldSum() const {
uint64_t fields = m_fields;
uint64_t sum = 0;
for (int k = 0; k < m_n; ++k) {
sum += fields & FIELD_MASK;
fields >>= FIELD_BITS;
}
return sum;
}
typedef std::vector<Counter> Counters;
int main(int argc, char* argv[]) {
int n = 0;
std::istringstream strm(argv[1]);
strm >> n;
Counter::setN(n);
int nBit = 2 * n - 1;
Value maxVal = static_cast<Value>(1) << nBit;
Counters allCounters;
for (Value val = 0; val < maxVal; ++val) {
Counter counter(val);
allCounters.push_back(counter);
}
std::sort(allCounters.begin(), allCounters.end());
Counters::iterator uniqEnd =
std::unique(allCounters.begin(), allCounters.end());
allCounters.resize(std::distance(allCounters.begin(), uniqEnd));
Counters solCounters;
int nSol = 0;
for (Value idx = 0; idx < allCounters.size(); ++idx) {
const Counter& counter = allCounters[idx];
bool valid = true;
for (int iSol = 0; iSol < nSol; ++iSol) {
if (solCounters[iSol].collides(counter)) {
valid = false;
break;
}
}
if (valid) {
solCounters.push_back(counter);
++nSol;
}
}
std::cout << "result: " << nSol << std::endl;
return 0;
}
L1[i]/2 <= L2[i] <= 2*L1[i]
. \$\endgroup\$match(A, B)
andmatch(B, C)
does not implymatch(A, C)
(same for the inverse). Example: [1] and [2] match, [2] and [3] match, but [1] and [3] do not. Similarly, [1,3] and [3,1] do not match, [3, 1] and [2, 3] do not match, but [1, 3] and [2, 3] match. \$\endgroup\$